[Xapian-devel] UUIDs for databases

[Richard Boulton]

The replication code (which is in trunk only currently, not in any 
release) uses the concept of a UUID for each database to identify 
whether a database at a particular location is the same database as 
produced by a previous replication (possible with alterations), or has 
been replaced with a new database.

Currently, the UUIDs generated aren't exactly universal, or unique: 
they're just the timestamp at which the database was first created.

The semantics required for the replication process to function correctly 
are just about satisfied by this; however, part of the result of this is 
that the replicated database has a different UUID to the source 
database, because it was created at a different time.  It also admits 
the possibility of replication getting confused if two databases are 
created at the same time, and one is then moved into place to replace 
the old database.

I'd like to change the UUID implementation to something more robust, but 
I've been thinking about what semantics should be.

UUIDs aren't currently externally exposed (other than as part of an 
opaque blob of data specifying a particular database/revision 
combination), so we can probably just focus on providing UUIDs which are 
good enough to allow the replication process to function robustly, 
rather than thinking about any other uses which they may be put to.

My thinking so far is that:

  - A new UUID should be created when a database is created from scratch.

  - A new UUID should be created when a database is replaced (eg, with 
one of the OVERWRITE options of the open method).

  - If a database is modified in any way (which will always involve a 
transaction occurring), the UUID should be left unchanged.  This allows 
a UUID/revision_number combination to identify a particular revision of 
a database.

  - If a database is replicated, the replica should have the same UUID 
as the original (because, to all intents and purposes, it _is_ the 
original).

  - If the replica of the database is then modified (eg, by adding a 
document to it), the UUID of the replica should be changed.  This is 
because, otherwise, after the next change on the source database, there 
will be two different databases in existence with the same UUID/revision 
combination, but different contents.  This would be bad because it would 
a future replication from the source database to the modified database 
wouldn't notice the differences, and would be likely to apply an 
incompatible set of changes, leading to a corrupt database.

  - In normal usage, we'd never expect a replicated database to receive 
any updates, so this is unlikely to be a problem.  However, one idea 
I've pondered for the future, for redundancy purposes, is to allow a 
pool of replicated databases to be built, in which there would be one 
master database.  Updates would be sent to all clients, but only the 
master would normally index them; all the other databases would 
replicate against the master.  If the master died, an election would be 
held to elect a new master, and that master would apply the updates to 
its databases, and serve the clients with replications.  If the original 
master then came back online, and the UUID in the new master with 
updates was the same as in the old master with its (different) updates, 
it would be impossible for clients to distinguish the two, again 
potentially leading to attempts to combine incompatible changesets, and 
eventually to broken databases.  (I've no intention of writing the code 
for such a pooling system at present, but I'd like not to preclude it, 
either.)

  - The replication protocol currently works by a client sending a 
message to the server saying "please give me the necessary updates to 
transform a database with a given UUID and a given revision number into 
a more recent version of the database".  Therefore, for efficient 
updates, the server needs to remember that the old revision number 
applied for databases before a particular revision number.

I think the upshot of this is that:

  1. A better UUID generation mechanism would be good, to reduce chance 
of random conflicts between databases.

  2. Replicas need to keep track of a flag saying that they're a replica 
of a database, not the original database, so that they know that they 
need to pick a new UUID if modifications are made to them (other than 
via the replication protocol).

  3. Databases need to keep track of the UUID which they had at any of 
the revisions for which they have changesets available.  Perhaps the 
easiest way to implement this would be to store the UUID of the database 
in the changeset files; the information is then available to be checked.

(1) is important before the replication code is put into a release, I 
think, to reduce the chance of conflicts, which would lead to corrupt 
databases

(2) would also be good to fix before a release, since otherwise 
perfectly valid code could result in a corrupt database.  (Note; until 
recently, it wasn't possible (without hackery) to modify a replicated 
database, because they are accessed by stub databases.  However, Olly 
has recently made it valid to open stub databases for writing, as long 
as they contain exactly one sub-database).

(3) is less important, because it would simply result in full-database 
copies occurring when changesets could be applied, leading to an 
efficiency drop, rather than corrupt databases.  However, it would be 
best to fix the changeset files to hold the information required before 
a release, even if we don't actually write the code to search through 
them if the database UUID doesn't match, so that incompatible changes 
aren't required to implement this in future.

-- 
Richard