Keep lists as images and a log of their changes, checkpointed off the owner

10 files changed, 662 insertions, 188 deletions

diff --git a/core/module-save.c b/core/module-save.c
index 0a4beaf..f0befb9 100644
--- a/core/module-save.c
+++ b/core/module-save.c
@@ -1,24 +1,46 @@
 #include "module-save.h"
 #include "module-text.h"
+#include "log.h"
 #include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 /* Stored forms. values: "PVS1", then per state {u8 type, u8 name length,
- * name, binary64 bits (little-endian)}. A list: "PLS2", u8 field count, per
- * field {u8 0 number | 1 text, u8 name length, name}, u64le the bytes of its
- * items, its items, then its journal's records to the end (module-list.h):
- * a save appends the records of the list's changes, and rewrites the items
- * with no records once the records outgrow them. "PLS1" (read, rewritten on
- * start) had no length, no records: its items reached the end. A text state:
- * its UTF-8 bytes. */
-static const unsigned char values_magic[4] = {'P', 'V', 'S', '1'}, list_magic[4] = {'P', 'L', 'S', '2'},
-                           list_magic_1[4] = {'P', 'L', 'S', '1'};
-/* Records a list keeps before its items are stored again: at least this,
- * else as many bytes as its items. So a save writes what changed, and the
- * list's stored bytes stay within twice its items (and this). */
-enum { JOURNAL_MIN = 1 << 16 };
+ * name, binary64 bits (little-endian)}. A text state: its UTF-8 bytes.
+ *
+ * A list lives in an image and in the log (core/log.h). Its image, the file
+ * image-NAME beside the store: "PLI1", u8 field count, per field {u8 0 number
+ * | 1 text, u8 name length, name}, u64le the number of the save it holds,
+ * then its items (module-list.h). The log has an entry for each save that
+ * changed lists: per list changed, {u8 name length, the name, u32le length,
+ * the records of its changes (module-list.h) in its image's fields}. A save
+ * with such an entry that also commits the tree (numbers, texts, links,
+ * documents) stores its number there as the state "seq": the entry counts
+ * only when the tree holds its number (or a later one), so both are kept or
+ * neither. A start
+ * reads each list's image and makes again the changes logged after the save
+ * it holds. A list gets an image before any change of it is logged (a new
+ * one, one stored before images, one whose record changed: in its new
+ * fields), and once its logged changes outgrow its items (and JOURNAL_MIN) a
+ * checkpoint writes its image anew from a snapshot; the log then lets go the
+ * entries every image holds. Before images a list was the tree's value
+ * "list-NAME": "PLS2" (the header, u64le the bytes of its items, its items,
+ * then records) or "PLS1" (the header, then items); a start reads it, writes
+ * its image and empties it. */
+static const unsigned char values_magic[4] = {'P', 'V', 'S', '1'}, image_magic[4] = {'P', 'L', 'I', '1'},
+                           list_magic[4] = {'P', 'L', 'S', '2'}, list_magic_1[4] = {'P', 'L', 'S', '1'};
+/* Logged changes a list keeps before its image is written again: at least
+ * JOURNAL_MIN, else as many bytes as its items; and whatever the lists, the
+ * log is kept within LOG_KEPT by writing the image that holds it back. */
+#ifdef PURE_STORE_TEST
+enum { JOURNAL_MIN = 256 };
+#define LOG_KEPT (UINT64_C(64) << 10)
+unsigned long pure_save_test_checkpoints;
+#else
+enum { JOURNAL_MIN = 1 << 20 };
+#define LOG_KEPT (UINT64_C(64) << 20)
+#endif
 /* links: "PLK1"; u8 outputs, each {u8 name length, name, u8 field count, the
  * fields' types, u64le last number} (the module's outputs, then those it
  * dropped, without fields); u16le sources, each {u8 length, the name, u64le
@@ -108,10 +130,14 @@ PURE_COLD PureResult pure_save_open_text(PureApp *app, const PureModule *m, uint
     return result;
 }
 
-static size_t list_header(const PureModule *m, uint32_t record, uint64_t items, unsigned char *out) {
+/* ---- Lists: images and the log */
+
+enum { IMAGE_HEADER = 5 + PURE_RECORD_FIELDS * (2 + PURE_MODULE_NAME) + 8 };
+
+static size_t image_header(const PureModule *m, uint32_t record, uint64_t seq, unsigned char *out) {
     const PureRecord *r = &m->record[record];
     size_t at = 0;
-    memcpy(out, list_magic, 4);
+    memcpy(out, image_magic, 4);
     at = 4;
     out[at++] = (unsigned char)r->count;
     for (unsigned f = 0; f < r->count; ++f) {
@@ -121,91 +147,309 @@ static size_t list_header(const PureModule *m, uint32_t record, uint64_t items,
         memcpy(out + at, name, strlen(name));
         at += strlen(name);
     }
-    for (unsigned b = 0; b < 8; ++b) out[at++] = (unsigned char)(items >> (8 * b));
-    return at;
+    return (size_t)(put_le(out + at, seq, 8) - out);
 }
 
-PureResult pure_save_rewrite_list(const PureModule *m, uint32_t state, const PureList *list, PureDraft *draft) {
-    size_t items = pure_list_size(list), length;
-    unsigned char header[5 + PURE_RECORD_FIELDS * (2 + PURE_MODULE_NAME) + 8], *bytes = malloc(sizeof(header) + items);
+static const char *directory_of(const PureApp *app) {
+    return app->data.directory ? app->data.directory(app->data.context) : NULL;
+}
+
+/* A list's changes as the log's entries had them at the start: the save, and
+ * the records, in the list's image's fields (valid while the log is open). */
+typedef struct { uint64_t seq; PureSpan records; } Logged;
+struct PureStartLog {
+    struct Named { char name[PURE_MODULE_NAME]; Logged *changes; size_t count, capacity; } *lists;
+    size_t count, capacity;
+    uint64_t tree, last; /* the tree's last save; the last entry that counts */
+    bool stopped, damaged;
+};
+
+static struct Named *named_list(struct PureStartLog *index, const char *name, size_t length, bool add) {
+    for (size_t i = 0; i < index->count; ++i)
+        if (strlen(index->lists[i].name) == length && !memcmp(index->lists[i].name, name, length)) return &index->lists[i];
+    if (!add) return NULL;
+    if (index->count == index->capacity) {
+        size_t capacity = index->capacity ? 2 * index->capacity : 8;
+        struct Named *grown = realloc(index->lists, capacity * sizeof(*grown));
+        if (!grown) return NULL;
+        index->lists = grown;
+        index->capacity = capacity;
+    }
+    struct Named *n = &index->lists[index->count++];
+    *n = (struct Named){{0}, NULL, 0, 0};
+    memcpy(n->name, name, length);
+    return n;
+}
+
+/* Each entry, while its save counts (a save that committed the tree counts
+ * when the tree holds its number): its lists' records, by list. */
+static bool index_entry(void *context, uint64_t seq, bool tree, PureSpan payload) {
+    struct PureStartLog *index = context;
+    if (tree && seq > index->tree) {
+        index->stopped = true;
+        return false;
+    }
+    for (size_t at = 0; at < payload.size;) {
+        size_t length = payload.data[at++];
+        if (!length || length >= PURE_MODULE_NAME || payload.size - at < length + 4) { index->damaged = true; return false; }
+        const char *name = (const char *)payload.data + at;
+        size_t records = (size_t)get_le(payload.data + at + length, 4);
+        at += length + 4;
+        if (records > payload.size - at) { index->damaged = true; return false; }
+        struct Named *list = named_list(index, name, length, true);
+        if (!list) { index->damaged = true; return false; }
+        if (list->count == list->capacity) {
+            size_t capacity = list->capacity ? 2 * list->capacity : 16;
+            Logged *grown = realloc(list->changes, capacity * sizeof(*grown));
+            if (!grown) { index->damaged = true; return false; }
+            list->changes = grown;
+            list->capacity = capacity;
+        }
+        list->changes[list->count++] = (Logged){seq, {payload.data + at, records}};
+        at += records;
+    }
+    index->last = seq;
+    return true;
+}
+
+void pure_save_close_start(PureApp *app) {
+    struct PureStartLog *index = app->start_log;
+    if (!index) return;
+    for (size_t i = 0; i < index->count; ++i) free(index->lists[i].changes);
+    free(index->lists);
+    free(index);
+    app->start_log = NULL;
+}
+
+PURE_COLD PureResult pure_save_open_log(PureApp *app) {
+    const char *directory = directory_of(app);
+    if (!directory) return PURE_OK;
+    PureResult result = pure_log_open(directory, &app->log);
+    if (result == PURE_OK) result = open_state(app, "", "seq", &app->stored_seq);
+    struct PureStartLog *index = result == PURE_OK ? calloc(1, sizeof(*index)) : NULL;
+    if (result == PURE_OK && !index) result = PURE_ALLOCATION;
+    if (result == PURE_OK && pure_draft_revision(app->stored_seq)) {
+        unsigned char *bytes;
+        size_t size;
+        result = read_whole(app->stored_seq, &bytes, &size);
+        if (result == PURE_OK) {
+            if (size == 8) index->tree = get_le(bytes, 8);
+            else result = PURE_STORE_ERROR;
+            free(bytes);
+        }
+    }
+    if (result == PURE_OK) result = pure_log_read(app->log, 0, index_entry, index);
+    if (result == PURE_OK && index->damaged) result = PURE_STORE_ERROR;
+    if (result != PURE_OK) {
+        app->start_log = index;
+        pure_save_close_start(app);
+        return result;
+    }
+    /* The entries after the last that counts are no longer the log's. */
+    if (index->stopped) pure_log_end(app->log, index->last);
+    app->seq = index->tree > index->last ? index->tree : index->last;
+    app->start_log = index;
+    return PURE_OK;
+}
+
+/* The log keeps the entries some image does not hold yet. */
+void pure_save_release(PureApp *app) {
+    if (!app->log) return;
+    uint64_t kept = app->seq + 1;
+    for (uint32_t i = 0; i < PURE_MODULE_STATES; ++i)
+        if (app->logged_since[i] && app->logged_since[i] < kept) kept = app->logged_since[i];
+    pure_log_release(app->log, kept - 1);
+}
+
+PureResult pure_save_image(PureApp *app, const PureModule *m, uint32_t state, const PureList *list) {
+    size_t items = pure_list_size(list);
+    unsigned char header[IMAGE_HEADER], *bytes = malloc(items ? items : 1);
     if (!bytes) return PURE_ALLOCATION;
-    length = list_header(m, m->state_ref[state], items, header);
-    memcpy(bytes, header, length);
-    pure_list_encode(list, bytes + length);
-    PureResult result = pure_draft_splice(draft, 0, pure_draft_size(draft), (PureSpan){bytes, length + items});
+    pure_list_encode(list, bytes);
+    PureSpan parts[2] = {{header, image_header(m, m->state_ref[state], app->seq, header)}, {bytes, items}};
+    PureResult result = pure_image_write(directory_of(app), m->state_names[state], parts, 2);
     free(bytes);
     return result;
 }
 
-PURE_COLD PureResult pure_save_open_list(PureApp *app, const PureModule *m, uint32_t state, PureList **out, PureDraft **draft,
-                               PureVersion *saved, size_t *journaled) {
+PURE_COLD PureResult pure_save_open_list(PureApp *app, const PureModule *m, uint32_t state, PureList **out,
+                                         PureDraft **legacy, PureSaved *saved) {
     uint32_t record = m->state_ref[state];
     const PureRecord *r = &m->record[record];
+    const char *name = m->state_names[state];
     *out = NULL;
-    PureResult result = open_state(app, "list-", m->state_names[state], draft);
-    if (result != PURE_OK) return result;
+    *legacy = NULL;
+    *saved = (PureSaved){0};
+    if (!directory_of(app)) return PURE_STORE_ERROR;
+    /* Its image, else what the tree kept before images. */
     unsigned char *bytes = NULL;
     size_t size = 0;
-    if (pure_draft_revision(*draft)) result = read_whole(*draft, &bytes, &size);
+    PureResult result = pure_image_read(directory_of(app), name, &bytes, &size);
+    bool image = result == PURE_OK;
+    if (result == PURE_NOT_FOUND) {
+        result = open_state(app, "list-", name, legacy);
+        if (result == PURE_OK && pure_draft_revision(*legacy) && pure_draft_size(*legacy))
+            result = read_whole(*legacy, &bytes, &size);
+    }
     /* The stored record: its fields' kinds and names. */
     char names[PURE_RECORD_FIELDS][PURE_MODULE_NAME] = {{0}};
     uint8_t text[PURE_RECORD_FIELDS] = {0};
     unsigned count = 0;
     size_t at = 0, items = 0;
-    bool stored = result == PURE_OK && bytes, first = stored && size >= 4 && !memcmp(bytes, list_magic_1, 4);
+    uint64_t holds = 0;
+    bool stored = result == PURE_OK && bytes, first = stored && !image && size >= 4 && !memcmp(bytes, list_magic_1, 4);
     if (stored) {
-        bool ok = size >= 5 && (first || !memcmp(bytes, list_magic, 4)) && bytes[4] <= PURE_RECORD_FIELDS;
+        const unsigned char *magic = image ? image_magic : first ? list_magic_1 : list_magic;
+        bool ok = size >= 5 && !memcmp(bytes, magic, 4) && bytes[4] <= PURE_RECORD_FIELDS;
         count = ok ? bytes[4] : 0;
         at = 5;
         for (unsigned f = 0; ok && f < count; ++f) {
             ok = named(bytes, size, &at, 0, &text[f], names[f]) && text[f] <= 1;
             for (unsigned k = 0; k < f; ++k) ok = ok && strcmp(names[k], names[f]);
         }
-        if (ok && !first) {
+        if (ok && image) { /* the save it holds, then its items */
+            ok = size - at >= 8;
+            holds = ok ? get_le(bytes + at, 8) : 0;
+            at += 8;
+            items = size - at;
+        } else if (ok && !first) {
             ok = size - at >= 8 && (items = (size_t)get_le(bytes + at, 8)) <= size - at - 8;
             at += 8;
         } else items = size - at;
         if (!ok) result = PURE_STORE_ERROR;
     }
-    /* The stored items, then the changes since they were stored. */
     PureList *from = NULL;
     if (result == PURE_OK && stored) {
         from = pure_list_new(count, text);
         result = from ? pure_list_read(from, bytes + at, items) : PURE_ALLOCATION;
-        if (result == PURE_OK) result = pure_list_replay(from, bytes + at + items, size - at - items);
+        if (result == PURE_OK && !image) result = pure_list_replay(from, bytes + at + items, size - at - items);
     }
-    *journaled = result == PURE_OK && stored ? size - at - items : 0;
     free(bytes);
+    /* Then the changes logged after the save it holds: only an image's
+     * list has any (one is written before any change of a list is logged). */
+    struct Named *logged = app->start_log ? named_list(app->start_log, name, strlen(name), false) : NULL;
+    for (size_t k = 0; result == PURE_OK && logged && k < logged->count; ++k) {
+        const Logged *change = &logged->changes[k];
+        if (change->seq <= holds) continue;
+        if (!image) result = PURE_STORE_ERROR;
+        else if ((result = pure_list_replay(from, change->records.data, change->records.size)) == PURE_OK) {
+            if (!saved->since) saved->since = change->seq;
+            saved->logged += change->records.size;
+        }
+    }
     bool same = stored && count == r->count;
     for (unsigned f = 0; same && f < count; ++f)
         same = text[f] == m->record_field_text[r->first + f] && !strcmp(names[f], m->record_field_names[r->first + f]);
-    if (result == PURE_OK && same && !first) {
+    if (result == PURE_OK && same && image) {
         *out = from;
-        *saved = pure_draft_version(*draft);
+        saved->image = holds;
         return PURE_OK;
     }
     if (result == PURE_OK) {
-        /* New, or stored with another record: its items move by field name. */
+        /* New, stored before images, or stored with another record (its items
+         * move by field name): its image is written before anything else of it. */
         const char *field_names[PURE_RECORD_FIELDS];
         for (unsigned f = 0; f < count; ++f) field_names[f] = names[f];
-        if (same) { /* stored in the earlier form: the same items, stored again */
+        if (same) {
             *out = from;
             from = NULL;
         } else if (from) result = pure_list_migrate(out, from, field_names, text, count, m, record);
         else if (!(*out = pure_list_new(r->count, m->record_field_text + r->first))) result = PURE_ALLOCATION;
     }
     pure_list_free(from);
-    *journaled = 0;
-    if (result == PURE_OK) result = pure_save_rewrite_list(m, state, *out, *draft);
     if (result != PURE_OK) {
         pure_list_free(*out);
-        pure_draft_close(*draft);
+        pure_draft_close(*legacy);
         *out = NULL;
-        *draft = NULL;
+        *legacy = NULL;
         return result;
     }
-    *saved = unsaved;
-    return PURE_OK;
+    *saved = (PureSaved){.rewrite = true};
+    /* What the tree kept goes: the image holds it now. */
+    if (*legacy && pure_draft_size(*legacy)) result = pure_draft_splice(*legacy, 0, pure_draft_size(*legacy), (PureSpan){0});
+    else {
+        pure_draft_close(*legacy);
+        *legacy = NULL;
+    }
+    return result;
+}
+
+/* ---- Checkpoints */
+
+struct PureCheckpoint {
+    PureSnapshot *snapshot;
+    uint32_t state;
+    char name[PURE_MODULE_NAME], *directory;
+    unsigned char header[IMAGE_HEADER];
+    size_t header_size, logged;
+    uint64_t seq, since;
+};
+
+void pure_app_background_checkpoints(PureApp *app, bool background) { app->background_checkpoints = background; }
+
+PureCheckpoint *pure_app_checkpoint(PureApp *app) {
+    const PureModule *m = app->module;
+    if (!app->log || app->checkpoint || app->open || app->uncertain || app->reading) return NULL;
+    /* A list whose logged changes outgrew its items, or, when the log grew
+     * past LOG_KEPT, the one that holds it back most. */
+    int due = -1, oldest = -1;
+    for (uint32_t i = 0; i < m->states && due < 0; ++i) {
+        if (m->state_type[i] != PURE_STATE_LIST || !app->logged_since[i]) continue;
+        size_t items = pure_list_size(app->lists[i]);
+        if (app->logged[i] > (items > JOURNAL_MIN ? items : JOURNAL_MIN)) due = (int)i;
+        else if (oldest < 0 || app->logged_since[i] < app->logged_since[oldest]) oldest = (int)i;
+    }
+    int pick = due >= 0 ? due : pure_log_bytes(app->log) > LOG_KEPT ? oldest : -1;
+    if (pick < 0) return NULL;
+    PureCheckpoint *c = calloc(1, sizeof(*c));
+    const char *directory = directory_of(app);
+    size_t length = strlen(directory) + 1;
+    if (c && (c->directory = malloc(length))) memcpy(c->directory, directory, length);
+    if (!c || !c->directory || !(c->snapshot = pure_app_snapshot(app))) {
+        if (c) free(c->directory);
+        free(c);
+        return NULL;
+    }
+    c->state = (uint32_t)pick;
+    snprintf(c->name, sizeof(c->name), "%s", m->state_names[pick]);
+    c->seq = app->seq;
+    c->header_size = image_header(m, m->state_ref[pick], c->seq, c->header);
+    c->logged = app->logged[pick];
+    c->since = app->logged_since[pick];
+    app->checkpoint = c;
+    return c;
+}
+
+PureResult pure_checkpoint_write(PureCheckpoint *c) {
+    const PureList *list = pure_snapshot_list(c->snapshot, c->state);
+    size_t items = pure_list_size(list);
+    unsigned char *bytes = malloc(items ? items : 1);
+    if (!bytes) return PURE_ALLOCATION;
+    pure_list_encode(list, bytes);
+    PureSpan parts[2] = {{c->header, c->header_size}, {bytes, items}};
+    PureResult result = pure_image_write(c->directory, c->name, parts, 2);
+    free(bytes);
+    return result;
+}
+
+void pure_app_checkpointed(PureApp *app, PureCheckpoint *c, PureResult result) {
+    if (!c) return;
+    uint32_t i = c->state;
+    if (result == PURE_OK && app->checkpoint == c) {
+        /* The image holds every change logged up to its save: those logged
+         * since stay (counted from the save after it). */
+        app->image_seq[i] = c->seq;
+        app->logged[i] -= c->logged;
+        app->logged_since[i] = app->logged[i] ? c->seq + 1 : 0;
+        pure_save_release(app);
+#ifdef PURE_STORE_TEST
+        ++pure_save_test_checkpoints;
+#endif
+    }
+    if (app->checkpoint == c) app->checkpoint = NULL;
+    pure_snapshot_release(c->snapshot);
+    free(c->directory);
+    free(c);
 }
 
 static bool scalar(uint8_t type) {
@@ -422,21 +666,26 @@ PURE_COLD PureResult pure_save_open_links(PureApp *app, const PureModule *m) {
     return result;
 }
 
-/* After a save of lists (the first count of states): kept, each list's
- * changes are stored (its journal empties), or, failed, each draft is as it
- * was; the holds the save took go either way. */
-static void settle_lists(PureApp *app, PureDraft *const *drafts, const uint32_t *states, size_t count,
-                         const PureVersion *before, const size_t *journaled, bool saved) {
-    for (size_t k = 0; k < count; ++k) {
-        uint32_t i = states[k];
-        if (app->module->state_type[i] != PURE_STATE_LIST) continue;
-        if (!saved) pure_draft_restore(drafts[k], before[i]);
-        else {
-            pure_list_forget(app->lists[i], 0);
-            app->journaled[i] = journaled[i];
-        }
-        pure_draft_hold(drafts[k], false);
+/* The lists' changes since the last save, as one log entry: per list changed,
+ * its name and its records. NULL with size 0 when no list changed. */
+static unsigned char *list_changes(const PureApp *app, size_t *size) {
+    const PureModule *m = app->module;
+    *size = 0;
+    for (uint32_t i = 0; i < m->states; ++i)
+        if (m->state_type[i] == PURE_STATE_LIST && app->lists[i] && pure_list_changes(app->lists[i]).size)
+            *size += 1 + strlen(m->state_names[i]) + 4 + pure_list_changes(app->lists[i]).size;
+    unsigned char *payload = *size ? malloc(*size) : NULL, *at = payload;
+    for (uint32_t i = 0; payload && i < m->states; ++i) {
+        PureSpan changes = m->state_type[i] == PURE_STATE_LIST && app->lists[i] ? pure_list_changes(app->lists[i]) : (PureSpan){0};
+        if (!changes.size) continue;
+        size_t length = strlen(m->state_names[i]);
+        *at++ = (unsigned char)length;
+        memcpy(at, m->state_names[i], length);
+        at = put_le(at + length, changes.size, 4);
+        memcpy(at, changes.data, changes.size);
+        at += changes.size;
     }
+    return payload;
 }
 
 PureResult pure_save_commit(PureApp *app, const double *values, void *const *documents, size_t document_count,
@@ -448,103 +697,103 @@ PureResult pure_save_commit(PureApp *app, const double *values, void *const *doc
             result = app->data.commit(app->data.context, documents[i], &revisions[i]);
         return result;
     }
+    /* A save that may or may not have been stored: until the app starts again
+     * from what the store has, no save follows it. */
+    if (app->uncertain) return PURE_CONFLICT;
     const PureModule *m = app->module;
-    PureDraft *drafts[2 * PURE_MODULE_STATES + 2];
-    uint32_t states[2 * PURE_MODULE_STATES + 2];
+    PureDraft *drafts[2 * PURE_MODULE_STATES + 3];
+    uint32_t states[2 * PURE_MODULE_STATES + 3];
     size_t count = 0;
     for (uint32_t i = 0; i < m->states; ++i) {
         PureDraft *draft = m->state_type[i] == PURE_STATE_TEXT ? app->texts[i] :
                            m->state_type[i] == PURE_STATE_LIST ? app->list_drafts[i] : NULL;
-        if (draft && (!same_version(pure_draft_version(draft), app->saved[i]) ||
-                      (m->state_type[i] == PURE_STATE_LIST && pure_list_changes(app->lists[i]).size))) {
+        if (draft && !same_version(pure_draft_version(draft), app->saved[i])) {
             states[count] = i;
             drafts[count++] = draft;
         }
     }
-    /* A list's changes go after its stored records, or, once the records
-     * would outgrow its items, the items are stored again with none. */
-    PureVersion lists_before[PURE_MODULE_STATES];
-    size_t journaled[PURE_MODULE_STATES];
-    for (size_t k = 0; k < count; ++k) {
-        uint32_t i = states[k];
-        if (m->state_type[i] != PURE_STATE_LIST) continue;
-        PureSpan changes = pure_list_changes(app->lists[i]);
-        size_t items = pure_list_size(app->lists[i]);
-        lists_before[i] = pure_draft_version(drafts[k]);
-        pure_draft_hold(drafts[k], true);
-        PureResult result = PURE_OK;
-        if (!changes.size) journaled[i] = app->journaled[i];
-        else if (app->journaled[i] + changes.size > (items > JOURNAL_MIN ? items : JOURNAL_MIN)) {
-            result = pure_save_rewrite_list(m, i, app->lists[i], drafts[k]);
-            journaled[i] = 0;
-        } else {
-            result = pure_draft_splice(drafts[k], pure_draft_size(drafts[k]), 0, changes);
-            journaled[i] = app->journaled[i] + changes.size;
-        }
-        if (result != PURE_OK) {
-            settle_lists(app, drafts, states, k + 1, lists_before, journaled, false);
-            return result;
-        }
-    }
-    size_t list_count = count;
     /* Numbers, cursors and indices: stored again only when their bytes change. */
-    PureVersion values_before = {0, 0};
-    bool values_changed = false;
+    PureVersion values_before = {0, 0}, links_before = {0, 0}, seq_before = {0, 0};
+    bool values_changed = false, links_written = false, seq_written = false;
+    PureResult result = PURE_OK;
     if (app->stored_values) {
         unsigned char encoded[VALUES_BYTES], *stored;
         size_t length = encode_values(m, values, encoded), size;
-        PureResult result = read_whole(app->stored_values, &stored, &size);
-        if (result != PURE_OK) {
-            settle_lists(app, drafts, states, list_count, lists_before, journaled, false);
-            return result;
+        result = read_whole(app->stored_values, &stored, &size);
+        if (result == PURE_OK) {
+            values_changed = size != length || memcmp(stored, encoded, length);
+            free(stored);
         }
-        values_changed = size != length || memcmp(stored, encoded, length);
-        free(stored);
         if (values_changed) {
             values_before = pure_draft_version(app->stored_values);
             pure_draft_hold(app->stored_values, true);
             result = pure_draft_splice(app->stored_values, 0, size, (PureSpan){encoded, length});
-            if (result != PURE_OK) {
-                pure_draft_hold(app->stored_values, false);
-                settle_lists(app, drafts, states, list_count, lists_before, journaled, false);
-                return result;
-            }
             states[count] = UINT32_MAX;
             drafts[count++] = app->stored_values;
         }
     }
     /* The links, written whole when they changed. */
-    PureVersion links_before = {0, 0};
-    bool links_written = false;
-    if (app->links_changed) {
-        PureResult result = app->stored_links ? PURE_OK : open_state(app, "", "links", &app->stored_links);
+    if (result == PURE_OK && app->links_changed) {
+        result = app->stored_links ? PURE_OK : open_state(app, "", "links", &app->stored_links);
         size_t length;
         unsigned char *encoded = result == PURE_OK ? encode_links(app, &length) : NULL;
         if (result == PURE_OK && !encoded) result = PURE_ALLOCATION;
         if (result == PURE_OK) {
             links_before = pure_draft_version(app->stored_links);
             pure_draft_hold(app->stored_links, true);
+            links_written = true;
             result = pure_draft_splice(app->stored_links, 0, pure_draft_size(app->stored_links), (PureSpan){encoded, length});
-            if (result != PURE_OK) pure_draft_hold(app->stored_links, false);
+            states[count] = UINT32_MAX;
+            drafts[count++] = app->stored_links;
         }
         free(encoded);
-        if (result != PURE_OK) {
-            if (values_changed) {
-                pure_draft_restore(app->stored_values, values_before);
-                pure_draft_hold(app->stored_values, false);
-            }
-            settle_lists(app, drafts, states, list_count, lists_before, journaled, false);
-            return result;
+    }
+    /* The lists' changes go to the log, one entry a save. A save that also
+     * commits the tree stores its number there: its entry counts only with it. */
+    size_t payload_size = 0;
+    unsigned char *payload = result == PURE_OK ? list_changes(app, &payload_size) : NULL;
+    if (payload_size && !payload) result = PURE_ALLOCATION;
+    bool tree = count || document_count;
+    uint64_t seq = app->seq + 1;
+    if (result == PURE_OK && tree && payload_size && app->log) {
+        result = app->stored_seq ? PURE_OK : open_state(app, "", "seq", &app->stored_seq);
+        if (result == PURE_OK) {
+            unsigned char number[8];
+            put_le(number, seq, 8);
+            seq_before = pure_draft_version(app->stored_seq);
+            pure_draft_hold(app->stored_seq, true);
+            seq_written = true;
+            result = pure_draft_splice(app->stored_seq, 0, pure_draft_size(app->stored_seq), (PureSpan){number, 8});
+            states[count] = UINT32_MAX;
+            drafts[count++] = app->stored_seq;
+        }
+    }
+    if (result == PURE_OK && payload_size) {
+        result = app->log ? pure_log_append(app->log, seq, tree, (PureSpan){payload, payload_size}) : PURE_STORE_ERROR;
+        if (result == PURE_UNCERTAIN) app->uncertain = true;
+    }
+    free(payload);
+    if (result == PURE_OK && tree) {
+        result = app->data.save(app->data.context, documents, document_count, drafts, count, revisions);
+        /* The logged entry is on the device: taken back when the tree's commit
+         * failed, or, when that may yet be stored, no save follows. */
+        if (result != PURE_OK && payload_size) {
+            if (result == PURE_UNCERTAIN) app->uncertain = true;
+            else pure_log_retract(app->log);
+        }
+    }
+    if (result == PURE_OK) {
+        for (size_t k = 0; k < count; ++k)
+            if (states[k] != UINT32_MAX) app->saved[states[k]] = pure_draft_version(drafts[k]);
+        for (uint32_t i = 0; i < m->states; ++i) {
+            PureSpan changes = m->state_type[i] == PURE_STATE_LIST && app->lists[i] ? pure_list_changes(app->lists[i]) : (PureSpan){0};
+            if (!changes.size) continue;
+            app->logged[i] += changes.size;
+            if (!app->logged_since[i]) app->logged_since[i] = seq;
+            pure_list_forget(app->lists[i], 0);
         }
-        links_written = true;
-        states[count] = UINT32_MAX;
-        drafts[count++] = app->stored_links;
-    }
-    if (!count && !document_count) return PURE_OK;
-    PureResult result = app->data.save(app->data.context, documents, document_count, drafts, count, revisions);
-    for (size_t k = 0; result == PURE_OK && k < count; ++k)
-        if (states[k] != UINT32_MAX) app->saved[states[k]] = pure_draft_version(drafts[k]);
-    settle_lists(app, drafts, states, list_count, lists_before, journaled, result == PURE_OK);
+        if (tree || payload_size) app->seq = seq;
+    }
     if (values_changed) {
         if (result != PURE_OK) pure_draft_restore(app->stored_values, values_before);
         pure_draft_hold(app->stored_values, false);
@@ -553,5 +802,9 @@ PureResult pure_save_commit(PureApp *app, const double *values, void *const *doc
         if (result != PURE_OK) pure_draft_restore(app->stored_links, links_before);
         pure_draft_hold(app->stored_links, false);
     }
+    if (seq_written) {
+        if (result != PURE_OK) pure_draft_restore(app->stored_seq, seq_before);
+        pure_draft_hold(app->stored_seq, false);
+    }
     return result;
 }
diff --git a/core/module-save.h b/core/module-save.h
index f83e294..819f948 100644
--- a/core/module-save.h
+++ b/core/module-save.h
@@ -4,25 +4,33 @@
 
 /* App states a data host keeps (docs/design/008-module-format.md), internal
  * to the module executor. Each text state is a stored draft, each list state
- * a stored draft of its items and the records of its changes since, and
- * numbers, cursors and indices are one stored value by name. A save
- * publishes what changed, all or nothing. */
+ * an image and the changes logged since, and numbers, cursors and indices
+ * are one stored value by name. A save publishes what changed, all or
+ * nothing. */
 
 bool pure_save_enabled(const PureApp *);
 /* A text state of m: its stored value, or its initial constant when none. */
 PureResult pure_save_open_text(PureApp *, const PureModule *m, uint32_t state, PureDraft **out, PureVersion *saved);
-/* A list state of m: its stored items with its stored changes made again,
- * fields moved by name when the stored record differs from m's; journaled is
- * the bytes of the records stored after its items. */
-PureResult pure_save_open_list(PureApp *, const PureModule *m, uint32_t state, PureList **out, PureDraft **draft,
-                               PureVersion *saved, size_t *journaled);
+/* Stored lists (module-save.c): at a start, the log opened and read for the
+ * lists (pure_save_open_log), each list opened from its image with its
+ * logged changes made again (pure_save_open_list; saved says what its image
+ * holds, or that it needs one: pure_save_image writes it, holding the last
+ * save), then the start's reading let go (pure_save_close_start). */
+typedef struct { uint64_t image, since; size_t logged; bool rewrite; } PureSaved;
+PureResult pure_save_open_log(PureApp *);
+PureResult pure_save_open_list(PureApp *, const PureModule *m, uint32_t state, PureList **out, PureDraft **legacy,
+                               PureSaved *saved);
+PureResult pure_save_image(PureApp *, const PureModule *m, uint32_t state, const PureList *list);
+void pure_save_close_start(PureApp *);
+/* The log keeps only the entries some list's image does not hold yet. */
+void pure_save_release(PureApp *);
+/* A snapshot's list (module.c). */
+const PureList *pure_snapshot_list(const PureSnapshot *, uint32_t state);
 /* Open the stored numbers, cursors and indices, and put each stored one of the
  * same name and kind that still fits into values, for the states of m that
  * kept marks as new (-1); texts and lists are m's. */
 PureResult pure_save_open_values(PureApp *, const PureModule *m, double *values, const int *kept,
                                  PureDraft *const *texts, PureList *const *lists);
-/* Store a list in its draft anew: header and items, no records. */
-PureResult pure_save_rewrite_list(const PureModule *m, uint32_t state, const PureList *list, PureDraft *draft);
 /* The stored links of a starting app (module.h, PureApp); CONFLICT when an
  * output with sends left is missing or has other fields. */
 PureResult pure_save_open_links(PureApp *, const PureModule *m);
diff --git a/core/module-store.c b/core/module-store.c
index 7e759fd..92200af 100644
--- a/core/module-store.c
+++ b/core/module-store.c
@@ -58,6 +58,10 @@ static PureResult save(void *context, void *const *documents, size_t document_co
     return result;
 }
 
+static const char *path_directory(void *context) { return context; }
+
+static const char *handle_directory(void *context) { return pure_store_path(context); }
+
 /* Through a store handle: documents and states share its mapping. */
 static PureResult open_handle_document(void *context, uint32_t collection, const char *key, void **document,
                                        int64_t *revision) {
@@ -78,11 +82,11 @@ static PureResult handle_state(void *context, const char *name, PureDraft **out)
 PureData pure_store_data(PureStore *store) {
     return (PureData){.context = store, .open = open_handle_document, .version = version, .read = read,
                       .splice = splice, .commit = commit, .close = close_document, .state = handle_state,
-                      .save = save};
+                      .save = save, .directory = handle_directory};
 }
 
 PureData pure_tree_data(const char *path) {
     return (PureData){.context = (void *)path, .open = open_document, .version = version,
                       .read = read, .splice = splice, .commit = commit, .close = close_document,
-                      .state = state, .save = save};
+                      .state = state, .save = save, .directory = path_directory};
 }
diff --git a/core/module.c b/core/module.c
index efa3b1d..c03d188 100644
--- a/core/module.c
+++ b/core/module.c
@@ -1,5 +1,6 @@
 #include "module.h"
 #include "module-save.h"
+#include "log.h"
 #include "module-text.h"
 #include <math.h>
 #include <stdio.h>
@@ -2439,7 +2440,7 @@ static void open_burst(PureApp *app) {
             pure_draft_hold(app->texts[i], true);
             app->durable_texts[i] = pure_draft_version(app->texts[i]);
         }
-        if (app->list_drafts[i]) app->durable_lists[i] = pure_list_changes(app->lists[i]).size;
+        if (app->lists[i]) app->durable_lists[i] = pure_list_changes(app->lists[i]).size;
     }
     app->open = true;
 }
@@ -2459,7 +2460,7 @@ static void close_burst(PureApp *app, bool keep) {
             if (!keep) pure_draft_restore(app->texts[i], app->durable_texts[i]);
             pure_draft_hold(app->texts[i], false);
         }
-        if (app->list_drafts[i] && !keep) pure_list_forget(app->lists[i], app->durable_lists[i]);
+        if (app->lists[i] && !keep) pure_list_forget(app->lists[i], app->durable_lists[i]);
     }
     if (keep) pure_undo_commit(&app->undo);
     else {
@@ -2512,6 +2513,9 @@ PureResult pure_app_save(PureApp *app) {
     PureResult result = pure_save_commit(app, app->values, documents, count, revisions);
     settle_links(app, result == PURE_OK);
     close_burst(app, result == PURE_OK);
+    /* Images due are written now, unless the host writes them on another thread. */
+    for (PureCheckpoint *c; result == PURE_OK && !app->background_checkpoints && (c = pure_app_checkpoint(app));)
+        pure_app_checkpointed(app, c, pure_checkpoint_write(c));
     return result;
 }
 
@@ -2538,6 +2542,8 @@ struct PureSnapshot {
 
 void pure_snapshot_hold(PureSnapshot *snapshot) { __atomic_add_fetch(&snapshot->refs, 1, __ATOMIC_RELAXED); }
 
+const PureList *pure_snapshot_list(const PureSnapshot *snapshot, uint32_t state) { return snapshot->lists[state]; }
+
 void pure_snapshot_release(PureSnapshot *snapshot) {
     while (snapshot && !__atomic_sub_fetch(&snapshot->refs, 1, __ATOMIC_ACQ_REL)) {
         PureSnapshot *newer = snapshot->newer;
@@ -2571,6 +2577,9 @@ void pure_app_stop(PureApp *app) {
     free(app->heard);
     free(app->carried);
     pure_draft_close(app->stored_links);
+    pure_draft_close(app->stored_seq);
+    pure_save_close_start(app);
+    pure_log_close(app->log);
     free(app->pending);
     pure_undo_free(&app->undo);
     for (unsigned i = 0; i < app->row_tables; ++i) free(app->rows[i].items);
@@ -2595,7 +2604,7 @@ static void mark_event(PureApp *app, Mark *mark) {
     open_burst(app);
     for (uint32_t i = 0; i < app->module->states; ++i) {
         if (app->texts[i]) mark->texts[i] = pure_draft_version(app->texts[i]);
-        if (app->list_drafts[i]) mark->lists[i] = pure_list_changes(app->lists[i]).size;
+        if (app->lists[i]) mark->lists[i] = pure_list_changes(app->lists[i]).size;
     }
     mark->undo = app->undo.count;
     mark->sent = app->sent_count;
@@ -2605,7 +2614,7 @@ static void mark_event(PureApp *app, Mark *mark) {
 static void undo_event(PureApp *app, const Mark *mark) {
     for (uint32_t i = 0; i < app->module->states; ++i) {
         if (app->texts[i]) pure_draft_restore(app->texts[i], mark->texts[i]);
-        if (app->list_drafts[i]) pure_list_forget(app->lists[i], mark->lists[i]);
+        if (app->lists[i]) pure_list_forget(app->lists[i], mark->lists[i]);
     }
     pure_undo_rollback(&app->undo, mark->undo);
     drop_sent(app, mark->sent);
@@ -3233,15 +3242,18 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module)
     double values[PURE_MODULE_STATES] = {0};
     PureDraft *texts[PURE_MODULE_STATES] = {0}, *list_drafts[PURE_MODULE_STATES] = {0};
     PureList *lists[PURE_MODULE_STATES] = {0};
-    PureVersion saved[PURE_MODULE_STATES] = {{0, 0}}, before[PURE_MODULE_STATES] = {{0, 0}};
-    size_t journaled[PURE_MODULE_STATES] = {0};
+    PureVersion saved[PURE_MODULE_STATES] = {{0, 0}};
+    PureSaved listed[PURE_MODULE_STATES] = {{0}};
     int kept[PURE_MODULE_STATES];
     bool rewrite[PURE_MODULE_STATES] = {false};
-    PureResult result = PURE_OK;
+    /* Lists are stored where the host names a directory for them (module-save.c). */
+    bool lists_stored = stored && app->data.directory && app->data.directory(app->data.context);
+    if (old && app->checkpoint) return PURE_CONFLICT; /* the host has a checkpoint of the running module out */
+    PureResult result = !old && lists_stored ? pure_save_open_log(app) : PURE_OK;
     for (uint32_t i = 0; i < module->states; ++i) {
         int previous = old ? pure_module_state(old, module->state_names[i]) : -1;
         kept[i] = previous >= 0 && old->state_type[previous] == module->state_type[i] ? previous : -1;
-        if (kept[i] >= 0) saved[i] = app->saved[kept[i]], journaled[i] = app->journaled[kept[i]];
+        if (kept[i] >= 0) saved[i] = app->saved[kept[i]];
         if (module->state_type[i] == PURE_STATE_TEXT) {
             if (kept[i] >= 0) texts[i] = app->texts[kept[i]];
             else if (result == PURE_OK)
@@ -3249,13 +3261,17 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module)
                          new_text(&texts[i], module, module->state_ref[i]);
         } else if (module->state_type[i] == PURE_STATE_LIST) {
             if (result != PURE_OK) continue;
+            bool rows = module->state_flags[i] & PURE_LIST_ROWS >> 8; /* rows are never stored */
             if (kept[i] >= 0) {
                 result = keep_list(&lists[i], app->lists[kept[i]], old, old->state_ref[kept[i]], module,
                                    module->state_ref[i]);
                 list_drafts[i] = app->list_drafts[kept[i]];
-                rewrite[i] = result == PURE_OK && list_drafts[i] && lists[i] != app->lists[kept[i]];
-            } else if (stored && !(module->state_flags[i] & PURE_LIST_ROWS >> 8)) { /* rows are never stored */
-                result = pure_save_open_list(app, module, i, &lists[i], &list_drafts[i], &saved[i], &journaled[i]);
+                listed[i] = (PureSaved){app->image_seq[kept[i]], app->logged_since[kept[i]], app->logged[kept[i]], false};
+                /* Its record changed: its image, in the new fields, holds it before any change is logged. */
+                rewrite[i] = result == PURE_OK && lists_stored && !rows && lists[i] != app->lists[kept[i]];
+            } else if (lists_stored && !rows) {
+                result = pure_save_open_list(app, module, i, &lists[i], &list_drafts[i], &listed[i]);
+                rewrite[i] = result == PURE_OK && listed[i].rewrite;
             } else if (!(lists[i] = new_list(module, module->state_ref[i]))) result = PURE_ALLOCATION;
         } else values[i] = kept[i] >= 0 ? app->values[kept[i]] : module->initial[i];
     }
@@ -3276,7 +3292,7 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module)
         }
         if (kept[i] < 0 || lists[i] != app->lists[kept[i]]) pure_list_free(lists[i]);
         lists[i] = sorted;
-        rewrite[i] = list_drafts[i] != NULL;
+        rewrite[i] = lists_stored && !(module->state_flags[i] & PURE_LIST_ROWS >> 8);
     }
     /* A cursor or index keeps its position only while its text or list is the
      * one it belonged to. */
@@ -3295,23 +3311,22 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module)
             values[i] = (double)moved[list][(size_t)values[i]];
     }
     for (uint32_t i = 0; i < module->states; ++i) free(moved[i]);
-    /* Store the lists whose record or order changed last, so that a failure
-     * can put every draft back as it was. */
-    for (uint32_t i = 0; i < module->states; ++i)
-        if (rewrite[i]) {
-            before[i] = pure_draft_version(list_drafts[i]);
-            pure_draft_hold(list_drafts[i], true);
-        }
+    if (!old) pure_save_close_start(app);
+    /* Images last, once nothing else can fail: first of the lists the new
+     * module drops whose changes are only logged (the log lets them go),
+     * then of the lists that need one. An image written cannot be taken
+     * back: a running app that fails here saves nothing more until it starts
+     * again, from what the store has. */
+    bool imaged = result == PURE_OK;
+    for (uint32_t j = 0; result == PURE_OK && old && j < old->states; ++j) {
+        bool dropped = old->state_type[j] == PURE_STATE_LIST && app->logged_since[j];
+        for (uint32_t i = 0; dropped && i < module->states; ++i) dropped = kept[i] != (int)j;
+        if (dropped) result = pure_save_image(app, old, j, app->lists[j]);
+    }
     for (uint32_t i = 0; i < module->states && result == PURE_OK; ++i)
-        if (rewrite[i]) {
-            result = pure_save_rewrite_list(module, i, lists[i], list_drafts[i]);
-            journaled[i] = 0;
-        }
-    for (uint32_t i = 0; i < module->states; ++i)
-        if (rewrite[i]) {
-            if (result != PURE_OK) pure_draft_restore(list_drafts[i], before[i]);
-            pure_draft_hold(list_drafts[i], false);
-        }
+        if (rewrite[i] && (result = pure_save_image(app, module, i, lists[i])) == PURE_OK)
+            listed[i] = (PureSaved){.image = app->seq};
+    if (imaged && result != PURE_OK && old) app->uncertain = true;
     if (result != PURE_OK) {
         for (uint32_t i = 0; i < module->states; ++i) {
             if (kept[i] >= 0) {
@@ -3340,10 +3355,17 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module)
     memcpy(app->texts, texts, sizeof(texts));
     memcpy(app->lists, lists, sizeof(lists));
     memcpy(app->list_drafts, list_drafts, sizeof(list_drafts));
-    memcpy(app->journaled, journaled, sizeof(journaled));
     memcpy(app->saved, saved, sizeof(saved));
+    for (uint32_t i = 0; i < PURE_MODULE_STATES; ++i) {
+        app->image_seq[i] = listed[i].image;
+        app->logged_since[i] = listed[i].since;
+        app->logged[i] = listed[i].logged;
+    }
+    pure_save_release(app);
     for (uint32_t i = 0; i < module->states; ++i) {
-        if (list_drafts[i]) pure_list_journal(lists[i], true); /* a stored list's changes are recorded from now on */
+        /* A stored list's changes are recorded from now on. */
+        if (lists_stored && module->state_type[i] == PURE_STATE_LIST && !(module->state_flags[i] & PURE_LIST_ROWS >> 8))
+            pure_list_journal(lists[i], true);
         /* Without memory for its keys a keyed list is still searched, only slower. */
         if (module->state_type[i] == PURE_STATE_LIST)
             (void)pure_list_keyed(lists[i], module->state_key[i] ? (int)module->state_key[i] - 1 : -1);
diff --git a/core/module.h b/core/module.h
index c8a5f3d..e5556fe 100644
--- a/core/module.h
+++ b/core/module.h
@@ -237,6 +237,10 @@ typedef struct {
     PureResult (*state)(void *context, const char *name, PureDraft **out);
     PureResult (*save)(void *context, void *const *documents, size_t document_count, PureDraft *const *states,
                        size_t count, int64_t *revisions);
+    /* Optional, with state and save: the directory where the app's lists are
+     * kept, their images and the log of their changes (core/log.h); without
+     * one, list states are not stored. */
+    const char *(*directory)(void *context);
 } PureData;
 
 /* A byte or text value inside one event or view: a range of the payload, a
@@ -264,8 +268,20 @@ typedef struct {
     PureDraft *texts[PURE_MODULE_STATES];
     PureList *lists[PURE_MODULE_STATES];
     PureUndo undo; /* list changes of the current event */
-    PureDraft *list_drafts[PURE_MODULE_STATES]; /* stored lists, when kept */
-    size_t journaled[PURE_MODULE_STATES];       /* a stored list's record bytes after its items */
+    PureDraft *list_drafts[PURE_MODULE_STATES]; /* lists the tree kept before images, until emptied */
+    /* Stored lists (module-save.c): the save each one's image holds, the
+     * first save logged since that changed it (0: none), and the bytes of its
+     * changes logged since; the log, the tree's number of its last save, the
+     * last save's number, and a checkpoint being written. */
+    uint64_t image_seq[PURE_MODULE_STATES], logged_since[PURE_MODULE_STATES];
+    size_t logged[PURE_MODULE_STATES];
+    struct PureLog *log;
+    PureDraft *stored_seq;
+    uint64_t seq;
+    struct PureCheckpoint *checkpoint;
+    struct PureStartLog *start_log; /* the log as read at a start, while lists open */
+    bool background_checkpoints;
+    bool uncertain; /* a save may or may not be stored: none follows until a start */
     PureDraft *stored_values;                   /* numbers, cursors and indices, when kept */
     PureVersion saved[PURE_MODULE_STATES];      /* text and list versions at the last save */
     /* Events since the last save: what a failed save returns to, and the
@@ -422,6 +438,18 @@ PureResult pure_app_deliver(PureApp *, uint32_t input, const char *source, uint6
  * without a data host that keeps states), or when memory runs out. The caller
  * gets a reference; the app keeps its own until the next snapshot. */
 typedef struct PureSnapshot PureSnapshot;
+/* Checkpoints (with a directory for lists): a list whose logged changes
+ * outgrew its items gets a new image, written from a snapshot, and then the
+ * log lets go the entries the images hold. By default each save writes the
+ * images due before it returns. With background checkpoints the host takes
+ * one due after a save (NULL: none, or one is still out), writes it on any
+ * thread, and hands the result back on the app's thread before the app stops
+ * or is replaced. */
+typedef struct PureCheckpoint PureCheckpoint;
+void pure_app_background_checkpoints(PureApp *, bool background);
+PureCheckpoint *pure_app_checkpoint(PureApp *);
+PureResult pure_checkpoint_write(PureCheckpoint *);
+void pure_app_checkpointed(PureApp *, PureCheckpoint *, PureResult);
 PureSnapshot *pure_app_snapshot(PureApp *);
 void pure_snapshot_hold(PureSnapshot *);
 /* On any thread; the last reference frees it. */
diff --git a/core/state.h b/core/state.h
index 2bf78b0..96410b3 100644
--- a/core/state.h
+++ b/core/state.h
@@ -27,6 +27,7 @@ PureResult pure_state_open(const char *path, const char *name, PureDraft **out);
  * its drafts. */
 typedef struct PureStore PureStore;
 PureResult pure_store_open(const char *path, PureStore **out);
+const char *pure_store_path(const PureStore *);
 void pure_store_close(PureStore *);
 PureResult pure_store_draft(PureStore *, const char *key, PureDraft **out);
 PureResult pure_store_state(PureStore *, const char *name, PureDraft **out);
diff --git a/core/test-module.c b/core/test-module.c
index 8ca031c..d361f4f 100644
--- a/core/test-module.c
+++ b/core/test-module.c
@@ -4,6 +4,7 @@
 #include "module-text.h"
 #include "store.h"
 #include <dirent.h>
+#include <fcntl.h>
 #include <math.h>
 #include <pthread.h>
 #include <stdio.h>
@@ -506,7 +507,7 @@ static void fake_close(void *context, void *document) {
 }
 
 static PureData fake_data(Memory *m) {
-    return (PureData){m, fake_open, fake_version, fake_read, fake_splice, fake_commit, fake_close, NULL, NULL};
+    return (PureData){m, fake_open, fake_version, fake_read, fake_splice, fake_commit, fake_close, NULL, NULL, NULL};
 }
 
 typedef struct { unsigned char bytes[256]; size_t size, spans; } Collected;
@@ -1725,6 +1726,25 @@ static void stored_crashes(void) {
         CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_OK && consistent(&app) == expected);
         pure_app_stop(&app);
     }
+    /* The list's change goes to the log before the tree commits: dying before
+     * or after writing it there, the save's entry does not count (the tree
+     * has not its number), and all three are as before. */
+    for (int stage = PURE_LOG_BEFORE_WRITE; stage <= PURE_LOG_BEFORE_SYNC; ++stage) {
+        pid_t child = fork();
+        CHECK(child >= 0);
+        if (!child) {
+            PureApp doomed;
+            if (pure_app_start(&doomed, &module_a, pure_tree_data(path)) != PURE_OK) _exit(1);
+            crash = 1;
+            fail_stage = stage;
+            pure_app_input(&doomed, 0, PURE_EDGE_DOWN);
+            _exit(0);
+        }
+        int status;
+        CHECK(waitpid(child, &status, 0) == child && WIFEXITED(status) && WEXITSTATUS(status) == 77);
+        CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_OK && consistent(&app) == expected);
+        pure_app_stop(&app);
+    }
     /* A failed commit leaves the app and the store as they were; after an
      * uncertain one the app no longer matches the store and its events fail
      * until it starts again, from what the store has. */
@@ -1739,6 +1759,21 @@ static void stored_crashes(void) {
     pure_app_stop(&app);
     CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_OK && consistent(&app) == expected + 1);
     CHECK(pure_app_input(&app, 0, PURE_EDGE_DOWN) == PURE_OK && consistent(&app) == expected + 2);
+    /* The log refusing its entry fails the save and changes nothing; the log
+     * failing its sync leaves it uncertain: no save follows until the app
+     * starts again, and then the entry does not count (the tree has not its
+     * number). */
+    fail_stage = PURE_LOG_BEFORE_WRITE;
+    CHECK(pure_app_input(&app, 0, PURE_EDGE_DOWN) == PURE_STORE_ERROR && consistent(&app) == expected + 2);
+    fail_stage = PURE_LOG_BEFORE_SYNC;
+    CHECK(pure_app_input(&app, 0, PURE_EDGE_DOWN) == PURE_UNCERTAIN && consistent(&app) == expected + 2);
+    fail_stage = -1;
+    CHECK(pure_app_input(&app, 0, PURE_EDGE_DOWN) == PURE_CONFLICT);
+    pure_app_stop(&app);
+    CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_OK && consistent(&app) == expected + 2);
+    CHECK(pure_app_input(&app, 0, PURE_EDGE_DOWN) == PURE_OK && consistent(&app) == expected + 3);
+    pure_app_stop(&app);
+    CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_OK && consistent(&app) == expected + 3);
     pure_app_stop(&app);
     remove_store(path);
 }
@@ -1853,17 +1888,24 @@ static void stored_migration(void) {
     CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_OK);
     CHECK(app.values[0] == 9 && app.values[2] == 0 && app.values[4] == 0);
     pure_app_stop(&app);
-    /* Damaged stored lists and texts are refused, not replaced. */
-    const char *damaged[] = {"list-tasks", "text-note"};
-    for (unsigned k = 0; k < 2; ++k) {
-        PureDraft *draft;
-        CHECK(pure_state_open(path, damaged[k], &draft) == PURE_OK);
-        CHECK(pure_draft_splice(draft, 0, 0, (PureSpan){(const unsigned char *)"\xff", 1}) == PURE_OK);
-        CHECK(pure_draft_commit(draft, &revision) == PURE_OK);
-        CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_STORE_ERROR);
-        CHECK(pure_draft_splice(draft, 0, 1, (PureSpan){0}) == PURE_OK && pure_draft_commit(draft, &revision) == PURE_OK);
-        pure_draft_close(draft);
-    }
+    /* Damaged stored lists (their images) and texts are refused, not replaced. */
+    char image[128];
+    snprintf(image, sizeof(image), "%s/image-tasks", path);
+    int fd = open(image, O_RDWR);
+    unsigned char byte;
+    CHECK(fd >= 0 && pread(fd, &byte, 1, 20) == 1);
+    byte ^= 0x40;
+    CHECK(pwrite(fd, &byte, 1, 20) == 1);
+    CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_STORE_ERROR);
+    byte ^= 0x40;
+    CHECK(pwrite(fd, &byte, 1, 20) == 1 && !close(fd));
+    PureDraft *draft;
+    CHECK(pure_state_open(path, "text-note", &draft) == PURE_OK);
+    CHECK(pure_draft_splice(draft, 0, 0, (PureSpan){(const unsigned char *)"\xff", 1}) == PURE_OK);
+    CHECK(pure_draft_commit(draft, &revision) == PURE_OK);
+    CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_STORE_ERROR);
+    CHECK(pure_draft_splice(draft, 0, 1, (PureSpan){0}) == PURE_OK && pure_draft_commit(draft, &revision) == PURE_OK);
+    pure_draft_close(draft);
     CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_OK);
     CHECK(pure_list_count(app.lists[TASKS]) == 3 && pure_draft_size(app.texts[NOTE]) == 3 && app.values[0] == 9);
     pure_app_stop(&app);
@@ -1871,10 +1913,14 @@ static void stored_migration(void) {
     remove_store(path);
 }
 
+extern unsigned long pure_save_test_checkpoints;
+
 static void stored_states(void) {
     static const char *const list_words[] = {"a", "\xea\xb0\x80", "", "\n", "\xf0\x9f\x98\x80"};
     static const char *const text_words[] = {"a", "\xea\xb0\x80", "\n", "\xf0\x9f\x98\x80", "xy\nz", ""};
+    unsigned long checkpoints = pure_save_test_checkpoints;
     stored_equivalence(list_spec, list_words, LEN(list_words), 0x9e3779b9u);
+    CHECK(pure_save_test_checkpoints > checkpoints + 5); /* images written again as the log grew */
     stored_equivalence(text_spec, text_words, LEN(text_words), 0x7f4a7c15u);
     stored_crashes();
     stored_frames();
@@ -3468,8 +3514,9 @@ static void snapshots_kept(Spec spec, const Spec *other, void (*event)(PureApp *
         event(&app, &seed);
         if (!app.open) continue;
         CHECK(!pure_app_snapshot(&app));
-        fail_stage = PURE_AFTER_HEADER;
-        saved = pure_app_save(&app); /* OK when the event changed nothing */
+        /* Its lists' changes fail before the log has them, the rest before the tree does. */
+        fail_stage = tries % 2 ? PURE_AFTER_HEADER : PURE_LOG_BEFORE_WRITE;
+        saved = pure_app_save(&app); /* OK when the event changed nothing the stage stores */
         fail_stage = -1;
     }
     CHECK(saved == PURE_STORE_ERROR);
diff --git a/docs/design/008-module-format.md b/docs/design/008-module-format.md
index 233f39b..d515c12 100644
--- a/docs/design/008-module-format.md
+++ b/docs/design/008-module-format.md
@@ -264,16 +264,36 @@ text·리스트가 남을 때만 위치를 유지한다.
 | 상태 | 저장 형태 (런타임 이름공간, 문서 키와 겹치지 않음) |
 |---|---|
 | text | `text-이름`: UTF-8 바이트 그대로. 앱의 draft가 곧 저장 문서라 입력 한 글자는 바뀐 익스텐트만 추가한다 |
-| 리스트 | `list-이름`: `PLS2`, 레코드 필드 수, 필드마다 종류·이름, 항목의 바이트 수(u64), 항목(수는 binary64, text는 u32 길이와 바이트), 그 뒤 끝까지 변경 기록(저널). 기록은 종류(u8: 1 삽입, 2 제거, 3 설정)와 위치(u32), 그리고 삽입이면 항목, 설정이면 필드(u8)와 값이다. 리스트 연산은 메모리의 항목을 바꾸고 기록을 남긴다. 저장은 기록을 문서 끝에 붙인다. 붙은 기록이 항목의 바이트 수(최소 64 KiB)를 넘게 되면 그 저장은 항목을 새로 쓰고 기록을 비운다. 시작은 항목을 읽고 기록을 차례로 다시 적용한다. `PLS1`(길이·기록 없음)은 읽고 시작할 때 `PLS2`로 다시 쓴다 |
+| 리스트 | 이미지와 로그(아래). 트리에는 두지 않는다 |
 | 수·커서·인덱스 | `values`: `PVS1`, 상태마다 종류·이름·binary64. 바뀐 이벤트에서만 다시 쓴다 |
 
-- **시작.** 저장된 상태를 이름과 종류로 불러온다. 없는 상태는 초기값으로 시작한다. 레코드가 달라진 리스트는
+- **리스트: 이미지와 로그.** 리스트는 저장소 디렉터리의 두 곳에 산다. **이미지** `image-이름`(파일 하나)은
+  `PLI1`, 레코드 필드 수, 필드마다 종류·이름, 그것이 담은 저장의 번호(u64), 항목(수는 binary64, text는 u32 길이와
+  바이트)이고, 통째로 옆에 써서 동기화한 뒤 이름을 바꿔 끼운다(파일 전체의 다이제스트로 잘림·손상을 거부).
+  **로그**(`log-0`, `log-1`, ... 구간, `core/log.h`)는 리스트를 바꾼 저장마다 항목 하나다. 항목은 저장 번호, 앞 항목의
+  번호와 다이제스트, 트리도 커밋했는지, 페이로드(바뀐 리스트마다 이름과 변경 기록: 종류 u8(1 삽입, 2 제거, 3 설정),
+  위치 u32, 삽입이면 항목, 설정이면 필드와 값, 모두 그 리스트 이미지의 필드로)다. 구간은 처음 만들 때 통째로 할당하고,
+  이미지가 모두 담은 항목만 가진 구간은 다시 쓴다. 그래서 덧붙이기는 파일을 키우지도 새 블록을 받지도 않아 동기화가
+  데이터만 쓴다. 항목은 앞 항목의 다이제스트를 가리키므로 찢긴 쓰기나 재사용한 구간에 남은 옛 바이트는 이어지지 않는다.
+- **저장 번호.** 저장마다 번호가 하나 오른다. 로그 항목이 있고 트리도 커밋하는 저장은 그 번호를 트리의 상태 `seq`에
+  함께 쓴다. 트리도 커밋한 저장의 로그 항목은 트리가 그 번호(이상)를 가질 때만 센다. 그래서 로그를 먼저 쓰고 트리를
+  나중에 커밋하는 사이에 죽어도 둘 다 남거나 둘 다 없다. 트리 커밋이 확실히 실패하면 로그 항목을 거둬 다음 저장이 그
+  자리에 쓰고, 동기화가 실패해 저장 여부를 모르면(불확실) 앱은 다시 시작할 때까지 저장하지 않는다(`conflict`).
+- **체크포인트.** 리스트의 로그 기록이 항목 바이트(최소 1 MiB)를 넘으면, 또는 로그가 64 MiB를 넘으면 그것을 가장
+  오래 붙잡은 리스트의 이미지를 스냅숏에서 새로 쓰고, 로그는 모든 이미지가 담은 항목을 놓는다. 기본은 저장 직후
+  같은 스레드에서 쓰고, `pure_app_background_checkpoints`면 호스트가 다른 스레드에서 쓴다(pure-serve). 리스트는 로그에
+  변경이 적히기 전에 이미지를 가진다: 새 리스트, 이미지 이전에 저장된 리스트, 레코드가 바뀐 리스트(새 필드로)는 시작이나
+  교체 때 이미지를 먼저 쓴다. 교체 중 이미지 쓰기가 실패하면 앱은 다시 시작할 때까지 저장하지 않는다.
+- **이미지 이전 형식.** 트리의 `list-이름`(`PLS2`: 머리글, 항목 바이트 수 u64, 항목, 기록 / `PLS1`: 머리글, 항목)은
+  시작할 때 읽어 이미지를 쓰고 비운다.
+- **시작.** 저장된 상태를 이름과 종류로 불러온다. 리스트는 이미지를 읽고 로그에서 그 이미지가 담은 저장 뒤의 변경을
+  차례로 다시 한다. 없는 상태는 초기값으로 시작한다. 레코드가 달라진 리스트는
   이름·종류가 같은 필드를 옮기고 새 필드는 기본값을 쓴 뒤 다시 저장한다(교체와 같은 규칙, 마이그레이션 스크립트 없음).
   커서가 text 범위나 글자 경계를 벗어나거나, 인덱스가 리스트 밖이면 0이 된다. 깨진 리스트·text(형식 오류, UTF-8
   아님)는 시작을 `store_error`로 멈춘다. 조용히 버리지 않는다.
 - **저장은 묶음이다.** 저장 한 번이 마지막 저장 이후 메시지가 고친 문서들과 바뀐 상태 문서들을 저장소의
-  **한 커밋**(`pure_draft_commit_all`)으로 공개한다. 모두 보이거나 하나도 보이지 않는다. 저장이 실패하면 마지막 저장
-  이후의 이벤트가 **모두** 되돌려진다(값, text와 리스트 draft, 리스트 되돌리기 기록과 저널, 이벤트·tick 수). 그래서
+  **한 커밋**(`pure_draft_commit_all`)과 로그 항목 하나로 공개한다. 모두 보이거나 하나도 보이지 않는다. 저장이 실패하면
+  마지막 저장 이후의 이벤트가 **모두** 되돌려진다(값, text draft, 리스트 되돌리기 기록과 저널, 이벤트·tick 수). 그래서
   "성공을 알린 이벤트는 저장됐고, 실패를 알린 이벤트는 흔적이 없다"가 성립한다. 결과 불명(`uncertain`)이나 다른
   기록자와의 충돌 뒤에는 앱이 저장소와 어긋나 이후 저장이 충돌로 실패한다. 다시 시작하면 저장소의 상태로 이어진다.
 - **기본은 이벤트마다 저장.** 키·text·메시지 이벤트는 저장까지 마치고 돌아온다(묶음 크기 1). 초당 60번 오는
diff --git a/serve/serve.c b/serve/serve.c
index 53d9ce0..8b4f172 100644
--- a/serve/serve.c
+++ b/serve/serve.c
@@ -193,8 +193,91 @@ typedef struct {
     unsigned wire_count;
     uint64_t trimmed[PURE_MODULE_INPUTS], answers;
     bool held[PURE_MODULE_INPUTS]; /* an answer failed to apply: the wire's sends stay until a restart */
+    struct Writer *writer; /* the thread writing the app's checkpoints, once one was due */
+    uint64_t checkpoints;  /* images it wrote */
 } Executor;
 
+/* The images of the app's lists are written on a thread of their own
+ * (pure_app_checkpoint): the owner hands one over after a save, and takes
+ * it back, written, after a later one. */
+typedef struct Writer {
+    pthread_mutex_t lock;
+    pthread_cond_t wake;
+    pthread_t thread;
+    PureCheckpoint *taken, *written;
+    PureResult result;
+    bool stopping;
+} Writer;
+
+static void *run_writer(void *context) {
+    Writer *w = context;
+    pthread_mutex_lock(&w->lock);
+    for (;;) {
+        while (!w->taken && !w->stopping) pthread_cond_wait(&w->wake, &w->lock);
+        if (!w->taken) break;
+        PureCheckpoint *c = w->taken;
+        pthread_mutex_unlock(&w->lock);
+        PureResult result = pure_checkpoint_write(c);
+        pthread_mutex_lock(&w->lock);
+        w->taken = NULL;
+        w->written = c;
+        w->result = result;
+    }
+    pthread_mutex_unlock(&w->lock);
+    return NULL;
+}
+
+/* After a save: a checkpoint written is handed back, and one due handed over. */
+static void checkpoint_round(Executor *ex) {
+    Writer *w = ex->writer;
+    if (w) {
+        pthread_mutex_lock(&w->lock);
+        PureCheckpoint *written = w->written;
+        PureResult result = w->result;
+        w->written = NULL;
+        pthread_mutex_unlock(&w->lock);
+        if (written) {
+            pure_app_checkpointed(&ex->app, written, result);
+            ex->checkpoints += result == PURE_OK;
+        }
+    }
+    PureCheckpoint *due = pure_app_checkpoint(&ex->app);
+    if (!due) return;
+    if (!w) {
+        w = calloc(1, sizeof(*w));
+        if (!w || pthread_mutex_init(&w->lock, NULL) || pthread_cond_init(&w->wake, NULL) ||
+            pthread_create(&w->thread, NULL, run_writer, w)) {
+            free(w); /* written here instead */
+            pure_app_checkpointed(&ex->app, due, pure_checkpoint_write(due));
+            return;
+        }
+        ex->writer = w;
+    }
+    pthread_mutex_lock(&w->lock);
+    w->taken = due;
+    pthread_cond_signal(&w->wake);
+    pthread_mutex_unlock(&w->lock);
+}
+
+/* The writer finishes the image it writes, which goes back to the app. */
+static void stop_writer(Executor *ex) {
+    Writer *w = ex->writer;
+    if (!w) return;
+    pthread_mutex_lock(&w->lock);
+    w->stopping = true;
+    pthread_cond_signal(&w->wake);
+    pthread_mutex_unlock(&w->lock);
+    pthread_join(w->thread, NULL);
+    if (w->written) {
+        pure_app_checkpointed(&ex->app, w->written, w->result);
+        ex->checkpoints += w->result == PURE_OK;
+    }
+    pthread_mutex_destroy(&w->lock);
+    pthread_cond_destroy(&w->wake);
+    free(w);
+    ex->writer = NULL;
+}
+
 /* A request made ready: its effect, what it names, and the thread that
  * answers it (or, for a surface's event, the waiter it wakes). */
 typedef struct { Host *host; PureEffect effect; Route route; Waiter *waiter; } Job;
@@ -1402,6 +1485,7 @@ static bool find_fresh(void *context, uint32_t output, uint64_t seq, PureSpan pa
 
 static void after_save(Executor *ex) {
     publish(ex);
+    checkpoint_round(ex);
     if (!ex->wire_count) return;
     Queueing q = {.executor = ex};
     pure_app_outbox_newest(&ex->app, find_fresh, &q);
@@ -2045,10 +2129,12 @@ static bool start_executor(Executor *ex, const PureModule *module, uint32_t show
         fputs("Cannot start the module on the store\n", stderr);
         return false;
     }
+    pure_app_background_checkpoints(&ex->app, true);
     return true;
 }
 
 static void stop_executor(Executor *ex) {
+    stop_writer(ex);
     pure_snapshot_release(ex->published);
     pure_app_stop(&ex->app);
     pure_store_close(ex->store);
@@ -2428,7 +2514,7 @@ int main(int argc, char **argv) {
     }
     size_t active = 0, retained = 0;
     uint64_t accepted = 0, requests = 0, bursts = owner.executor.bursts, events = owner.executor.burst_events, expired = 0,
-             ticks = owner.executor.ticks, shown = 0;
+             ticks = owner.executor.ticks, shown = 0, checkpoints = 0;
     for (unsigned i = 0; i < threads; ++i) {
         shown += hosts[i].shown;
         active += hosts[i].active;
@@ -2450,7 +2536,9 @@ int main(int argc, char **argv) {
         pure_wire_close(owner.executor.wires[i]); /* what was not delivered stays in the outbox */
     }
     if (owned) {
+        checkpoints = owner.executor.checkpoints;
         stop_executor(&owner.executor);
+        checkpoints = owner.executor.checkpoints;
         free(owner.jobs);
     }
     unsigned long groups, grouped;
@@ -2459,9 +2547,10 @@ int main(int argc, char **argv) {
             ",\"bursts\":%" PRIu64 ",\"burst_events\":%" PRIu64 ",\"ticks\":%" PRIu64 ",\"expired\":%" PRIu64
             ",\"threads\":%u,\"owner\":%s,\"snapshots\":%" PRIu64 ",\"views_from_snapshots\":%" PRIu64
             ",\"delivered\":%" PRIu64 ",\"delivery_attempts\":%" PRIu64 ",\"answers\":%" PRIu64
-            ",\"commit_groups\":%lu,\"grouped_commits\":%lu}\n",
+            ",\"commit_groups\":%lu,\"grouped_commits\":%lu,\"checkpoints\":%" PRIu64 "}\n",
             active, retained, accepted, requests, bursts, events, ticks, expired, threads, owned ? "true" : "false",
-            owner.executor.publications, shown, delivered, attempts, owner.executor.answers, groups, grouped);
+            owner.executor.publications, shown, delivered, attempts, owner.executor.answers, groups, grouped,
+            checkpoints);
     free(hosts);
     free(thread);
     return 0;
diff --git a/store/store-tree.c b/store/store-tree.c
index b9ae847..83f59e3 100644
--- a/store/store-tree.c
+++ b/store/store-tree.c
@@ -1418,6 +1418,8 @@ PureResult pure_store_open(const char *path, PureStore **out) {
     return PURE_OK;
 }
 
+const char *pure_store_path(const PureStore *store) { return store->path; }
+
 void pure_store_close(PureStore *store) {
     if (!store) return;
     release_mapping(store->mapping);