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.

2 files changed, 63 insertions, 7 deletions

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;
 }