Previous Notes Next Notes
The LDAP WG went through an extended process of researching replication for LDAP servers. On the way, they did a good job of describing terminology and defining a list of requirements and non-requirements
. Certainly Chandler replication will have some different requirements, but we ought to be going through much the same process in getting to our different requirements.
There's a clear explanation of this as a design pattern
. The replication stage is done by propagating changes from the master to the slaves, overwriting any content changes on the slaves. It's a very simple model and that's not a bad thing.
How would master/slave replication work when translated into what must appear like a peer group to the user? Well, for starters, let's elect the source of the data as the "Master". So if Alice shares her calendar to Bob and Carl, Alice's Chandler repository is the master simply because that's where the data began. It's easy to start a sharing circle when everybody other than the source is a slave. Later, when Bob wants to add information to an event on Alice's calendar, Bob's repository does this by submitting the change to Alice's repository. Of course this is automatically accepted, because that's what we've decided sharing means (there's no step of "approving" the change in this use case). Then the new calendar data gets replicated from Alice's repository out to Bob and Carl's repositories, so everybody's got the new data provided by Bob. None of the users can tell that this isn't an equal-peers replication strategy.
The master/slave pattern works very well when a server is available, and this is a very easy way to do "replication". When a user wants to share data Chandler uploads it to a server which becomes the master. All changes are submitted to the master and repropagated from there.
How would master/slave replication work with offline users? This easy when a slave goes offline -- the slave simply records the change to the item and keeps it in a queue for submitting to the master when they go back online.
When the master goes offline, there are a few options.
- The easy one is to say that the slaves cannot synchronize with each other until the master does come online. That's probably unacceptable in the long run but might be a short term solution until we get more sophisticated.
- A slave wishing to make changes when the master for that content is unavailable could declare itself the new master and send out persistent notifications to all addresses in the sharing circle. Other slaves would now synchronize to the new master. The original master may remain a slave when they come online again. This would tend to keep highly-available machines in the master role for longer.
- See the fault-tolerant master-slave replication described in this paper. It mimics a more egalitarian model by allowing slaves to become masters if an existing master is unavailable.
Master-Master Replication (or multi-master)
Also described as a design pattern
. This is the pattern recommended when changes need to be made at any copy, even when offline. The pattern description has very useful pictures, terminology explanations, and a list of conflict resolution methods -- highly recommended reading
"Hint: You should avoid using referential integrity in a Master-Master Replication scenario because it can give you major problems. You must ensure that the replication data is written to the databases without side effects, such as double updates due to referential integrity. This is very complex when you have referential integrity on both masters because of the two-way data exchange for the same set of data. "
True sharing involves a great many orthogonal design decisions. Research is available on many of them. There are some relationships between options, but not always (for example, if polling is done over low-bandwidth connections, then it really helps to have the source provide change lists based on replication tokens -- but it's not a necessary combination). This list of options was generated in discussions with Ted.
When to fetch
- On-demand: good performance online, but bad characteristics if user goes offline
- Blocking Pre-fetch: User must wait while new share is entirely prefetched
- Non-blocking Pre-fetch: Most difficult
Where to read, where to write
- Read-One-Write-All (ROWA): not only simplest, but best
- Read/write from Quorum
- Majority is quorum
- Tree determines quorum
- Grid determines quorum
- Master-Slave, in which a change to source always overwrites changes to other locations. See research below and explanation of how this can appear more peer-like to users.
- Master-Master. See research. See also conflict resolution.
Conflict resolution - depends on type of conflict
- Priority based - the change from the repository with the highest priority wins.
- Value based - e.g. the most recent timestamp wins.
- Merge changes automatically
- Overwrite changes
- Manual - by change maker, before replication
- Manual - by anybody - achieved by storing both changes and flagging as conflict.
- Some combination of above.
- Transactional Consistency
- Eventual (or transient) Consistency
- Limited Effort Eventual (or probabilistic) Consistency
- Loosest Consistency
- Ad hoc
Granularity of replication activity
- All-XML: pack attributes as XML and include other data base64-encoded
- Blob: Very poor cross-version behavior
- Bodies + Properties: Although attributes can be packed as XML, other data is file data --> like WebDAV
- Standard File Formats: Exchange email as RFC822, contacts as VCards, events/todos as iCal documents
Determining Change Lists
- Destination pulls item lists and change IDs, compares to local to get change list
- Source maintains and provides replication state tokens and limited change lists
is Sun's allegedly open peer-to-peer protocol technology. It's naturally got a lot of Java implementations and related projects, but in theory it's language-neutral (and platform neutral) -- in fact there's already a project to do a Python binding
, although the finished C implementation
might be more useful to us. There are already PIM (iFreestyle
) and replication
applications built using JXTA. Some features:
- Peer discovery - can advertise resources on each peer
- Peer group membership - peers can self-organize into groups like sharing circles
- Some peer trust issues -- certificates??
- Search protocol for searching content on other peers
- Bindings to both HTTP and TCP
- Ability to open pipe or channel
What this means is that the semantics of notifications or file browsing or replication aren't defined, but a lot of the setup work is done for you. Note that one could also use another protocol over the channel provided by JXTA -- for example, use XMPP or WebDAV over the JXTA channel. So this is like saying we'd use SOAP -- except that the basic services of JXTA are more useful in Chandler environments than those of SOAP.
Here's the link to the technical faq info on certificates, public keys, etc: http://www.jxta.org/project/www/docs/DomainFAQTech.html#security
- 06 Apr 2004
one of the jxta python team members was an early poster to the design mailing list: http://lists.osafoundation.org/pipermail/dev/2002-October/000042.html
- 07 Apr 2004