Bbtree: 가장 빠른 정렬 맵

요약

Rust 표준 BTreeMap 자리에 그대로 끼우면 5배 빨라진다는 정렬 맵 Bbtree가 공개됐습니다.

마이크로소프트에서 실제로 운영 중인 Bf-Tree를 만드는 등 박사 과정 내내 B-트리를 연구한 하오샹펑의 글입니다. 코드는 모두 LLM이 썼고, 설계 결정과 코드에 대한 책임은 본인이 진다고 밝혔습니다.

왜 중요한가

정렬 맵은 DB 인덱스와 LSM 트리(쓰기를 메모리에 모았다가 디스크로 내리는 저장 구조)의 바탕이라 파급력이 큽니다.
fjall, SlateDB 등 LSM 트리 네 곳에서 맵만 바꿨더니 1.37~6.83배 빨라졌다고 했습니다.
속도 개선은 LLM에게 맡기고, 정확성은 사람의 설계 감독과 자동 검증으로 지키는 개발 방식을 보여 줍니다.

핵심 내용

캐시 미스(약 100ns), 명령어 수, 캐시 일관성 트래픽(코어끼리 캐시를 맞추는 비용) 순으로 줄이는 비용 모델을 따랐습니다.
문자열 키는 앞 몇 바이트만 노드 안에 담은 인라인 키로 먼저 비교해, 비교할 때마다 힙을 읽는 일을 줄였습니다.
부모 노드의 구분 키들이 공유하는 접두사는 건너뛰어, URL처럼 앞부분이 같은 키에서도 인라인 키가 통하게 했습니다.
여러 키를 한 번에 찾을 때는 캐시 미스를 Rust의 Future로 다뤄, 메모리를 기다리는 동안 다른 키를 처리합니다.
표준 BTreeMap과 결과를 대조하는 퍼징, Verus 형식 검증, Shuttle 동시성 테스트로 정확성을 확인한다고 했습니다.

HN 반응

실제 3D 메시 프로그램에 넣어 본 이용자는 순회만 5~15배 빨랐고 삽입과 조회는 오히려 느려졌다며 벤치마크 조건이 좁다고 반박했습니다.
"LLM보다 코드를 잘 쓰는 사람은 없다"는 문구에 AI가 쓴 글이라는 비판이 잇따랐고, 트라이 계열 구조가 더 빠를 수 있다는 지적도 나왔습니다.

23개 표시 · 전체 23개

nicknash1일 전 HN

B-트리 류 자료구조의 진짜 경쟁 상대는 트라이 기반 구조입니다. 버스트 트라이, (최적화된) q-fast 트라이와 p-fast 트라이, 레벨 압축 트라이, 버킷 트라이, 경로 압축 트라이 같은 것들이요.

키 길이가 허락한다면 최적화된 계층 트리(van Emde Boas) 구현도 있습니다.

비교 기반 구조가 꼭 필요한 경우는 드뭅니다. 정수, 부동소수점, 문자열 등은 사전식 구조로 다룰 수 있으니까요.

특히 트라이는 (비현실적인) 균등 랜덤 데이터에서 로그 로그 시간의 연산 속도로 터무니없이 잘 동작합니다.

그래서 여기서 말하는 "가장 빠른"이라는 표현에는 회의적입니다.

그래도 B-트리는 훌륭하죠. 수고하셨습니다!
bollu14시간 전 HN

자료구조를 정말 많이 아시나 봐요 :) 2010년대나 2020년대에 나온 새롭고 멋진 자료구조도 있나요?

virtualritz21시간 전 HN

결과는 상황에 따라 다를 수 있습니다.

제가 만들고 있는 3D 불리언 메시 커널에서 테스트해 봤습니다(std::BTreeMap만 바꿔 끼웠고 다른 코드는 그대로입니다).

  ┌────────────────────────────────────┬──────────────────────┐
  │       bench 96..1536 faces         │        change        │
  ├────────────────────────────────────┼──────────────────────┤
  │ union/difference,                  │ +11% to +21% slower  │
  ├────────────────────────────────────┼──────────────────────┤
  │ intersection stage,                │ +16% to +34% slower  │
  └────────────────────────────────────┴──────────────────────┘

그러다 큰 맵에서는 빛을 발하는 건가 싶었습니다. 즉 더 조밀하고 복잡한 메시에서요.

그래서 테스트 픽스처 중 하나인, 정점 ID가 백만 개인 네페르티티 흉상 스캔을 썼습니다.

  ┌──────────────────────────────────────┬───────┬────────┐
  │     cage op (seconds, best of 3)     │  std  │ bbtree │
  ├──────────────────────────────────────┼───────┼────────┤
  │ difference                           │ 84.2  │ 83.0   │
  ├──────────────────────────────────────┼───────┼────────┤
  │ union                                │ 83.2  │ 85.6   │
  ├──────────────────────────────────────┼───────┼────────┤
  │ intersection                         │ 61.3  │ 67.1   │
  ├──────────────────────────────────────┼───────┼────────┤
  │ limit-surface difference (best of 2) │ 123.9 │ 147.2  │
  └──────────────────────────────────────┴───────┴────────┘

