diff options
8 files changed, 274 insertions, 10 deletions
diff --git a/docs/research/085-cycle-sized-files.md b/docs/research/085-cycle-sized-files.md new file mode 100644 index 0000000..dc32b6b --- /dev/null +++ b/docs/research/085-cycle-sized-files.md @@ -0,0 +1,62 @@ +# 085 — 압축한 파일에 한 주기의 0을: 커밋이 새 블록을 받지 않게 + +2026-09-27. [084](084-parallel-syncs.md)에서 쓰기의 꼬리 지연을 만드는 것이 새 블록(꼬리를 늘리며 쓰는 0과 그 크기·블록의 +저널 커밋)이라고 확인한 뒤 고친 것. 트리 저장소(`store/store-tree.c`)의 파일 형식은 그대로다. + +착수 기준: + +- 바꿀 결정: 커밋이 필요할 때마다 꼬리를 256 KiB씩 늘리게 둘지, 압축이 새 파일을 만들 때 다음 압축까지 쓸 만큼의 0을 한 번에 + 써 둘지. 공간을 제자리에서 다시 쓰는 저장소(두 파일을 번갈아 쓰거나 고리처럼 돌려 쓰기)는 읽는 쪽이 모두 잠금을 쥐어야 + 하고(지금은 다른 프로세스도 잠금 없이 옛 파일을 매핑해 읽는다) 둘째 파일만큼 디스크를 더 쓴다. 그보다 싼 길이 있는지 본다. +- 최소 확인: 저장소만의 커밋(HTTP 없이)과 앱의 내구성 POST에서, 커밋 속도와 지연, ext4 저널 커밋 수(`/proc/fs/jbd2`)를 전과 + 번갈아 잰다. 압축 사이에 파일이 커지지 않고, 살아 있는 데이터가 줄면 파일도 준다는 것을 검사로 지킨다. +- 중단 기준: 처리량이나 지연 중 하나라도 잡음 밖으로 나빠지면 되돌린다. + +## 한 것 + +압축한 파일을 설치할 때 0을 `cycle_end`까지 써 둔다. 다음 압축은 끝이 `4 × live + slack`을 넘을 때 일어나므로, 거기에 커밋 +하나가 앞에 요구하는 여유(`TAIL_MIN`)를 더한 곳까지다. 다만 대신하는 파일이 닿았던 크기를 넘지 않는다. 그래서 저장소는 전보다 +공간을 더 쓰지 않고, 살아 있는 데이터가 줄면 파일도 따라 준다. 그 주기의 커밋은 이미 있는 블록만 덮어쓴다. 동기화가 데이터만 +내보내고 저널 커밋을 하지 않는다. + +새 검사 `cycles`(`store/test-tree-store.c`)는 두 가지를 확인한다. 4 KiB 값 32개를 1,600번 덮어쓰면, 값이 다 생긴 뒤 두 번째 +압축부터 압축 사이에 파일 크기가 한 번도 바뀌지 않는다(압축 스물 번 남짓). 같은 키를 64 B로 바꾸면 압축 세 번 안에 파일이 +가장 컸을 때의 절반 아래로 준다. 기존 검사(고장, 단계마다 죽는 프로세스, 찢긴 헤드, 레코드, 압축, 손상)도 ASan·UBSan 빌드에서 +그대로 통과한다. + +## 장치가 말한 것 + +Raspberry Pi 5, SD 카드의 ext4. + +**저장소만.** 문서 64개 중 하나의 앞에 16 B를 넣는 커밋 4,000번, 변형마다 네 라운드의 중앙값, 순서는 라운드마다 돌린다 +([journal.py](../../research/experiments/013-parallel-syncs/journal.py)): + +| | 커밋/s | p90 | p99 | 저널 커밋 | +|---|---:|---:|---:|---:| +| 전(커밋이 꼬리를 늘림) | 317.5 | 4.07 ms | 29.5 ms | 109 | +| 지금(압축한 파일에 한 주기의 0) | **385.5** | 3.98 ms | 26.9 ms | **45** | +| 상한(압축도 꼬리 늘리기도 없음) | 466.0 | 3.92 ms | 22.6 ms | 16.5 | + +([원시 결과](../../research/experiments/013-parallel-syncs/2026-09-27-journal-ext4-linux-aarch64.jsonl).) 바꾸기 전에 같은 방식으로 +잰 첫 비교에서는 366 → 447 커밋/s, p99 45.5 → 23.4 ms, 저널 커밋 113.5 → 46이었다 +([원시 결과](../../research/experiments/013-parallel-syncs/2026-09-27-journal-before-085-ext4-linux-aarch64.jsonl)). 커밋은 ++21–22%, 저널 커밋은 −59%다. 상한까지 남은 것은 압축 자체의 비용(새 파일, 이름 바꾸기, 디렉터리 동기화)이다. + +**앱.** 점수판의 내구성 POST 64연결, 4초씩 여덟 라운드([variants.py](../../research/experiments/013-parallel-syncs/variants.py), +[원시 결과](../../research/experiments/013-parallel-syncs/2026-09-27-store-variants-085-ext4-linux-aarch64.jsonl)): + +| | posts/s | p99 | +|---|---:|---:| +| 전 | 21,725 | 14.8 ms | +| 지금 | **22,881** | 17.9 ms | +| 상한 | 23,486 | 14.3 ms | + +처리량은 +5.3%다. p99는 이 실행에서 3 ms 나빴지만, 앞선 여섯 라운드 실행에서는 반대였다(23.0 → 15.9 ms). 두 실행을 합친 +라운드 열네 개의 중앙값은 15.0 ms와 15.5 ms로 같다. 이 SD 카드에서는 라운드마다 p99가 12–26 ms로 흔들려 이 차이를 가려내지 +못한다. 알아 둘 것이 하나 있다. 0을 쓰는 일이 주기에 걸쳐 다섯 번쯤 나뉘던 것이 압축 한 번에 모인다. 그래서 멈춤은 드물어지고 +한 번은 길어진다(점수판에서 약 1.1 MiB, 10 ms 안팎). 기기가 하는 일은 저널 커밋이 줄어든 만큼 적다. + +## 다음 + +- 압축을 없애는 것(상한): 쓸 공간을 제자리에서 다시 쓰는 저장소. 읽는 쪽이 매핑하는 동안 공유 잠금(`flock`)을 쥐고, 쓰는 쪽은 + 배타 잠금을 얻을 때만 옛 파일을 다시 쓴다. 디스크는 둘째 파일만큼 더 든다. 작은 저장소(한 주기가 수십 MiB 아래)부터 고려한다. diff --git a/research/experiments/013-parallel-syncs/2026-09-27-journal-before-085-ext4-linux-aarch64.jsonl b/research/experiments/013-parallel-syncs/2026-09-27-journal-before-085-ext4-linux-aarch64.jsonl new file mode 100644 index 0000000..5b8320d --- /dev/null +++ b/research/experiments/013-parallel-syncs/2026-09-27-journal-before-085-ext4-linux-aarch64.jsonl @@ -0,0 +1,20 @@ +{"round": 0, "store": "as it is", "commits_per_second": 362, "p50_ms": 1.26, "p90_ms": 3.98, "p99_ms": 55.11, "journal_commits": 113} +{"round": 0, "store": "no compaction", "commits_per_second": 427, "p50_ms": 1.27, "p90_ms": 3.91, "p99_ms": 36.68, "journal_commits": 44} +{"round": 0, "store": "no compaction, no growth", "commits_per_second": 541, "p50_ms": 1.27, "p90_ms": 3.17, "p99_ms": 5.49, "journal_commits": 8} +{"round": 0, "store": "compacted file sized like the old", "commits_per_second": 477, "p50_ms": 1.26, "p90_ms": 3.21, "p99_ms": 10.87, "journal_commits": 46} +{"round": 1, "store": "no compaction", "commits_per_second": 458, "p50_ms": 1.28, "p90_ms": 3.52, "p99_ms": 16.56, "journal_commits": 43} +{"round": 1, "store": "no compaction, no growth", "commits_per_second": 440, "p50_ms": 1.27, "p90_ms": 4.08, "p99_ms": 25.17, "journal_commits": 7} +{"round": 1, "store": "compacted file sized like the old", "commits_per_second": 413, "p50_ms": 1.26, "p90_ms": 3.22, "p99_ms": 25.22, "journal_commits": 48} +{"round": 1, "store": "as it is", "commits_per_second": 370, "p50_ms": 1.29, "p90_ms": 4.01, "p99_ms": 33.16, "journal_commits": 110} +{"round": 2, "store": "no compaction, no growth", "commits_per_second": 424, "p50_ms": 1.28, "p90_ms": 3.94, "p99_ms": 25.66, "journal_commits": 9} +{"round": 2, "store": "compacted file sized like the old", "commits_per_second": 461, "p50_ms": 1.26, "p90_ms": 3.3, "p99_ms": 21.71, "journal_commits": 46} +{"round": 2, "store": "as it is", "commits_per_second": 340, "p50_ms": 1.28, "p90_ms": 4.21, "p99_ms": 35.79, "journal_commits": 114} +{"round": 2, "store": "no compaction", "commits_per_second": 404, "p50_ms": 1.28, "p90_ms": 4.13, "p99_ms": 31.76, "journal_commits": 33} +{"round": 3, "store": "compacted file sized like the old", "commits_per_second": 433, "p50_ms": 1.25, "p90_ms": 3.13, "p99_ms": 25.18, "journal_commits": 46} +{"round": 3, "store": "as it is", "commits_per_second": 373, "p50_ms": 1.27, "p90_ms": 3.94, "p99_ms": 56.67, "journal_commits": 114} +{"round": 3, "store": "no compaction", "commits_per_second": 384, "p50_ms": 1.27, "p90_ms": 3.98, "p99_ms": 53.28, "journal_commits": 36} +{"round": 3, "store": "no compaction, no growth", "commits_per_second": 475, "p50_ms": 1.27, "p90_ms": 3.91, "p99_ms": 21.46, "journal_commits": 13} +{"store": "as it is", "commits": 4000, "commits_per_second": 366.0, "p50_ms": 1.275, "p90_ms": 3.995, "p99_ms": 45.45, "journal_commits": 113.5} +{"store": "no compaction", "commits": 4000, "commits_per_second": 415.5, "p50_ms": 1.275, "p90_ms": 3.9450000000000003, "p99_ms": 34.22, "journal_commits": 39.5} +{"store": "no compaction, no growth", "commits": 4000, "commits_per_second": 457.5, "p50_ms": 1.27, "p90_ms": 3.925, "p99_ms": 23.315, "journal_commits": 8.5} +{"store": "compacted file sized like the old", "commits": 4000, "commits_per_second": 447.0, "p50_ms": 1.26, "p90_ms": 3.215, "p99_ms": 23.445, "journal_commits": 46.0} diff --git a/research/experiments/013-parallel-syncs/2026-09-27-journal-ext4-linux-aarch64.jsonl b/research/experiments/013-parallel-syncs/2026-09-27-journal-ext4-linux-aarch64.jsonl new file mode 100644 index 0000000..0c14f32 --- /dev/null +++ b/research/experiments/013-parallel-syncs/2026-09-27-journal-ext4-linux-aarch64.jsonl @@ -0,0 +1,20 @@ +{"round": 0, "store": "as it is", "commits_per_second": 411, "p50_ms": 1.27, "p90_ms": 3.96, "p99_ms": 25.68, "journal_commits": 52} +{"round": 0, "store": "no compaction", "commits_per_second": 449, "p50_ms": 1.27, "p90_ms": 3.99, "p99_ms": 23.52, "journal_commits": 46} +{"round": 0, "store": "no compaction, no growth", "commits_per_second": 519, "p50_ms": 1.27, "p90_ms": 3.14, "p99_ms": 5.55, "journal_commits": 4} +{"round": 0, "store": "tail grown as commits need it", "commits_per_second": 346, "p50_ms": 1.29, "p90_ms": 4.01, "p99_ms": 26.25, "journal_commits": 117} +{"round": 1, "store": "no compaction", "commits_per_second": 360, "p50_ms": 1.28, "p90_ms": 3.94, "p99_ms": 32.97, "journal_commits": 42} +{"round": 1, "store": "no compaction, no growth", "commits_per_second": 413, "p50_ms": 1.28, "p90_ms": 4.07, "p99_ms": 26.58, "journal_commits": 18} +{"round": 1, "store": "tail grown as commits need it", "commits_per_second": 270, "p50_ms": 1.28, "p90_ms": 4.34, "p99_ms": 50.93, "journal_commits": 110} +{"round": 1, "store": "as it is", "commits_per_second": 382, "p50_ms": 1.25, "p90_ms": 3.99, "p99_ms": 26.49, "journal_commits": 40} +{"round": 2, "store": "no compaction, no growth", "commits_per_second": 463, "p50_ms": 1.27, "p90_ms": 3.96, "p99_ms": 22.29, "journal_commits": 21} +{"round": 2, "store": "tail grown as commits need it", "commits_per_second": 289, "p50_ms": 1.27, "p90_ms": 3.99, "p99_ms": 32.56, "journal_commits": 104} +{"round": 2, "store": "as it is", "commits_per_second": 356, "p50_ms": 1.27, "p90_ms": 3.93, "p99_ms": 37.21, "journal_commits": 46} +{"round": 2, "store": "no compaction", "commits_per_second": 393, "p50_ms": 1.26, "p90_ms": 4.08, "p99_ms": 32.96, "journal_commits": 41} +{"round": 3, "store": "tail grown as commits need it", "commits_per_second": 406, "p50_ms": 1.27, "p90_ms": 4.12, "p99_ms": 26.45, "journal_commits": 108} +{"round": 3, "store": "as it is", "commits_per_second": 389, "p50_ms": 1.27, "p90_ms": 4.06, "p99_ms": 27.31, "journal_commits": 44} +{"round": 3, "store": "no compaction", "commits_per_second": 392, "p50_ms": 1.26, "p90_ms": 3.4, "p99_ms": 52.8, "journal_commits": 44} +{"round": 3, "store": "no compaction, no growth", "commits_per_second": 469, "p50_ms": 1.27, "p90_ms": 3.88, "p99_ms": 22.84, "journal_commits": 15} +{"store": "as it is", "commits": 4000, "commits_per_second": 385.5, "p50_ms": 1.27, "p90_ms": 3.975, "p99_ms": 26.9, "journal_commits": 45.0} +{"store": "no compaction", "commits": 4000, "commits_per_second": 392.5, "p50_ms": 1.2650000000000001, "p90_ms": 3.965, "p99_ms": 32.965, "journal_commits": 43.0} +{"store": "no compaction, no growth", "commits": 4000, "commits_per_second": 466.0, "p50_ms": 1.27, "p90_ms": 3.92, "p99_ms": 22.564999999999998, "journal_commits": 16.5} +{"store": "tail grown as commits need it", "commits": 4000, "commits_per_second": 317.5, "p50_ms": 1.275, "p90_ms": 4.0649999999999995, "p99_ms": 29.505000000000003, "journal_commits": 109.0} diff --git a/research/experiments/013-parallel-syncs/2026-09-27-store-variants-085-ext4-linux-aarch64.jsonl b/research/experiments/013-parallel-syncs/2026-09-27-store-variants-085-ext4-linux-aarch64.jsonl new file mode 100644 index 0000000..5e26b0f --- /dev/null +++ b/research/experiments/013-parallel-syncs/2026-09-27-store-variants-085-ext4-linux-aarch64.jsonl @@ -0,0 +1,36 @@ +{"round": 0, "store": "as it is", "posts_per_second": 23632.25, "p50_us": 1984, "p99_us": 21504, "max_us": 61440, "errors": 0} +{"round": 0, "store": "no compaction", "posts_per_second": 21552.25, "p50_us": 2176, "p99_us": 17408, "max_us": 147456, "errors": 0} +{"round": 0, "store": "no compaction, no growth", "posts_per_second": 24320.25, "p50_us": 1984, "p99_us": 12800, "max_us": 61440, "errors": 0} +{"round": 0, "store": "tail grown as commits need it", "posts_per_second": 21392.25, "p50_us": 2176, "p99_us": 16384, "max_us": 69632, "errors": 0} +{"round": 1, "store": "no compaction", "posts_per_second": 21942.75, "p50_us": 2176, "p99_us": 13312, "max_us": 65536, "errors": 0} +{"round": 1, "store": "no compaction, no growth", "posts_per_second": 22688.25, "p50_us": 1984, "p99_us": 15360, "max_us": 163840, "errors": 0} +{"round": 1, "store": "tail grown as commits need it", "posts_per_second": 21433.5, "p50_us": 2176, "p99_us": 14336, "max_us": 73728, "errors": 0} +{"round": 1, "store": "as it is", "posts_per_second": 24960.25, "p50_us": 1984, "p99_us": 12800, "max_us": 73728, "errors": 0} +{"round": 2, "store": "no compaction, no growth", "posts_per_second": 23088.0, "p50_us": 2176, "p99_us": 12800, "max_us": 53248, "errors": 0} +{"round": 2, "store": "tail grown as commits need it", "posts_per_second": 22016.25, "p50_us": 2176, "p99_us": 15360, "max_us": 65536, "errors": 0} +{"round": 2, "store": "as it is", "posts_per_second": 23760.25, "p50_us": 1984, "p99_us": 12288, "max_us": 90112, "errors": 0} +{"round": 2, "store": "no compaction", "posts_per_second": 21280.25, "p50_us": 2176, "p99_us": 14336, "max_us": 59392, "errors": 0} +{"round": 3, "store": "tail grown as commits need it", "posts_per_second": 22081.25, "p50_us": 2176, "p99_us": 13824, "max_us": 65536, "errors": 0} +{"round": 3, "store": "as it is", "posts_per_second": 22594.75, "p50_us": 2176, "p99_us": 12288, "max_us": 81920, "errors": 0} +{"round": 3, "store": "no compaction", "posts_per_second": 21104.25, "p50_us": 2176, "p99_us": 21504, "max_us": 139264, "errors": 0} +{"round": 3, "store": "no compaction, no growth", "posts_per_second": 23419.25, "p50_us": 2176, "p99_us": 13312, "max_us": 57344, "errors": 0} +{"round": 4, "store": "as it is", "posts_per_second": 22673.25, "p50_us": 2048, "p99_us": 15360, "max_us": 81920, "errors": 0} +{"round": 4, "store": "no compaction", "posts_per_second": 23472.25, "p50_us": 2048, "p99_us": 14336, "max_us": 69632, "errors": 0} +{"round": 4, "store": "no compaction, no growth", "posts_per_second": 23881.5, "p50_us": 1984, "p99_us": 16384, "max_us": 61440, "errors": 0} +{"round": 4, "store": "tail grown as commits need it", "posts_per_second": 17632.25, "p50_us": 2304, "p99_us": 12800, "max_us": 589824, "errors": 0} +{"round": 5, "store": "no compaction", "posts_per_second": 19040.25, "p50_us": 2176, "p99_us": 14336, "max_us": 655360, "errors": 0} +{"round": 5, "store": "no compaction, no growth", "posts_per_second": 23552.25, "p50_us": 2048, "p99_us": 18432, "max_us": 59392, "errors": 0} +{"round": 5, "store": "tail grown as commits need it", "posts_per_second": 22192.0, "p50_us": 2176, "p99_us": 15872, "max_us": 73728, "errors": 0} +{"round": 5, "store": "as it is", "posts_per_second": 20928.25, "p50_us": 2176, "p99_us": 21504, "max_us": 77824, "errors": 0} +{"round": 6, "store": "no compaction, no growth", "posts_per_second": 24608.25, "p50_us": 1984, "p99_us": 12800, "max_us": 61440, "errors": 0} +{"round": 6, "store": "tail grown as commits need it", "posts_per_second": 19088.25, "p50_us": 2176, "p99_us": 15872, "max_us": 589824, "errors": 0} +{"round": 6, "store": "as it is", "posts_per_second": 22576.25, "p50_us": 2048, "p99_us": 20480, "max_us": 77824, "errors": 0} +{"round": 6, "store": "no compaction", "posts_per_second": 23184.25, "p50_us": 1984, "p99_us": 16384, "max_us": 73728, "errors": 0} +{"round": 7, "store": "tail grown as commits need it", "posts_per_second": 22080.25, "p50_us": 2176, "p99_us": 14336, "max_us": 69632, "errors": 0} +{"round": 7, "store": "as it is", "posts_per_second": 23088.25, "p50_us": 2048, "p99_us": 21504, "max_us": 65536, "errors": 0} +{"round": 7, "store": "no compaction", "posts_per_second": 23051.75, "p50_us": 2048, "p99_us": 14336, "max_us": 65536, "errors": 0} +{"round": 7, "store": "no compaction, no growth", "posts_per_second": 22586.5, "p50_us": 2048, "p99_us": 19456, "max_us": 57344, "errors": 0} +{"store": "as it is", "rounds": 8, "posts_per_second_median": 22880.75, "p99_us_median": 17920.0, "max_us": 90112} +{"store": "no compaction", "rounds": 8, "posts_per_second_median": 21747.5, "p99_us_median": 14336.0, "max_us": 655360} +{"store": "no compaction, no growth", "rounds": 8, "posts_per_second_median": 23485.75, "p99_us_median": 14336.0, "max_us": 163840} +{"store": "tail grown as commits need it", "rounds": 8, "posts_per_second_median": 21724.875, "p99_us_median": 14848.0, "max_us": 589824} diff --git a/research/experiments/013-parallel-syncs/journal.py b/research/experiments/013-parallel-syncs/journal.py new file mode 100644 index 0000000..5f49095 --- /dev/null +++ b/research/experiments/013-parallel-syncs/journal.py @@ -0,0 +1,66 @@ +#!/usr/bin/env python3 +"""The tree store's commits under each store variant of variants.py, without +HTTP: latency percentiles of research/experiments/010-one-sync-commit +/commits.c, and how many ext4 journal commits (jbd2 transactions, read from +/proc/fs/jbd2) each run caused. Rounds rotate the variants' order.""" +import argparse +import json +import re +import shutil +import statistics +import subprocess +import sys +import tempfile +from pathlib import Path + +import variants + +HERE = Path(__file__).resolve().parent +ROOT = HERE.parents[2] +COMMITS = HERE.parent / '010-one-sync-commit' / 'commits.c' + + +def transactions(device): + return int(re.match(r'(\d+) transactions', (Path('/proc/fs/jbd2') / device / 'info').read_text()).group(1)) + + +def main(): + parser = argparse.ArgumentParser() + parser.add_argument('--directory', type=Path, default=Path('/var/tmp'), help='on the device to measure') + parser.add_argument('--journal', default='mmcblk0p2-8', help='its /proc/fs/jbd2 entry') + parser.add_argument('--rounds', type=int, default=4) + parser.add_argument('--commits', type=int, default=4000) + args = parser.parse_args() + with tempfile.TemporaryDirectory() as work: + work = Path(work) + binaries = {} + for number, (name, patches) in enumerate(variants.PATCHES.items()): + source = (ROOT / 'store' / 'store-tree.c').read_text() + for old, new in patches: + assert old in source, old + source = source.replace(old, new) + (work / f'store-{number}.c').write_text(source) + binaries[name] = work / f'commits-{number}' + subprocess.run(['cc', '-O2', '-std=c17', f'-I{ROOT / "core"}', '-o', str(binaries[name]), str(COMMITS), + str(work / f'store-{number}.c'), '-lpthread'], check=True) + names, runs = list(binaries), {name: [] for name in binaries} + for round_ in range(args.rounds): + for name in names[round_ % len(names):] + names[:round_ % len(names)]: + store = Path(tempfile.mkdtemp(dir=args.directory, prefix='pure-journal-')) + shutil.rmtree(store) + try: + before = transactions(args.journal) + out = subprocess.run([str(binaries[name]), str(store), str(args.commits)], capture_output=True, + text=True, check=True) + measured = {**json.loads(out.stdout), 'journal_commits': transactions(args.journal) - before} + finally: + shutil.rmtree(store, ignore_errors=True) + runs[name].append(measured) + print(json.dumps({'round': round_, 'store': name, **measured}), flush=True) + for name in names: + print(json.dumps({'store': name, 'commits': args.commits, **{key: statistics.median(r[key] for r in runs[name]) + for key in ('commits_per_second', 'p50_ms', 'p90_ms', 'p99_ms', 'journal_commits')}})) + + +if __name__ == '__main__': + sys.exit(main()) diff --git a/research/experiments/013-parallel-syncs/variants.py b/research/experiments/013-parallel-syncs/variants.py index 2c48ab6..ee49d2a 100644 --- a/research/experiments/013-parallel-syncs/variants.py +++ b/research/experiments/013-parallel-syncs/variants.py @@ -1,9 +1,10 @@ #!/usr/bin/env python3 """Where the tree store's extra sync work goes (docs/research/084-parallel-syncs.md). -Builds pure-serve with three stores from store/store-tree.c: as it is; with no -compaction; and with no compaction and a 64 MiB tail written at creation (no -tail growth during a run). Then durable score posts (64 connections), the +Builds pure-serve with stores from store/store-tree.c: as it is; with no +compaction; with no compaction and a 64 MiB tail written at creation (no tail +growth during a run); and as before 085, compacted files getting only 256 KiB +of zeros and commits growing the tail as they need it. Then durable score posts (64 connections), the builds in rotated order per round, each on a fresh store after 64 warm-up posts. Prints one JSON line per run and a summary. """ @@ -25,6 +26,9 @@ PATCHES = { 'no compaction': [('enum { COMPACT_SLACK = 1048576 };', 'enum { COMPACT_SLACK = 1 << 30 };')], 'no compaction, no growth': [('enum { COMPACT_SLACK = 1048576 };', 'enum { COMPACT_SLACK = 1 << 30 };'), ('TAIL_STEP = 262144', 'TAIL_STEP = 67108864')], + # Before 085: a compacted file got 256 KiB of zeros, and commits grew the tail as they needed it. + 'tail grown as commits need it': [('zero_fill(fd, head->end, cycle_end(head, replaced));', + 'zero_fill(fd, head->end, tail_end(head->end));')], } diff --git a/store/store-tree.c b/store/store-tree.c index 146e919..024809b 100644 --- a/store/store-tree.c +++ b/store/store-tree.c @@ -925,15 +925,28 @@ static int create_temporary(int directory, char name[96]) { return -1; } +/* Where a fresh file's written zeros should reach: past everything the cycle + * to the next compaction will write (4 x live + slack more), so the commits + * of that cycle neither grow the file nor take new blocks, whose sync costs + * a journal commit (research 084: +22% commits, half the p99). No further + * than the file it replaces reached, so a store never takes more space than + * it did; a store whose live data shrank shrinks with it. */ +static uint64_t cycle_end(const Head *head, uint64_t replaced) { + uint64_t cycle = head->end + 4 * head->live + COMPACT_SLACK + TAIL_MIN; + uint64_t end = cycle < replaced ? cycle : replaced; + return end > tail_end(head->end) ? end : tail_end(head->end); +} + /* Publish a fresh file with both slots pointing at head. It is synced whole - * before it is renamed into place, so its head names no commit bytes. */ -static bool install(int directory, char temporary[96], int fd, Head *head) { + * before it is renamed into place, so its head names no commit bytes. + * replaced: the size of the file it replaces (0 for none). */ +static bool install(int directory, char temporary[96], int fd, Head *head, uint64_t replaced) { unsigned char slot[SLOT]; struct stat file; head->start = head->end; head->check = digest_end(&(Digest){0}); encode_head(slot, head_magic, head); - zero_fill(fd, head->end, tail_end(head->end)); + zero_fill(fd, head->end, cycle_end(head, replaced)); bool ok = write_at(fd, slot, SLOT, 0) && write_at(fd, slot, SLOT, BLOCK) && sync_fd(fd) && !fstat(fd, &file); if (close(fd)) ok = false; ok = ok && !renameat(directory, temporary, directory, tree_name); @@ -971,7 +984,7 @@ static void compact(int directory, int source, const struct stat *file, const He write_root(&tree, writer, &fresh, false) && flush(writer); if (ok) { Head compacted = {head->seq + 1, writer->at, fresh.ref, fresh.bytes, writer->at - DATA, 0, 0}; - ok = install(directory, temporary, fd, &compacted); + ok = install(directory, temporary, fd, &compacted, (uint64_t)file->st_size); fd = -1; } if (fd >= 0) close(fd); @@ -1010,7 +1023,7 @@ PureResult pure_store_init(const char *path) { char temporary[96]; int created_fd = create_temporary(directory, temporary); head = (Head){.seq = 1, .end = DATA}; - ok = created_fd >= 0 && install(directory, temporary, created_fd, &head); + ok = created_fd >= 0 && install(directory, temporary, created_fd, &head, 0); if (*temporary) unlinkat(directory, temporary, 0); } } diff --git a/store/test-tree-store.c b/store/test-tree-store.c index 1130acd..3ec55c0 100644 --- a/store/test-tree-store.c +++ b/store/test-tree-store.c @@ -1098,6 +1098,48 @@ static void one_sync(const char *path) { CHECK(pure_tree_test_syncs() - syncs == 20 && file_size(path) == size); } +/* A compacted file carries written zeros for its whole cycle: once the sizes + * settle, the commits between two compactions never grow the file (no new + * blocks, no journal commit for them). When the live data shrinks, the file + * shrinks with it. */ +static void cycles(const char *path) { + char name[512], key[16]; + snprintf(name, sizeof(name), "%s/pure.tree", path); + unsigned char big[4096], small[64]; + memset(big, 'b', sizeof(big)); + memset(small, 's', sizeof(small)); + int64_t revisions[32] = {0}; + struct stat was, now; + CHECK(stat(name, &was) == 0); + unsigned compactions = 0, grown = 0, sized = 0; + uint64_t largest = 0; + for (unsigned i = 0; i < 1600; ++i) { + snprintf(key, sizeof(key), "c%u", i % 32); + CHECK(pure_store_put(path, key, revisions[i % 32], (PureSpan){big, sizeof(big)}, &revisions[i % 32]) == PURE_OK); + CHECK(stat(name, &now) == 0); + /* Once the 32 values all exist (after the first compaction past them + * the next compacted file is sized for them), no cycle grows. */ + if (now.st_ino != was.st_ino) { + if (i >= 32 && !sized) sized = compactions + 2; + ++compactions; + } else if (sized && compactions >= sized && now.st_size != was.st_size) ++grown; + if ((uint64_t)now.st_size > largest) largest = (uint64_t)now.st_size; + was = now; + } + CHECK(sized && compactions >= sized + 4 && grown == 0); + /* The same keys with small values: a few compactions later the file is + * down to the least a fresh file has (its data and 256 KiB of zeros). */ + unsigned settled = compactions; + for (unsigned i = 0; i < 20000 && compactions < settled + 3; ++i) { + snprintf(key, sizeof(key), "c%u", i % 32); + CHECK(pure_store_put(path, key, revisions[i % 32], (PureSpan){small, sizeof(small)}, &revisions[i % 32]) == PURE_OK); + CHECK(stat(name, &now) == 0); + if (now.st_ino != was.st_ino) ++compactions; + was = now; + } + CHECK(compactions == settled + 3 && (uint64_t)now.st_size < largest / 2); +} + static void clean(const char *path) { DIR *entries = opendir(path); CHECK(entries); @@ -1115,7 +1157,7 @@ int main(void) { isolation, corruption, many_keys, revision_limit, keys, drafts, typing, draft_conflict, draft_relocation, draft_faults, draft_versions, anonymous_draft, batch, store_handle, threads, grouped, - lost_commit, pending_head, one_sync, records}; + lost_commit, pending_head, one_sync, records, cycles}; for (size_t i = 0; i < sizeof(checks) / sizeof(*checks); ++i) { char path[] = "/tmp/pure-tree-check-XXXXXX"; CHECK(mkdtemp(path) && pure_store_init(path) == PURE_OK); @@ -1126,6 +1168,7 @@ int main(void) { puts("{\"tree_store\":\"random-oracle-balance-held-views-one-byte-amplification-faults-" "process-crash-torn-head-lockless-isolation-compaction-corruption-1024-keys-revision-limit-key-listing-" "draft-oracle-typing-arena-conflict-relocation-commit-faults-held-versions-anonymous-" - "atomic-batch-runtime-keys-store-handle-threads-group-commit-lost-commit-pending-head-one-sync-records\"}"); + "atomic-batch-runtime-keys-store-handle-threads-group-commit-lost-commit-pending-head-one-sync-records-" + "cycles\"}"); return 0; } |