bbtree: 스키프리스트 대비 최대 6.83배를 주장하는 Rust 정렬 맵, 그리고 댓글러들이 의심하는 점

bbtree는 Rust 정렬 맵(B-트리)으로, 저자는 캐시 바운드 워크로드에서 스키프리스트와 std::collections::BTreeMap보다 성능이 우수하다고 주장합니다. 4개의 프로덕션 LSM-트리에서 memtable로 사용할 때 1.37-6.83배의 속도 향상, 인메모리 데이터베이스 인덱스로 사용할 때 2.22배 빠른 삽입, 디스크에서 메모리 매핑할 때 160-2,500배 빠른 첫 응답을 보고합니다. 이 게시물은 Hacker News에 "Bbtree: Fastest Ordered Map"(153점, 21개 댓글)으로 게시되었으며, bbtree.xiangpeng.systems에서 호스팅되고 사용자 aoli-al이 제출했습니다.

bbtree가 주장하는 것

핵심 주장은 B-트리가 대부분의 빅데이터 시스템의 기반이므로, 더 빠른 B-트리는 그 위에 구축된 모든 것을 개선한다는 것입니다: 에이전트 메모리, LLM 훈련, RAG, KV 저장소, 상태 캐싱, 벡터 검색. 게시물은 벤치마크 수치와 함께 세 가지 대표적인 사용 사례를 제시합니다.

1. LSM-트리 memtable에서 스키프리스트 교체

모든 LSM-트리는 최근 쓰기를 memtable이라는 정렬 맵에 메모리에 유지합니다. Rust에서 그 맵은 일반적으로 crossbeam-skiplist와 같은 스키프리스트입니다. 게시물은 bbtree가 각 시스템의 자체 벤치마크에서 단일 스레드로 Ryzen 9 9900X에서 맵만 변경하여 1.37-6.83배의 속도로 교체한다고 보고합니다:

fjall: gets 2.47x, inserts 1.61x, write batches 3.00x
SlateDB: gets 1.71x, puts 1.65x, write batches of 10 rows 2.36x
Tonbo: 10M-row writes 6.83x, conflict-checked transactions 4.10x
Lance의 MemWAL 인덱스(자체 스키프리스트): point lookups 2.19x, batched lookups 3.94x, batched puts 4.21x

명시된 인터페이스 이점은 bbtree가 crossbeam-skiplist와 유사하지만 더 간단한 API를 노출하고, epoch가 없으며 언제 epoch를 고정하거나 다시 입력해야 하는지 고민할 필요가 없다는 것입니다. 메모리 관리도 더 제어 가능합니다: 커스텀 할당자를 처음부터 지원하며, 할당은 비정규(2의 거듭제곱이 아닌) 크기에서 발생하지 않아 외부 단편화를 피하고, 할당 실패를 우아하게 처리할 수 있습니다.

2. 인메모리 데이터베이스 인덱스

Turso의 스키프리스트를 교체하여 삽입이 2.22배 빠르고 인덱스 SELECT가 1.90배 빠르다고 보고합니다.

3. 디스크에서 bbtree 메모리 매핑

bbtree는 직접 mmap할 수 있으므로 재시작 후 재구축 단계가 없습니다. 게시물은 std의 BTreeMap보다 첫 응답이 160-2,500배 더 빠르다고 보고합니다.

설계 뒤의 비용 모델

게시물은 모든 최적화를 우선순위 순서로 나열된 세 가지 비용으로 구성합니다:

연결된 캐시 라인 수. 캐시 미스는 약 100 ns가 소요됩니다.
실행된 명령어 수. 명령어는 약 0.5 ns가 소요됩니다.
캐시 일관성 트래픽. 동시 액세스에 가장 중요합니다. 캐시 미스를 강제하며 100 ns보다 약간 더 비쌉니다.

캐시 미스는 명령어 비용의 약 200배이므로, 지배적인 목표는 캐시 미스를 최소화하고 각 미스에 대해 검색 공간을 최대한 좁히는 것입니다.

약 16개 항목 미만에서는 선형 검색이 이진 검색보다 우수