그러니까 글에서 내세운 주장 상당수는 저자가 테스트한 특정한, 어쩌면 좁은 사용 사례에서만 성립할 가능성이 큽니다.

std::BTreeMap은 이상적으로는 어떤 사용 사례에서도 무난하게 버텨야 합니다. 그러려면 늘 타협이 따를 수밖에 없습니다.

xiangpeng21시간 전 HN

안녕하세요, 저자입니다. bbtree를 테스트해 주셔서 감사합니다. bbtree는 InlinkeKey 트레이트를 구현할 수 있을 때 가장 잘 동작합니다. 워크로드를 보여 주시면 제가 놓친 게 있는지 확인해 보고 싶습니다. 저장소에 이슈를 남겨 주셔도 좋습니다!

virtualritz8시간 전 HN

요약: 당신의 에이전트가 작성했다고 말하고 당신이 실험으로 "확인했다"는 내용이 무엇이든, 현실과는 어딘가에서 어긋나 있습니다.

저는 이 일에 시간을 허비했습니다. 말 그대로, 그리고 비유적으로도요.

InlinkeKey 마이크로벤치 결과는 아래와 같습니다.

각 행은 키 n개를 한 번 훑은 결과이며, 세 변형을 한 프로세스에서 번갈아 실행했습니다.

  ┌──────────────────────┬────────┬────────┬─────────┐
  │     n = 65536,       │  std   │ bbtree │ bbtree  │
  │    VertexId(u32)     │ BTree- │  Auto  │ Inline- │
  │                      │  Map   │        │   Key   │
  ├──────────────────────┼────────┼────────┼─────────┤
  │ insert               │ 18.3ms │ 12.3ms │ 20.8ms  │
  ├──────────────────────┼────────┼────────┼─────────┤
  │ get                  │ 14.0ms │  9.2ms │ 16.6ms  │
  ├──────────────────────┼────────┼────────┼─────────┤
  │ iterate              │ 0.74ms │ 0.05ms │ 0.10 ms │
  ├──────────────────────┼────────┼────────┼─────────┤
  │ entry().or_default() │ 52ms   │ 47ms   │ 54 ms   │
  │ .push                │        │        │         │
  └──────────────────────┴────────┴────────┴─────────┘

같은 양상이 항목 4천 개와 100만 개에서도, 그리고 제 크레이트가 쓰는 (u32,u32) 쌍과 (u8,usize) 튜플에서도 나타납니다. InlineKey를 붙이면 폭이 좁은 키에서는 InlineKey 없는 bbtree보다 오히려 더 느려집니다.

24바이트짜리 엣지 키에서만 트레이트 없는 버전을 이깁니다. 하지만 그것도 여전히 std에는 뒤집니다!

글에서 증명했다는(?) u64 구현이 제 CPU(Rhyzen 6800H, 8코어/16스레드)에서는 이 메커니즘의 상한선일 가능성이 있습니다. 4천~6만 5천 개에서는 std와 동률이고, 100만 개에서는 10퍼센트쯤 앞섭니다.

순회에서는 bbtree가 정말로 5~15배 이기지만, 제 커널의 시간은 순회에서 쓰이지 않습니다. 대부분의 애플리케이션도 마찬가지일 거라고 생각합니다.

결국에는 데이터를 넣고 읽고 가져오는 일을 해야 하니까요.

hugmynutus1일 전 HN

[flagged]
xiangpeng1일 전 HN

안녕하세요, 저자입니다. 우선 AI 슬롭(slop)을 읽어 주신 시간에 감사드립니다. 아마 이 저장소에 저보다 더 많은 시간을 쓰셨을 텐데, 고맙습니다!

인라인 키는 맞습니다. 모든 종류의 정수와 문자열에 적용되고, InlineKey 트레이트를 공개하므로 직접 인라인 접두사를 구현할 수도 있습니다.

체크리스트 항목은 체크하는 걸 깜빡했을 뿐 전부 구현돼 있습니다. 다만 그 체크리스트 항목은 bbtree와는 상관이 없다고 생각합니다. 그래도 분명 제 결함입니다.
hugmynutus1일 전 HN

흔한 정수 타입 대부분을 구현하는 매크로를 작성했다면 시간을 아낄 수 있었을 겁니다.

그리고 bf-tree 논문과 작업 잘 봤습니다. 저도 그걸 바탕으로 취미로 파일 시스템을 만들기 시작했어요.
ytxm1일 전 HN

동적인 웹 페이퍼 형식은 설명 위주의 교육용 글에는 좋지만, 여기서는 발명 자체를 읽는 시간만큼이나 동적 요소를 건너뛰며 사람의 손길을 찾는 데 시간을 썼습니다. 다행히 사람의 흔적은 충분히 있었지만요. 구조가 다소 로봇 같긴 해도 적어도 누군가 교정은 봤습니다.

/usr/share/dict/words로 map<String, usize>(값은 사전 오프셋)를 만들어 측정해 보니, std::collections::BtreeMap보다 일관되게 메모리를 40% 더 씁니다. 메모리를 덜 쓴다는 저자의 주장은 정수에 한정된 것이었으니, 반박이라기보다는 데이터 포인트 하나입니다.
jared_hulbert1일 전 HN

