diff options
Diffstat (limited to 'docs/research/073-single-file-persistent-tree.md')
| -rw-r--r-- | docs/research/073-single-file-persistent-tree.md | 126 |
1 files changed, 126 insertions, 0 deletions
diff --git a/docs/research/073-single-file-persistent-tree.md b/docs/research/073-single-file-persistent-tree.md new file mode 100644 index 0000000..e2a2ee9 --- /dev/null +++ b/docs/research/073-single-file-persistent-tree.md @@ -0,0 +1,126 @@ +# 073 — 한 파일 안의 영속 트리: 편집 비용을 문서 크기에서 경로 길이로 + +2026-09-25. 선택형 저장소 `store-tree.c`를 추가했다. 기본 빌드와 기본 저장 형식은 바뀌지 않았다. + +착수 기준: + +- 바꿀 결정: 문서를 "키 하나 = 연속 바이트 파일 하나"로 두는 관례를 계속 전제로 할지, + 모든 문서를 한 파일의 불변·구조 공유 트리로 둘지. +- 남은 질문: 삽입·삭제에서도 문서 전체를 다시 쓰지 않고 내구성 있게 커밋할 수 있는가? + 기존 `store.h` 계약과 호스트·충돌·고장 검사를 그대로 통과하는가? 작은 문서·읽기·코드 비용은? +- 최소 확인: 기존 계약을 그대로 구현한 저장소 하나를 만들어 기존 검사와 새 고장·오라클 검사를 + 통과시키고, 같은 SD 카드에서 세 저장소를 같은 편집으로 비교한다. +- 중단 기준: 기존 계약 검사를 통과하지 못하거나, 1 MiB 문서의 삽입 저장이 기본 대비 크게 + 줄지 않거나, 작은 문서가 눈에 띄게 나빠지면 닫는다. + +## 의심한 관례 + +| 관례 | 이 저장소에서 바꾼 것 | +|---|---| +| 값 = 연속 바이트 배열 | 값 = 불변 익스텐트(최대 4 KiB)의 순서열. 연속 배열은 필요한 소비자에게만 만든다 | +| 새 버전 = 새 사본 | 새 버전 = 바뀐 leaf와 그 조상 경로만 새로 쓰고 나머지는 이전 버전과 공유 | +| 저장 단위 = 키마다 파일, 목록 = 디렉터리 | 저장소 = 추가 전용 파일 하나. 문서 목록(카탈로그)도 같은 트리 구조의 레코드열 | +| 읽기도 잠근다 | 읽기는 잠금 없이 공개된 불변 접두부를 매핑한다 | +| 호스트가 저장 형식을 안다 | TUI가 `obj-` 파일명을 직접 읽던 코드를 `pure_store_keys`로 옮김 | + +## 구조 + +- 파일: `[head 슬롯 0][head 슬롯 1][커밋된 노드…]`. head는 순번·공개 끝 위치·카탈로그 루트· + 압축 후 크기와 찢김 검출용 체크섬을 가진다. +- leaf는 원시 문서 바이트다. 여러 leaf로 나눌 때는 균형 분할해 각 leaf가 2 KiB 이상이다. + branch는 `PTB1`, 자식 수·높이, 자식별 (참조, 하위 바이트 수) 최대 32개다. 모든 leaf의 깊이가 같다. +- 편집 `splice(offset, remove, insert)`는 영향받은 leaf와 조상만 새로 만든다. 새로 만든 노드가 + 기준보다 작으면 이웃과 병합하고, 루트의 단일 자식은 접는다. +- 카탈로그는 키 순서의 96 B 레코드(키 64 B, 루트, 크기, 리비전)다. 같은 편집 코드로 갱신하고 + 이진 탐색으로 찾는다. 문서 하나를 바꾸면 카탈로그도 한 경로만 다시 쓴다. +- 커밋: 새 노드 추가 → `fsync` → 오래된 head 슬롯에 새 head → `fsync`. OK는 두 번째 동기화 뒤다. + 복구는 유효한 슬롯 중 순번이 큰 쪽을 쓰고, 그 끝 뒤의 바이트는 확인받지 않은 커밋이라 + 다음 writer가 잘라낸다. 쓰기 중 고장 단계는 기존 저장소와 같은 결과(오류 또는 결과 불명)를 낸다. +- 압축: 공개 크기의 증가가 `4 × 압축 후 크기 + 1 MiB`를 넘으면 도달 가능한 노드만 새 파일에 쓰고 + 교체한다. 이미 읽은 쪽은 이전 파일의 매핑을 계속 사용한다. +- 읽기: 한 leaf 안의 범위는 파일을 그대로 매핑한다(기본 저장소와 같은 무복사). 여러 leaf에 + 걸친 범위는 기존 API가 연속 뷰를 요구하므로 익명 매핑에 복사한다. + +## 측정 + +같은 Raspberry Pi 5(Linux 6.18.39 AArch64), ext4 `/dev/mmcblk0p2`, GCC 14 `-O2`. +[저장소 API 직접 측정](../../research/experiments/008-tree-store-edit-cost/bench.c)은 시나리오마다 32회 편집의 +중앙값이다. [원시 결과](../../research/experiments/008-tree-store-edit-cost/2026-09-25-ext4-linux-aarch64.json). + +| 1 MiB 문서, 편집 1회 | 기본 파일 | 선택형 페이지 | 영속 트리 | +|---|---:|---:|---:| +| 가운데 1 B 삽입 | 78.51 ms | 86.57 ms | **8.58 ms** | +| 가운데 1 B 삭제 | 78.76 ms | 85.29 ms | **8.51 ms** | +| 마지막 1 B 교체 | 79.20 ms | 13.96 ms | **6.49 ms** | +| 끝에 1 B 추가 | 77.89 ms | 86.04 ms | **8.47 ms** | +| write 호출 바이트/편집 | 약 1,048,600 | 16,944–1,065,528 | **2,716–4,912** | +| 장치 쓰기 바이트/편집 | 약 1,064,960 | 32,768–1,081,344 | **35,328–37,376** | + +페이지 저장소는 크기가 같은 교체에서만 부분 기록을 하고, 삽입·삭제·추가는 전체를 다시 쓴다. +트리는 네 가지 편집 모두 경로만 쓴다. + +[실제 TUI 측정](../../research/experiments/008-tree-store-edit-cost/tui.py)은 065와 같은 방법으로 +Ctrl+S부터 저장 완료 프레임까지 잰다. 1 MiB 문서, 저장소별 3세션 × 8회 = 24회의 중앙값이다. +[원시 결과](../../research/experiments/008-tree-store-edit-cost/2026-09-25-tui-ext4-linux-aarch64.json). + +| Ctrl+S → 완료 표시 | 기본 파일 | 선택형 페이지 | 영속 트리 | +|---|---:|---:|---:| +| 마지막 문자 교체 | 86.32 ms | 21.31 ms | **16.97 ms** | +| 끝에 한 글자 입력 | 84.59 ms | 93.29 ms | **16.60 ms** | + +일반 입력처럼 문서가 커지는 저장에서 기본 대비 약 5.1배, 페이지 대비 약 5.6배 짧았다. + +## 검증 + +[`test-tree-store.c`](../../prototypes/connections/test-tree-store.c)는 ASan·UBSan에서도 통과했다. + +- 4개 키에 6,000회 무작위 편집을 평면 배열 오라클과 매번 비교했다(최대 333,510 B, 높이 2). + 매 편집 뒤 저장된 모든 비루트 노드가 기준 이상으로 채워졌는지 확인했다. +- 이전에 받은 뷰는 이후의 커밋과 압축을 지나도 바이트가 그대로다. +- 1 MiB 문서의 1 B 편집은 최대 4,912 B만 추가한다(높이 2, leaf 258개). +- 다섯 고장 단계, 각 단계에서의 프로세스 사망(공개 안 된 꼬리는 다음 writer가 잘라냄), + 찢긴 최신 head, 다른 프로세스의 400회 커밋·압축 중 잠금 없는 읽기의 격리, + 3,000회 1비트 손상(OK·저장 오류·없음만 반환), 1,024개 키, 리비전 상한, 키 목록. + +저장소만 바꾸고 기존 검사를 그대로 실행하는 `make check-tree`도 통과했다. +`test-runtime`, `test-splice`(오라클·이전 스냅샷·경계·충돌·고장 단계), `test-async`, 고정·소스 +TUI의 실제 PTY 검사(1 MiB, UTF-8, 충돌, 1,024개 문서 목록)다. 기본 `check-release`와 +선택형 페이지 검사도 TUI의 목록 변경 뒤 다시 통과했다. + +## 비용과 한계 + +- **코드 크기가 크다.** `store-tree.c` 오브젝트 `text`는 `-O2` 15,899 B, `-Os` 13,242 B다. + 기본 저장소는 4,453 B, 페이지 저장소는 9,198 B다. 고정 정의 CLI의 링크 `text`는 + 19,268 → 31,978 B, 고정 TUI는 32,375 → 44,217 B다. 선택형이며 기본 빌드에는 들어가지 않는다. + 마이크로 목표에 맞추려면 줄여야 할 첫 항목이다. +- **연속 읽기는 복사한다.** 여러 leaf에 걸친 1 MiB 전체 읽기의 중앙값은 0.23–0.37 ms로, + 기본 매핑의 0.06–0.10 ms보다 느리다. 기존 API가 연속 뷰를 요구하기 때문이다. +- **작은 문서는 이득이 없다.** 256 B 편집 지연은 비슷하지만(6.47–9.14 ms 대 8.32–9.31 ms) + 동기화가 두 번이라 장치 쓰기가 16 KiB에서 32 KiB로 늘었다. +- **공간이 늦게 회수된다.** 압축 전까지 파일이 자란다. 1 MiB 문서를 32회 편집한 뒤 + 1.14–1.21 MB였다. 압축은 전체 재작성이며 그동안 writer 잠금을 잡는다. +- 문서 하나를 파일 단위로 지우거나 복사하는 외부 조작은 더 이상 없다. TUI 검사의 외부 삭제 + 시나리오는 이 저장소에서 생략한다. 기본 형식으로의 전환은 CLI `show`/`apply` 경로뿐이며 + 전용 변환 도구는 아직 없다. +- head 체크섬은 찢김 검출용이며 적대적 파일 방어가 아니다. 노드 데이터에는 체크섬이 없어 + 비트 부패를 검출하지 않는다(기존 저장소와 같음). writer 잠금은 기존의 프로세스 단위 + `fcntl` 잠금이다. 읽기는 잠그지 않으므로 페이지 저장소의 같은 프로세스 읽기·쓰기 잠금 문제는 없다. +- 물리 전원 차단 내구성, macOS, x86_64는 검증하지 않았다. + +## 선행 기술 + +경로 복사 B-tree와 번갈아 쓰는 두 메타 슬롯은 LMDB, 텍스트 편집용 익스텐트 트리는 로프· +피스 테이블 계열 편집기, 추가 전용 기록과 압축은 로그 구조 저장소가 이미 쓰는 기법이다. +이번 결과는 이 기법들을 Pure 계약 아래에 작게 결합했다는 것이며 신규성 주장이 아니다. +차별성은 같은 구조가 저장 계층을 넘어 편집 초안·전송까지 공유될 때 판단한다. + +## 다음 결정 + +TUI의 17 ms 중 저장소 자체는 약 8.5 ms다. 나머지는 저장본 전체를 연속 뷰로 다시 읽어 +초안과 비교하는 "초안 대 저장본 비교" 관례의 비용이다. 편집기는 무엇을 바꿨는지 이미 알고 있다. + +1. 편집 연산을 그대로 전달하고, 초안을 같은 트리의 커밋되지 않은 루트로 둔다. 그러면 + 전체 비교, 전체 복사, 별도 gap buffer가 사라지는지 확인한다. +2. 연속 뷰 대신 익스텐트 열을 소비자에게 준다(HTTP `writev`, 피어 전송, TUI 렌더). +3. Pure 간 동기화에서 상대에게 없는 노드만 보낸다. +4. 코드 크기를 줄인다. 기본 저장소 승격 여부는 1–4의 결과와 macOS·전원 차단 검증 뒤에 판단한다. |