L3 — RustRawBlockBackend.batched_remove 락 흡수 (default fan-out → 단일 batch)

한 줄 요약: StoragePluginInterface 의 default batched_remove 가 N 회의 per-key remove() 로 fall back 하던 것을, _pin_lock 한 번 + _core.delete_many 한 번 호출로 일괄 처리하도록 override. lock 획득 N → 1, core API 호출 N → 1.

---

0. Contribution Rule 요약 (이 PR 작성 시 준수 사항)

근거: CONTRIBUTING.md, AGENTS.md, docs/coding_standards.md, DCO.

0.1 Branch / Base

• 공식 가이드: dev 브랜치 base.
• 현재 작업 브랜치: perf/raw-block-batched-remove ← 이 브랜치에서 commit/PR.

0.2 DCO Sign-off (필수)

• 모든 commit 에 Signed-off-by: <Name> <email> trailer 포함. (현 commit 2a031316 에 이미 sign-off 적용됨)

0.3 Commit Message 스타일

• 현 commit 제목: [perf] override batched_remove in RustRawBlockBackend to reduce lock contention
• 다른 PR 들의 패턴 ([Tag][SubTag] Subject) 과 맞추려면 PR 제목은 [Perf][RawBlock] Override batched_remove to reduce lock contention 권장.

0.4 Linting (CI 에서 검사)

• pre-commit run --all-files 통과 필수. (ruff check + ruff format + isort + mypy + codespell)
• SPDX 헤더, import 헤더 유지.

0.5 Coding Standard (이 변경에 직접 적용되는 항목)

• 신규 메서드 docstring 의무 — batched_remove 의 Args/Returns/시맨틱 명시.
• Type hint 완비 — 시그니처 (list[CacheEngineKey], bool, int) 모두 구체 타입.
• private 멤버 외부 접근 금지 — 본 변경은 같은 클래스 내부의 _pin_lock, _pinned_keys, _core 만 사용. 위반 없음.
• assert 금지 — 본 변경은 validation 추가 없음.

0.6 PR Scope

• "PRs must be small and focused" — batched_remove override 단일 메서드 추가
  • 단일 테스트 추가. 적절한 범위.
• L1 / L2 / T1 와 분리되어 있으며 본 PR 에 포함하지 않음.

0.7 테스트 규칙

• 위치: tests/v1/storage_backend/test_rust_raw_block_backend.py 에 함수 단위 추가.
• 외부 클래스 private 멤버 접근 없이 backend.contains(key, pin=False) 와 backend.pin(key) 등 공개 API 만으로 검증.

0.8 Caller Impact 분석

• batched_remove override 는 abstract base 의 default 구현을 대체. 호출자는 StorageManager 와 그 하위 — 시그니처/리턴 타입 (list[CacheEngineKey] -> int) 변경 없음.
• default fallback 이 remove() 를 N 회 호출하는 시맨틱과 외부 관찰 가능 결과는 동일 하며, lock 획득 횟수만 감소.

---

1. 변경 배경

1.1 현재 구조 — default fan-out

abstract_backend.py:234-251

# TODO(Jiayi): Optimize batched remove
def batched_remove(self, keys, force=True):
    num_removed = 0
    for key in keys:
        num_removed += self.remove(key, force=force)
    return num_removed

RustRawBlockBackend.remove 는 (rust_raw_block_backend.py:339-345)

def remove(self, key, force=True):
    spec = encode_legacy_key(key)
    with self._pin_lock:
        removed = self._core.delete_many([spec.encoded], force=force)[0]
        if removed:
            self._pinned_keys.discard(spec.encoded)
    return removed

→ N 키 일괄 삭제 시 _pin_lock 획득 N 회 + _core._lock 획득 N 회 + N 회의 single-element delete_many 호출.

1.2 비용 구조

key 1개 처리 시:

단계	비용
_pin_lock 획득	1 회
_core.delete_many([1])	core _lock 1 회 + 단일 element 루프
_pinned_keys.discard	python set discard 1 회
encode_legacy_key	per-key

N=100 일괄 삭제:

• _pin_lock: 100 회 (현재) → 1 회 (제안)
• _core._lock: 100 회 (현재) → 1 회 (제안)
• core.delete_many 호출: 100 회 (각 N=1) → 1 회 (N=100)
• encode_legacy_key: 100 회 (현재 = 제안, 변화 없음)