게시물은 u64 값의 정렬된 배열에 대한 사고 실험을 실행합니다. 이진 검색은 캐시 미스당 남은 검색 공간을 절반으로 줄입니다. 선형 검색은 미스당 cache_line_size / item_size 항목을 제외하며, u64의 경우 64 / 8 = 8입니다. 따라서 손익분기점은 약 16개 항목이며, 두 전략 모두 최대 두 번의 캐시 미스가 발생합니다. 두 가지 주의 사항이 실제 손익분기점을 더 높입니다: CPU 프리페처가 후속 캐시 라인을 자체적으로 가져올 수 있어 선형 검색에 유리하고, 선형 검색이 더 간단하여 CPU 파이프라인 병렬 처리를 더 많이 허용합니다. 게시물은 64개의 정렬된 u64 값(캐시 라인당 8개)으로 이를 설명합니다: 이진 검색은 3번의 미스가 필요하고 선형 검색은 6번이 필요하지만, 16개 항목에서는 둘 다 최대 2번이 필요합니다.

이것이 bbtree가 노드를 약 16-32개 항목으로 크기 조정하여 항상 선형 검색을 사용할 수 있게 하고 SIMD도 가능하게 하는 이유입니다. 설계는 캐시 인식 B+ 트리에 대한 이전 작업(Rao and Ross, SIGMOD 2000)을 따릅니다.

inline_keys: 힙 할당 키를 캐시 친화적으로 만들기

문자열 키는 위의 산술을 깨뜨립니다. String의 바이트는 힙에 있으며 노드에 인라인되지 않으므로 키 하나를 로드하는 것이 8개의 키를 제공하는 하나의 미스 대신 자체 캐시 미스가 됩니다. 따라서 String 키의 경우 이진 검색이 일반적으로 더 좋습니다.

bbtree의 답은 inline_keys이며, 게시물은 이를 데이터베이스가 수십 년 동안 사용해 온 아이디어로 설명하며, German strings 및 Apache Arrow의 StringView와 유사합니다. 각 키에서 파생된 고정 너비 코드가 노드에 인라인으로 저장됩니다. 고정 크기 인라인 키를 사용하면 하나의 캐시 미스가 다시 8개 이상의 키를 로드하고, 비교가 동률일 때만 전체 키가 로드됩니다.

prefix_keys는 긴 공유 접두사 처리

URL 및 파일 경로와 같은 키는 종종 긴 접두사를 공유하므로 인라인 키로 처음 8바이트만 취하면 유용한 비교가 없을 수 있습니다. bbtree는 prefix_keys 값을 저장합니다: 노드의 모든 키의 공통 접두사. 어떤 노드도 해당 바이트를 명시적으로 저장할 필요가 없습니다. 노드의 모든 키는 부모의 양쪽에 있는 두 구분자 사이에서 정렬되므로, 두 구분자가 처음 20바이트를 공유하면 자식 노드의 모든 키는 동일한 20바이트로 시작합니다. 따라서 각 노드는 접두사의 길이만 저장하고 각 키의 바로 뒤 창을 유지합니다. 이 기술은 Prefix B-Trees(Bayer and Unterauer, TODS 1977)로 거슬러 올라갑니다.

정수 키도 이점

u64 및 u128과 같은 정수 키는 빅엔디안으로 저장되어 바이트가 숫자와 동일한 순서로 정렬되는 경우 동일한 트릭을 사용할 수 있습니다.

InlineKey 특성 및 Rust의 타입 시스템

사용자는 복합 구조체 키를 포함한 자체 키 유형에 대해 InlineKey 특성을 구현할 수 있습니다. 특성은 2, 4 또는 8의 바이트 너비와 주어진 오프셋에서 키 인코딩의 8바이트를 반환하는 함수(빅엔디안, 끝을 지나서 0으로 채움)를 선언합니다:

pub trait InlineKey: Ord {
    /// How many bytes of each inline key the nodes keep: 2, 4 or 8.
    const WIDTH: InlineWidth = InlineWidth::Eight;

    /// Bytes `offset..offset + 8` of the key's encoding, big-endian,
    /// zero past its end, which orders as the keys do.
    fn inline_key_at(&self, offset: usize) -> InlineWord;
}

게시물은 Rust의 타입 시스템을 가장 까다로운 부분으로 식별합니다. 모든 키 유형이 InlineKey를 구현하도록 요구하면 bbtree가 std의 BTreeMap 및 BTreeSet의 드롭인 교체가 되지 않습니다. Nightly Rust에는 정확히 이 목적을 위한 특수화(RFC 1210, 2016년부터 불안정)가 있습니다. 안정적인 Rust의 경우 bbtree는 일반적인 유형을 수동으로 특수화합니다: u64, i64, u128, i128, String, str, &str, Vec, &[u8], Box, Box<[u8]>, [u8; 16], [u8; 20], [u8; 32]. 따라서 내장 유형은 추가 작업 없이 최적화되며 사용자 유형은 선택할 수 있습니다.

