https://github.com/dragonflydb/dragonfly

• Redis, Memcached compatible(을 목표로 하는 중)
• The fastest in-memory store in the universe(라고 주장 중)

스타 수도 많아졌고 예전보다 이런 벤치마크가 뽑히는 이유 중 메모리 관리에 대해 잘 정리해줬는데, 해당 내용을 쭉 보다 보니까 재밌는 내용인 것 같아서 간단하게 정리했습니다.

Redis의 캐시 알고리즘

Redis의 캐시 알고리즘은 Approximated LRU라고 표현합니다.

• 샘플링 → 그 중에 마지막 참조 Timestamp 아이템 Eviction
• 샘플링 하는 방식 덕분에 Redis는 정렬에 필요한 메타 데이터 16바이트 정도를 매 데이터 엔트리마다 아낄 수 있게 됐지만 러프한 LRU 방식이기 때문에 이론보다 더 낮은 Memory hit 발생

Dragonfly 캐시 알고리즘

Dragonfly 캐시 알고리즘은 2Q Cache Management를 확장한 방식이라고 합니다.

2 Queue Cache Management

• ARC와 컨셉상 유사한 느낌입니다. ARC는 IBM이 특허를 가지고 있다고 합니다. PostgreSQL에서 메모리 버퍼로 사용하던 알고리즘인데 특허 때문에 2Q 알고리즘으로 변경했고 성능 차이가 없다고 주장합니다. (링크)
• 아이템을 처음 메모리에 추가할 때 Probationary Buffer라고 불리는 버퍼에 쌓습니다. 이는 일시적으로 발생하는 참조를 worthless하게 만드는 데 도움을 줍니다. 이 버퍼는 전체 캐시 메모리의 10% 정도만 차지합니다.
• 그 다음 Probationary Buffer에서 재참조가 발생하게 되면 그때서야 Protected Buffer로 이동하게 됩니다. Protected Buffer는 LRU 입니다. 그리고 Protected Buffer 부분에 만약 자리가 없으면 가장 Rank가 낮은 아이템과 자리를 바꿉니다.

Dashtable

Dashtable은 DragonflyDB가 KV 저장소를 만들기 위해 활용한 해시 테이블입니다. Extendible hashing 방식이라 Rehashing 시점에 많은 데이터를 재배치 할 필요가 없습니다.

• 일정한 사이즈의 세그먼트로 테이블(세그먼트 딕셔너리)가 나눠집니다. 각 세그먼트는 56개의 일반 버킷을 가지고 있고 각 버킷은 다수의 슬롯을 가지고 있습니다. 그리그 하나의 슬롯이 하나의 아이템을 담습니다. 그리고 각 세그먼트는 4개의 Stash Bucket이라고 하는 여분의 버킷을 갖습니다.