Synchronization Toolkit

Not to be confused with replication, my concept of synchronization is to
manage changes between a server table (or tables) and one or more mobile,
disconnected databases (i.e. PalmPilot, laptop, etc.).

I read through the notes in the TODO for this topic and devised a tool kit
for doing synchronization. I hope that the Postgresql development community
will find this useful and will help me refine this concept by offering
insight, experience and some good old fashion hacking if you are so
inclined.

The bottom of this message describes how to use the attached files.

I look forward to your feedback.

--rob

Methodology:

I devised a concept that I call "session versioning". This means that every
time a row changes it does NOT get a new version. Rather it gets stamped
with the current session version common to all published tables. Clients,
when they connect for synchronization, will immediately increment this
common version number reserve the result as a "post version" and then
increment the session version again. This version number, implemented as a
sequence, is common to all synchronized tables and rows.

Any time the server makes changes to the row gets stamped with the current
session version, when the client posts its changes it uses the reserved
"post version". The client then makes all it's changes stamping the changed
rows with it's reserved "post version" rather than the current version. The
reason why is explained later. It is important that the client post all its
own changes first so that it does not end up receiving records which changed
since it's last session that it is about to update anyway.

Reserving the post version is a two step process. First, the number is
simply stored in a variable for later use. Second, the value is added to a
lock table (last_stable) to indicate to any concurrent sessions that rows
with higher version numbers are to be considered "unstable" at the moment
and they should not attempt to retrieve them at this time. Each client,
upon connection, will use the lowest value in this lock table (max_version)
to determine the upper boundary for versions it should retrieve. The lower
boundary is simply the previous session's "max_version" plus one. Thus
when the client retrieves changes is uses the following SQL "where"
expression:

WHERE row_version >= max_version and row_version <= last_stable_version and
version <> this_post_version

The point of reserving and locking a post version is important in that it
allows concurrent synchronization by multiple clients. The first, of many,
clients to connect basically dictates to all future clients that they must
not take any rows equal to or greater than the one which it just reserved
and locked. The reason the session version is incremented a second time is
so that the server may continue to post changes concurrent with any client
changes and be certain that these concurrent server changes will not taint
rows the client is about to retrieve. Once the client is finished with it's
session it removes the lock on it's post version.

Partitioning data for use by each node is the next challenge we face. How
can we control which "slice" of data each client receives? A slice can be
horizontal or vertical within a table. Horizontal slices are easy, it's
just the where clause of an SQL statement that says "give me the rows that
match X criteria". We handle this by storing and appending a where clause
to each client's retrieval statement in addition to where clause described
above. Actually, two where clauses are stored and appended. One is per
client and one is per publication (table).

We defined horizontal slices by filtering rows. Vertical slices are limits
by column. The tool kit does provide a mechanism for pseudo vertical
partitioning. When a client is "subscribed" to a publication, the toolkit
stores what columns that node is to receive during a session. These are
stored in the subscribed_cols table. While this does limit the number
columns transmitted, the insert/update/delete triggers do not recognize
changes based on columns. The "pseudo" nature of our vertical partitioning
is evident by example:

Say you have a table with name, address and phone number as columns. You
restrict a client to see only name and address. This means that phone
number information will not be sent to the client during synchronization,
and the client can't attempt to alter the phone number of a given entry.
Great, but . . . if, on the server, the phone number (but not the name or
address) is changed, the entire row gets marked with a new version. This
means that the name and address will get sent to the client even though they
didn't change.

Well, there's the flaw in vertical partitioning. Other than wasting
bandwidth, the extra row does no harm to the process. The workaround for
this is to highly normalize your schema when possible.

Collisions are the next crux one encounters with synchronization. When two
clients retrieve the same row and both make (different)changes, which one is
correct? So far the system operates totally independent of time. This is
good because it doesn't rely on the server or client to keep accurate time.
We can just ignore time all together, but then we force our clients to
synchronize on a strict schedule in order to avoid (or reduce) collisions.
If every node synchronized immediately after making changes we could just
stop here. Unfortunately this isn't reality. Reality dictates that of two
clients: Client A & B will each pick up the same record on Monday. A will
make changes on Monday, then leave for vacation. B will make changes on
Wednesday because new information was gathered in A's absence. Client B
posts those changes Wednesday. Meanwhile, client A returns from vacation on
Friday and synchronizes his changes. A over writes B's changes even though
A made changes before the most recent information was posted by B.