배치 모드: 캐시 미스를 Future로 취급

두 번째 최적화 클래스는 대기 시간을 줄이는 것이 아니라 숨기는 것입니다. 소프트웨어 프리페칭은 도움이 되지만 B-트리에는 충분하지 않습니다. B-트리의 메모리 액세스는 근본적으로 연결되어 있기 때문입니다: 현재 노드가 검색될 때까지 다음 노드를 가져올 수 없습니다.

bbtree는 B-트리가 종종 배치로 읽히거나 구축된다는 사실을 활용합니다. get_many_copied 및 insert_many와 같은 배치 API는 키 배열을 입력으로 받고 답 배열을 출력으로 반환합니다. 내부적으로 bbtree는 캐시 미스를 Future로 취급하고 Rust 코드가 IO 작업을 기다리는 것과 같은 방식으로 기다립니다. 코드의 모양은 대략 다음과 같습니다:

fn get_many<const N: usize>(&self, keys: [&K; N]) -> [Option<V>; N] {
    let lanes = keys.map(|key| self.search(key));
    block_on(join_all(lanes))
}

async fn search(&self, key: &K) -> Option<V> {
    let mut node = self.root();
    while node.is_internal() {
        let edge = node.search(key);
        node = node.child(edge);
        prefetch(node.header()).await;
    }
    node.get(key)
}

세 가지 제약이 구현을 형성합니다. 첫째, 캐시 미스는 약 100 ns가 소요되므로 Future는 매우 가벼워야 합니다. tokio와 같은 범용 런타임은 캐시 미스 자체보다 오버헤드가 더 들 수 있으므로 bbtree는 할당을 하지 않고 런타임을 사용하지 않는 자체 소형 실행기로 레인을 폴링합니다. 둘째, 컴파일 타임에 생성된 함수별 async 상태 머신은 상태 전환이 저렴하도록 가능한 한 작아야 합니다. 셋째, 캐시 라인이 이미 상주하는지 알 수 있는 방법이 없으므로 bbtree는 추측합니다: 리프가 L2 캐시를 초과하면 리프는 거의 항상 미스이고, 더 작은 트리는 키를 한 번에 하나씩 조회합니다. 게시물은 데이터베이스 연구가 수년 동안 수동 및 코루틴으로 이렇게 조회를 인터리브했다고 언급합니다.

정확성

게시물은 속도는 쉽고 정확성은 어렵다고 명시합니다: 성능은 측정 가능하고 LLM은 워크로드를 반복할 수 있지만 정확성은 암시적이며 어떤 프롬프트도 모든 DON'T를 나열하지 않고 어떤 테스트 스위트도 코드가 올바르다는 것을 증명하지 않으며 누구도 모든 원하는 속성을 열거할 수 없습니다. 게시물은 bbtree가 정확성에 접근하기 위해 세 가지 가드를 가지고 있다고 명시합니다. 한 댓글러는 프로젝트 자체의 작업 프레이밍을 인용합니다: "형식 검증, 모델 검사, 결정적 시뮬레이션, 퍼징 및 많은 테스트를 통해 프로덕션 준비 완료." 이 섹션 주변에 인용된 참조는 선형 고스트 유형으로 Rust 프로그램을 검증하기 위한 Verus, 동시 Rust 코드 테스트를 위한 AWS의 Shuttle, 포크 기반 결정적 동시성 테스트 도구인 ffs를 가리킵니다.

주장이 반박을 만나는 곳

Hacker News 토론은 "fastest"라는 단어에 눈에 띄게 회의적이며 여러 댓글러가 반대 데이터를 제공합니다.

교체가 더 느린 실제 워크로드

댓글러 virtualritz는 3D 부울 메시 커널에서 bbtree를 테스트하고 std::BTreeMap을 다른 코드 변경 없이 교체하여 성능 저하를 보고했습니다: 96~1536 면의 메시에 대한 합집합 및 차집합 연산이 11%에서 21% 느려졌고 교집합 단계가 16%에서 34% 느려졌습니다. 더 큰 픽스처인 100만 정점 ID를 가진 네페르티티 흉상 스캔(최상의 3회, 초):

cage op	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

결론은 bbtree의 이점이 특정하고 아마도 좁은 사용 사례에서만 유지될 가능성이 높으며 std::BTreeMap과 같은 범용 맵은 임의의 워크로드에서 성능을 유지하기 위해 절충을 해야 한다는 것입니다.