1.3 왜 이렇게 짜였는가

• StoragePluginInterface.batched_remove 는 명시적 TODO (# TODO(Jiayi): Optimize batched remove) — 의도적으로 fan-out fallback 만 제공.
• backend 별로 batch 가능 여부가 다르므로 base 가 보수적인 default 만 두고, 각 backend 가 필요시 override 하는 패턴.
• DAXBackend 는 이미 같은 패턴으로 override 되어 있음 (dax_backend.py:573-587). RustRawBlockBackend 만 override 가 누락된 상태.

1.4 다른 PR 들과의 직교성

	수정 파일	수정 메서드	사용 lock
L1 (5a27732f)	raw_block/core.py	_write_one, put_many	core _lock
L2 (93403c0f)	plugins/rust_raw_block_backend.py	batched_submit_put_task	_put_lock
L3 (본 PR)	plugins/rust_raw_block_backend.py	batched_remove (신규)	_pin_lock

→ L1 은 파일이 다름. L2 와는 같은 파일이지만 메서드 단위로 직교 (메서드 사이 라인 충돌 없음, 사용 lock 도 _put_lock vs _pin_lock 으로 분리). 시맨틱 충돌 없음.

1.5 T1 (9fc5a901) 와의 의존

T1 은 RawBlockCore.delete_many 의 반환 타입을 list[bool] 에서 list[RawBlockDeleteResult] 로 확장. 본 PR 은 현재 T1 미적용 베이스에서 작성되어 delete_many(...) 결과를 bool 처럼 사용 — if removed: truthy 검사, sum(results) 합산.

T1 머지 후 rebase 시 mechanical 수정 필요 (§6 참조):

• for encoded_key, removed in zip(...) 안의 if removed: → if result.deleted:
• return sum(results) → return sum(1 for r in results if r.deleted)

---

2. 검토 내용

2.1 lock 획득 횟수 시맨틱

현재 (default fallback): _pin_lock 을 N 회 잡았다 놓으므로, N 키 삭제 도중에 다른 thread 가 _pin_lock 을 잡고 pin/unpin/contains 를 수행할 수 있음 — 즉 다른 thread 와 인터리브 가능.

제안: 한 번 잡고 N 키를 일괄 처리. 다른 thread 의 _pin_lock 작업이 batch 완료까지 직렬화됨.

lock holding time 영향:

• python set discard N 회: ~50ns × N → N=1000 에서도 ≤ 50μs.
• core delete_many(N): core _lock 보유 + 인덱스 dict pop × N → ~100ns × N.
• 합계: N=100 에서 ≤ 20μs, N=1000 에서 ≤ 200μs. 다른 critical section 들도 μs 단위라 contention 영향 미미.

2.2 force=False 시맨틱 보존

_core.delete_many(..., force=False) 는 lock 된 키를 보존하고 결과 비트맵에 False 를 반환. 본 PR 은 for ... removed in zip(encoded_keys, results) 로 비트맵을 순회하며 삭제된 키만 _pinned_keys.discard — single-key remove() 시맨틱과 정확히 일치.

2.3 부분 실패 처리

delete_many 의 결과 비트맵 N 개에 대해:

• True → _pinned_keys.discard + 합산 카운터에 포함
• False → discard 안 함, 합산에서 제외

→ sum(results) 가 실제 삭제된 키 수와 동일. abstract base 의 "removed count" 시맨틱과 일치.

2.4 빈 입력 처리

if not keys: return 0 early-return. _core.delete_many([]) 가 0-iteration 루프지만 lock 만 잡고 풀므로 short-circuit 이 cheap.

2.5 race window

• _pin_lock 외부에서의 pin() race: 본 변경은 _pin_lock 획득 시점만 늦출 뿐이고 동일 lock 을 사용하므로 atomicity 동등. 외부 호출자가 pin(K) 직전에 K 가 batched_remove 에 포함되어 있으면 단일 키 remove() 와 정확히 같은 순서대로 직렬화됨.
• core _lock 과의 inversion: _pin_lock → core _lock 순서는 single-key remove() 와 동일. lock 순서 역전 없음.

2.6 검토에서 배제한 항목

• pin/contains/get_metadata_prefix 의 batched 화 — L3 와 별도 (별도 PR 후보, 본 노트는 delete 경로만 다룸).
• abstract batched_remove contract 명시 (default fallback 의 시맨틱 / force 의 backend 별 해석) — abstract interface 문서화 작업으로 분리 (후속 PR; L2 F4/F13 과 함께 처리).
• exists_inflight 와 delete 의 interaction — 현재도 single-key path 가 delete_many 안에서 inflight 취소를 처리하므로 batch 화로 새로 생기는 race 없음.

---

3. 효과

3.1 정량 효과

항목	N=10	N=100	N=1000	단위
_pin_lock 획득	10 → 1	100 → 1	1000 → 1	회
_core._lock 획득	10 → 1	100 → 1	1000 → 1	회
core.delete_many 호출	10 (각 N=1)	100 (각 N=1)	1000 (각 N=1)	호출
호출 overhead 절감	python ↔ Rust ABI 호출 9회	99회	999회	호출

→ N 이 클수록 효과 비례 증가. 호출 빈도가 가장 높은 eviction path 가 가장 큰 수혜.

3.2 정성 효과

• DAXBackend.batched_remove 와 동일한 패턴으로 backend 일관성 회복.
• StoragePluginInterface.batched_remove 의 TODO 해소 (한 backend 분).

3.3 비효과

• single-key remove() 시그니처/시맨틱 — 미변경.
• _core.delete_many 시그니처 — 미변경.
• on-disk format — 미변경.
• _pinned_keys 보호 invariant — 동일 lock 으로 동일 하게 유지.

---

4. 변경점

4.1 batched_remove override 추가

rust_raw_block_backend.py:347-374

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:
        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)

