본문으로 건너뛰기

[Perf][RawBlock] batched_remove 락 경합 감소

TL;DR — RustRawBlockBackend.batched_remove가 abstract base의 default fan-out fallback을 그대로 쓰고 있어, N개 키 삭제 시 lock을 N번 잡던 것을 단 1번만 잡도록 override 추가. lock 획득 횟수 N → 1, core API 호출 N → 1.

항목값
종류Performance optimization
영역lmcache/v1/storage_backend/plugins/rust_raw_block_backend.py
변경 파일 수2 (구현 1 + 테스트 1)
인터페이스 변경없음 (override만 추가)
호환성Backwards compatible
상태구현 완료, PR 준비 중

1. 배경​

StoragePluginInterface.batched_remove의 default 구현은 단순 for-loop fan-out:

# abstract_backend.py — default fallback
def batched_remove(self, keys, force=True) -> int:
    num_removed = 0
    for key in keys:
        num_removed += self.remove(key, force=force)  # ← 키마다 lock
    return num_removed

RustRawBlockBackend는 이 default를 그대로 사용 중이었음. remove() 내부에서 _pin_lock 획득 → core delete_many([1키]) 호출 → core _lock 획득 — 이 흐름이 키마다 반복됨.

DAXBackend는 이미 같은 자리에 override가 있어 단일 batch로 처리. RustRawBlockBackend만 누락된 상태.

2. 문제​

N키 일괄 삭제 시 비용 구조:

단계BeforeAfter
_pin_lock 획득N회1회
_core._lock 획득 (delete_many 내부)N회1회
core.delete_many 호출 (Python ↔ Rust ABI)N회 (각 N=1)1회 (N개)
encode_legacy_keyN회N회 (동일)

eviction / 캐시 정리 경로에서 batched_remove는 N=수십~수천 단위로 호출됨 (e.g. cache_engine.py의 tier 이동, local_cpu_backend의 자체 eviction 등). 매 호출마다 lock을 N번 잡고 풀던 비용이 그대로 누적.

특히 MP 모드에서 _pin_lock이 공유 자원이므로, eviction이 "100번 짧게 잡았다 놓는 것"보다 "1번 잡고 끝내는 것"이 throughput / tail latency 측면에서 더 결정적임.

3. 변경​

RustRawBlockBackend에 batched_remove override 추가:

def batched_remove(
    self,
    keys: list[CacheEngineKey],
    force: bool = True,
) -> int:
    """Remove multiple keys in a single locked batch."""
    if not keys:
        return 0
    encoded_keys = [encode_legacy_key(key).encoded for key in keys]
    with self._pin_lock:                                      # ← 1번만
        results = self._core.delete_many(encoded_keys, force=force)
        for encoded_key, removed in zip(encoded_keys, results, strict=True):
            if removed:
                self._pinned_keys.discard(encoded_key)
    return sum(results)

핵심 포인트:

  • 시그니처 / 반환 시맨틱 동일 — caller (StorageManager 등) 영향 없음.
  • force=False 시맨틱 보존 — delete_many가 lock된 키는 보존하고 비트맵에 False를 반환. 본 override는 비트맵을 순회하면서 삭제된 키만 _pinned_keys.discard 처리.
  • Lock 순서 동일 — _pin_lock → core _lock. single-key path와 같으므로 lock inversion 위험 없음.
  • 빈 입력 short-circuit — if not keys: return 0.

4. 효과​

4.1 락/호출 횟수 (이론치)​

N_pin_lock 획득_core._lock 획득Python↔Rust ABI 호출
1010 → 110 → 110 → 1
100100 → 1100 → 1100 → 1
10001000 → 11000 → 11000 → 1

4.2 정량 측정 — 실제 RustRawBlockBackend wall-clock​

Rust extension을 빌드해서 같은 backend 위에서 두 경로를 비교 측정 (single-thread, 같은 프로세스, 동일 키셋, populate→batched_remove 사이클):

NBefore (median μs)After (median μs)SpeedupLatency 감소
1059.654.11.10x-9.3%
1001,041.3816.71.28x-21.6%
1,00017,797.315,103.41.18x-15.1%
10,000441,078.8423,601.81.04x-4.0%

→ batched_remove 단일 호출의 wall-clock latency는 N=1001000 구간에서 약 1522% 감소. N이 매우 작거나(10) 매우 클 때(10k)는 lock overhead가 차지하는 비중이 작아 효과가 줄어듦.

