diff options
Diffstat (limited to 'store')
| -rw-r--r-- | store/store-tree.c | 23 | ||||
| -rw-r--r-- | store/test-tree-store.c | 47 |
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; } |