15 · 인덱싱: 인메모리 인덱스 + 디스크 토큰

감사 로그가 1천만 건을 넘으면, 인덱스 없이 "사용자 alice의 모든 행동"을 찾으려면 전체를 읽어야 합니다. DB가 B-tree 보조 인덱스를 만들 듯, Quipu-Log도 인덱스를 만듭니다. 단, 디스크 위에 별도 B-tree 파일을 쓰는 대신 메모리 안에 HashMap을 품고, 재시작 시 로그 재생으로 재구축하는 방식을 택했습니다. 왜 그랬는지, 그리고 디스크에 영속하는 "토큰"이 어떻게 검색을 가능하게 만드는지를 이번 챕터에서 살펴봅니다.

당신이 아는 것: DB의 보조 인덱스

관계형 DB에서 SELECT * FROM users WHERE email = 'alice@example.com'을 실행하면, email 컬럼에 인덱스가 없는 한 테이블 전체를 스캔합니다(full table scan). 인덱스를 만들면 — CREATE INDEX ON users(email) — DB는 별도 B-tree 구조를 유지합니다. B-tree에는 이메일 값 → 행 주소(heap tuple pointer)가 정렬되어 들어있어, 검색이 O(log n)으로 끝납니다.

이 B-tree 인덱스는 디스크의 별도 파일에 영속됩니다. 새 행이 삽입될 때마다 인덱스도 함께 갱신되고, DB 재시작 후에도 그대로 사용 가능합니다.

레지스트리: 엔티티 메타데이터를 담는 테이블

감사 로그의 행(log row)은 "누가(actor) 무슨 행위를 했는가"만 기록합니다. "alice가 어떤 사람인지" — 이름, 역할, 부서 같은 메타데이터 — 는 레지스트리(registry)에 따로 저장됩니다. 레지스트리도 append-only 로그이지만, 저장하는 건 엔티티의 버전 이력입니다.

레지스트리의 핵심 자료구조는 RegistryIndex입니다. 이것이 곧 "인덱스"입니다.

crates/quipu-core/src/registry.rsstruct RegistryIndex {
    schema: TypeSchema,
    /// entity_id -> 버전 uid 목록 (오래된 순)
    versions: HashMap<String, Vec<Uid>>,
    /// uid -> 실제 레코드
    by_uid: HashMap<Uid, RegistryRecord>,
    /// 인덱스 필드 -> 검색키 -> entity_id 집합 (주 색인)
    index: HashMap<String, HashMap<Vec<u8>, HashSet<String>>>,
    /// 블라인드 토큰 색인: 필드 -> 토큰 다이제스트 -> entity_id 집합
    token_index: HashMap<String, HashMap<String, HashSet<String>>>,
    // ...인메모리 평문 캐시 (opt-in)
}

이 중에서 실제로 검색을 빠르게 만드는 두 층이 보입니다. index는 평문 값(또는 SHA-256/HMAC 다이제스트)으로 검색하는 주 색인, token_index는 접두사·부분문자열 검색을 위한 블라인드 토큰 색인입니다.

인덱스는 언제, 어떻게 채워지나

RegistryIndex는 두 경로로 채워집니다.

1. 쓰기 시점 — absorb(): 새 엔티티 버전이 디스크 레지스트리 로그에 기록된 직후, 인메모리 인덱스에 반영합니다.

crates/quipu-core/src/registry.rsfn absorb(&mut self, rec: RegistryRecord) {
    for (name, stored) in &rec.fields {
        if let Some(key) = index_key(stored) {
            self.index.entry(name.clone()).or_default()
                     .entry(key).or_default()
                     .insert(rec.entity_id.clone());
        }
    }
    for (field, tokens) in &rec.tokens {
        let posting = self.token_index.entry(field.clone()).or_default();
        for d in &tokens.digests {
            posting.entry(d.clone()).or_default()
                   .insert(rec.entity_id.clone());
        }
    }
    // versions / by_uid 갱신...
}

2. 재시작 시점 — 재구축: 프로세스가 새로 뜰 때, TypeRegistry::open()이 레지스트리 로그 전체를 스캔하여 모든 레코드에 absorb()를 호출합니다.

