From 987056eaefe8eb3819a665e4e3273784f4d2b45c Mon Sep 17 00:00:00 2001 From: David Bremner Date: Sun, 9 Aug 2015 11:24:41 +0200 Subject: [PATCH] [PATCH 1/5] lib: Add per-message last modification tracking --- 10/c912024038e275061914f9a44b102537ed2110 | 334 ++++++++++++++++++++++ 1 file changed, 334 insertions(+) create mode 100644 10/c912024038e275061914f9a44b102537ed2110 diff --git a/10/c912024038e275061914f9a44b102537ed2110 b/10/c912024038e275061914f9a44b102537ed2110 new file mode 100644 index 000000000..0f5646948 --- /dev/null +++ b/10/c912024038e275061914f9a44b102537ed2110 @@ -0,0 +1,334 @@ +Return-Path: +X-Original-To: notmuch@notmuchmail.org +Delivered-To: notmuch@notmuchmail.org +Received: from localhost (localhost [127.0.0.1]) + by arlo.cworth.org (Postfix) with ESMTP id EF72F6DE1654 + for ; Sun, 9 Aug 2015 02:27:43 -0700 (PDT) +X-Virus-Scanned: Debian amavisd-new at cworth.org +X-Spam-Flag: NO +X-Spam-Score: 0.139 +X-Spam-Level: +X-Spam-Status: No, score=0.139 tagged_above=-999 required=5 tests=[AWL=0.129, + T_HEADER_FROM_DIFFERENT_DOMAINS=0.01] autolearn=disabled +Received: from arlo.cworth.org ([127.0.0.1]) + by localhost (arlo.cworth.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id a6v1vDbKtd-S for ; + Sun, 9 Aug 2015 02:27:41 -0700 (PDT) +Received: from gitolite.debian.net (gitolite.debian.net [87.98.215.224]) + by arlo.cworth.org (Postfix) with ESMTPS id 9DB506DE100F + for ; Sun, 9 Aug 2015 02:27:41 -0700 (PDT) +Received: from remotemail by gitolite.debian.net with local (Exim 4.80) + (envelope-from ) + id 1ZOMrf-0005Wc-L9; Sun, 09 Aug 2015 09:25:59 +0000 +Received: (nullmailer pid 7061 invoked by uid 1000); Sun, 09 Aug 2015 + 09:24:47 -0000 +From: David Bremner +To: notmuch@notmuchmail.org +Subject: [PATCH 1/5] lib: Add per-message last modification tracking +Date: Sun, 9 Aug 2015 11:24:41 +0200 +Message-Id: <1439112285-6681-2-git-send-email-david@tethera.net> +X-Mailer: git-send-email 2.1.4 +In-Reply-To: <1439112285-6681-1-git-send-email-david@tethera.net> +References: <1439112285-6681-1-git-send-email-david@tethera.net> +X-BeenThere: notmuch@notmuchmail.org +X-Mailman-Version: 2.1.18 +Precedence: list +List-Id: "Use and development of the notmuch mail system." + +List-Unsubscribe: , + +List-Archive: +List-Post: +List-Help: +List-Subscribe: , + +X-List-Received-Date: Sun, 09 Aug 2015 09:27:44 -0000 + +From: Austin Clements + +This adds a new document value that stores the revision of the last +modification to message metadata, where the revision number increases +monotonically with each database commit. + +An alternative would be to store the wall-clock time of the last +modification of each message. In principle this is simpler and has +the advantage that any process can determine the current timestamp +without support from libnotmuch. However, even assuming a computer's +clock never goes backward and ignoring clock skew in networked +environments, this has a fatal flaw. Xapian uses (optimistic) +snapshot isolation, which means reads can be concurrent with writes. +Given this, consider the following time line with a write and two read +transactions: + + write |-X-A--------------| + read 1 |---B---| + read 2 |---| + +The write transaction modifies message X and records the wall-clock +time of the modification at A. The writer hangs around for a while +and later commits its change. Read 1 is concurrent with the write, so +it doesn't see the change to X. It does some query and records the +wall-clock time of its results at B. Transaction read 2 later starts +after the write commits and queries for changes since wall-clock time +B (say the reads are performing an incremental backup). Even though +read 1 could not see the change to X, read 2 is told (correctly) that +X has not changed since B, the time of the last read. In fact, X +changed before wall-clock time A, but the change was not visible until +*after* wall-clock time B, so read 2 misses the change to X. + +This is tricky to solve in full-blown snapshot isolation, but because +Xapian serializes writes, we can use a simple, monotonically +increasing database revision number. Furthermore, maintaining this +revision number requires no more IO than a wall-clock time solution +because Xapian already maintains statistics on the upper (and lower) +bound of each value stream. +--- + lib/database-private.h | 16 +++++++++++++++- + lib/database.cc | 50 ++++++++++++++++++++++++++++++++++++++++++++++++-- + lib/message.cc | 22 ++++++++++++++++++++++ + lib/notmuch-private.h | 10 +++++++++- + 4 files changed, 94 insertions(+), 4 deletions(-) + +diff --git a/lib/database-private.h b/lib/database-private.h +index 24243db..5c5a2bb 100644 +--- a/lib/database-private.h ++++ b/lib/database-private.h +@@ -100,6 +100,12 @@ enum _notmuch_features { + * + * Introduced: version 3. */ + NOTMUCH_FEATURE_INDEXED_MIMETYPES = 1 << 5, ++ ++ /* If set, messages store the revision number of the last ++ * modification in NOTMUCH_VALUE_LAST_MOD. ++ * ++ * Introduced: version 3. */ ++ NOTMUCH_FEATURE_LAST_MOD = 1 << 6, + }; + + /* In C++, a named enum is its own type, so define bitwise operators +@@ -145,6 +151,8 @@ struct _notmuch_database { + + notmuch_database_mode_t mode; + int atomic_nesting; ++ /* TRUE if changes have been made in this atomic section */ ++ notmuch_bool_t atomic_dirty; + Xapian::Database *xapian_db; + + /* Bit mask of features used by this database. This is a +@@ -158,6 +166,11 @@ struct _notmuch_database { + * next library call. May be NULL */ + char *status_string; + ++ /* Highest committed revision number. Modifications are recorded ++ * under a higher revision number, which can be generated with ++ * notmuch_database_new_revision. */ ++ unsigned long revision; ++ + Xapian::QueryParser *query_parser; + Xapian::TermGenerator *term_gen; + Xapian::ValueRangeProcessor *value_range_processor; +@@ -179,7 +192,8 @@ struct _notmuch_database { + * will have it). */ + #define NOTMUCH_FEATURES_CURRENT \ + (NOTMUCH_FEATURE_FILE_TERMS | NOTMUCH_FEATURE_DIRECTORY_DOCS | \ +- NOTMUCH_FEATURE_BOOL_FOLDER | NOTMUCH_FEATURE_GHOSTS) ++ NOTMUCH_FEATURE_BOOL_FOLDER | NOTMUCH_FEATURE_GHOSTS | \ ++ NOTMUCH_FEATURE_LAST_MOD) + + /* Return the list of terms from the given iterator matching a prefix. + * The prefix will be stripped from the strings in the returned list. +diff --git a/lib/database.cc b/lib/database.cc +index 6a15174..52e2e8f 100644 +--- a/lib/database.cc ++++ b/lib/database.cc +@@ -101,6 +101,9 @@ typedef struct { + * + * SUBJECT: The value of the "Subject" header + * ++ * LAST_MOD: The revision number as of the last tag or ++ * filename change. ++ * + * In addition, terms from the content of the message are added with + * "from", "to", "attachment", and "subject" prefixes for use by the + * user in searching. Similarly, terms from the path of the mail +@@ -310,6 +313,8 @@ static const struct { + * them. */ + { NOTMUCH_FEATURE_INDEXED_MIMETYPES, + "indexed MIME types", "w"}, ++ { NOTMUCH_FEATURE_LAST_MOD, ++ "modification tracking", "w"}, + }; + + const char * +@@ -737,6 +742,23 @@ _notmuch_database_ensure_writable (notmuch_database_t *notmuch) + return NOTMUCH_STATUS_SUCCESS; + } + ++/* Allocate a revision number for the next change. */ ++unsigned long ++_notmuch_database_new_revision (notmuch_database_t *notmuch) ++{ ++ unsigned long new_revision = notmuch->revision + 1; ++ ++ /* If we're in an atomic section, hold off on updating the ++ * committed revision number until we commit the atomic section. ++ */ ++ if (notmuch->atomic_nesting) ++ notmuch->atomic_dirty = TRUE; ++ else ++ notmuch->revision = new_revision; ++ ++ return new_revision; ++} ++ + /* Parse a database features string from the given database version. + * Returns the feature bit set. + * +@@ -904,6 +926,7 @@ notmuch_database_open_verbose (const char *path, + notmuch->atomic_nesting = 0; + try { + string last_thread_id; ++ string last_mod; + + if (mode == NOTMUCH_DATABASE_MODE_READ_WRITE) { + notmuch->xapian_db = new Xapian::WritableDatabase (xapian_path, +@@ -962,6 +985,14 @@ notmuch_database_open_verbose (const char *path, + INTERNAL_ERROR ("Malformed database last_thread_id: %s", str); + } + ++ /* Get current highest revision number. */ ++ last_mod = notmuch->xapian_db->get_value_upper_bound ( ++ NOTMUCH_VALUE_LAST_MOD); ++ if (last_mod.empty ()) ++ notmuch->revision = 0; ++ else ++ notmuch->revision = Xapian::sortable_unserialise (last_mod); ++ + notmuch->query_parser = new Xapian::QueryParser; + notmuch->term_gen = new Xapian::TermGenerator; + notmuch->term_gen->set_stemmer (Xapian::Stem ("english")); +@@ -1369,7 +1400,8 @@ notmuch_database_upgrade (notmuch_database_t *notmuch, + + /* Figure out how much total work we need to do. */ + if (new_features & +- (NOTMUCH_FEATURE_FILE_TERMS | NOTMUCH_FEATURE_BOOL_FOLDER)) { ++ (NOTMUCH_FEATURE_FILE_TERMS | NOTMUCH_FEATURE_BOOL_FOLDER | ++ NOTMUCH_FEATURE_LAST_MOD)) { + notmuch_query_t *query = notmuch_query_create (notmuch, ""); + total += notmuch_query_count_messages (query); + notmuch_query_destroy (query); +@@ -1396,7 +1428,8 @@ notmuch_database_upgrade (notmuch_database_t *notmuch, + + /* Perform per-message upgrades. */ + if (new_features & +- (NOTMUCH_FEATURE_FILE_TERMS | NOTMUCH_FEATURE_BOOL_FOLDER)) { ++ (NOTMUCH_FEATURE_FILE_TERMS | NOTMUCH_FEATURE_BOOL_FOLDER | ++ NOTMUCH_FEATURE_LAST_MOD)) { + notmuch_query_t *query = notmuch_query_create (notmuch, ""); + notmuch_messages_t *messages; + notmuch_message_t *message; +@@ -1433,6 +1466,14 @@ notmuch_database_upgrade (notmuch_database_t *notmuch, + if (new_features & NOTMUCH_FEATURE_BOOL_FOLDER) + _notmuch_message_upgrade_folder (message); + ++ /* Prior to NOTMUCH_FEATURE_LAST_MOD, messages did not ++ * track modification revisions. Give all messages the ++ * next available revision; since we just started tracking ++ * revisions for this database, that will be 1. ++ */ ++ if (new_features & NOTMUCH_FEATURE_LAST_MOD) ++ _notmuch_message_upgrade_last_mod (message); ++ + _notmuch_message_sync (message); + + notmuch_message_destroy (message); +@@ -1615,6 +1656,11 @@ notmuch_database_end_atomic (notmuch_database_t *notmuch) + return NOTMUCH_STATUS_XAPIAN_EXCEPTION; + } + ++ if (notmuch->atomic_dirty) { ++ ++notmuch->revision; ++ notmuch->atomic_dirty = FALSE; ++ } ++ + DONE: + notmuch->atomic_nesting--; + return NOTMUCH_STATUS_SUCCESS; +diff --git a/lib/message.cc b/lib/message.cc +index 1ddce3c..26b5e76 100644 +--- a/lib/message.cc ++++ b/lib/message.cc +@@ -998,6 +998,16 @@ _notmuch_message_set_header_values (notmuch_message_t *message, + message->modified = TRUE; + } + ++/* Upgrade a message to support NOTMUCH_FEATURE_LAST_MOD. The caller ++ * must call _notmuch_message_sync. */ ++void ++_notmuch_message_upgrade_last_mod (notmuch_message_t *message) ++{ ++ /* _notmuch_message_sync will update the last modification ++ * revision; we just have to ask it to. */ ++ message->modified = TRUE; ++} ++ + /* Synchronize changes made to message->doc out into the database. */ + void + _notmuch_message_sync (notmuch_message_t *message) +@@ -1010,6 +1020,18 @@ _notmuch_message_sync (notmuch_message_t *message) + if (! message->modified) + return; + ++ /* Update the last modification of this message. */ ++ if (message->notmuch->features & NOTMUCH_FEATURE_LAST_MOD) ++ /* sortable_serialise gives a reasonably compact encoding, ++ * which directly translates to reduced IO when scanning the ++ * value stream. Since it's built for doubles, we only get 53 ++ * effective bits, but that's still enough for the database to ++ * last a few centuries at 1 million revisions per second. */ ++ message->doc.add_value (NOTMUCH_VALUE_LAST_MOD, ++ Xapian::sortable_serialise ( ++ _notmuch_database_new_revision ( ++ message->notmuch))); ++ + db = static_cast (message->notmuch->xapian_db); + db->replace_document (message->doc_id, message->doc); + message->modified = FALSE; +diff --git a/lib/notmuch-private.h b/lib/notmuch-private.h +index cc9ce12..f52b4e4 100644 +--- a/lib/notmuch-private.h ++++ b/lib/notmuch-private.h +@@ -107,7 +107,8 @@ typedef enum { + NOTMUCH_VALUE_TIMESTAMP = 0, + NOTMUCH_VALUE_MESSAGE_ID, + NOTMUCH_VALUE_FROM, +- NOTMUCH_VALUE_SUBJECT ++ NOTMUCH_VALUE_SUBJECT, ++ NOTMUCH_VALUE_LAST_MOD, + } notmuch_value_t; + + /* Xapian (with flint backend) complains if we provide a term longer +@@ -194,6 +195,9 @@ void + _notmuch_database_log (notmuch_database_t *notmuch, + const char *format, ...); + ++unsigned long ++_notmuch_database_new_revision (notmuch_database_t *notmuch); ++ + const char * + _notmuch_database_relative_path (notmuch_database_t *notmuch, + const char *path); +@@ -305,6 +309,10 @@ _notmuch_message_set_header_values (notmuch_message_t *message, + const char *date, + const char *from, + const char *subject); ++ ++void ++_notmuch_message_upgrade_last_mod (notmuch_message_t *message); ++ + void + _notmuch_message_sync (notmuch_message_t *message); + +-- +2.1.4 + -- 2.26.2