aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authoreunhhu <[email protected]>2026-09-27 14:46:31 +0100
committereunhhu <[email protected]>2026-09-27 14:46:31 +0100
commitaea3f640ea59d91f7ca9b193acfcc3e26740318b (patch)
tree5329bdb7ea61881c4f73d5f646e2ff1511d95a40
parent87480ce170895f841c40930ce24a7a026646ae14 (diff)
downloadpure-aea3f640ea59d91f7ca9b193acfcc3e26740318b.tar.gz
pure-aea3f640ea59d91f7ca9b193acfcc3e26740318b.zip
Give a compacted file the zeros of its whole cycle (085)
Commits grew the tree store's tail 256 KiB at a time, each growth a sync that also committed the ext4 journal for the new size and blocks. A file installed by compaction now carries written zeros up to where the next compaction will come (4 x live + slack, plus a commit's margin), capped at the size of the file it replaces, so a store never takes more space than before and shrinks when its live data does. The cycle's commits then only overwrite blocks the file has. Store commits: 317.5 -> 385.5 a second, ext4 journal commits 109 -> 45 for 4,000 commits; durable app posts +5.3%, their p99 the same within this SD card's noise. The new cycles test keeps sizes still between compactions once the live data is whole, and shows the file shrinking with it.
-rw-r--r--docs/research/085-cycle-sized-files.md62
-rw-r--r--research/experiments/013-parallel-syncs/2026-09-27-journal-before-085-ext4-linux-aarch64.jsonl20
-rw-r--r--research/experiments/013-parallel-syncs/2026-09-27-journal-ext4-linux-aarch64.jsonl20
-rw-r--r--research/experiments/013-parallel-syncs/2026-09-27-store-variants-085-ext4-linux-aarch64.jsonl36
-rw-r--r--research/experiments/013-parallel-syncs/journal.py66
-rw-r--r--research/experiments/013-parallel-syncs/variants.py10
-rw-r--r--store/store-tree.c23
-rw-r--r--store/test-tree-store.c47
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;
}