4.2 docstring

다음 invariant 명시:

• abstract base 의 default fallback 대비 lock 획득 횟수 N → 1.
• force=False 시 locked 키는 보존.
• 반환값 = 실제로 삭제된 키 수.

4.3 테스트

test_rust_raw_block_backend.py:572-667 — test_rust_raw_block_backend_batched_remove

• 빈 입력 → 0 반환
• 5 키 일괄 삭제 happy path
• pin() 후 force=False 일 때 pinned 키만 보존
• 모두 missing 인 batch → 0 반환 (no error)
• force=True 로 pinned 키 강제 삭제

---

5. 개선 포인트 확인 방법

5.1 lock contention 측정

# CountingLock 으로 _pin_lock 을 swap
# batched_remove(keys=[100]) 1회
# assert _pin_lock.acquire_count == 1 (변경 후) / 100 (변경 전)

5.2 호출 횟수 측정

# patch.object(backend._core, "delete_many", side_effect=...)
# batched_remove(keys=[100]) 1회
# assert mock.call_count == 1 (변경 후)

5.3 정합성

pytest tests/v1/storage_backend/test_rust_raw_block_backend.py::test_rust_raw_block_backend_batched_remove -v

---

6. 위험 / 롤백

6.1 위험 항목

위험	가능성	영향	완화
T1 머지 후 delete_many 반환 타입 변경으로 rebase 시 코드 깨짐	확실	컴파일/런타임 에러	rebase 시 if result.deleted:/sum(1 for r in results if r.deleted) 로 mechanical 수정. §1.5 참조
_pin_lock 보유 시간 증가로 다른 thread 의 pin/contains 지연	낮음	일시적 latency 증가	§2.1 의 holding time 분석 — N=1000 에서도 ≤ 200μs
force=False 시 pinned 키 잔존 후 비트맵 해석 오류	낮음	카운터 mismatch	§2.2 + 테스트의 force=False/True 양쪽 케이스로 회귀 방지

6.2 롤백

• 변경이 단일 메서드 추가 + 단일 테스트 추가에 국한. PR 단위 revert 충분.
• on-disk format / 공개 인터페이스 미변경 → 운영 중 롤백 시 마이그레이션 불필요.

6.3 머지 순서 의존성

• T1 (9fc5a901) 머지 전에는 본 PR 그대로 머지 가능 (현 베이스가 T1 미적용).
• T1 머지 후 본 PR rebase 시 §1.5 의 mechanical 수정 필요.
• L1, L2 와는 무관 — 어느 순서로 머지해도 충돌 없음.

권장 머지 순서: T1 → L1 → (L2, L3 순서 무관, 병렬 가능).

---

7. 변경 로그

일자	작성자	내용
2026-06-01	ny	본 디자인 문서 초안 작성 (commit 2a031316 사후 작성). 변경 자체는 단순 override 패턴이지만 T1 와의 의존성 / L1·L2 와의 직교성 명시.