Valkey, skiplist 걷어내고 sorted set 메모리 최대 43% 절감
Valkey kills the skiplist, cuts sorted set overhead by up to 43%
Valkey 9.2에서 대형 sorted set의 skiplist를 61-way fanout의 B+ tree 변형인 fbtree로 교체했다. 노드마다 따로 할당되던 skiplist와 달리 여러 멤버를 하나의 노드에 묶어 포인터 오버헤드와 캐시 미스 의존 fetch를 줄였다. 500만 멤버 테스트에서 멤버당 오버헤드가 36~43% 감소해 최대 109MB를 아꼈고, ZADD 처리량은 105%, ZREM은 76% 늘었다. 명령 동작은 그대로이며 OBJECT ENCODING만 skiplist 대신 btree를 반환한다.
sorted set은 원소 자체를 저장하는 것보다 원소의 정렬 순서를 설명하는 데 더 많은 메모리를 쓸 수 있다.
HN 토론
42- antirez
공정성을 위해 말하자면: 저는 Redis에서 다른 기법을 사용해 비슷한 최적화 작업을 했습니다(PR을 제출했을 때 동료들이 ValKey와 다른 Redis 팀이 이 작업을 하고 있다고 알려줬는데, 저는 몰랐습니다: 세 가지 구현 중에서 광범위한 벤치마크 후에 제 것을 선택했습니다). 이 ValKey 최적화와 비교해 때로는 수십 퍼센트의 RAM 절감을 달성했습니다. 따라서 sorted set의 메모리 절감에 흥분하신다면 두 구현을 모두 시도해 보시기 바랍니다. 또한 많은 사용 사례에서 skiplist에 비해 훨씬 더 많은 속도를 얻었습니다.
- hinkley
솔직히 말하면 나는 항상 Bill Pugh(스킵리스트 씨)에 대해 반신반의했다.
그의 동시성 아이디어 중 일부는 꽤 좋았지만, 스킵 리스트는 내가 성능을 위한 이론적 설계와 실제 설계가 분기되었다는 것을 깨닫던 시기와 겹쳤고, 스킵 리스트는 엄청난 캐시 미스 부담이었다.
내가 아는 몇몇 사람들이 실제 성능 분석 결과가 부정적이거나 불확실해서 다른 것으로 돌아간 것도 도움이 되었다(한 가지가 다른 것보다 낫다는 것을 증명할 수 없다면 더 단순한 것을 사용하는데, 스킵리스트는 단순하지 않다).
- tyre
약간 관련된 이야기지만, 이 기능의 최종 PR에 있는 PR 섹션이 꽤 좋다[0].
권장 읽기 순서가 있는 리뷰 가이드, 명확한 설계 결정, 의도적으로 포함하지 않은 것에 대한 범위 경계가 있다.
이런 종류의 작업은 LLM이 매우 잘하고 인간 리뷰어에게 높은 ROI를 제공하는 유형이다.
- rsalus
나는 오래전에 CPQ에 MultiQueue 알고리즘으로 넘어갔는데, 이제 SkipList는 사용 사례가 거의 없어진 것 같다...
- dnchdnd
요즘 valkey가 권장되는 redis 대안인가요?