B-tree 하나로 LSM-tree를 최대 6.83배 빠르게 만든 bbtree
Bbtree: Fastest Ordered Map
Rust로 구현된 정렬 맵 bbtree는 캐시 미스 수를 최소화하는 비용 모델을 바탕으로 설계됐다. fjall, SlateDB, Tonbo, Lance 등 네 개 LSM-tree의 skiplist를 대체해 쓰기 배치 3.00배, 10M 행 쓰기 6.83배, 배치 조회 4.21배 속도 향상을 보였다. String 키를 위한 inline_keys와 prefix_keys, 그리고 캐시 미스를 Future로 다루는 배치 모드가 핵심이다.
B-tree의 메모리 접근은 근본적으로 연쇄적이다. 현재 노드를 탐색하기 전까지는 다음에 어떤 노드를 가져와야 할지 알 수 없기 때문이다.
- geraneum
형식 검증, 모델 체킹, 결정론적 시뮬레이션, 퍼징, 그리고 수많은 테스트를 거쳐 프로덕션 레디라니.
여기서 모델 체킹이 무슨 뜻이지?
- tyilo
> 어떤 인간도 LLM보다 더 나은 코드를 작성할 수 없다.
대담한 주장이네...
- jared_hulbert
정말 좋은 작업이네요. 저도 이거랑... 비슷한 쪽 일을 하고 있는 것 같아요. 저는 intrinsics를 훨씬 더 적극적으로 써야 하고, 캐시 라인에 완전히 집중해야 하고, DRAM을 비동기 블록 디바이스처럼 다뤄야 한다는 생각을 계속 강조해 왔는데, coherence 트래픽의 영향을 보여줄 생각을 못 했다니 믿기지가 않네요! 시간이 나면 제 기법 몇 가지를 bbtree에 적용해 볼까 해요. DM 주세요. 그때 연락드릴 수 있으면 좋겠네요.