Rust의 “제로 코스트” 이터레이터가 벡터화를 조용히 막고 있어 병목이 되었던 사례를 통해, 배치 이터레이터로 SIMD 최적화를 되살려 쿼리 지연 시간을 크게 낮춘 과정을 살펴본다.
쿼리 가격 최대 94% 인하쿼리 가격을 최대 94%까지 인하했습니다
CustomersPricingCompanyJobsBlogDocsContactDashboardSign up
February 18, 2026•Xavier Denis (Engineer)
Rust의 “제로 코스트” 이터레이터 내부를 들여다본 결과, 그것들이 조용히 벡터화를 방해하고 있다는 사실을 발견해 전체 텍스트 검색 쿼리의 지연 시간을 220ms → 47ms로 줄였습니다. 이 글은 제로 코스트 추상화가 기계적 공감(mechanical sympathy)을 실천하지 않아도 된다는 뜻은 아니라는 점을 상기시키기 위한 것입니다.
avg latency, filtered BM25 query, 5 million documents
before ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ 220 ms
after ▓▓▓▓▓▓▓▓▓▓▓▓▓ 47 ms
avg latency,
filtered BM25 query,
5 million documents
░░░░ 220 ms
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░ ▓▓▓▓ 47 ms
░░░░ ▓▓▓▓
░░░░ ▓▓▓▓
══════ ══════
before after
몇 달 전, 고객 중 한 곳이 권한 검사를 잔뜩 수행하는 전체 텍스트(BM25) 쿼리에서 높은 지연 시간으로 어려움을 겪고 있었습니다. ContainsAny 필터에 수천 개까지 권한 식별자가 전달되는 경우가 있었죠. 대략 이런 형태입니다:
{
"filters": ["attribute", "ContainsAny", ["a", "c", "f", "j", "m", "o", "t", "x", "z", ...]],
"rank_by": ["text", "BM25", "some query string"]
}이런 필터된 BM25 쿼리는 turbopuffer에서 흔하며, 수백만 문서에 대해서도 보통 50ms 미만이 걸립니다. 이 쿼리는 겉보기엔 무해해 보였지만, 그보다 4배 넘게 오래 걸리고 있었습니다. 쿼리 프로파일을 살펴보니 흥미로운 사실이 드러났습니다. 실제 BM25 랭킹에는 약 10ms만 쓰이고 있었고, 나머지(200ms 이상)는 _필터 평가_에 쓰이고 있었습니다.
이런 종류의 필터 평가는 저렴해야 합니다. 실제로 쿼리 플래너는 이 쿼리에 관련된 필터 비트맵(각 필터 값에 대해 어떤 문서가 매칭되는지 나타냄)의 크기를 67MB로 보고했습니다. 냅킨 계산에 따르면 NVMe SSD(최대 처리량 6,240 MB/s)에서 읽고 처리하는 데는 10–20ms 정도면 충분해야 합니다.
보통 냅킨 계산과 현실 사이에 큰 간극이 있으면 최적화의 큰 기회가 있거나, 우리의 이해에 버그가 있다는 뜻입니다. 그래서 파고들기 시작했습니다…
turbopuffer는 모든 인덱싱 데이터를 Log-Structured Merge (LSM) tree에 저장합니다. 키-값 쌍은 오브젝트 스토리지의 정렬된 파일(SSTable)에 저장됩니다. 정렬된 파일 하나만 있으면 읽기는 단순해지지만(낮은 read amplification), 쓰기마다 전체 데이터셋을 다시 정렬해야 합니다(높은 write amplification). 대신, write amplification을 최소화하기 위해 새 KV 쌍을 작은 파일에 기록하고, 비동기로 컴팩션(병합 및 중복 제거)하여 더 큰 파일로 만들어 read amplification을 최소화합니다. LSM 컴팩션은 쓰기를 빠르게 유지하면서도, 읽기가 터치해야 하는 파일 수를 제한합니다.
각 파일에는 최소/최대 키를 설명하는 메타데이터가 들어 있습니다. 읽기를 처리할 때 쿼리 엔진은 이 메타데이터를 사용해 매칭되는 키를 포함할 수 있는 파일을 찾고, byte-range fetch로 파일에서 해당 키 범위만 가져옵니다.
query(i OR j) ─▶ read ─▶ merge 3 iters ─▶ filter/rank ─▶ result
▲▲▲
┌┘│└─────┐
╔═ LSM tree ════│═│══════│═════════════════════════╗
║ │ └──┐ │ ║
║ ┌──┐ ┌──┐ │┌──┐│ ╔╧═╗ ┌──┐ ┌──┐ ┌──┐ ║
║ │ab│ │cd│ ││fg││ ║ij║ │mn│ │op│ │xy│ ║
║ └──┘ └──┘ │└──┘│ ╚══╝ └──┘ └──┘ └──┘ ║
║ │ │ ║
║ │ │ ║
║ ┌──┬──┬──┬──┐│ ╔╧═╗──┬──┬──┐ ┌──┬──┬──┬──┐ ║
║ │ab│cd│ef│gh││ ║ij║kl│mn│op│ │rs│tu│vw│yz│ ║
║ └──┴──┴──┴──┘│ ╚══╝──┴──┴──┘ └──┴──┴──┴──┘ ║
║ │ ║
║ │ ║
║ ┌──┬──┬──┬──╔╧═╗──┬──┐ ┌──┬──┬──┬──┬──┬──┬──┐ ║
║ │ab│cd│ef│gh║ij║kl│mn│ │op│qr│st│uv│wx│yz│⍺β│ ║
║ └──┴──┴──┴──╚══╝──┴──┘ └──┴──┴──┴──┴──┴──┴──┘ ║
║ ║
╚══════════════════════════════════════════════════╝
query(i OR j) ─▶ read ─▶ merge
▲▲▲
││└──┐
╔═ LSM tree ═════││═══│═══════════╗
║ │└┐ │ ║
║ ┌──┐ ┌──┐ ┌──┐│╔╧═╗│┌──┐ ┌──┐ ║
║ │ab│ │cd│ │fg││║ij║││mn│ │op│ ║
║ └──┘ └──┘ └──┘│╚══╝│└──┘ └──┘ ║
║ │ │ ║
║ │ ┌─┘ ║
║ ┌──┬──┬──┬──┐ │╔═╧╗──┬──┬──┐ ║
║ │ab│cd│ef│gh│ │║ij║kl│mn│op│ ║
║ └──┴──┴──┴──┘ │╚══╝──┴──┴──┘ ║
║ │ ║
║ │ ║
║ ┌──┬──┬──┬──╔═╧╗──┬──┬──┬──┐ ║
║ │ab│cd│ef│gh║ij║kl│mn│op│rs│ ║
║ └──┴──┴──┴──╚══╝──┴──┴──┴──┘ ║
║ ║
╚═════════════════════════════════╝
고객의 쿼리는 ContainsAny 필터를 사용합니다. 본질적으로는 모든 값을 매칭하기 위한 OR입니다(예: "a" OR "c" OR "f" OR "j" OR "m" OR "o" OR "t" OR "x" OR "z" OR ...).
필터의 각 값은 분리된 여러 키 범위로 팬아웃되는 별도의 키 조회를 트리거합니다.
query(a OR c OR f OR ──────▶ read ─▶ merge 24 iters ─▶ filter/rank ─▶ result
j OR m OR o OR ▲▲▲
t OR x OR z) │││
┌──────┘│└───┐
╔═ LSM tree ══════════│═══════│════│═══════════════╗
║ ┌──────┬──────┬──────┬───┴─┬──────┬──────┐ ║
║ ╔═╧╗ ╔═╧╗ ╔═╧╗ │ ╔═╧╗ ╔╧═╗│ ╔╧═╗ ╔╧═╗ ║
║ ║ab║ ║cd║ ║fg║ │ ║ij║ ║mn║│ ║op║ ║xy║ ║
║ ╚══╝ ╚══╝ ╚══╝ │ ╚══╝ ╚══╝│ ╚══╝ ╚══╝ ║
║ │ │ ║
║ ┌──┬──┬──────────┼────┬──┬─────────┬─────┐ ║
║ ╔═╧╦═╧╦═╧╗··· ╔═╧╗··╔╧═╦╧═╗ │···╔╧═╗··╔╧═╗ ║
║ ║ab║cd║ef║gh· ║ij║kl║mn║op║ │·rs║tu║vw║xy║ ║
║ ╚══╩══╩══╝··· ╚══╝··╚══╩══╝ │···╚══╝··╚══╝ ║
║ │ ║
║ ┌──┬──┬─────┬─────┬────┬──────┼────┬──┐ ║
║ ╔═╧╦═╧╦═╧╗··╔═╧╗··╔═╧╗ ╔╧═╗··╔═╧╗··╔╧═╦╧═╗··· ║
║ ║ab║cd║ef║gh║ij║kl║mn║ ║op║qr║st║uv║wx║yz║⍺β· ║
║ ╚══╩══╩══╝··╚══╝··╚══╝ ╚══╝··╚══╝··╚══╩══╝··· ║
║ ║
╚══════════════════════════════════════════════════╝
query(a OR c OR ─▶ read ─▶ merge
f OR j OR ▲▲▲
m OR o) │││
┌─┘│└─────┐
╔═ LSM tree ═════│══│══════│══════╗
║ ┌────┬────┬────┼───┬────┐ ║
║ ╔═╧╗ ╔═╧╗ ╔═╧╗│╔═╧╗ ╔╧═╗│╔╧═╗ ║
║ ║ab║ ║cd║ ║fg║│║ij║ ║mn║│║op║ ║
║ ╚══╝ ╚══╝ ╚══╝│╚══╝ ╚══╝│╚══╝ ║
║ │ │ ║
║ ┌──┬──┬────────┬────┬─┴┐ ║
║ ╔═╧╦═╧╦═╧╗··┐ │╔═╧╗··╔╧═╦╧═╗ ║
║ ║ab║cd║ef║gh╵ │║ij║kl║mn║op║ ║
║ ╚══╩══╩══╝··┘ │╚══╝··╚══╩══╝ ║
║ │ ║
║ ┌──┬──┬─────┼─────┬──┐ ║
║ ╔═╧╦═╧╦═╧╗··╔═╧╗··╔═╧╦═╧╗··┐ ║
║ ║ab║cd║ef║gh║ij║kl║mn║op║rs╵ ║
║ ╚══╩══╩══╝··╚══╝··╚══╩══╝··┘ ║
║ ║
╚═════════════════════════════════╝
반환된 각 키 범위는 해당 KV 쌍에 대한 이터레이터를 만들고, 이 이터레이터들은 필터링과 랭킹을 위해 단일한 정렬·중복 제거 스트림으로 병합되어야 합니다.
모든 키 범위의 이터레이터는 병합 이터레이터로 전달되며, 병합 이터레이터는 키를 순서대로 반환하고 중복 키가 발생하면 가장 최근의 KV 쌍을 유지합니다.
수천 개의 필터 값을 가진 고객의 ContainsAny 쿼리는(각 값이 별도의 키 범위를 만들 수 있으므로) 몇 개의 연속된 키 범위만 가져오는 쿼리보다 비교적 병합 비용이 더 비쌉니다.
그럼에도 병합 자체는 저렴해야 합니다. 우리의 병합 이터레이터는 그저 키를 비교하고 이긴 엔트리를 앞으로 이동시키는 작업을 합니다. 상대적으로 가벼운 일이죠. 또한 Rust 표준 Iterator 트레잇, 즉 제로 코스트 추상화 위에 구축되어 있으니 추가 오버헤드 없이 손으로 직접 쓴 루프와 동일한 코드로 컴파일되어야 합니다. 다른 거의 모든 쿼리에서는 무시할 만했습니다. 하지만 이 특정 고객 쿼리의 프로파일은 병합이 _전체 런타임의 60% 이상_을 소비하고 있음을 명확히 보여주었습니다.
숨은 비용을 찾기 위해, 병합 이터레이터 코드의 핵심 일부를 단순화한 Rust 스켈레톤을 보겠습니다. scan() 함수는 모든 후보 키 범위 이터레이터(여기서는 위치를 가진 정수 슬라이스로 단순화)를 기반으로 병합을 만들고, 루프에서 이를 소모합니다. next()를 호출할 때마다 병합 구조를 재귀적으로 내려가 한 번에 값 하나를 만들어냅니다. 프로덕션에서는 루프 본문이 필터를 평가하고 결과를 스코어링합니다. 여기서는 이터레이터 비용을 분리하려고, 그 대신 사소한 산술로 바꿉니다.
fn scan(keys: &[Vec<u64>]) -> u64 {
let mut merge_tree = Merge::build(keys);
let mut sum = 0u64;
// next() recurses down to produce the smallest current key
while let Some(v) = merge_tree.next() {
// Simple arithmetic: sum if even
let x = v + 1;
if x % 2 == 0 { sum += x; }
}
sum
}현대적인 3 GHz CPU에서 100,000개의 정수를 scan한다면(스칼라 연산만 가정) 대략 130μs 정도를 기대할 수 있습니다(100K 값 × 값당 4개 명령 ÷ 초당 30억 사이클). 그런데 실제로는 6.5ms가 걸립니다! 이터레이터가 정말 “제로 코스트”라면 그렇지 않아야 하는데, 기대치보다 50배나 비쌉니다.
겉보기엔 Rust에서 비용을 설명할 만한 것이 없습니다. 작업은 순수하게 메모리 내에서 일어나므로 I/O는 배제할 수 있는데도, CPU가 이 정수들을 빠르게 처리하지 못하게 하는 무언가가 분명히 있습니다. 모든 엔지니어가 알듯 컴퓨터는 거짓말 추상화의 탑이므로, 추상화 아래로 내려가 컴파일러가 실제로 무엇을 생성하는지 봐야 합니다.
제로 코스트 추상화는 동일한 로직에 대해 우리가 더 빠른 어셈블리를 손으로 써낼 수 없다는 것을 약속합니다. scan()의 ARM 어셈블리를 보고 어떻게 컴파일되는지 살펴봅시다:
LBB10_1: ; loop {
sbfx x8, x1, #0, #1 ;
add x9, x1, #1 ; x = v + 1
and x8, x8, x9 ; x = (x is even) ? x : 0
add x19, x8, x19 ; sum += x
add x0, sp, #8 ;
bl __ZN14bench9ChainTree4next17haad780538028036aE ; Some(v) = tree.next() else { break }
tbnz w0, #0, LBB10_1 ; }Rust 컴파일러(LLVM)는 7개 명령으로 구성된 루프를 만들어냈습니다. 첫 4개는 루프 본문, 마지막 3개는 루프 제어입니다.
루프 제어는 next()를 호출하고, None이 반환되면 종료하며, 그렇지 않으면 계속합니다:
add x0, sp, #8 ; pass &mut self to next()
bl __ZN14bench9ChainTree4next17haad780538028036aE ; tree.next()
tbnz w0, #0, LBB10_1 ; continue if Some루프 본문에서는 LLVM이 조건 산술을 꽤 영리하게 처리했습니다. if/브랜치를 평가하는 대신, 비트마스킹 트릭을 사용해 값이 홀수일 때는 합계에 0을 더하도록 만들었습니다.
sbfx x8, x1, #0, #1 ; mask: 0xFFFF..FFFF if v is odd (x is even), 0x0 if v is even
add x9, x1, #1 ; x = v + 1
and x8, x8, x9 ; x = x & mask (x is even ? x : 0)
add x19, x8, x19 ; sum += x이는 분기 예측 실패 비용을 피하기 위해 조건을 순수 산술로 바꾸는 표준적인 컴파일러 기법인 _프레디케이션(predication)_입니다.
LLVM 덕분에 루프 본문 내부 작업은 원소당 산술 명령 4개로 컴파일됩니다. 냅킨 계산대로라면 약 130µs가 걸려야 합니다. 그런데 왜 50배나 더 오래 걸릴까요?
컴파일러는 반복을 더 큰 블록으로 언롤(unroll)하고, SIMD(Single Instruction, Multiple Data)로 벡터화하여 여러 값을 병렬로 처리하고 싶어합니다.
하지만 여기서는 next()의 재귀적 성격 때문에 그 어떤 것도 할 수 없습니다. next() 호출 하나하나는 이터레이터들 사이를 비교하고 내부 위치를 변경하며 값을 하나 반환합니다. 각 호출의 출력은 이전 호출이 남긴 상태에 의존하므로, 현재 호출이 끝나기 전에는 다음 호출이 무엇을 반환할지 컴파일러가 예측할 수 없습니다. 이것이 언롤을 죽입니다(예측할 수 없는 호출을 배치로 묶을 수 없음). 또한 벡터화도 죽입니다(값이 한 번에 하나씩만 도착하면 여러 값을 동시에 처리할 수 없음).
여기서 우리의 병합 이터레이터에서 Rust의 제로 코스트 추상화가 가진 숨은 기회비용이 드러납니다. 이터레이터 자체는 단일 호출에 대해 손으로 쓸 법한 코드로 컴파일됩니다. 그 의미에서는 제로 코스트가 맞습니다. 하지만 이 추상화는 호출 _사이_에서 컴파일러가 SIMD와 언롤을 적용하는 것을 막습니다. 그래서 루프 본문이 현대 CPU가 좋아하는 단순하고 직렬적인 작업임에도, 컴파일러는 이를 벡터화할 수 없습니다. 그리고 next()로의 재귀 호출은 130µs의 유용한 작업을 6.5ms의 병합 오버헤드 속에 묻어버립니다.
고객의 ContainsAny처럼 많은 분리된 키 범위가 많은 이터레이터를 만들어내는 쿼리에서는 병합 비용이 지배적이 됩니다.
기회비용을 제거하려면, 중간에 재귀 함수 호출이 없는 상태로 연속된 데이터에 대한 타이트한 루프를 컴파일러에게 다시 제공해야 합니다.
해결책은? **배치 이터레이터(batched iterators)**라는 고전적인 데이터베이스 기법입니다.
호출당 단일 원소를 생성하는 대신, 병합 이터레이터가 입력들을 비교하고 KV 쌍을 교차(interleave)하여 배치를 채운 뒤, 배치 전체를 한 번에 반환합니다. 소비자는 그 배치를 재귀 호출 없이 타이트한 루프로 순수 배열처럼 처리합니다.
업데이트된 Rust 스켈레톤은 다음과 같습니다:
fn scan(keys: &[Vec<u64>]) -> u64 {
let mut merge_tree = Merge::build(keys);
let mut sum = 0u64;
// next_batch() recurses down, but produces a batch (N=512) of KV pairs
while let Some(batch) = merge_tree.next_batch() {
// process the array
for val in batch {
let x = val + 1;
if x % 2 == 0 { sum += x; }
}
}
sum
}배치 처리는 작업을 두 개의 루프로 나눕니다:
병합 비용이 사라지지는 않지만, 이제는 매 KV 쌍마다 지불하던 비용을 512개 KV 쌍에 걸쳐 상각합니다. 그리고 안쪽 루프는 단순 배열을 순회하기만 하므로, 컴파일러는 루프 본문 전체를 볼 수 있고 반복을 언롤하며 SIMD 명령으로 벡터화하는 등 공격적으로 최적화할 수 있습니다.
어셈블리는 안쪽 루프(LBB11_4)에서 핵심적인 차이를 보여주며 최적화를 확인해 줍니다. 기존 루프는 7개의 스칼라 명령으로 컴파일되었지만, 배치 버전은 SIMD 명령(끝이 .2d, .16b로 끝나는 것들)을 사용해 한 번에 8개 값을 처리합니다:
LBB11_4: ; loop {
add x9, x21, x8 ;
ldp q4, q5, [x9, #16] ; let vals = batch[i..i+8];
ldp q6, q7, [x9, #48] ;
and.16b v16, v4, v20 ; let mask = vals & 1
cmeq.2d v16, v16, #0. ; mask = (vals & 1 == 0) ? all-ones : all-zeros
add.2d v4, v4, v20 ; let xs = vals + 1
bic.16b v4, v4, v16 ; let xs = xs & mask
add.2d v1, v4, v1 ; sum += xs
add x8, x8, #64 ; i += 8;
cmp x8, #1, lsl #12 ; if i == batch.len() { break }
b.ne LBB11_4 ; }이 변경 후 scan 벤치마크(100,000개 값)는 약 110μs에 실행됩니다. 이전보다 60배 빠르고, SIMD 덕분에 130μs 냅킨 계산치보다도 더 빨라졌습니다.
merge iterator execution time, 100k values in 64 blocks
before ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ 6.5 ms
after ▓ 110 μs
merge execution,
100k values, 64 blocks
░░░░ 6.5 ms
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░
░░░░ ▓▓▓▓ 110 μs
══════ ══════
before after
“제로 코스트”는 추상화가 컴파일 과정에서 사라진다는 약속이지, 부작용이 전혀 없다는 약속은 아닙니다. Rust의 이터레이터는 각 호출을 손으로 작성할 법한 코드로 컴파일했지만, 호출 사이의 추상화 경계가 컴파일러가 호출 전반에 걸쳐 SIMD와 언롤을 적용하기 위해 필요로 하는 루프 형태를 가려버렸습니다.
프로덕션 코드를 배치 이터레이터를 사용하도록 업데이트한 뒤, 고객의 쿼리 지연 시간은 약 220ms에서 47ms로 떨어졌습니다. ContainsAny 필터는 여전히 많은 키 범위로 팬아웃되지만, 병합 비용은 이제 배치 전체에 상각되며 각 배치 내에서는 SIMD 벡터화가 적용됩니다.
이 문제는 새로운 것이 아니며, 해결책도 새롭지 않습니다. 배치 이터레이터는 수십 년 된 데이터베이스 기법입니다. 하지만 추상화 아래를 들여다보고 CPU가 실제로 무엇을 필요로 하는지 알아차릴 수 있는 기계적 공감이 필요했습니다. 현대 CPU는 이런 단순하고 직렬적인 작업을 더 빠르게 처리하는 방향으로만 발전할 것입니다. 우리의 최신 full-text search 및 approximate nearest neighbor 알고리즘은 이를 체현합니다. 결국 프로덕션 프로파일은 이론과 추상화보다 우선합니다. turbopuffer에서는 이를 지속적으로 들여다보며 데이터베이스의 성능을 더더짜내고 있습니다.
turbopuffer는 2.5T+ 문서를 호스팅하고, 10M+ writes/s를 처리하며, 10k+ queries/s를 제공하는 빠른 검색 엔진입니다. 우리는 훨씬 더 큰 규모도 준비되어 있습니다. 여러분의 쿼리를 우리에게 맡겨주시길 바랍니다.
CompanyJobsPricingStorePress & mediaSystem status
Support
Follow
© 2026 turbopuffer Inc.
Terms of serviceData Processing AgreementPrivacy PolicySecurity & Compliance