From 46fd0601c89a535a6501b475ff08ae11b3137ea9 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sat, 26 Sep 2026 07:12:17 +0100 Subject: 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. --- .../2026-09-26-ext4-linux-aarch64.json | 148 +++++++++++++++++++++ research/experiments/010-one-sync-commit/commits.c | 47 +++++++ research/experiments/010-one-sync-commit/probe.c | 70 ++++++++++ research/experiments/010-one-sync-commit/run.py | 63 +++++++++ 4 files changed, 328 insertions(+) create mode 100644 research/experiments/010-one-sync-commit/2026-09-26-ext4-linux-aarch64.json create mode 100644 research/experiments/010-one-sync-commit/commits.c create mode 100644 research/experiments/010-one-sync-commit/probe.c create mode 100644 research/experiments/010-one-sync-commit/run.py (limited to 'research') diff --git a/research/experiments/010-one-sync-commit/2026-09-26-ext4-linux-aarch64.json b/research/experiments/010-one-sync-commit/2026-09-26-ext4-linux-aarch64.json new file mode 100644 index 0000000..a78f512 --- /dev/null +++ b/research/experiments/010-one-sync-commit/2026-09-26-ext4-linux-aarch64.json @@ -0,0 +1,148 @@ +{ + "rounds": [ + { + "probe": [ + { + "way": "append, fsync, head, fsync (two syncs)", + "p50_ms": 9.02, + "p90_ms": 11.11, + "max_ms": 64.61 + }, + { + "way": "append, head, fdatasync", + "p50_ms": 5.75, + "p90_ms": 8.26, + "max_ms": 60.96 + }, + { + "way": "append, head, fsync", + "p50_ms": 5.69, + "p90_ms": 8.39, + "max_ms": 13.53 + }, + { + "way": "overwrite written zeros, head, fdatasync", + "p50_ms": 2.44, + "p90_ms": 5.45, + "max_ms": 67.07 + }, + { + "way": "overwrite written zeros, head, fsync", + "p50_ms": 5.7, + "p90_ms": 8.33, + "max_ms": 88.51 + } + ], + "commits": { + "two syncs": { + "commits_per_second": 103, + "p50_ms": 9.19, + "p90_ms": 11.15, + "p99_ms": 62.85 + }, + "one sync": { + "commits_per_second": 292, + "p50_ms": 2.48, + "p90_ms": 4.69, + "p99_ms": 56.77 + } + } + }, + { + "probe": [ + { + "way": "append, fsync, head, fsync (two syncs)", + "p50_ms": 9.19, + "p90_ms": 10.95, + "max_ms": 62.65 + }, + { + "way": "append, head, fdatasync", + "p50_ms": 5.82, + "p90_ms": 8.55, + "max_ms": 58.98 + }, + { + "way": "append, head, fsync", + "p50_ms": 5.66, + "p90_ms": 8.67, + "max_ms": 59.21 + }, + { + "way": "overwrite written zeros, head, fdatasync", + "p50_ms": 2.53, + "p90_ms": 6.02, + "max_ms": 61.15 + }, + { + "way": "overwrite written zeros, head, fsync", + "p50_ms": 5.75, + "p90_ms": 8.68, + "max_ms": 8.87 + } + ], + "commits": { + "one sync": { + "commits_per_second": 289, + "p50_ms": 2.44, + "p90_ms": 5.49, + "p99_ms": 53.59 + }, + "two syncs": { + "commits_per_second": 109, + "p50_ms": 8.82, + "p90_ms": 11.42, + "p99_ms": 61.67 + } + } + }, + { + "probe": [ + { + "way": "append, fsync, head, fsync (two syncs)", + "p50_ms": 8.82, + "p90_ms": 11.09, + "max_ms": 63.3 + }, + { + "way": "append, head, fdatasync", + "p50_ms": 5.61, + "p90_ms": 9.51, + "max_ms": 78.07 + }, + { + "way": "append, head, fsync", + "p50_ms": 6.21, + "p90_ms": 8.28, + "max_ms": 8.43 + }, + { + "way": "overwrite written zeros, head, fdatasync", + "p50_ms": 2.41, + "p90_ms": 4.67, + "max_ms": 58.57 + }, + { + "way": "overwrite written zeros, head, fsync", + "p50_ms": 5.07, + "p90_ms": 7.71, + "max_ms": 14.71 + } + ], + "commits": { + "two syncs": { + "commits_per_second": 94, + "p50_ms": 9.09, + "p90_ms": 12.2, + "p99_ms": 63.22 + }, + "one sync": { + "commits_per_second": 304, + "p50_ms": 2.46, + "p90_ms": 5.15, + "p99_ms": 19.8 + } + } + } + ] +} diff --git a/research/experiments/010-one-sync-commit/commits.c b/research/experiments/010-one-sync-commit/commits.c new file mode 100644 index 0000000..8bc5878 --- /dev/null +++ b/research/experiments/010-one-sync-commit/commits.c @@ -0,0 +1,47 @@ +#define _POSIX_C_SOURCE 200809L +/* Commit latency of the tree store: COMMITS sequential 16-byte inserts at + * the start of one of 64 documents, as in the HTTP put benchmark. + * commits STORE [COMMITS] -> one JSON object. */ +#include "store.h" +#include +#include +#include + +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; +} +int main(int argc, char **argv) { + if (argc < 2) return 2; + const char *path = argv[1]; + int commits = argc > 2 ? atoi(argv[2]) : 200; + if (commits < 1 || pure_store_init(path) != PURE_OK) return 1; + int64_t revision[64] = {0}; + char key[16]; + const unsigned char body[16] = "0123456789abcdef"; + for (int k = 0; k < 64; ++k) { + snprintf(key, sizeof(key), "k%d", k); + if (pure_store_put(path, key, 0, (PureSpan){body, 16}, &revision[k]) != PURE_OK) return 1; + } + double *t = malloc(sizeof(double) * (size_t)commits), start = now_ms(); + if (!t) return 1; + for (int i = 0; i < commits; ++i) { + int k = i % 64; + snprintf(key, sizeof(key), "k%d", k); + double begun = now_ms(); + if (pure_store_splice(path, key, revision[k], 0, 0, (PureSpan){body, 16}, PURE_OBJECT_LIMIT, + &revision[k]) != PURE_OK) return 1; + t[i] = now_ms() - begun; + } + double total = now_ms() - start; + qsort(t, (size_t)commits, sizeof(double), order); + printf("{\"commits_per_second\":%.0f,\"p50_ms\":%.2f,\"p90_ms\":%.2f,\"p99_ms\":%.2f}\n", commits / total * 1e3, + t[commits / 2], t[commits * 9 / 10], t[commits * 99 / 100]); + free(t); + return 0; +} 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 +#include +#include +#include +#include +#include + +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; +} diff --git a/research/experiments/010-one-sync-commit/run.py b/research/experiments/010-one-sync-commit/run.py new file mode 100644 index 0000000..9a01c07 --- /dev/null +++ b/research/experiments/010-one-sync-commit/run.py @@ -0,0 +1,63 @@ +#!/usr/bin/env python3 +"""Commit cost on the store's device (see docs/research/076-one-sync-commit.md). + +Runs probe.c (the ways of making a small commit durable) and commits.c (tree +store commit latency) built against the two-sync store of --before and the +current one, alternating their order per round so device drift reaches both +alike. Prints one JSON document. +""" +import argparse +import json +import shutil +import subprocess +import sys +import tempfile +from pathlib import Path + +HERE = Path(__file__).resolve().parent +ROOT = HERE.parents[2] +PURE = ROOT / 'prototypes' / 'connections' + + +def build(output, sources): + subprocess.run(['cc', '-O2', '-std=c17', f'-I{PURE}', '-o', str(output)] + [str(s) for s in sources] + ['-lpthread'], + check=True) + + +def main(): + parser = argparse.ArgumentParser() + parser.add_argument('--directory', type=Path, default=Path('/var/tmp'), help='on the device to measure') + parser.add_argument('--before', default='ad2197c', help='a revision with the two-sync commit') + parser.add_argument('--rounds', type=int, default=3) + parser.add_argument('--commits', type=int, default=200) + args = parser.parse_args() + with tempfile.TemporaryDirectory() as work: + work = Path(work) + before = work / 'store-tree-before.c' + before.write_text(subprocess.run(['git', '-C', str(ROOT), 'show', f'{args.before}:prototypes/connections/store-tree.c'], + capture_output=True, text=True, check=True).stdout) + build(work / 'probe', [HERE / 'probe.c']) + builds = {'two syncs': work / 'commits-before', 'one sync': work / 'commits-after'} + build(builds['two syncs'], [HERE / 'commits.c', before]) + build(builds['one sync'], [HERE / 'commits.c', PURE / 'store-tree.c']) + results = {'rounds': []} + for round_ in range(args.rounds): + probe = subprocess.run([str(work / 'probe'), str(args.directory)], capture_output=True, text=True, check=True) + measured = {'probe': [json.loads(line) for line in probe.stdout.splitlines()], 'commits': {}} + names = list(builds) if round_ % 2 == 0 else list(builds)[::-1] + for name in names: + store = Path(tempfile.mkdtemp(dir=args.directory, prefix='pure-commit-cost-')) + shutil.rmtree(store) + try: + run = subprocess.run([str(builds[name]), str(store), str(args.commits)], capture_output=True, text=True, + check=True) + measured['commits'][name] = json.loads(run.stdout) + finally: + shutil.rmtree(store, ignore_errors=True) + results['rounds'].append(measured) + print(json.dumps(measured), file=sys.stderr, flush=True) + print(json.dumps(results, indent=1)) + + +if __name__ == '__main__': + sys.exit(main()) -- cgit v1.2.3