crates/quipu-core/src/registry.rspub fn open(dir: &Path, schema: TypeSchema, ...) -> Result<Self> {
    let mut table = Table::open(dir, max_segment_bytes)?;
    let mut idx = RegistryIndex::new(schema, cache_plaintexts);
    let records: Vec<RegistryRecord> = table.scan()?.collect::<Result<Vec<_>>>()?;
    for rec in records { idx.absorb(rec); }
    Ok(Self { table, idx, fingerprints: HashMap::new() })
}

레지스트리 레코드는 엔티티 버전이므로, 사용자 1000명 × 평균 3버전 = 3000개입니다. 이걸 한 번 스캔하는 비용은 무시할 수준이지요. 그래서 "별도 인덱스 파일을 관리하는 복잡성" 없이 "재시작마다 재구축"이 실용적인 선택입니다.

디스크에 영속하는 것: FieldTokens

인덱스 자체는 인메모리입니다. 그런데 보호 필드(SHA-256·HMAC 등으로 해시된 필드)는 특별한 문제가 있습니다. 해시는 단방향이라 재시작 후에 원문을 복원할 수 없습니다. 접두사·부분문자열 검색을 위한 토큰 다이제스트를 재구축할 원본이 없는 것이죠.

해법은 쓰기 시점에 토큰을 미리 계산해서 레코드 자체에 영속하는 것입니다. RegistryRecord.tokens 필드가 바로 그 역할입니다.

crates/quipu-core/src/registry.rspub struct RegistryRecord {
    pub uid: Uid,
    pub entity_id: String,
    pub fields: BTreeMap<String, StoredValue>,  // 보호된 값
    /// 쓰기 시점에 계산·영속된 블라인드 인덱스 토큰 다이제스트.
    /// 원문이 디스크에 없는 보호 필드를 재시작 후에도 검색 가능하게 한다.
    pub tokens: BTreeMap<String, FieldTokens>,
}

pub struct FieldTokens {
    pub key_version: u32,  // 어떤 HMAC 키로 다이제스트 했는지
    pub digests: Vec<String>,   // 예: ["digest(ali)", "digest(lic)", "digest(ice)"]
}

예를 들어 사용자 이름 "Alice"를 HMAC-SHA256으로 보호하고, trigram(n=3) 인덱스를 선언했다면, 쓰기 시 "ali", "lic", "ice" 세 토큰의 다이제스트가 계산되어 레코드에 저장됩니다. 재시작 후 absorb()가 이 레코드를 읽으면 tokens에서 다이제스트를 꺼내 token_index에 넣습니다. 원문 없이도 재구축 완료.

스키마로 인덱스 행동 결정: FieldIndex

어떤 필드를 어떤 형태로 인덱싱할지는 스키마 선언으로 결정됩니다. FieldIndex enum이 세 가지 검색 형태를 정의합니다.

crates/quipu-core/src/schema.rspub enum FieldIndex {
    None,                // 인덱스 없음 (기본)
    Exact,               // 전체 값을 소문자화한 토큰 1개 (대소문자 무시 정확 일치)
    Prefix(usize),     // 1..=n 길이 접두사 토큰 (Prefix(4) → "a","al","ali","alic")
    Ngram(usize),      // n글자 슬라이딩 창 토큰 (Ngram(3) → "ali","lic","ice")
}

Prefix(n)은 n글자 이하의 접두사 검색을 인덱스만으로(스캔 없이) 처리합니다. Ngram(n)은 n글자 이상 탐색어의 부분문자열 검색을 후보 집합으로 좁힙니다. 두 경우 모두 토큰 다이제스트가 레코드에 영속되어 재시작 후에도 동작합니다.

정리

• DB의 B-tree 보조 인덱스와 달리, Quipu-Log는 인메모리 HashMap을 인덱스로 쓰고 재시작마다 레지스트리 로그 재생으로 재구축한다.
• 보호 필드의 접두사·부분문자열 검색을 위한 토큰 다이제스트는 쓰기 시점에 레코드에 영속된다 (RegistryRecord.tokens). 원문이 없어도 재구축 가능.
• FieldIndex::Exact / Prefix(n) / Ngram(n) 스키마 선언이 쓰기 시 생성되는 토큰의 종류를 결정한다.
• 블라인드 인덱스의 암호학적 상세 — 토큰 다이제스트 생성 방식, 정보 누출 분석 — 는 26장 블라인드 인덱스에서 다룬다.