34 · 수평 확장: 샤딩·일관성 해싱·읽기 복제

단일 writer 하나로 버틸 수 있는 쓰기 속도에는 한계가 있습니다. "그럼 writer를 여러 개로 늘리면 되지 않나?" — 좋은 생각입니다. 하지만 Quipu-Log의 tamper-evidence는 단일 writer를 전제로 합니다. 이 챕터는 그 전제를 깨지 않으면서 쓰기를 N배로 늘리는 방법을 다룹니다: 테넌트별 샤딩.

왜 단일 writer가 병목인가

모든 이벤트가 한 writer 스레드를 통과합니다. 내부적으로 파이프라인 큐(29장 비동기 파이프라인)가 버퍼링하지만, 큐를 소비하는 것도 결국 한 스레드입니다. CPU 1개와 디스크 I/O 1개를 나눠 쓰는 셈이죠. 이 천장을 넘으려면 writer 자체를 늘려야 합니다.

문제는, 여러 writer가 같은 체인에 동시에 쓰면 체인 헤드가 분기됩니다. 어느 쪽이 진짜인지 합의가 필요해지고, 그 합의 로직에 버그가 생기는 순간 변조 탐지의 전제가 무너집니다.

해법: 체인을 여러 개로 쪼갭니다. 각 체인은 여전히 writer 하나입니다. 다만 서로 다른 테넌트의 이벤트가 서로 다른 체인에 쓰입니다.

ShardRouter: 쓰기 라우팅 + 읽기 팬아웃

ShardRouter는 N개의 독립 AuditPipeline을 묶는 얇은 조율자입니다. 코어 스토리지 엔진(quipu-core)은 손대지 않았습니다 — 각 샤드는 오늘날의 단일 스토어와 똑같이 동작하는 AuditStore이고, ShardRouter는 그것들의 "교통 경찰"입니다.

일관 해싱: 적게 재분배하고 많이 확장한다

테넌트를 어느 샤드로 보낼지 결정하는 건 ShardMap입니다. 단순히 tenant_id % N을 해버리면 샤드 수가 바뀔 때 모든 테넌트가 다른 샤드로 이동합니다. 이것은 큰 문제입니다 — 이전에 기록한 이력이 다 다른 샤드에 있으니까요.

해법이 일관 해싱(consistent hashing)입니다. 해시 링에 각 샤드의 가상 노드(virtual node)를 배치하고, 테넌트 해시가 링에서 어느 가상 노드 다음에 오는지로 샤드를 찾습니다. 샤드가 추가될 때 이동하는 테넌트는 전체의 일부만입니다.

crates/quipu-middleware/src/sharding/shard_map.rsconst VNODES_PER_SHARD: u32 = 64; // 샤드당 가상 노드 수

pub fn route_write(&self, tenant: &str) -> ShardId {
    let h = self.hash(&tenant);
    // 링에서 h 이상인 첫 가상 노드 → 그 가상 노드가 속한 샤드.
    match self.ring.binary_search_by_key(&h, |(rh, _)| *rh) {
        Ok(i) => self.ring[i].1,
        Err(i) if i < self.ring.len() => self.ring[i].1,
        Err(_) => self.ring[0].1, // 링 끝을 넘으면 맨 앞으로
    }
}

리샤딩은 add-only: 레코드를 옮기지 않는다

append-only 체인은 재배치할 수 없습니다. 한번 쓴 레코드를 다른 샤드로 옮기면 체인이 끊어지고 tamper-evidence가 무너집니다. 그래서 리샤딩은 이렇게 작동합니다.

1. 기존 샤드를 freeze합니다. 이제부터 그 샤드는 쓰기를 받지 않습니다 — 영원히.
2. 새 빈 샤드를 추가해 액티브로 만듭니다.
3. 이후 쓰기는 일관 해싱에 따라 새 샤드로 향합니다.

frozen 샤드의 과거 이력은 그 자리에 그대로 있습니다. 테넌트의 읽기는 현재 소유 샤드와 모든 frozen 샤드를 함께 조회합니다(read_targets). 레코드는 절대 이동하지 않고, 단일 writer 불변식도 절대 깨지지 않습니다.

crates/quipu-middleware/src/sharding/shard_map.rspub fn read_targets(&self, tenant: Option<&str>) -> Vec<ShardId> {
    match tenant {
        Some(t) => {
            // 현재 액티브 소유 샤드 + 모든 frozen 샤드
            // (리샤딩 전 이력이 frozen에 있을 수 있다)
            let mut targets = vec![self.route_write(t)];
            targets.extend(self.frozen.iter());
            targets
        }
        None => self.all_shards().collect(), // 테넌트 없으면 전체 팬아웃
    }
}

크로스 샤드 쿼리: 팬아웃 + 타임스탬프 머지

여러 샤드에 걸친 쿼리는 각 샤드에 동일한 서브 쿼리를 날리고, 결과를 (timestamp_micros, log_id) 기준으로 k-way 머지합니다. 전역 총 순서가 없기 때문에 타임스탬프가 기준이 됩니다.

페이지네이션이 까다롭습니다. 전역 인덱스가 없으므로, 페이지를 넘길 때마다 각 샤드에서 어디까지 읽었는지를 들고 다녀야 합니다. 그것이 MultiCursor입니다 — 샤드별 독립 커서의 맵.

crates/quipu-middleware/src/sharding/fanout.rs/// 재개 가능한 크로스 샤드 커서. 샤드별로 "마지막으로 낸 행 다음" 위치를 기억.
pub struct MultiCursor {
    per_shard: BTreeMap<u32, String>,  // 샤드별 불투명 커서
    done: BTreeSet<u32>,               // 소진된 샤드 — 재시작하지 않는다
}

전역 순서는 포기한다 — 대신 무결성은 지킨다

샤딩하면 글로벌 단일 타임라인이 없습니다. 서로 다른 샤드의 이벤트는 클럭 기반 타임스탬프로만 정렬됩니다. 이것은 의도된 트레이드오프입니다(ADR-2).

하지만 무결성은 완전히 보존됩니다. 각 샤드는 독립적으로 체인, 체크포인트, 앵커링을 유지합니다. 여기에 더해 교차 샤드 앵커링(ADR-5, GlobalCheckpoint)이 "샤드 전체 삭제 또는 롤백"을 탐지합니다 — 각 샤드는 개별적으로 검증을 통과해도, 샤드 집합 자체가 바뀌면 글로벌 체크포인트가 잡아냅니다.

읽기 복제: sealed 세그먼트는 그냥 복사해도 된다

sealed(봉인된) 세그먼트는 8장 세그먼트와 롤오버에서 설명한 대로 불변입니다. 바이트 하나도 변하지 않죠. 그래서 이것을 다른 호스트에 rsync 또는 스냅샷으로 복사해 쿼리 전용 노드를 만들 수 있습니다. 무결성에 영향이 없습니다 — 복사본도 CRC와 Merkle 트리로 검증됩니다.

단, 액티브(현재 쓰는 중인) 세그먼트 꼬리는 복사 시점에 완전하지 않을 수 있으므로 제외합니다. POST /v1/admin/flush로 플러시한 뒤 복사하면 꼬리까지 일관된 스냅샷을 얻을 수 있습니다.