Skip to content

docs

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

docs

README.md

AccelerateMVCC — 현황 & 로드맵

디스크 기반 DBMS(InnoDB/MySQL)의 MVCC를 가속하는 인메모리 보조 인덱스. 하태성의 2023년 졸업프로젝트를 단독으로 재개 (현재는 졸업용이 아닌 개인 프로젝트). 이 문서는 진행과 함께 갱신되는 리빙 도큐먼트입니다.

  • 최종 수정: 2026-07-02 (세션 17 — Phase 3 완료: 논문 Tier 1–3 반영·vDriver head-to-head·한글판 재생성)
  • 상세 포렌식·이슈 트래커 → findings.md
  • 세션별 진행 로그 → progress-log.md · 논문 작업 현황 → paper-review-todo.md

1. 문제 & 목표

문제. HTAP 워크로드에서 long-lived transaction이 존재하면 InnoDB의 version chain(undo log 체인)이 길어진다. 최신 가시 버전을 찾으려 긴 체인을 따라가며 다수의 undo log page를 buffer pool로 읽어야 하고, 이는 ① I/O 비용, ② buffer pool 오염, ③ GC와 long transaction의 경합을 유발한다. 졸프 프로파일링에서 long transaction 존재 시 row_search_mvcc 계열이 CPU의 ~45% 를 차지함을 확인.

