Make a tree store commit durable with one sync

A commit used to sync its nodes, then write the head and sync again: the
order of writes was forced by syncs. Now the head carries where the
commit's bytes start and their digest, and one fdatasync makes the bytes
and the head durable together. A crash during it can leave a head whose
bytes did not all reach the device; its digest then fails and the older
slot stands, which is safe because a writer only builds on a durable head.

Commits overwrite written zeros kept after the published end, so the sync
changes neither the size nor the block map and needs no journal commit.
On the SD card this is 2.4 ms per commit against 9.1 ms for two syncs;
the store commits 289-304 times a second instead of 94-109, and pure-serve
answers 2,012-2,611 durable PUTs a second against 583 for crash-safe axum.

A process remembers the heads it published or checked, so it reads a
commit's bytes at most once and never its own. Its readers pass over the
head it is still making durable and so never answer with a commit a crash
could take back. Head slots get a block each and the format becomes
PURETRE2; a handle's refresh reads the slots through its mapping.

1 files changed, 70 insertions, 0 deletions

diff --git a/research/experiments/010-one-sync-commit/probe.c b/research/experiments/010-one-sync-commit/probe.c
new file mode 100644
index 0000000..0569192
--- /dev/null
+++ b/research/experiments/010-one-sync-commit/probe.c
@@ -0,0 +1,70 @@
+#define _GNU_SOURCE
+/* What each way of making a small commit durable costs on one device: an
+ * 8 KiB commit plus a 64-byte head, 40 times per way. The ways run
+ * round-robin so device drift reaches all of them alike.
+ * probe DIRECTORY -> one JSON object per way (milliseconds). */
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+
+static double now_ms(void) {
+    struct timespec t;
+    clock_gettime(CLOCK_MONOTONIC, &t);
+    return t.tv_sec * 1e3 + t.tv_nsec / 1e6;
+}
+static int order(const void *a, const void *b) {
+    double x = *(const double *)a, y = *(const double *)b;
+    return x < y ? -1 : x > y;
+}
+enum { WAYS = 5, ROUNDS = 40, REGION = 8192 };
+static const char *names[WAYS] = {
+    "append, fsync, head, fsync (two syncs)",
+    "append, head, fdatasync",
+    "append, head, fsync",
+    "overwrite written zeros, head, fdatasync",
+    "overwrite written zeros, head, fsync",
+};
+int main(int argc, char **argv) {
+    const char *directory = argc > 1 ? argv[1] : "/var/tmp";
+    char path[WAYS][512];
+    int fd[WAYS];
+    off_t end[WAYS];
+    static char region[REGION], head[64];
+    memset(region, 'r', sizeof(region));
+    for (int w = 0; w < WAYS; ++w) {
+        snprintf(path[w], sizeof(path[w]), "%s/pure-sync-probe-%d", directory, w);
+        fd[w] = open(path[w], O_RDWR | O_CREAT | O_TRUNC, 0600);
+        if (fd[w] < 0) return 1;
+        end[w] = 4096;
+        if (w >= 3) {
+            size_t bytes = (size_t)(ROUNDS + 2) * REGION + 4096;
+            char *zeros = calloc(1, bytes);
+            if (!zeros || pwrite(fd[w], zeros, bytes, 0) != (ssize_t)bytes) return 1;
+            free(zeros);
+        } else if (pwrite(fd[w], region, 4096, 0) != 4096) return 1;
+        fsync(fd[w]);
+    }
+    double t[WAYS][ROUNDS];
+    for (int r = 0; r < ROUNDS; ++r)
+        for (int w = 0; w < WAYS; ++w) {
+            head[0] = (char)r;
+            double start = now_ms();
+            if (pwrite(fd[w], region, REGION, end[w]) != REGION) return 1;
+            end[w] += REGION;
+            if (w == 0) fsync(fd[w]);
+            if (pwrite(fd[w], head, 64, (r % 2) * 64) != 64) return 1;
+            if (w == 1 || w == 3) fdatasync(fd[w]); else fsync(fd[w]);
+            t[w][r] = now_ms() - start;
+        }
+    for (int w = 0; w < WAYS; ++w) {
+        qsort(t[w], ROUNDS, sizeof(double), order);
+        printf("{\"way\":\"%s\",\"p50_ms\":%.2f,\"p90_ms\":%.2f,\"max_ms\":%.2f}\n", names[w], t[w][ROUNDS / 2],
+               t[w][ROUNDS * 9 / 10], t[w][ROUNDS - 1]);
+        close(fd[w]);
+        unlink(path[w]);
+    }
+    return 0;
+}