V1 — _validate_loaded_entries batched_read 병렬화

상태: 로컬 구현 완료 — perf/validate-batched-read (worktree /home/ny/workspace/LMCache-v1-validate, base: PR #3274 ankit-sam/raw_iouring_cmd)
우선순위: P3 (startup-only, 정확성 영향 없음, HC-SSD 대규모 환경에서 효과)
다음 단계: PR #3274 머지 후 dev 리베이스 → upstream PR 제출

---

1. 문제

_validate_loaded_entries는 startup/recovery 시 1회 호출되며, 체크포인트에서 복원한 모든 인덱스 항목의 슬롯 헤더를 디스크에서 읽어 정합성을 검증한다.

# core.py:1411-1412
for encoded_key, entry in items:
    slot_hdr = self._read_slot_header(int(entry.offset))   # ← N번 순차 pread

_read_slot_header는 매 호출마다:

1. _lock 획득·해제 × 2 (_inflight_io_count 증감)
2. pread_into — POSIX 동기 syscall 1회

HC-SSD에서 슬롯 수 = (용량 / slot_bytes) — 15 TB NVMe + slot_bytes 4 MB 기준 ~3,750개. NVMe 랜덤 read latency 100 µs 가정 시 순차 → 375 ms, batched_read로 병렬화 시 (queue depth 256, 디바이스 IOPS 1M+) → ~4 ms (95%+ 단축 예상).

---

2. 목표

io_uring 경로에서 _validate_loaded_entries가 N개 헤더를 한 번의 batched_read 호출로 병렬 읽기. POSIX 경로는 현행 유지 (변경 없음).

---

3. 선행 의존: PR #3274

PR #3274가 머지되면 _read_buffers(offsets, buffers, payload_lens, total_lens) dispatcher가 core.py에 추가된다.

하지만 dispatcher를 통하면 _is_buffer_aligned 검사에서 걸릴 수 있다:

# _read_buffers 내부 (PR #3274 post-merge 추정, §2.4)
if can_batch and all(_is_buffer_aligned(buf) for buf in buffers):
    batched_read(...)          # ← 진짜 병렬 (원하는 경로)
else:
    for ...: read_uring(...)   # ← 동기 직렬 (현재와 같은 성능)

bytearray(header_bytes)는 pointer alignment 보장 없음 → _is_buffer_aligned = False → 직렬 fallback.

따라서 _read_buffers 경유가 아니라, 직접 batched_read + wait_iouring 호출해야 진짜 병렬 효과.

---

4. 설계 결정 사항

4.1 io_engine 분기

io_engine != "io_uring":
    기존 순차 pread_into 루프 (변경 없음)

io_engine == "io_uring" and len(items) > 1:
    → _read_slot_headers_batched(offsets) 신규 헬퍼
    → batched_read + wait_iouring

io_engine == "io_uring" and len(items) <= 1:
    기존 경로 (단건은 batched 이점 없음)

4.2 aligned buffer 전략

batched_read는 use_odirect=True일 때 block_align(보통 4096 B) pointer-aligned 버퍼 필요.

선택지:

전략	장점	단점
A. bytearray 단순 사용	구현 간단	use_odirect=True면 Rust가 ValueError → exception fallback 필요
B. mmap 1개 (n×header_bytes)	page-aligned 보장, 단일 할당	startup-only인데 mmap lifecycle 관리 추가
C. 큰 bytearray 할당 후 aligned view	의존성 없음, 구현 명확	코드 약간 길어짐
D. use_odirect=False일 때만 batched	가장 단순, 안전	O_DIRECT 환경에서 개선 없음

권장: C + fallback으로 D

def _alloc_aligned_bufs(self, n: int) -> list[memoryview]:
    align = self.block_align
    hdr = self.header_bytes
    # 연속 버퍼 하나로 n개 헤더 수용 + 앞에 alignment padding
    raw = bytearray(n * hdr + align - 1)
    import ctypes
    addr = ctypes.addressof(ctypes.c_byte.from_buffer(raw))
    pad = (-addr) % align
    # _raw_backing: GC가 raw를 수집하지 않도록 참조 유지
    views = [
        memoryview(raw)[pad + i * hdr : pad + (i + 1) * hdr]
        for i in range(n)
    ]
    return views, raw  # caller가 raw 참조 유지 필요

4.3 _inflight_io_count 관리

현재 _read_slot_header는 슬롯마다 lock 2회 (inc/dec). 배치 경로는 lock 1회 inc → wait_iouring 완료 후 1회 dec.

with self._lock:
    self._inflight_io_count += 1  # 1회
try:
    batch_id = raw_dev.batched_read(offsets, views, total_lens)
    raw_dev.wait_iouring(batch_id)
finally:
    with self._lock:
        self._inflight_io_count -= 1
        self._last_io_ts = time.monotonic()

---

5. 구현 완료 내역 (2026-06-08)

브랜치 정보

• worktree: /home/ny/workspace/LMCache-v1-validate
• branch: perf/validate-batched-read
• base: ankit-sam/raw_iouring_cmd 최신 커밋 (21bad9f4 — PR #3274)
• 상태: 미커밋 (PR #3274 머지 후 dev 리베이스 예정)

변경 파일

파일	변경 내용
lmcache/v1/storage_backend/raw_block/core.py	_read_slot_headers_batched 헬퍼 신규 추가 + _validate_loaded_entries 분기 수정
tests/v1/storage_backend/test_raw_block_core.py	헬퍼 2개 + 단위 테스트 7개 추가

_read_slot_headers_batched 핵심 구현

_read_slot_header 바로 아래에 삽입. aligned buffer 전략 C (단일 bytearray + ctypes pad 계산):

def _read_slot_headers_batched(
    self, offsets: list[int]
) -> list[Optional[tuple[int, int]]]:
    n = len(offsets)
    if n == 0:
        return []

    align = self.block_align
    hdr = self.header_bytes
    raw_buf = bytearray(n * hdr + align - 1)
    addr = ctypes.addressof(ctypes.c_byte.from_buffer(raw_buf))
    pad = (-addr) % align
    views = [
        memoryview(raw_buf)[pad + i * hdr : pad + (i + 1) * hdr]
        for i in range(n)
    ]

    with self._lock:
        self._inflight_io_count += 1
    try:
        raw_dev = self._rawdev()
        batch_id = raw_dev.batched_read(offsets, views, [hdr] * n)
        raw_dev.wait_iouring(batch_id)
    except Exception:
        return [None] * n
    finally:
        with self._lock:
            self._inflight_io_count -= 1
            self._last_io_ts = time.monotonic()

    return [self._decode_slot_header(bytes(v)) for v in views]

• _rawdev() 한 번만 호출 (기존 설계안의 2회 → 1회로 수정)
• _decode_slot_header는 bytes 인자 수용 확인 완료 (§7.1 해소)

_validate_loaded_entries 분기

def _validate_loaded_entries(self) -> None:
    with self._lock:
        items = list(self._index.items())

    if self.io_engine == "io_uring" and not self.use_uring_cmd and len(items) > 1:
        offsets = [int(e.offset) for _, e in items]
        hdrs: list[Optional[tuple[int, int]]] = self._read_slot_headers_batched(offsets)
    else:
        hdrs = [self._read_slot_header(int(e.offset)) for _, e in items]

    # ... (검증 로직 동일)

• not self.use_uring_cmd 조건 추가: use_uring_cmd 경로는 _read_uring_cmd_buffers로 직렬 처리 — batched_read 미지원
• 검증 루프는 분기 없이 공유 (중복 제거)

단위 테스트 7개

_make_mocked_core + _populate_index 헬퍼로 Rust extension 없이 테스트:

테스트명	검증 내용
test_read_slot_headers_batched_empty	offsets=[] → 즉시 []
test_read_slot_headers_batched_io_exception_returns_all_none	batched_read 예외 → [None]*n
test_read_slot_headers_batched_decodes_valid_headers	헤더 디코딩 + wait_iouring 호출 확인
test_validate_loaded_entries_iouring_uses_batched_read	io_uring + len>1 → batched 경로
test_validate_loaded_entries_posix_uses_sequential	posix → sequential 경로
test_validate_loaded_entries_single_item_skips_batched	io_uring + len=1 → sequential
test_validate_loaded_entries_uring_cmd_uses_sequential	use_uring_cmd=True → sequential

---

6. 성능 검증 계획 및 결과

검증을 4단계로 나눈다. 단계 1–3은 완료, 단계 4(실 NVMe)는 PR #3274 머지 + 실 HW 확보 후 예정.

단계	내용	상태
1	단위 테스트 — dispatch 정확성	✅ 완료
2	Rust 소스 분석 — 병렬성 보장 근거	✅ 완료
3	벤치마크 (tmpfile) — syscall/GIL/lock 오버헤드 실측	✅ 완료
4	실장 테스트 (실 NVMe) — device-level 병렬성 실증	⏳ PR #3274 머지 후

---

단계 1 — 단위 테스트 ✅ 완료

목적: batched/sequential 경로가 올바르게 분기되는지, 각 경계 조건(예외·빈 입력·단건)을 정확히 처리하는지 확인. I/O 정확성 검증이지 성능 검증은 아님.

방법: _rawdev()를 MagicMock으로 교체(monkeypatch) → 실제 Rust extension 없이 Python 로직만 테스트.

통과 항목:

테스트	무엇을 확인하나
test_read_slot_headers_batched_empty	offsets=[] → 즉시 [] 반환, I/O 호출 없음
test_read_slot_headers_batched_io_exception_returns_all_none	batched_read 예외 → [None]*n (부분 성공 없음)
test_read_slot_headers_batched_decodes_valid_headers	버퍼에 쓰인 헤더 bytes를 올바르게 디코딩, wait_iouring 1회 호출
test_validate_loaded_entries_iouring_uses_batched_read	io_engine="io_uring", use_uring_cmd=False, len>1 → batched 경로 진입
test_validate_loaded_entries_posix_uses_sequential	io_engine="posix" → sequential 경로 유지
test_validate_loaded_entries_single_item_skips_batched	io_uring + len=1 → sequential (batched 이점 없음)
test_validate_loaded_entries_uring_cmd_uses_sequential	use_uring_cmd=True → sequential (NVMe passthrough 경로)

전체 CI 스위트 통과 (pytest -xvs + pre-commit run --all-files).

---

단계 2 — Rust 소스 분석 ✅ 완료

목적: batched_read가 실제로 N개 I/O를 동시에 커널에 전달하는지, 아니면 내부에서 직렬화하는지 확인.

방법: rust/raw_block/src/lib.rs 직접 분석.

2-A. Python → Rust: batched_read 호출 경로

// lib.rs:2667 — GIL 해제 후 N개 IoSubmission 큐잉
let res = py.allow_threads(move || {
    for i in 0..n {
        // 버퍼 ptr 검증 (use_odirect=True일 때만 정렬 체크)
        let sub = IoSubmission { fd, offset: offsets[i], len: total_lens[i],
                                 ptr_addr: ptrs[i], is_write: false, batch_id, .. };
        {
            let mut q = queue.lock().unwrap();
            q.push(sub);          // ← 큐에 push (아직 커널 미전달)
        }
        batch_ready.signal_producer();  // ← worker thread 깨우기
    }
    Ok(())
});

• GIL이 해제된 상태에서 루프 실행 → Python 레벨 직렬화 없음
• 각 push 후 signal을 보내지만, worker가 즉시 깨어나더라도 큐는 이미 여러 항목이 쌓여 있음 (Rust 루프가 Python GIL 재획득 없이 연속 실행)

2-B. worker thread: 큐 전체 드레인 후 단일 submit

// lib.rs:1559 — worker thread 루프 핵심
let mut batch: Vec<IoSubmission> = std::mem::take(&mut *q);  // 큐 전체를 한번에 가져옴
let batch_len = batch.len();
let available = ring_size - ring_clone.submission_len();
let to_submit_count = std::cmp::min(available, batch_len);

// N개 SQE 빌드 후 한 번의 submit()
for sub in batch.iter().take(to_submit_count) {
    build_and_submit_sqe(&ring_clone, sub, user_data);
}
ring.submitter().submit()  // ← 단 1회 syscall로 N SQE 커널 전달

std::mem::take가 핵심: 큐 전체를 원자적으로 비워 가져온 뒤 한 번의 submit() syscall로 N개 SQE를 커널에 동시 전달한다. 커널은 NVMe NCQ(Native Command Queuing) 또는 FDP 명령 큐를 통해 이 N개 요청을 device에 병렬로 내린다.

2-C. aligned buffer 요건

// lib.rs:2685-2697
if use_odirect {
    if (offset as usize) % alignment != 0 { return Err(PyValueError) }
    if total_len % alignment != 0         { return Err(PyValueError) }
    if ptrs[i] % alignment != 0           { return Err(PyValueError) }
}

• use_odirect=False: 정렬 검사 없음 → tmpfile 환경에서도 aligned buffer 전략이 불필요하지만 유지해도 무해
• use_odirect=True (실 NVMe O_DIRECT): 구현의 (-addr) % align pad 계산이 이 검사를 통과시킴

2-D. 결론

batched_read는 진짜 병렬 I/O다. N개 SQE가 동시에 커널 submission queue에 들어가고, NVMe controller는 이를 병렬 처리한다. Python 레벨이나 Rust 워커 레벨에서 직렬화하는 구간 없음.

---

단계 3 — 벤치마크 (tmpfile, page cache) ✅ 완료 (2026-06-08)

환경

항목	값
OS	Linux 6.14.0-33-generic
파일	tmpfs 임시 파일 (/tmp)
io_engine	io_uring (use_odirect=False, iouring_queue_depth=256)
I/O latency	≈ 0 (page cache hit)
Rust extension	PR #3274 브랜치 소스 → maturin develop --release 빌드
Python	3.12 (lmcache worktree editable install)
스크립트	benchmarks/storage_backend_io/bench_validate_batched.py (worktree)
반복	7 iter / slot 수, warm-up 없음

이 조건에서 측정되는 것은 device I/O latency가 아닌 Python/Rust 레이어 오버헤드:

• _lock acquire/release 횟수: sequential 2N회 vs batched 2회
• Python 함수 호출 오버헤드: sequential N번 vs batched 1번
• io_uring SQE 제출 방식: sequential N번 submit() vs batched 1번 submit()
• GIL 해제 구간: sequential 매 호출마다 짧게 vs batched 1회 길게

측정 방법

sequential: T0 → for off in offsets: _read_slot_header(off) → T1
batched:    T0 → _read_slot_headers_batched(offsets) → T1

각 iter마다 새 RawBlockCore 인스턴스를 생성 (startup 시뮬레이션). 체크포인트는 POSIX 경로로 사전 생성 후 재사용.

원시 결과 — slots=100 (7 iter)

iter	sequential (ms)	batched (ms)	speedup
1	9.16	0.73	12.6×
2	2.87	0.65	4.4×
3	5.78	0.40	14.5×
4	4.02	0.68	5.9×
5	5.91	1.15	5.2×
6	5.44	0.99	5.5×
7	4.36	1.18	3.7×
mean	5.36	0.83	6.5×
stdev	±2.00	±0.29

원시 결과 — slots=200 (7 iter)

iter	sequential (ms)	batched (ms)	speedup
1	11.90	1.26	9.4×
2	12.56	2.17	5.8×
3	9.77	1.63	6.0×
4	1.61 †	1.64	1.0×
5	8.41	1.49	5.7×
6	7.79	2.16	3.6×
7	9.35	2.01	4.7×
mean	8.77	1.77	5.0×
stdev	±3.60	±0.35

† iter 4 sequential 이상치(1.61ms): OS 스케줄러 lucky-run 또는 페이지캐시 pre-fetch로 추정.

원시 결과 — slots=500 (7 iter)

iter	sequential (ms)	batched (ms)	speedup
1	5.32	3.38	1.6×
2	6.35	3.67	1.7×
3	24.41	1.19	20.5×
4	24.35	4.34	5.6×
5	24.19	4.76	5.1×
6	25.46	1.15	22.2×
7	8.52	2.27	3.8×
mean	16.94	2.97	5.7×
stdev	±9.61	±1.46

원시 결과 — slots=1000 (7 iter)

iter	sequential (ms)	batched (ms)	speedup
1	30.51	6.34	4.8×
2	23.42	5.48	4.3×
3	36.57	7.01	5.2×
4	41.21	2.05	20.2×
5	35.28	3.46	10.2×
6	19.06	4.97	3.8×
7	21.91	45.67 ‡	0.5×
mean (전체)	29.71	10.71	2.8×
mean (‡ 제외)	29.71	5.22	5.7×
stdev	±8.41	±15.51 (‡ 포함) / ±1.68 (제외)

‡ iter 7 batched 45.67ms: io_uring worker 스케줄 지연(OS 레벨)으로 추정. queue depth=256 < N=1000이므로 ceil(1000/256)=4회 submit 라운드 필요 → 라운드 사이 scheduler preemption에 취약. 나머지 6회 평균은 5.22ms.

요약 표

slots	seq mean (ms)	bat mean (ms)	speedup (대표)	seq stdev	bat stdev
100	5.4	0.83	6.5×	±2.0	±0.29
200	8.8	1.77	5.0×	±3.6	±0.35
500	16.9	2.97	5.7×	±9.6	±1.46
1000	29.7	5.22 ‡제외	5.7×	±8.4	±1.68 ‡제외

분석

1. sequential은 N에 선형, batched는 sub-linear

sequential: 100→200→500→1000슬롯 = 5.4→8.8→16.9→29.7ms. N이 10배 늘면 시간도 ~5.5배 증가 (N-linear 확인).
batched: 0.83→1.77→2.97→5.22ms. N이 10배 늘어도 ~6.3배 증가. queue depth=256 범위 내에서는 N개를 단일 submit()으로 처리하므로 N에 거의 무감.

2. sequential 분산 크고, batched는 안정적

sequential stdev가 mean의 3060%에 달한다. N번의 lock acquire 사이에 OS가 preempt하거나 다른 스레드와 경합하면 그 지연이 N번 누적되기 때문. batched는 lock 1회 + submit 1회로 jitter 누적 지점 자체가 없어 stdev가 mean의 1035%로 낮다.

3. page cache에서도 5-6× 나오는 이유

실제 device I/O latency가 0인 최악의 조건(batched에 가장 불리)에서도 5-6×가 나오는 이유:

• lock 2N→2: N=1000이면 2,000회 → 2회
• Python _read_slot_header dispatch N번 제거
• io_uring worker submit() N번 → 1번(또는 ceil(N/256)번)
• GIL 해제를 1회 길게 유지 vs N회 짧게 반복의 차이

4. 1000슬롯 이상치 (‡) 원인

queue depth 256 < N=1000이면 Rust worker가 4라운드로 나눠 submit한다. 라운드 사이에 OS가 worker thread를 preempt하면 수십ms 지연이 발생한다. 실 NVMe 환경에서는 device I/O time이 preempt window를 가리기 때문에 이 현상이 훨씬 드물어진다. 필요시 iouring_queue_depth를 N에 맞게 키우면 단일 라운드로 처리 가능.

5. 이 측정의 한계

page cache 조건은 "device I/O가 없는 최악"이다. 실 NVMe에서는 sequential이 ~100µs/slot이 추가로 누적되지만 batched는 병렬 처리로 그 대부분을 흡수한다. 따라서 실 NVMe에서는 아래 단계 4 예측값대로 speedup이 훨씬 커진다.

---

단계 4 — 실장 테스트 (실 NVMe) ⏳ 예정

조건: PR #3274 머지 + dev 리베이스 완료 + 실 NVMe HW 확보

목적

page cache를 제거하고 실제 device latency 하에서 병렬성 효과를 실증한다. 특히 HC-SSD(15~30TB) 대용량 환경에서 startup 지연이 실제로 줄어드는지 확인한다.

환경 요구사항

항목	요건
NVMe	Samsung HC-SSD 또는 동급 (IOPS 1M+, latency ~100µs)
파일시스템	O_DIRECT 지원 (use_odirect=True) 또는 loop device
io_uring	kernel 5.10+ (io_uring_cmd은 6.x 권장)
슬롯 수	최소 1,000개 이상 (HC-SSD 기준 ~3,750개)

준비 절차

# 1. 대량 슬롯 생성 및 체크포인트
python -c "
from tests.v1.storage_backend.raw_block_test_utils import *
from lmcache.v1.storage_backend.raw_block import RawBlockCore, encode_object_key
from lmcache.v1.distributed.api import ObjectKey

cfg = RawBlockCoreConfig(
    device_path='/dev/nvme0n1',   # 또는 loop device
    capacity_bytes=16 * 1024**3,  # 16 GB
    slot_bytes=4 * 1024**2,       # 4 MB
    use_odirect=True,
    io_engine='io_uring',
    iouring_queue_depth=256,
    ...
)
core = RawBlockCore(cfg, key_namespace='object')
# N=3000 슬롯 write...
core.checkpoint_now()
core.close()
"

# 2. page cache 제거 (root 필요)
sync; echo 3 > /proc/sys/vm/drop_caches

# 3. 벤치마크 실행 (--drop-caches로 매 iter마다 제거)
python benchmarks/storage_backend_io/bench_validate_batched.py \
    --slots 3000 --iters 5 --drop-caches

정확성 검증 (필수 병행)

batched와 sequential이 동일한 to_drop 집합을 만드는지 확인. 일부 슬롯을 의도적으로 corrupt한 뒤 양 경로의 결과를 비교:

# 의도적 corrupt (raw write로 일부 슬롯 헤더 덮어쓰기)
with open('/dev/nvme0n1', 'r+b') as f:
    f.seek(corrupt_slot_offset)
    f.write(b'\x00' * 4096)

# sequential 경로로 to_drop 수집
core_seq = RawBlockCore(cfg_posix, ...)  # io_engine="posix"
dropped_seq = _collect_dropped(core_seq)

# batched 경로로 to_drop 수집
core_bat = RawBlockCore(cfg_uring, ...)  # io_engine="io_uring"
dropped_bat = _collect_dropped(core_bat)

assert dropped_seq == dropped_bat, f"mismatch: {dropped_seq ^ dropped_bat}"

성공 기준

항목	기준
speedup (N=3,000, cold NVMe)	≥ 30× (이론 ~94× 대비 보수적 기준)
정확성	sequential과 batched의 to_drop 집합 동일
예외 없음	batched_read에서 PyValueError/PyRuntimeError 없음

이론 예측값

HC-SSD 파라미터 (Samsung 실측 기준):

파라미터	값
NVMe random read latency	100 µs
IOPS	1,000,000
io_uring queue depth	256
슬롯 수 (15 TB / 4 MB)	3,750

sequential:  3,750 × 100 µs = 375 ms
batched:     ceil(3,750 / 256) × (100 µs + submit overhead) ≈ 15 × ~270 µs ≈ 4 ms
             (batch당 256개 병렬 → 256개가 동시에 완료, 다음 batch 시작)
speedup:     375 / 4 ≈ 94×

iouring_queue_depth=256이면 한 submit()에 최대 256 SQE. 3,750개는 ceil(3750/256)=15번 배치로 처리. 각 배치의 완료 시간은 device의 max latency (256개 중 가장 느린 것) 기준이므로 실제 ~1배 latency에 가까움.

---

7. 미결 사항 (해소 현황)

#	항목	상태
1	_decode_slot_header — bytes 인자 호환성	✅ 해소 — bytes(v) 통과 확인
2	use_odirect=True 정렬 오류 시 예외 타입	✅ 해소 — Rust가 PyValueError 반환, except Exception으로 모두 캐치
3	대용량 N의 메모리 사용	✅ 해소 — N=10,000, hdr=4096 → ~40MB, startup 1회성 할당 무방
4	batched_read 실제 시그니처 확인	✅ 해소 — (offsets, buffers, total_lens) 확인 완료
5	use_uring_cmd 경로 처리	✅ 해소 — not self.use_uring_cmd 조건 추가로 직렬 경로 유지

---

8. PR 구조

• 단일 PR: _validate_loaded_entries batched_read 병렬화
• base: dev (post #3274)
• 크기: core.py 변경 ~60 LOC, 테스트 ~80 LOC (헬퍼 포함)
• 제목: [Perf][RawBlock] Parallelize startup header validation via io_uring batched_read
• 제출 조건: PR #3274 머지 후 dev 리베이스 → /pre-pr-check → /create-pr

---

작성: 2026-06-06 | 구현 완료 + 검증 추가: 2026-06-08