접근. undo log의 메타데이터 + 소형 in-page 행 image를 인메모리 구조에 보관하여, 가시 버전을 빠르게 찾는 데서 나아가 undo walk를 건너뛰고 결과를 직접 serve하는 derived·ephemeral·non-authoritative 캐시를 만든다(dead-zone 검출은 vDriver[SIGMOD'20]에서 차용·각색, DIVA는 SIGMOD'22의 관련 연구). 과회수→wrong serve 위험은 conservative-superset 설계로 구조적으로 배제(no-wrong-serve).

완성 기준(범위).

  • 1차 목표: A + B + C
  • 최종 목표: A + B + C + D
  • 전 과정을 문서/리포트(필요 시 도표·차트)로 정리.

2. 아키텍처

flowchart TD
  R["레코드 (table_id, index)"] --> K["Cuckoo Hash · Kuku"]
  K -->|"value = header 포인터"| H["interval_list_header"]
  H --> E0["epoch_node N"]
  E0 --> E1["epoch_node N-1 ..."]
  E0 --> U["undo_entry 체인<br/>(trx_id, space/page/offset)"]
  TM["Trx_manager<br/>active_trx_list snapshot"] --> DZ["deadzone"]
  E0 -. "epoch_table->insert" .-> ET["Epoch_table"]
  DZ --> ET
  ET -. "garbage_collect (pruning)" .-> E1
Loading
구성요소 파일 역할
Cuckoo Hash (Kuku) accelerateMVCC.cpp 레코드(table_id, index) → interval_list_header 포인터 O(1) 매핑. Kuku item의 value 슬롯에 헤더 주소를 저장
interval_list / epoch_node interval_list.h epoch(=trx_id/EPOCH_SIZE) 단위로 묶인 version chain. undo_entry_node = (trx_id, space/page/offset)
Trx_manager trxManager.h trx_id 발급, active transaction snapshot(read view) 제공
Epoch_table epoch_table.h epoch 인덱싱(lock-free 리스트) + deadzone pruning 기반 interval GC (Steam 스타일)

상수: EPOCH_SIZE=100, EPOCH_TABLE_SIZE=100, NUM_DEADZONE=50 (common.h, epoch_table.h).

통합(Stage D)에서: 위 코어가 mysqld 안에서 돈다. InnoDB undo가 off-latch drainer를 통해 캐시로 채워지고(populate), reader는 consistent-read 시점에 consult(GC-safe lineage walk)로 가시 버전을 찾아 캐시 레코드를 서빙한다. deadzone GC는 standalone Trx_manager가 아니라 InnoDB의 active read-view (pushed clock + leaf-domain registry)로 재구동된다 — 상세 design-D5-gc.md.

3. 현재 상태 (2026-07-02 기준)

  • 개발 완전 완료 (Stage A–D, 세션 13) + Phase 3 완료 (세션 14–17) — 멀티런/error-bar(gate ①)·raw-log 아카이브(gate ②)·TPC-C(④)·no-wrong-serve semi-formal 논증(design-D7)·memory-scope 결정(design-D8)·논문 영문판(canonical) §1–§8 + 3자 리뷰 리비전 + Tier 3 측정 반영 + 한글판 재생성 전부 완료. 남은 것 = 사용자 논문 검토 + (선택) LaTeX 조판. 논문 작업의 재개 지점은 paper-review-todo.md.
  • 헤드라인(멀티런): held deep read serve 64M ~210×(중앙값, vanilla N=6 baseline; 2/8 degrade tail은 정확한 walk로) · 메모리 비율 LLT 나이에 선형 19.5×/40.5×/81.9× · effective ~29×(GC-off; GC-on은 128M까지 2.6–3.3× 생존) · mid-table 곡선(용량 sizing 시 50k/200k/500k = 280×/189×/93×) · TPC-C serve byte-정확 (regime 경계 = base-page I/O 지배, 진단 = phys m0≈m1) · vDriver same-hardware head-to-head(체인 walk vanilla 0→1000 linear vs vDriver ≤6 bounded, 둘 다 정확). 전 측정 construct_BAD=0.
  • 1차 목표 A+B+C ✅ · 최종 D ✅ — 실제 InnoDB 통합: populate → consult → authoritative serve → 성능 payoff.
  • ⑤ purge-view GC(메모리 유계): ⑤a-2 ✅ — deadzone GC가 통합 mysqld에서 InnoDB read-view로 구동돼 실제로 회수(정확·효율·race/UAF 0·메모리 유계). serve는 안전망(5-2b C1·C2) 위에서 GC와 함께 정확.
  • ⑤b-lite ✅ · C3(mode-1 serve-only 안전 출하) ✅ — gc_generation 2nd firewall(race detector·mode-1 한정)
    • 1-in-N walk-audit(observe-only). construct_BAD=0 도처(mode-2 soak 100만+ · mode-1 ship 4-way AND green).
  • ⑥ chain-sever → drain-cap으로 안정화 — GC storm이 navigation 경로 회수 시 consult가 정답 walk로 degrade였으나 (construct_BAD=0 항상), GC-tuning drain-cap(ACCEL_DRAIN_CAP≈1000)이 ⑥를 fragile(1/4 붕괴)→stable(0 붕괴)로 (design-D5-gc §13). α(FG cooperative reclaim)는 측정상 이득 0.
  • Phase 2 완료 ✅ (세션 11) — ⓠ3 중심 헤드라인(in-middle deadzone이 LLT 하 tail-only 압도)이 실 InnoDB write-heavy+LLT+HTAP에서 생존·확정(캐시 bounded ~6–9k, HLL은 LLT에 선형 → 비율 20×/40×/63×@15/30/60s, 승리는 동시 read-view 리더 gap 요구=대조군 0.9×, 5-3 후퇴 트리거 안 됨) + ⓠ5(effective ~34× I/O-bound) + ⓝ6(LOB 안전 제외=Limitation) + 키 일반화·savepoint·full-mysqld ASan 전부 construct_BAD=0. 상세 phase2-q3-llt.md. 다음 = Phase 3(논문 한글+영문·multi-run/error-bar·로그 보존·패치 vendor·cold-key 결정). 세션별 progress-log.md, 마스터 트래커 open-items.md §0d.
트랙 상태
코어 (A·B·동시성 1a~1c) ✅ marked-pointer + per-traversal EBR + 전용 BG GC + FG cooperative unlink + tight-bound deadzone
Stage C 실험 (HTAP/long-txn) ✅ 60s LLT 하 deadzone vs tail-only chain-CDF (design-gc.md §11)
D-populate (쓰기) ✅ off-latch drainer가 InnoDB undo를 캐시로 적재 (write tput = vanilla)
D-consult (읽기) ✅ GC-safe lineage walk — 가시 버전 byte-정확 (construct_BAD=0)
D-serve (authoritative) ✅ mode-2 verify-serve(GC 위 49만 construct_BAD=0) + C3 mode-1 안전 출하(gen-gate+audit)
⑥ 성능 payoff ✅ held-reader deep read ~190× (64M ~4.7s·4G 0.27s); drain-cap(cap≤1000)으로 GC-on서 stable(0 degrade·construct_BAD=0·메모리 ∝window)
⑤ purge-view GC (메모리 유계) ✅ ⑤a-2 통합 GC-on + FG+BG 스테이지 완료(α null·drain-cap stabilizer; β navigation은 구조적 불가) (design-D5-gc.md §13)

4. 로드맵

A. 빌드 부활 ✅ (완료 2026-06-18)

  • DoD: WSL2에서 AccelerateMVCC + test_with_google 컴파일 성공, 기존 테스트/벤치 실행 확인. → 달성(빌드·실행 OK, 안전 테스트 30/31 통과).
  • 작업: WSL2 셋업 → CMake 손상 수정 → include 케이스 정리 → Kuku를 소스에서 빌드·링크 → build 산출물 .gitignore 처리.

B. 프로토타입 완성·검증 ✅ (단일스레드 완료 2026-06-18)

  • DoD: GC/deadzone 버그 수정, insert/search/GC/deadzone 정확성 단위테스트 통과(가시성 + deadzone pruning). → 달성: correctness_test.cpp 6개 통과 + ASAN 클린 + 기존 단일스레드 GC 테스트 통과.
  • 완료: snapshot 보존(#7·#8), deadzone 초기화/가드(#4), GC sweep 메모리안전(#5·#6), garbage_collect 완료/return, list 방향 통일(Q1), search 최신 가시버전 반환.
  • 추후(동시성/하드닝): 멀티스레드 GC reclamation, 빈 snapshot fast-path, dummy-list 누수. (deadzone 출처 = vDriver 재구현, findings 참조)

C. 실험·결과 산출 ✅ (완료 2026-06-20)

  • DoD: HTAP(OLTP+OLAP 병렬) / long-transaction 워크로드에서 baseline 대비 search 비용·GC 효과를 수치 + 차트로 제시. → 달성.
  • 결과(상세 design-gc.md §11): vDriver 하니스를 stage_c_bench.cpp로 이식(Zipfian writer + OLTP reader + 60s LLT + Guard-safe chain 샘플러). baseline = 프로토타입 내 tail-only GC 모드(InnoDB purge 모델). 60s LLT 하 deadzone hot-chain max 155 vs tail-only 845,977(~5,500×), read tput 1.36M/s vs 487/s(~2,800×), retire 22.4M vs 277. skew 0.8/1.2/1.6 전반 견고(~8,000×). FG cooperative unlink는 read-path +30%. 전 run LLT visibility OK + ASan/TSan clean. version-chain length CDF 차트 생성.

D. MySQL/InnoDB 통합 ✅ (2026-06)

  • DoD: 실제 InnoDB 소스에 가속 인덱스 연결, held-snapshot 깊은 읽기에서 vanilla 대비 효과 측정.
  • 달성: populate(drainer) → consult(lineage walk, construct_BAD=0) → authoritative serve → ⑥ payoff (held-reader deep read 64M 98s→0.16s[GC-off]/0.45s[GC-on], 190775×). 상세 design-D.md· design-D4b-shadow.md.

⑤ purge-view GC + serve under GC ✅ (GC-side 완료)

  • 목표: 캐시 메모리를 working-set으로 유계(GC) + 그 위에서 정확하게 서빙. 설계 design-D5-gc.md.
  • ⑤a-2 ✅ deadzone GC를 InnoDB read-view로 구동(통합서 정확·효율·메모리 유계) · 5-2b ✅ C1(over-prune 오라클)· C2(mode-2 verify-serve)·C3(mode-1 안전 출하: gen-gate+walk-audit) 완료 · ⑤b-lite ✅ · FG+BG 스테이지 ✅ (α 측정상 null · drain-cap이 ⑥ stabilizer; β 구조적 불가). 상세 design-D5-gc.md §9~§13.

Phase 2 — 워크로드 폭·correctness breadth ✅ (세션 11)

  • ⓠ3 in-middle 헤드라인 실 InnoDB 생존(20×/40×/63×@LLT) · ⓠ5 effective speedup(~34× I/O-bound, held reader HIT ~100%) · ⓝ6 LOB/off-page/virtual 안전 제외(Limitation) · composite/string-PK·secondary-index·savepoint correctness · full-mysqld ASan CLEAN. 전부 construct_BAD=0. 상세 phase2-q3-llt.md.

Phase 3 (테스트·정리·논문) ✅ (세션 13–17, 2026-06-29 ~ 07-02)

  • 신뢰성 게이트: ① multi-run/error-bar(q11/q15/q3/q5 멀티런, 전 run construct_BAD=0) · ② raw-log 아카이브 (integration/results/) · ③ memory-scope 결정(design-D8) · ④ TPC-C (phase3-tpcc.md) · ⑤ no-wrong-serve semi-formal 논증(design-D7).
  • 논문: 영문판(canonical) §1–§8 + figure 5종 → 3자 리뷰(6 agents, "Major revision") → Tier 1+2 리비전 → Tier 3 측정 반영(⭐vDriver head-to-head·GC-on crossover·N=6 baseline(290→210×)· mid-table regime 곡선·CH shape) → References 확정 → 한글판 재생성. 현황·이력 = paper-review-todo.md.
  • 남은 것: 사용자 논문 검토 + (선택) LaTeX 조판. 마스터 트래커 open-items.md §0g.

5. 개발 환경

  • 결정: WSL2 (Ubuntu, root 운용). C(sysbench/perf/MySQL)·D(InnoDB)가 사실상 리눅스 전용이고, 코어 코드는 표준 C++17/20이라 리눅스에서 그대로 빌드된다.
  • 현 상태: gcc-13/15·cmake 4.2·sysbench 설치됨. standalone 빌드 ~/acc-build*, MySQL 8.4.10 소스/빌드 ~/mysql-server/~/mysql-build(gcc-13). 빌드·테스트·측정 레시피는 NEXT-SESSION.md와 integration/scripts/가 canonical.

6. 문서 인덱스

논문 (최종 산출물)

상태·핸드오프 (living)

  • README.md (이 문서) — 개요·아키텍처·로드맵·상태 (front page)
  • NEXT-SESSION.md — 재개 가이드: 현재 위치·빌드/검증/측정 레시피
  • open-items.md — 마스터 트래커(deferred·threats-to-validity; 최신 현황 §0g→§0f→… 역순)
  • progress-log.md — 세션별 진행 로그(시간순 서사; 세션 14+는 open-items·paper-review-todo가 상세)

측정 기록 (Phase 2–3)

설계 근거 (design-*)

기타

  • REPORT.md — A~D 통합 보고서(논문의 substrate; 논문 확정 내용이 우선)
  • findings.md — 초기 포렌식·이슈 트래커(역사 기록)
  • 원자료: Google Drive AccelerateMVCC 폴더 (졸프 문서, 미팅 영상, 논문 정리, 테스트 결과)