diff options
Diffstat (limited to 'docs/research')
| -rw-r--r-- | docs/research/073-single-file-persistent-tree.md | 2 | ||||
| -rw-r--r-- | docs/research/075-http-host-against-axum.md | 15 | ||||
| -rw-r--r-- | docs/research/076-one-sync-commit.md | 144 |
3 files changed, 160 insertions, 1 deletions
diff --git a/docs/research/073-single-file-persistent-tree.md b/docs/research/073-single-file-persistent-tree.md index 092b6ad..13884e3 100644 --- a/docs/research/073-single-file-persistent-tree.md +++ b/docs/research/073-single-file-persistent-tree.md @@ -36,6 +36,8 @@ - 커밋: 새 노드 추가 → `fsync` → 오래된 head 슬롯에 새 head → `fsync`. OK는 두 번째 동기화 뒤다. 복구는 유효한 슬롯 중 순번이 큰 쪽을 쓰고, 그 끝 뒤의 바이트는 확인받지 않은 커밋이라 다음 writer가 잘라낸다. 쓰기 중 고장 단계는 기존 저장소와 같은 결과(오류 또는 결과 불명)를 낸다. + (2026-09-26: 동기화 한 번으로 바뀌었다. head가 커밋 바이트의 다이제스트를 갖고, 커밋은 0을 써 둔 꼬리를 + 덮어쓴다 — [076](076-one-sync-commit.md).) - 압축: 공개 크기의 증가가 `4 × 압축 후 크기 + 1 MiB`를 넘으면 도달 가능한 노드만 새 파일에 쓰고 교체한다. 이미 읽은 쪽은 이전 파일의 매핑을 계속 사용한다. - 읽기: 한 leaf 안의 범위는 파일을 그대로 매핑한다(기본 저장소와 같은 무복사). 여러 leaf에 diff --git a/docs/research/075-http-host-against-axum.md b/docs/research/075-http-host-against-axum.md index ab26a37..8a03889 100644 --- a/docs/research/075-http-host-against-axum.md +++ b/docs/research/075-http-host-against-axum.md @@ -123,4 +123,17 @@ ThreadSanitizer는 이 커널(47비트 가상 주소)을 지원하지 않아 쓰 **저장 보장 쓰기 측정의 함정.** 저장 장치는 SD 카드 하나뿐이고, 동기 쓰기가 몇 분 이어지면 내부 정리로 크게 느려진다 (같은 설정이 순서에 따라 연결 8개에서 350/s → 17/s, p99 4.4초). 앞의 표들의 쓰기 수치는 순서 영향을 받았다. 쓰기 비교는 -설정 순서를 섞어 여러 번 돌리고, 매번 장치의 fsync 지연을 함께 재서 보고해야 한다(다음 작업). +설정 순서를 섞어 여러 번 돌리고, 매번 장치의 fsync 지연을 함께 재서 보고해야 한다. 하네스가 이제 그렇게 한다 +(`--rounds`, 라운드마다 서버 순서 회전, 쓰기 직전 장치 탐침). + +## 4단계: 커밋당 동기화 한 번 + +저장소 커밋을 동기화 한 번으로 줄였다([076](076-one-sync-commit.md)). 같은 하네스로 3초 × 3라운드의 중앙값: + +| PUT 16 B, keep-alive | pure-serve | pure-serve 3샤드 | axum 비안전 | axum 충돌 안전 | +|---|---:|---:|---:|---:| +| 연결 64 | **2,012** (p50 20.5 ms) | **2,611** (12.3 ms) | 1,040 (41.0 ms) | 583 (69.6 ms) | +| 연결 8 | **601** (6.4 ms) | **637** (7.7 ms) | 260 (18.4 ms) | 166 (30.7 ms) | + +충돌에 안전한 axum 대비 쓰기 처리량 3.4–4.5배, 봉우리 RSS 3.0–4.6 MiB 대 7.3–9.6 MiB다. 이제 읽기, 1 MiB 읽기, +저장 보장 쓰기 모두에서 axum보다 빠르고 메모리를 덜 쓴다. diff --git a/docs/research/076-one-sync-commit.md b/docs/research/076-one-sync-commit.md new file mode 100644 index 0000000..8176a82 --- /dev/null +++ b/docs/research/076-one-sync-commit.md @@ -0,0 +1,144 @@ +# 076 — 커밋당 동기화 한 번: 순서를 동기화로 강제하지 않고 헤드가 검증한다 + +2026-09-26. 트리 저장소(`store-tree.c`)의 커밋을 동기화 두 번에서 한 번으로 줄였다. 파일 형식이 바뀌었다 +(`PURETRE1` → `PURETRE2`, 이전 파일은 읽지 않는다). + +착수 기준: + +- 바꿀 결정: 커밋의 내구성을 "데이터 동기화 → 헤드 기록 → 헤드 동기화"라는 순서로 보장할지, 헤드가 자기 + 커밋을 검증하게 해서 한 번의 동기화로 보장할지. +- 남은 질문: 동기화 한 번이 이 장치에서 실제로 얼마나 싼가? 동기화 도중 전원이 나가 헤드만 남은 커밋을 확실히 + 버릴 수 있는가? 그 확인 비용을 읽기 경로가 매번 치르지 않을 수 있는가? +- 최소 확인: 장치에서 방식별 비용을 같은 조건으로 재고, 새 커밋을 기존 고장·오라클 검사와 새 "잃어버린 커밋" + 검사에 통과시킨 뒤 저장소와 HTTP 수준에서 이전 커밋과 번갈아 잰다. +- 중단 기준: 장치 비용이 절반 이하로 줄지 않거나, 잃어버린 커밋을 받아들이는 경우가 하나라도 있으면 닫는다. + +## 의심한 관례 + +| 관례 | 바꾼 것 | +|---|---| +| 커밋의 원자성은 쓰기 순서를 동기화로 강제해 얻는다 | 헤드가 커밋 바이트의 다이제스트를 가진다. 바이트가 다 닿지 않은 헤드는 스스로 드러난다 | +| 파일 끝에 덧붙인다 | 미리 0을 써 둔 꼬리를 덮어쓴다. 크기도 블록 할당도 바뀌지 않아 저널 커밋이 없다 | +| `fsync` | `fdatasync`(시각은 동기화하지 않는다) | +| 두 헤드 슬롯은 파일 첫 블록에 나란히 | 슬롯마다 4 KiB 블록 하나. 한 슬롯의 찢긴 쓰기가 다른 슬롯에 닿지 않는다 | +| 읽기는 보이는 최신 헤드를 믿는다 | 같은 프로세스가 아직 동기화 중인 헤드는 읽기가 건너뛴다 | + +## 장치가 말한 것 + +같은 Raspberry Pi 5, ext4 SD 카드(`/dev/mmcblk0p2`). 8 KiB 커밋 + 64 B 헤드를 방식별로 40번, 방식들을 번갈아 +가며 쟀다([probe.c](../../research/experiments/010-one-sync-commit/probe.c)). 세 번 반복의 p50 범위(ms): + +| 방식 | p50 | +|---|---:| +| 덧붙이기, fsync, 헤드, fsync (이전) | 8.82–9.19 | +| 덧붙이기, 헤드, fdatasync | 5.61–5.82 | +| 덧붙이기, 헤드, fsync | 5.66–6.21 | +| **0을 써 둔 곳 덮어쓰기, 헤드, fdatasync** | **2.41–2.53** | +| 0을 써 둔 곳 덮어쓰기, 헤드, fsync | 5.07–5.75 | + +동기화 횟수만 줄이면 약 1.6배다. 나머지는 파일 크기·블록 할당·수정 시각 같은 메타데이터 때문에 생기는 저널 커밋이다. +세 가지를 모두 없애야 약 3.7배가 된다. + +## 구조 + +- 파일: `[슬롯 0 블록][슬롯 1 블록][커밋된 노드…][0으로 채운 꼬리]`. 데이터는 8 KiB부터다. +- 헤드 슬롯(128 B): 순번, 공개 끝, 카탈로그 루트, 압축 후 크기, **커밋 시작 위치, 커밋 바이트의 다이제스트**, + 슬롯 자체의 다이제스트. 다이제스트는 xxHash64 구성(네 갈래 곱셈-회전, 수 GB/s)이고, 찢김과 누락 검출용이지 + 적대적 파일 방어용은 아니다. +- 커밋: 쓰는 쪽이 노드를 버퍼에서 내보낼 때마다 다이제스트를 갱신한다(데이터를 다시 읽지 않는다). 노드를 + 공개 끝부터 쓰고, 오래된 슬롯에 헤드를 쓰고, `fdatasync`를 한 번 한다. OK는 그 뒤다. +- 복구: 최신 슬롯의 헤드가 가리키는 바이트의 다이제스트가 맞아야 그 헤드를 쓴다. 틀리면 이전 슬롯을 쓴다. + 쓰는 쪽은 항상 내구성 있는 헤드 위에서만 쓰기 때문에 이전 슬롯은 검사할 필요가 없다. 새 헤드는 이전 커밋의 + 동기화가 끝난 뒤에야 쓰였다. 공개되지 않은 바이트는 꼬리에 남아 있다가 다음 커밋에 덮어써진다. 잘라 내지 않는다. +- 헤드 확인 비용: 프로세스는 자기가 공개했거나 검사한 헤드를 기억한다(32개). 그래서 커밋 바이트를 헤드당 + 최대 한 번 읽고, 자기가 쓴 커밋은 읽지 않는다. 쓰는 쪽은 자기가 내구성을 확인하지 않은 헤드(죽은 writer가 + 동기화 전에 남긴 것일 수 있다)를 만나면 한 번 동기화한 뒤 그 위에 쓴다. 검사에 실패한 헤드도 기억해 다시 + 읽지 않는다. +- 읽기 격리: 헤드를 쓰기 직전에 "동기화 중" 표시를 하고 동기화가 끝나면 지운다. 이 프로세스의 읽기는 표시된 + 헤드를 건너뛰고 이전 헤드를 읽는다. 그래서 전원이 나가면 사라질 커밋으로 답하지 않는다. 샤드가 여러 개일 때도 + 같다. 다른 프로세스의 읽기는 이전 설계와 마찬가지로 동기화 전의 헤드를 볼 수 있다. +- 꼬리: writer 세션을 열 때 꼬리가 64 KiB보다 짧으면 `max(256 KiB, 파일의 1/8)`만큼 0을 쓴다. 그 0은 다음 + 커밋의 동기화와 함께 내구성을 얻는다. 저널 커밋은 그 한 커밋만 치른다. 압축으로 만든 새 파일도 꼬리를 가진 채 + 설치된다. +- 핸들의 새로 고침: 매핑이 헤드 슬롯을 보여 주므로, 바뀌지 않은 저장소를 확인하는 데는 `fstatat` 하나만 든다 + (이전에는 `pread`까지 둘). 새 헤드는 언제나 현재 헤드가 없는 쪽 슬롯에 먼저 쓰이므로 그 슬롯의 순번만 보면 된다. + +## 측정 + +**저장소 단독.** [commits.c](../../research/experiments/010-one-sync-commit/commits.c)는 64개 문서 중 하나의 앞에 +16 B를 넣는 커밋을 200번 연달아 한다. 동기화 두 번 판(`ad2197c`)과 한 번 판을 라운드마다 순서를 바꿔 가며 세 번 +쟀다([run.py](../../research/experiments/010-one-sync-commit/run.py), +[원시 결과](../../research/experiments/010-one-sync-commit/2026-09-26-ext4-linux-aarch64.json)). + +| 커밋 | 동기화 두 번 | 동기화 한 번 | +|---|---:|---:| +| 초당 커밋 | 94–109 | **289–304** | +| p50 | 8.82–9.19 ms | **2.44–2.48 ms** | +| p90 | 11.15–12.20 ms | **4.69–5.49 ms** | +| p99 | 61.7–63.2 ms | 19.8–56.8 ms | + +p99는 장치 쪽 잡음이 지배한다. 꼬리를 늘리는 단위를 64 KiB, 256 KiB, 1 MiB로 바꿔 봐도 p99가 일정하게 움직이지 +않았다. + +**HTTP.** [075](075-http-host-against-axum.md)의 하네스를 고쳐 라운드마다 서버 순서를 바꾸고 쓰기 직전에 장치를 +재게 했다. 3초 × 3라운드의 중앙값이고, 성공 응답/초와 괄호 안 p50(ms)이다. 두 판 모두 장치 탐침은 1.0–1.5 ms였다 +(연결 8개 1스레드 이전 판은 2.5–3.1 ms). + +| PUT 16 B, keep-alive | pure-serve 이전 | pure-serve | 3샤드 이전 | 3샤드 | axum 비안전 | axum 충돌 안전 | +|---|---:|---:|---:|---:|---:|---:| +| 연결 64 | 1,245 | **2,012** (20.5) | 1,980 | **2,611** (12.3) | 1,040 (41.0) | 583 (69.6) | +| 연결 8 | 380 | **601** (6.4) | 313 | **637** (7.7) | 260 (18.4) | 166 (30.7) | + +충돌에 안전한 axum과 비교하면 쓰기 처리량은 3.4–4.5배이고, p50은 3.8–5.7배 짧다. 봉우리 RSS는 pure-serve +3.0 MiB, 3샤드 4.6 MiB, axum 7.3–9.6 MiB였다. + +## 검증 + +[`test-tree-store.c`](../../prototypes/connections/test-tree-store.c)는 ASan·UBSan에서도 통과했다. 새로 넣은 검사: + +- **잃어버린 커밋**: 최신 커밋의 바이트 하나를 바꾸고 프로세스의 기억을 지우면(재부팅 뒤의 새 프로세스와 같다) + 읽기, 핸들, writer가 모두 이전 커밋을 쓴다. 다음 커밋은 잃어버린 커밋이 있던 자리부터 쓴다. +- **동기화 중인 헤드**: 헤드를 쓰고 동기화 전에 멈춘 사이 같은 프로세스의 핸들과 읽기는 이전 버전을 보고, + 동기화가 끝나면 새 버전을 본다. +- **동기화 한 번**: 커밋 20번에 동기화가 정확히 20번이고 파일 크기가 그대로다. +- **고장 단계**: 동기화 전에 죽은 writer의 헤드를 이어받는 첫 커밋은 동기화를 두 번 한다. 확인 한 번과 커밋 한 번이다. + 다른 단계의 커밋은 한 번이다. 찢긴 최신 슬롯, 1비트 손상, 격리, 압축, 그룹 커밋 검사도 새 배치에서 그대로 통과한다. + +모듈 검사(`make check-module`, ASan 포함), `make check-tree`(런타임·splice·async와 실제 PTY 편집기), aup와 vega의 +검사(서버 병렬성·파이프라이닝·kill -9 내구성 포함)가 모두 통과했다. + +이 과정에서 기존 Makefile 버그를 찾았다. `MODULE` 변수가 `pure-serve` 규칙보다 뒤에서 정의돼 있어서, 저장소나 모듈 +실행기를 고쳐도 `pure-serve`가 다시 빌드되지 않았다(규칙의 선행 조건은 읽을 때 전개된다). 정의를 앞으로 옮겼다. +첫 HTTP 측정은 이 때문에 이전 바이너리로 돌았고, 그 값이 위 표의 "이전" 열이다. + +## 비용과 한계 + +- **공간.** 파일 끝에 256 KiB 또는 파일 크기의 1/8까지 0이 있다. 헤드 두 슬롯이 8 KiB를 차지한다. 작은 저장소가 + 이전보다 커진다. +- **장치 쓰기가 두 배.** 커밋 바이트가 들어갈 자리에 0을 먼저 쓰므로 장치는 같은 블록을 두 번 쓴다. 작은 커밋에서는 + 저널 커밋(약 3.5 ms)보다 훨씬 싸지만, 큰 문서를 잇달아 쓰는 작업은 대역폭을 더 쓴다. 꼬리를 늘리는 커밋은 0을 + 쓰고 저널 커밋까지 치른다. +- **다른 프로세스의 첫 커밋.** 새 프로세스의 첫 writer 세션은 확인 동기화를 한 번 더 한다. `aup run --store`처럼 + 짧은 명령은 커밋마다 동기화가 두 번이다. 다른 프로세스의 커밋을 처음 읽을 때는 그 커밋의 바이트를 한 번 읽는다. +- **격리는 프로세스 안에서만.** 동기화가 끝나지 않은 커밋은 같은 프로세스에서는 보이지 않지만, 다른 프로세스의 + 읽기에는 보인다(이전 설계도 두 번째 동기화 동안 같았다). +- **형식 변경.** `PURETRE1` 파일은 열리지 않는다(`pure_store_init`은 읽을 수 없는 파일을 바꾸지 않는다). 변환 도구는 + 없다. +- macOS는 `fdatasync` 대신 `fsync`를 쓰고, `F_FULLFSYNC`는 쓰지 않는다. 실제 전원 차단, macOS, x86_64는 검증하지 + 않았다. 페이지 크기가 16 KiB인 이 커널에서 두 슬롯은 같은 페이지에 있다. 블록 단위로 쓰는 파일 시스템에서는 + 서로 닿지 않지만, 장치가 바뀌지 않은 블록까지 다시 쓰는 경우의 찢김은 장치 동작에 맡긴다. + +## 선행 기술 + +ext4/jbd2의 `journal_async_commit`은 커밋 블록에 체크섬을 넣어, 데이터 블록을 기다리지 않고 커밋 블록을 쓰게 한다. +SQLite WAL은 프레임마다 누적 체크섬을 두어 커밋당 동기화 한 번으로 끝낸다. PostgreSQL은 WAL 세그먼트를 0으로 채워 +재사용한다(`wal_init_zero`, `wal_recycle`). LMDB는 두 메타 페이지를 서로 다른 페이지에 둔다. 다이제스트는 xxHash64 +구성이다. 이번 일은 이 기법들을 Pure의 한 파일 트리에 맞게 결합한 것이며 신규성 주장이 아니다. Pure 쪽 기여는 +프로세스 안의 "동기화 중" 표시로, 커밋을 공개 경로에서 떼어 내지 않고도 이 프로세스의 읽기가 내구성 없는 +커밋을 보지 않게 했다는 점이다. + +## 다음 결정 + +1. 꼬리를 늘리는 비용을 커밋 경로에서 빼기(백그라운드 준비나 세그먼트 재사용). 지금은 한 커밋이 치른다. +2. 여러 프로세스가 같은 저장소를 쓸 때의 확인 동기화를 줄이는 방법(동기화 완료를 공유 메모리로 알리기). +3. 동기화를 다음 묶음의 실행과 겹치기. 커밋 결과를 기다리는 동안 다음 묶음의 이벤트를 준비한다. |