서론

분산 키-값 저장 시스템에서 범위 조회(Range Query)는 가장 핵심적이면서도 빈번하게 사용되는 연산입니다. TiKV는 고성능 분산 트랜잭션 키-값 데이터베이스로서, 방대한 데이터셋에서 효율적인 스캔 성능을 보장하기 위해 다양한 최적화 기법을 범위 조회 구현에 적용합니다. 이 글에서는 TiKV 범위 조회의 구현 메커니즘, 최적화 기술, 그리고 모범 사례를 심층적으로 살펴봅니다.

범위 조회 기본 개념

범위 조회란?

범위 조회는 키의 접두사(prefix) 또는 특정 범위 조건에 따라 여러 키-값 쌍을 검색하는 연산입니다. 단일 키 조회와 달리, 범위 조회는 연속된 키 공간을 스캔해야 하므로 저장 엔진에 더 높은 성능 요구 사항을 제기합니다.

TiKV에서의 범위 조회 유형

TiKV는 여러 종류의 범위 조회 연산을 지원합니다.

• 순방향 스캔(Forward Scan): 시작 키에서 종료 키 방향으로 탐색
• 역방향 스캔(Reverse Scan): 종료 키에서 시작 키 방향으로 탐색
• 배치 스캔(Batch Scan): 여러 개의 불연속 범위를 동시에 스캔
• 키 전용 스캔(Key-Only Scan): 값 없이 키만 반환하여 네트워크 전송량 감소

핵심 구현 메커니즘

저장 엔진 아키텍처

TiKV는 다계층 저장 아키텍처를 채택하여 효율적인 범위 조회를 구현합니다. 최상위 계층은 Raft 합의 프로토콜을 통한 복제를 담당하고, 하위 계층은 RocksDB를 기반으로 한 로컬 저장소 엔진이 실제 데이터를 관리합니다. RocksDB는 LSM-Tree(Log-Structured Merge-Tree) 구조를 사용하여 쓰기 성능을 높이고, 블룸 필터(Bloom Filter)와 블록 캐시(Block Cache)를 통해 읽기 성능을 최적화합니다.

반복자 디자인 패턴

TiKV는 커서(Cursor) 패턴을 사용하여 범위 스캔을 구현합니다. 커서는 저장소 엔진의 반복자(Iterator)를 래핑하여 상태를 추적하고, seek, next, prev 등의 연산을 제공합니다.

pub struct Cursor<I: Iterator> {
    iter: I,
    scan_mode: ScanMode,
    valid: bool,
}

impl<I: Iterator> Cursor<I> {
    pub fn seek(&mut self, key: &Key, stats: &mut CfStatistics) -> Result<bool>;
    pub fn next(&mut self, stats: &mut CfStatistics);
    pub fn prev(&mut self, stats: &mut CfStatistics);
    pub fn key(&self, stats: &mut CfStatistics) -> &[u8];
    pub fn value(&self, stats: &mut CfStatistics) -> &[u8];
}

스캔 알고리즘 흐름

범위 조회의 핵심 알고리즘은 시작 키를 찾은 후, 조건에 맞는 다음 키로 이동하며 데이터를 수집하는 과정입니다. TiKV는 이 과정에서 시간 조각(Time Slice) 기반의 협력적 스케줄링을 사용하여 긴 스캔이 시스템을 독점하는 것을 방지합니다.

성능 최적화 전략

1. 시간 조각 스케줄링 최적화

TiKV는 협력적 스케줄링 전략을 통해 긴 스캔이 시스템을 차단하는 것을 방지합니다.

const MAX_TIME_SLICE: Duration = Duration::from_millis(2);
const MAX_BATCH_SIZE: usize = 1024;

async fn forward_raw_scan(...) -> Result<Vec<Result<KvPair>>> {
    let mut row_count = 0;
    let mut time_slice_start = Instant::now();
    while cursor.valid()? {
        row_count += 1;
        if row_count >= MAX_BATCH_SIZE {
            if time_slice_start.saturating_elapsed() > MAX_TIME_SLICE {
                reschedule().await;
                time_slice_start = Instant::now();
            }
            row_count = 0;
        }
    }
}

2. 메모리 관리 최적화

최적화 전략	설명	이점
제로 카피	저장소의 데이터에 대한 참조를 직접 반환	메모리 할당 및 복사 감소
배치 처리	한 번에 1024개의 키-값 쌍을 처리	컨텍스트 스위칭 감소
객체 풀	커서 및 반복자 객체 재사용	가비지 컬렉션 부하 감소

3. 인덱스 가속

TiKV는 RocksDB의 SkipList와 Bloom Filter를 활용하여 범위 조회를 가속화합니다.