정말 멋진 작업입니다. 저도 이와 맞닿은 작업을 하고 있습니다. 저는 인트린식을 훨씬 적극적으로 활용하고, 캐시 라인에 레이저처럼 집중하고, DRAM을 비동기 블록 장치처럼 다뤄야 한다고 계속 주장해 왔는데, 코히어런스 트래픽의 영향을 보여 줄 생각은 한 번도 못 했다니 믿기지 않네요! 시간이 나면 제 요령 몇 가지를 bbtree에 적용해 볼까 합니다. DM 주세요. 그때가 되면 연락드리고 싶습니다.

https://news.ycombinator.com/item?id=50218616
throwaway8152318시간 전 HN

HN에는 DM이 없어요.
tyilo1일 전 HN

어떤 사람도 LLM보다 나은 코드를 쓸 수 없다.

대담한 주장이네요...
ashkankiani1일 전 HN

제목을 보고 글을 읽기 시작했을 때부터 "이 사람은 젊은, 아마 학생이겠구나" 싶었습니다. 이분 배경(https://xiangpeng.systems/)을 보면 "가장 빠른" 같은 비과학적인 표현을 쓴 게 아이러니하네요. 그러니 분명 마케팅 목적일 겁니다. 구직 홍보나 이력서 용도일 수도 있고요.

이 라이브러리에 쓰인 기법, 특히 성능에 가장 크게 기여하는 기법 중 일부나 전부를 갖추고 이보다 더 빠르게 특정 도메인에 맞춰 B-트리를 직접 만든 사람이 분명히 있다고 장담할 수 있습니다. 프리페칭이 아마 저자가 내세울 대표 기법일 텐데, 저는 그걸 갖춘 사내 전용 구현을 개인적으로 알고 있습니다.

좀 더 겸손한 모습을 보고 싶습니다. 하지만 자기 가능성을 이미 LLM보다 아래로 포기해 버렸다면 무슨 소용이겠습니까.

더는 성장하는 게 불가능하고 의미도 없다는 거죠. 다음 주에 나올 어떤 새 최첨단 모델이 이 사람이 만든 덧없이 유용한 프로젝트를 능가할 테니까요. 그런 논리 아닌가요?
0c3ca831일 전 HN

특히 코드를 들여다보면 틀렸다는 게 너무 쉽게 증명되니까요. 예외 없이 형편없습니다.

코드를 읽지 않는 사람이나 쓸 수 있는 말입니다.
marci1일 전 HN
저자의 LLM들이 비교 대상에 sanakirja도 넣었으면 좋았겠어요. 사람이 만든 속도 주장이 몇 가지 있거든요.
- https://docs.rs/sanakirja-core
- https://pijul.org/posts/2021-02-06-rethinking-sanakirja#benchmarks
geraneum1일 전 HN

형식 검증, 모델 검사, 결정론적 시뮬레이션, 퍼징, 그리고 방대한 테스트를 통해 프로덕션에 쓸 준비가 되어 있다.

여기서 모델 검사(model checking)가 무슨 뜻인가요?
aw16211071일 전 HN

제 추측으로는 https://en.wikipedia.org/wiki/Model_checking 입니다. 이 분야에서는 C Bounded Model Checker 0가 비교적 잘 알려진 사례입니다.
geraneum1일 전 HN

감사합니다. 도움이 됐어요.
rurban1일 전 HN

아니요, 저자는 Rust 도구인 verus를 썼습니다. 그리고 shuffle과 ffs도요. 저자의 문서를 보세요.
aw16211071일 전 HN

맞습니다. 저자가 CBMC를 썼다는 뜻이 아니라, 모델 검사의 한 예라는 말이었습니다.

덧붙이면 문서에는 어떤 모델 검사기를 썼는지 나와 있지 않은 것 같습니다. verus, shuffle, ffs 중 어느 것도 엄밀히는 모델 검사기가 아니라고 생각합니다(적어도 스스로 그렇게 소개하지는 않습니다).
ozgrakkurt1일 전 HN

웹사이트 첫 번째 섹션만 읽고도 AI 슬롭이라는 경보가 울렸습니다.

맨 위의 인용문은 이 모든 내용과 아무 관련이 없어서, 꽤 웃기면서도 거슬립니다.
elendilm1일 전 HN

훌륭해 보입니다.

저희 Dip에는 "배치" 요청으로 들어온 작업의 중복을 제거하는 스마트 배칭이 있습니다. 전처리 "스캐터" 단계에서 중복 작업을 제거하는 데 BTreeMap을 씁니다.

스마트 배칭의 이 중복 제거는 대량 쓰기 워크로드(요청 한 번에 20만 건 이상 삽입) 대부분에서 가장 느린 단계이고, 팬아웃, DB 쓰기, DB 커밋, 개더를 합친 시간의 최대 3배가 걸리기도 합니다.

Bbtree로 바꿔 보고 어떻게 되는지 보겠습니다.
MiroslavPokorny19시간 전 HN

출처는요?

Hacker News에서 보기 ↗