[Candidate A1] `batched_remove` lock overhead — raw_block / local_cpu

작성: 2026-05-29 · 업데이트: 2026-06-02
상태: upstream PR 업로드 완료, 리뷰 대기 (#3494, 브랜치 nayeonikim:perf/raw-block-batched-remove, OPEN)
대상 영역: lmcache/v1/storage_backend/
성격: Performance optimization (락 획득 횟수 감소)

W23 진행 결과 요약 (자세한 내용 §8.4 참고)

RustRawBlockBackend.batched_remove override 추가 (+30), 동작 변경 없음

신규 단위 테스트 1건 / 5케이스 (+99)

raw_block 관련 테스트 54/54 통과, pre-commit run --all-files clean

upstream PR #3494 업로드 (2026-06-02), 리뷰 대응 단계

A1-2 (LocalCPUBackend + chunking) 은 별도 PR — 설계 단계

1. 한 줄 주장

raw_block backend와 local_cpu backend는 단일-lock batch 능력을 이미 보유하고 있는데, batched_remove override가 없어서 키 N개 삭제 시 락을 N번 잡고 있다. DAX backend는 같은 자리에 override를 추가해 이미 해결한 패턴 — raw_block / local_cpu가 그 패턴을 안 따른 것이 문제.

2. 코드 증거

2.1 기반: `abstract_backend.py:235`

# TODO(Jiayi): Optimize batched remove
def batched_remove(self, keys: list[CacheEngineKey], force: bool = True) -> int:
    num_removed = 0
    for key in keys:
        num_removed += self.remove(key, force=force)  # ← 키마다 self.remove()
    return num_removed

기본 구현은 단순 for-loop. 각 backend의 remove()는 내부적으로 락을 잡음 → N키 입력 시 N번 락.

2.2 DAX는 이미 override (`plugins/dax_backend.py:573`)

def batched_remove(self, keys, force=True) -> int:
    return sum(self._core.delete_many(keys, force=force))   # ← 단일 호출

delete_many는 내부에서 _lock 한 번 잡고 N키 전부 처리. 락 1회 acquire/release.

2.3 raw_block은 override 없음 (`plugins/rust_raw_block_backend.py:339`)

def remove(self, key, force=True) -> bool:
    spec = encode_legacy_key(key)
    with self._pin_lock:                                            # ← pin_lock 획득
        removed = self._core.delete_many([spec.encoded], force=force)[0]
        # delete_many 내부에서 _core._lock 획득
        ...
    return removed

# batched_remove 없음 → abstract의 for-loop fallback 사용

→ N키 입력 시:

_pin_lock N번 acquire/release
_core._lock N번 acquire/release
delete_many([1키]) 호출 N번

2.4 local_cpu도 override 없음 (`local_cpu_backend.py:271`)

def remove(self, key, force=True) -> bool:
    if force:
        self.cpu_lock.acquire()                # ← cpu_lock 획득
    if key not in self.hot_cache:
        ...
    memory_obj = self.hot_cache.pop(key)
    memory_obj.ref_count_down()
    if force:
        self.cache_policy.update_on_force_evict(key)
        self.cpu_lock.release()                # ← release
    ...
    return True

# batched_remove 없음 → for-loop fallback

→ N키 입력 시 cpu_lock N번 acquire/release.

3. 시나리오 — 언제 batched_remove가 호출되는가

3.1 호출 경로 (`cache_engine.py` → `storage_manager.py` → backend)

cache_engine.py:1247   storage_manager.batched_remove(keys, locations=[old_position])
cache_engine.py:1401   storage_manager.batched_remove(keys, locations=[location])
cache_engine.py:1461   storage_manager.batched_remove(keys, locations=[location])
                           ↓
storage_manager.py:1092    backend.batched_remove(keys)  ← 각 backend별 호출
                           ↓
                           raw_block / local_cpu / dax / ...

3.2 실제 호출 컨텍스트

호출 지점	컨텍스트	일반적 N (키 개수)
`cache_engine.py:1247`	retrieve 후 다른 tier에서 제거 (계층 이동)	KV chunk batch 크기 (수십~수백)
`cache_engine.py:1401`	캐시 정리	정리 범위에 따라 수십~수천
`cache_engine.py:1461`	캐시 정리 (다른 케이스)	동일
`local_disk_backend.py:347`	자체 eviction 내부 호출	eviction batch (수십)
`local_cpu_backend.py:641`	자체 eviction	수십~수백
`local_cpu_backend.py:884`	전체 clear	전체 캐시 키 수 (수만)
`nixl_storage_backend.py:1054`	NIXL eviction	수십~수백

→ 수십~수만 N 입력이 일상적. 락을 N번 잡는 vs 1번 잡는 차이가 직접적인 throughput / tail latency로 나타남.

4. 성능 시나리오 분석

4.1 단일-thread, 락 경합 없음

락 자체의 비용 (Python threading.Lock): acquire+release ≈ 100-300ns
N=100 → 10-30μs overhead가 그냥 사라짐
작은 영향. 하지만 모든 eviction에 누적됨.

4.2 다중-thread / MP 모드 (실제 문제)

LMCache는 MP 모드에서 N개 vLLM worker가 동시에 store/retrieve 요청을 서버에 보냄. 서버 내부에서 raw_block / local_cpu backend는 공유 자원.

Worker 0: put 요청 (cpu_lock 필요)        ┐
Worker 1: get 요청 (cpu_lock 필요)        ├ 동시 진행
Worker 2: 백그라운드 eviction → batched_remove(100 키) ┘

현재: Worker 2의 batched_remove가 cpu_lock을 100번 lock/unlock → 매 사이클마다 Worker 0/1이 끼어들 기회 있음.

순기능: 다른 워커 starvation 방지
역기능: 매 unlock-relock 사이 context switch 오버헤드 + 캐시 라인 ping-pong + 100번의 GIL 경합

100번 잠깐씩 락 잡는 것보다 1번 길게 잡고 끝내는 게 빠르고 결정적임. 특히 eviction은 빠르게 끝내고 다음 요청 처리하는 게 더 중요.

4.3 Samsung NVMe 컨텍스트

raw_block backend는 NVMe SSD 위에서 동작. delete_many는 슬롯 메타데이터 정리 + free slot 추가만 함 (디스크 I/O 없음 — 그건 checkpoint에서 일괄). 즉 이 락 경합은 순전히 CPU/Python 레벨 오버헤드이고, NVMe 성능과는 무관.

다만 raw_block은 대용량 SSD를 가정 → eviction 시 N이 큼 (수백~수천 슬롯). N이 클수록 락 N번의 비용이 누적되는 효과가 큼. Samsung 대용량 SSD 사용 시나리오에서 더 두드러지는 perf issue.

5. 제안 변경

5.1 raw_block backend override 추가

# rust_raw_block_backend.py — batched_remove 신규 메서드 추가

def batched_remove(
    self,
    keys: list[CacheEngineKey],
    force: bool = True,
) -> int:
    """Remove multiple keys in a single locked batch.
    
    Args:
        keys: Cache keys to remove.
        force: Passed through to the core deletion logic.

    Returns:
        Number of keys actually removed.
    """
    if not keys:
        return 0
    specs = [encode_legacy_key(k).encoded for k in keys]
    with self._pin_lock:
        results = self._core.delete_many(specs, force=force)
        for spec, removed in zip(specs, results, strict=True):
            if removed:
                self._pinned_keys.discard(spec)
    return sum(results)

변경 효과: _pin_lock 1회, _core._lock 1회 (delete_many 내부) → 총 lock acquire 횟수 N → 2.

5.2 local_cpu backend override 추가

# local_cpu_backend.py — batched_remove 신규 메서드 추가

def batched_remove(
    self,
    keys: list[CacheEngineKey],
    force: bool = True,
) -> int:
    if not keys:
        return 0
    num_removed = 0
    if force:
        self.cpu_lock.acquire()
    try:
        for key in keys:
            if key not in self.hot_cache:
                continue
            memory_obj = self.hot_cache.pop(key)
            memory_obj.ref_count_down()
            if force:
                self.cache_policy.update_on_force_evict(key)
            if self.batched_msg_sender is not None:
                self.batched_msg_sender.add_kv_op(
                    op_type=OpType.EVICT,
                    key=key.chunk_hash,
                )
            num_removed += 1
    finally:
        if force:
            self.cpu_lock.release()
    return num_removed

변경 효과: cpu_lock 1회 acquire/release로 N키 처리.

5.3 abstract_backend는 그대로 유지

기본 fallback은 그대로. override 없는 backend는 기존 동작 유지 → backwards compatible. DAX는 이미 override 있음 → 영향 없음.

6. 스코프 / 리스크

항목	평가
변경 파일	2 (rust_raw_block_backend.py, local_cpu_backend.py)
인터페이스 변경	없음 (override만 추가, 시그니처 동일)
호환성	backwards compatible (default fallback 유지)
caller impact	없음 (return 의미·타입 동일)
테스트 부담	기존 `batched_remove` 테스트가 그대로 적용됨. 신규 단위 테스트 권장 (perf 회귀 방지용은 옵션).
동시성 리스크	있음 — 락을 길게 잡으면 다른 워커 starvation 가능. eviction batch 크기 제한이 필요할 수 있음 (예: 1000키 초과 시 chunking).

6.1 동시성 리스크 상세

local_cpu의 N=수만 케이스 (local_cpu_backend.py:884 clear 호출):

락 한 번에 수만 키 처리 → 락 점유 시간이 수십 ms~ 단위가 될 수 있음
그 시간 동안 다른 워커는 put/get 전체 블록됨
chunking 도입 필요 (예: 1024키 단위로 락 분리)

→ 단순 override만 하면 안 됨. batch size limit을 도입해야 함.

7. 동료 작업과의 충돌

동료 작업	충돌 여부
박대준 #3226 + S2 compaction (`_write_full_base`)	체크포인트 쓰기 영역 — 다른 함수. 충돌 없음
한대규 FDP 설계	`cdw13.dspec` 영역 — 다른 함수. 충돌 없음
한대규 #3305 checksum	`_write_one` 영역 — 다른 함수. 충돌 없음
Ankit #3274 io_uring	`_write_buffers/_read_buffers` — 다른 함수. 충돌 없음
서동주 #3119 MP L2 adapter	adapter 레이어 — 다른 모듈. 충돌 없음
권상윤 #3260 alignment	device cleanup — 다른 함수. 충돌 없음

충돌 없음. raw_block 동료 작업이 활발한 영역이지만, 본 작업은 backend 클래스의 새 메서드 추가에 국한되어 같은 함수를 동시에 건드리지 않음.

8. 검증 계획

8.1 단위 테스트

기존 batched_remove 테스트가 동일 시그니처/동일 반환을 검증함 → 그대로 통과해야 함.

신규 추가 (권장):

N키 일괄 삭제 시 락을 한 번만 잡는지 (mock으로 락 acquire count 측정)
chunking 적용 시 expected chunk boundary

8.2 성능 측정

Before/After microbenchmark:
- batched_remove([key] * N) 호출 시간 (N=100, 1000, 10000)
- 동시 thread 환경에서 다른 thread의 put/get 처리량
Samsung 대용량 SSD 시나리오: N=수천 이상에서 차이 측정

8.3 사전 검증

pre-commit run --all-files 통과
tests/v1/storage_backend/test_raw_block_core.py, test_rust_raw_block_backend.py, test_local_cpu_backend.py, L2 adapter 테스트

8.4 실제 검증 결과 (W23, 2026-06-01~06-07)

브랜치: nayeonikim:perf/raw-block-batched-remove
upstream PR: #3494 — 2026-06-02 업로드, OPEN (리뷰 대기)
대상 파일: lmcache/v1/storage_backend/plugins/rust_raw_block_backend.py 만 변경 (A1-1 스코프)
분량: 구현 +30 / 테스트 +99, 인터페이스·시그니처 미변경
신규 단위 테스트 1건, 5케이스:
1. 빈 입력
2. batch 삭제
3. pin 보존
4. 미존재 키
5. force 우회
raw_block 관련 테스트 54/54 통과
pre-commit run --all-files clean
다른 backend·MP path(L2 adapter) 영향 없음 (override만 추가, default fallback 유지)

9. PR 분할 제안

9.1 Option A: 단일 PR (raw_block + local_cpu)

장점: 패턴 통일성 한 번에 확보. 단점: 리뷰 범위 약간 큼.

9.2 Option B: 2개 PR (raw_block 먼저, local_cpu 나중)

장점:

raw_block PR은 Samsung 색깔 강함 + 정당화 명확
local_cpu PR은 chunking 설계가 추가로 필요해서 별도로 분리 가능
첫 PR은 빠른 머지 가능

단점: 동일한 패턴을 두 번 리뷰

9.3 추천: Option B

raw_block override → 첫 PR (작고 명확, Samsung 색깔)
local_cpu override + chunking → 두 번째 PR (설계 토론 포함)

10. PR 제목 후보

[perf] override batched_remove in RustRawBlockBackend to single locked batch
[perf][raw_block] use delete_many in batched_remove to reduce lock contention

11. 우선순위 갱신

메인:    M3 (io_uring setup flags, #3274 대기)
서브 1:  A1-1 (raw_block batched_remove)  ← 신규, 바로 착수 가능
서브 2:  M2 (local_disk batching)
서브 3:  A1-2 (local_cpu batched_remove + chunking) ← 설계 필요
서브 4:  M1 (LFU O(1))

A1-1은 M3 대기 중 가장 우선순위 높은 서브 작업.

1. 한 줄 주장​

2. 코드 증거​

2.1 기반: abstract_backend.py:235​

2.2 DAX는 이미 override (plugins/dax_backend.py:573)​

2.3 raw_block은 override 없음 (plugins/rust_raw_block_backend.py:339)​

2.4 local_cpu도 override 없음 (local_cpu_backend.py:271)​

3. 시나리오 — 언제 batched_remove가 호출되는가​

3.1 호출 경로 (cache_engine.py → storage_manager.py → backend)​

3.2 실제 호출 컨텍스트​

4. 성능 시나리오 분석​

4.1 단일-thread, 락 경합 없음​

4.2 다중-thread / MP 모드 (실제 문제)​

4.3 Samsung NVMe 컨텍스트​

5. 제안 변경​

5.1 raw_block backend override 추가​

5.2 local_cpu backend override 추가​

5.3 abstract_backend는 그대로 유지​

6. 스코프 / 리스크​

6.1 동시성 리스크 상세​

7. 동료 작업과의 충돌​

8. 검증 계획​

8.1 단위 테스트​

8.2 성능 측정​

8.3 사전 검증​

8.4 실제 검증 결과 (W23, 2026-06-01~06-07)​

9. PR 분할 제안​

9.1 Option A: 단일 PR (raw_block + local_cpu)​

9.2 Option B: 2개 PR (raw_block 먼저, local_cpu 나중)​

9.3 추천: Option B​

10. PR 제목 후보​

11. 우선순위 갱신​