How to Generate Globally Unique Key Values in Distributed Databases

[perv...@gmail.com]

A synchronization system contains distributed databases. How do you
ensure that new records created on these databases have unique primary
key values? In a single DB system, people usually use AUTO_INCREMENT
columns (e.g. in Mysql) or sequence objects (e.g. in Oracle) that
produce unique sequence numbers. These won’t work in a multi-DB
environment where different DBs might generate same primary key values
that would conflict with each other when new records are synced from
one DB to another.

Pervasync has a "sync sequence" feature that is specifically designed
to solve this issue. You publish a sync sequence defining its start
value and window size. Each sync client would get a window of a
sequence (a range of numbers) from which it can draw globally unique
values for unique keys. When the client is about to run out of the
numbers, a new range is synced to the client. All the application
needs to do is to call the sequenceNextval Java API to retrieve the
numbers locally. In addition to Java API, for Oracle one can use the
locally created native sequence objects directly and for Mysql, one
can use stored procedures to retrieve the sequence numbers.

Please refer to the Javadoc of the SyncServerAdmin for methods that
publish sync sequences. Also refer to the Javadoc of the
SyncClientAdmin for methods that return local sequence values. To use
sequence procedures in Mysql, look up the stored procedures in
pvcadmin schema.

We believe that sync sequence is the best choice for most situations.
Still, there are other options that may fit your specific needs. We
list them below.

1. Only allow transactions to happen on central DB. Device local DBs
are made read-only, i.e. for queries only. Believe it or not, there
are systems that adopt this model.

2. Use randomly generated numbers for key values. The length of the
random numbers has to be long to reduce the possibility of collisions.

3. Use a composite key. The sync client API has a method taht returns
the sync client ID. Apparently this is a globally unique number. You
can use the client ID as the first column of a primary key. You then
use a second column that takes locally unique values. Let’s call it
LUID column. You define the client ID column and the LUID column
together as your composite primary key. The values of the composite
key are globally unique.

4. Compute a GUID using client ID and LUID. For example, you could
use this formula:

GUID = <client ID> * 1000000000 + LUID

5. Map local UID with GUID. This is the technique used by OMA DS, AKA
SyncML, and Activesync. Locally created records are assigned an LUID.
During Activesync synchronization, a GUID for the same record is
generated on server and synced backto client. For OMA DS, client sends
an LUID back to server for every server sent record. A map table of
LUID and GUID is maintained on server.

The mapping methods maybe OK for simple PIM sync. However for
enterprise applications that have large amount of data, a lot of
tables and complex referencial relationships between tables, the
mapping would cause performance and maintainence problems. Pervasync
does not support this method.