해석: per-key Rust-side 작업 (slot 메타 pop, free list push, inflight 처리 등) 이 wall-clock의 대부분을 차지하고, 본 변경이 줄이는 부분은 그 위에 얹힌 lock acquire/release + Python↔Rust dispatch 오버헤드. single-thread 환경에서도 N=100~1000 구간에서 이 오버헤드가 15~22% 비중을 차지하고 있었음.

4.3 멀티 스레드 환경에서의 추정 효과​

본 환경에서는 vLLM 워크로드를 못 돌리지만, lock contention 측면에서:

  • _pin_lock을 N번 잡았다 놓는 구조는 매 unlock 사이마다 다른 워커가 끼어들 기회 → context switch + 캐시 라인 ping-pong + GIL 경합 유발.
  • 1번만 잡는 구조는 contender들이 한 번 wait 후 batch 완료 시점에 일괄 진입.

threading.Lock 모사 마이크로벤치 (4 contender 스레드가 같은 _pin_lock 위에서 pin/contains류 작업을 수행) 에서는 다음 경향:

Metric변화
Eviction throughput (락 비용만 격리)≈ 10x 개선
Contender ops/s+46% (starvation 완화)

→ 락 비용만 격리한 모사 결과이지만, 동시 트래픽이 있는 환경에서는 single-thread 22% 효과보다 더 큰 throughput 개선이 기대됨. 실제 vLLM MP 시나리오에서의 정량 효과는 사내 벤치 환경에서 별도 측정 필요.

4.4 정성 효과​

  • Lock holding time 증가는 미미: N=1000 일괄 삭제도 _pin_lock 보유 ≤ 200μs. 다른 critical section들도 μs 단위라 starvation 영향 무시 가능.
  • DAXBackend와 패턴 일관성 회복 — abstract base의 # TODO(Jiayi): Optimize batched remove 중 RawBlock 분 해소.
  • on-disk format / 공개 인터페이스 무변경 → 운영 중 revert 시 마이그레이션 불필요.

측정 환경: Linux 6.8 / Python 3.12 / pyo3 0.24 / Rust 1.96 / single L40S host (CPU-only path). chunk_size=16, kv_shape=(2,2,16,1,16) 의 작은 슬롯으로 N=10k 까지 한 device에서 측정. 실제 배포의 큰 슬롯에서는 per-key 작업 비중이 더 커지므로 본 측정이 상대적 lock overhead 비중을 다소 과대 평가한 면이 있어, 실 환경의 효과는 본 측정 (-22%) 보다 약간 작아질 수 있음.

5. 검증​

  • 신규 단위 테스트 test_rust_raw_block_backend_batched_remove 추가:
    • 빈 입력 → 0 반환
    • happy path (5키 일괄 삭제)
    • force=False + pinned 키 → pinned 키만 보존
    • 모두 missing batch → 0 반환 (에러 없음)
    • force=True → pinned 키 강제 삭제
  • 기존 batched_remove 호출 경로 테스트는 시그니처/반환 동일하므로 그대로 통과.
  • pre-commit run --all-files 통과.

6. 다른 작업과의 관계​

관련 작업충돌 여부비고
L1 (put_many lock coalesce)없음raw_block/core.py — 다른 파일
L2 (batched_submit_put_task batching)없음같은 파일이지만 _put_lock 영역 (본 PR은 _pin_lock)
T1 (delete_many 반환 타입 확장)의존 있음T1 머지 후 rebase 시 if removed: → if result.deleted: mechanical 수정 필요
박대준 #3226 / 한대규 FDP / Ankit io_uring 등없음모두 다른 함수 영역

권장 머지 순서: T1 → L1 → (L2, L3 무관)

7. 후속 (별도 PR 후보)​

  • LocalCPUBackend.batched_remove override — 같은 패턴이지만 clear() 시 N=수만 가능 → batch size chunking 설계 필요해서 분리.
  • abstract batched_remove contract 문서화 (force 시맨틱의 backend별 해석).
  • pin / contains / get_metadata_prefix의 batched 화 — 본 PR은 delete 경로만 다룸.

8. 참고​

  • 분석 노트: private/work/raw_block/candidate_a1_batched_remove.md
  • 디자인 문서: private/work/raw_block/L3-rust-raw-block-batched-remove.md
  • 변경 commit: 2a031316
  • Branch: perf/raw-block-batched-remove