• 접두사 Bloom Filter: 특정 접두사 존재 여부를 빠르게 판단
• 블록 캐시: 자주 접근하는 데이터 블록 캐싱
• 인덱스 블록: 키 위치 찾기 가속

4. 병렬 스캔

대규모 범위 조회의 경우, TiKV는 Region 수준의 병렬 스캔을 지원합니다.

pub async fn raw_batch_scan(
    &self,
    ctx: Context,
    cf: String,
    ranges: Vec<KeyRange>,
    limit: usize,
) -> Result<Vec<Vec<KvPair>>> {
    let futures = ranges.into_iter().map(|range| {
        self.raw_scan(ctx.clone(), cf.clone(), range, limit)
    });
    future::try_join_all(futures).await
}

트랜잭션 일관성 보장

MVCC 다중 버전 동시성 제어

TiKV는 MVCC(Multi-Version Concurrency Control)를 통해 범위 조회의 일관성을 보장합니다. 각 키-값 쌍은 여러 버전을 가지며, 스냅샷 격리 수준에서 동작하여 읽기 작업이 쓰기 작업에 방해받지 않도록 합니다.

스냅샷 격리

범위 조회는 스냅샷 격리 수준에서 작동하여 일관된 데이터 읽기를 보장합니다.

impl Storage {
    pub fn raw_scan(
        &self,
        ctx: Context,
        cf: String,
        start_key: Vec<u8>,
        end_key: Vec<u8>,
        limit: usize,
        key_only: bool,
    ) -> impl Future<Output = Result<Vec<KvPair>>> {
        let snapshot = self.engine.snapshot(ctx.clone());
        self.with_snapshot(snapshot, |store| {
            store.forward_raw_scan(cf, start_key, end_key, limit, key_only)
        })
    }
}

모니터링 및 진단

성능 지표 모니터링

TiKV는 범위 조회 성능을 진단하기 위한 다양한 모니터링 지표를 제공합니다.

지표 이름	유형	설명
raw_scan_duration	Histogram	스캔 소요 시간 분포
scan_keys_per_second	Gauge	초당 스캔 키 수
scan_bytes_per_second	Gauge	초당 스캔 데이터량
iterator_seek_count	Counter	반복자 위치 지정 횟수

느린 쿼리 진단

느린 범위 조회를 진단하는 방법은 다음과 같습니다.

• 느린 쿼리 로그 분석: 기간이 1초를 초과하는 range_scan 유형 쿼리 식별
• 스캔 통계 분석: EXPLAIN ANALYZE를 사용하여 스캔 효율성 평가

모범 사례

1. 쿼리 최적화 제안

전체 테이블 스캔 회피:

// 권장하지 않음: 전체 범위 스캔
let results = store.raw_scan("", vec![], vec![], 10000, false).await;

// 권장: 명확한 범위 사용
let results = store.raw_scan("", b"user_100", b"user_200", 100, false).await;

limit 합리적 설정:

// 한 번에 너무 많은 데이터를 가져오지 않도록 조정
let results = store.raw_scan("", start_key, end_key, 1000, false).await;

2. 인덱스 설계 원칙

시나리오	권장 전략	이유
범위 조회 빈번	정렬된 접두사 사용	무작위 I/O 감소
조회 패턴 고정	사전 파티션 설계	핫스팟 Region 방지
데이터량 방대	계층형 저장	핫/콜드 데이터 분리

3. 시스템 파라미터 튜닝

[storage]
scan-batch-size = 1024

[rocksdb]
max-sequential-skip-in-iterations = 100000
memtable_prefix_bloom_size_ratio = 0.1

[server]
scan-concurrency = 8

문제 해결

일반적인 문제 및 해결 방법

문제1: 스캔 성능 저하

• 원인: Region 분포 불균형 또는 핫스팟 Region 발생
• 해결책: PD 스케줄러를 사용하여 Region 재분배

문제2: 메모리 오버플로우

• 원인: 한 번에 너무 많은 데이터를 스캔
• 해결책: limit 값을 줄이고, 여러 배치로 나누어 스캔

문제3: 응답 시간 변동

• 원인: Compaction이 I/O 성능에 영향
• 해결책: Compaction 전략 조정 및 피크 시간 회피

미래 발전 방향

1. 벡터화 스캔

TiKV는 SIMD 명령어를 활용한 벡터화 스캔 기술을 탐색 중입니다.

let results = store.vectorized_scan(range, |batch| {
    let mask = batch.keys().simd_compare_prefix("user_");
    batch.filter(mask)
}).await;

2. 지능형 프리페치

머신 러닝 기반의 쿼리 패턴 예측을 통해 데이터를 사전에 로드하여 지연 시간을 줄입니다.

3. 이기종 저장소 지원

TiFlash의 컬럼 기반 저장소와 결합하여 분석형 범위 조회에 더 나은 성능을 제공합니다.