트라이는 실제 경쟁자

댓글러 nicknash는 B-트리의 자연스러운 경쟁자는 트라이 기반 구조(버스트 트라이, 최적화된 q-fast 및 p-fast 트라이, 레벨 압축 트라이, 버킷 트라이, 경로 압축 트라이)와 키 길이가 허용하는 경우 van Emde Boas 레이아웃과 같은 최적화된 계층 트리라고 주장했습니다. 완전히 비교 기반 구조는 정수, 부동 소수점 및 문자열이 사전식 구조로 처리될 수 있으므로 거의 필요하지 않으며 트라이는 로그-로그 시간 연산으로 균일한 무작위 데이터에서 특히 잘 수행된다고 주장했습니다. 댓글러는 작업을 좋다고 부르면서도 "fastest"라는 라벨에 대해 회의적이었습니다.

문자열 키의 메모리 사용량

댓글러 ytxm은 /usr/share/dict/words에 대한 String에서 usize로의 맵(값은 사전 오프셋)을 측정하고 bbtree가 std::collections::BTreeMap보다 약 40% 더 많은 RAM을 사용한다고 보고했습니다. 게시물의 낮은 메모리 주장이 특히 정수 키에 관한 것이므로 이것은 반박이 아니라 데이터 포인트라고 언급했습니다. 같은 댓글러는 애니메이션 웹 페이퍼 형식을 비판하며 동적 요소가 읽기만큼 건너뛰어야 한다고 말했습니다.

프레이밍에 대한 회의론

다른 댓글은 프로젝트의 포지셔닝에 의문을 제기했습니다. 한 댓글러는 "No human can write better code than LLMs"를 인용하고 대담한 주장이라고 불렀습니다. 다른 댓글러는 이 맥락에서 모델 검사가 무엇을 의미하는지 물었습니다. 또 다른 댓글러는 글을 "AI slop"으로 일축하고 시작 인용에 반대했습니다. 한 명은 단순히 소스를 요청했습니다.

실무자의 관심

모든 반응이 부정적인 것은 아닙니다. 댓글러 elendilm은 자신의 시스템 Dip에서 "스마트 배칭"의 분산 단계에서 작업을 중복 제거하기 위해 BTreeMap을 사용한다고 설명했으며, 이 중복 제거는 단일 요청에서 200k+ 삽입의 대부분의 대량 쓰기 워크로드에서 가장 느린 단계이며 때로는 팬아웃, 데이터베이스 쓰기, 커밋 및 수집의 결합 시간의 최대 3배가 걸린다고 말했습니다. 그들은 거기서 bbtree를 시도할 계획이었습니다. 인접한 문제를 작업하는 댓글러 jared_hulbert는 게시물의 일관성 트래픽 처리를 강조하고 자신의 기술을 bbtree에 적용할 의도가 있다고 말했습니다.

주요 시사점

bbtree는 std::BTreeMap 및 BTreeSet의 드롭인 교체로 제시되는 Rust 정렬 맵이며 LSM-트리 memtable의 스키프리스트도 교체합니다.
주요 수치는 각 시스템의 자체 벤치마크에서 4개의 LSM-트리 통합(최대 6.83배), 인메모리 데이터베이스 인덱스(삽입 2.22배, 인덱스 SELECT 1.90배), mmap된 디스크 상주 트리(std의 BTreeMap보다 첫 응답 160-2,500배 빠름)에서 나옵니다.
설계는 세 가지 메커니즘을 통해 캐시 미스를 중심으로 구성됩니다: 선형으로 검색되는 16-32개 항목 노드, 노드에 고정 너비 키 코드를 유지하는 inline_keys, 노드 키의 공유 접두사 길이만 저장하는 prefix_keys.
배치 API는 미스를 awaitable Future로 취급하고 tokio 대신 목적에 맞게 제작된 할당 없는 실행기로 레인을 폴링하여 캐시 미스 대기 시간을 숨깁니다.
독립 테스트는 3D 부울 메시 커널에서 성능 저하와 String 키 맵에서 약 40% 더 높은 메모리 사용을 보고하므로 성능 주장은 보편적이기보다 워크로드 의존적으로 보입니다.
게시물은 출판 전에 Andrew Lamb(InfluxData), Zac Farrell, Eddie Tejeda, Divya Ranganathan(Hotdata), Jacopo Tagliabue(bauplan), Wanxiang Zhong, Junxuan Liao가 검토했습니다.