It is clear that we need some form of time stamp to cope with the above
example. While clocks aren't the most reliable, they are the only common
version control available to solve this problem. The system is set up to
accept (but not require) timestamps from clients and changes on the server
are time stamped. The system, when presented a time stamp with a row, will
compare them to figure out who wins in a tie. The system makes certain
"sanity" checks with regard to these time stamps. A client may not attempt
to post a change with a timestamp that is more than one hour in the future
(according to what the server thinks "now" is) nor one hour before it's last
synchronization date/time. The client row will be immediately placed into
the collision table if the timestamp is that far out of whack.
Implementations of the tool kit should take care to ensure that client &
server agree on what "now" is before attempting to submit changes with
timestamps.

Time stamps are not required. Should a client be incapable of tracking
timestamps, etc. The system will assume that any server row which has been
changed since the client's last session will win a tie. This is quite error
prone, so timestamps are encouraged where possible.

Inserts pose an interesting challenge. Since multiple clients cannot share
a sequence (often used as a primary key) while disconnected. They will be
responsible for their own unique "row_id" when inserting records. Inserts
accept any arbitrary key, and write back to the client a special kind of
update that gives the server's row_id. The client is responsible for making
sure that this update takes place locally.

Deletes are the last portion of the process. When deletes occur, the
row_id, version, etc. are stored in a "deleted" table. These entries are
retrieved by the client using the same version filter as described above.
The table is pruned at the end of each session by deleting all records with
versions that are less than the lowest 'last_version' stored for each
client.

Having wrapped up the synchronization process, I'll move on to describe some
points about managing clients, publications and the like.

The tool kit is split into two objects: SyncManagement and Synchronization.
The Synchronization object exposes an API that client implementations use to
communicate and receive changes. The management functions handle system
install and uninstall in addition to publication of tables and client
subscriptions.

Installation and uninstallation are handled by their corresponding functions
in the API. All system tables are prefixed and suffixed with four
underscores, in hopes that this avoids conflict with an existing tables.
Calling the install function more than once will generate an error message.
Uninstall will remove all related tables, sequences, functions and triggers
from the system.

The first step, after installing the system, is to publish a table. A table
can be published more than once under different names. Simply provide a
unique name as the second argument to the publish function. Since object
names are restricted to 32 characters in Postgres, each table is given a
unique id and this id is used to create the trigger and sequence names.
Since one table can be published multiple times, but only needs one set of
triggers and one sequence for change management a reference count is kept so
that we know when to add/drop triggers and functions. By default, all
columns are published, but the third argument to the publish function
accepts an array reference of column names that allows you to specify a
limited set. Information about the table is stored in the "tables" table,
info about the publication is in the "publications" table and column names
are stored in "subscribed_cols" table.

The next step is to subscribe a client to a table. A client is identified
by a user name and a node name. The subscribe function takes three
arguments: user, node & publication. The subscription process writes an
entry into the "subscribed" table with default values. Of note, the
"RefreshOnce" attribute is set to true whenever a table is published. This
indicates to the system that a full table refresh should be sent the next
time the client connects even if the client requests synchronization rather
than refresh.

The toolkit does not, yet, provide a way to manage the whereclause stored at
either the publication or client level. To use or test this feature, you
will need to set the whereclause attributes manually.

Tables and users can be unpublished and unsubscribed using the corresponding
functions within the tool kit's management interface. Because postgres
lacks an "ALTER TABLE DROP COLUMN" function, the unpublish function only
removes default values and indexes for those columns.

The API isn't the most robust thing in the world right now. All functions
return undef on success and an error string otherwise (like DBD). I hope to
clean up the API considerably over the next month. The code has not been
field tested at this time.

The files attached are:

1) SynKit.pm (A perl module that contains install/uninstall functions and a
simple api for synchronization & management)

2) sync_install.pl (Sample code to demonstrate the installation, publishing
and subscribe process)

3) sync_uninstall.pl (Sample code to demonstrate the uninstallation,
unpublishing and unsubscribe process)

To use them on Linux (don't know about Win32 but should work fine):

- set up a test database and make SURE plpgsql is installed

- install perl 5.05 along with Date::Parse(TimeDate-1.1) , DBI and DBD::Pg
modules [www.cpan.org]

- copy all three attached files to a test directory

- cd to your test directory

- edit all three files and change the three DBI variables to suit your
system (they are clearly marked)

- % perl sync_install.pl

- check out the tables, functions & triggers installed

- % perl sync.pl

- check out the 'sync_test' table, do some updates/inserts/deletes and run
sync.pl again
NOTE: Sanity checks default to allow no more than 50% of the table
to be changed by the client in a single session.
If you delete all (or most of) the rows you will get errors when
you run sync.pl again! (by design)

- % perl sync_uninstall.pl (when you are done)

- check out the sample scripts and the perl module code (commented, but
not documented)