1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
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·전원 차단 검증 뒤에 판단한다.
|
