Novell is now a part of Micro Focus

Transitive Synchronization Revisited

Articles and Tips: article

Kevin Burnett
Senior Research Engineer
Novell AppNotes

01 Jun 2002


Previously, we discussed Transitive Synchronization in this column. Since then, I have received several e-mails requesting possible corrections to what was printed and also requesting greater detail about the Transitive Synchronization process. I recently had the opportunity to visit with one of Novell's key NDS Engineers about this subject. Needless to say, we discussed Transitive Synchronization in great detail. The following is the result of that conversation.

Vital Concepts

Before we can adequately discuss Transitive Synchronization in detail, there are a few directory concepts that should be defined:


Directory Concept
Definition

Partition

A distinct portion of the directory tree that stores and replicates directory information.

Replica

A single instance of a partition.

Synchronization

The propagation of directory information from one replica to another so the information in each partition is consistent with each other.

Schema

Defines the types of objects that can be created in your tree (such as users, printers, and groups) and what information is required or is optional at the time the object is created. Every object has a defined schema class for that type of object.

Background Process

A task or set of tasks that happen without user intervention to maintain directory information (such as synchronization).

Also, it would be good to understand object synchronization concepts:


Directory Concept
Definition

Replica Types

Master, Read/Write, Filtered

Replica Ring

The set of eDirectory agents that hold a replica of a given partition and therefore participate in the synchronization of objects contained within that partition.

Deltas

Time-based differences between copies of a given object.

Change Cache

The collection of objects with deltas for a given replica.

Transitive Synchronization

A method for providing convergence of data without requiring an eDirectory agent with changes (i.e., state-based deltas) to directly contact and synchronize those changes with every other agent in the replica ring.

There is one last set of definitions that we will need to understand; Partition Root Object Attributes.


Partition Root Attribute
Definition

Replica

A synchronizing multi-valued attribute whose value represents an eDirectory agent that is participating in the replication of this partition and how it can be contacted.

Transitive Vector

A synchronizing multi-value attribute whose value represents a state in time up to which the specified eDirectory agent has received changes.

Local Received Up To (LRUT)

A non-synchronizing single valued attribute whose value represents the current state in time up to which the local eDirectory agent has received changes.

Purge Vector

A non-synchronizing single valued attribute whose value represents the oldest state in time that has been seen by each eDirectory agent in the replica ring. Uses the Transitive Vector to find the oldest state seen by all the agents in the ring for each replica.

Before diving into the process of Transitive Synchronization, we should also discuss the Local Received Up To or LRUT attribute. So the logical question to ask is: "What is the LRUT used for?"

For in-bound traffic, the LRUT attribute is used:

  • To keep track of what changes have been received from other replicas

  • To inform inbounding replica's the current synchronization state

  • To advertise the local state when the agent is ready to do so during outbound synchronization

As the LRUT attribute prepares to Out-bound, it:

  • Reads the last TimeStamp issued on the local replica from the partition record

  • Updates the row in the LRUT attribute that corresponds to the local replica number

  • Updates the Transitive vector value that corresponds to the local agent ("server")

Transitive Synchronization Briefly Defined

Let's say that you have two servers: a source server and a destination or target server. With Transitive Synchronization the source server looks at the replica list on the target server's Transitive Vector. If the source server's Transitive Vector is more recent than the target server's vector, the source server needs to synchronize with the target server. This prevents a lot of network traffic, since only the servers whose replicas need updating are actually updated.

Transitive Synchronization provides the following benefits:

  • It reduces network traffic, since it only sends the needed changes.

  • It handles larger replica lists because of reduced synchronization traffic.

  • It supports IP directly, whereas previous synchronization strategies had to support IP through intermediary servers.

How Transitive Synchronization Works

The following steps describe the Transitive Synchronization process and how it works.

Let's assume that we have three, servers: Server A, Server B, and Server C. And lets also assume that Server A is home to Replica A, Server B to Replica B, and Server C to Replica C, as illustrated in the following table:


Server
Contained Replica

Server A

Replica A

Server B

Replica B

Server C

Replica C

The network is set up as illustrated in Figure 1.

Server A is able to communicate with Server B, with Server B being able to communicate with Server C, and Server C is able to communicate with Server A. Remember from our previous discussion about Transitive Vectors (February 2002), each server in the replica ring holds a Transitive Vector with timestamps showing when the last updates were made on all the replicas.

The actual process of Transitive Synchronization in eDirectory version 8.6 and greater is currently quite complex with multiple threads executing simultaneously. For the sake of keeping this article within reasonable bounds, Transitive Synchronization will be discussed as if there is only one thread of execution occurring at a time. The following steps are performed during Transitive Synchronization:

Time=time(10)

  1. An in-bound change request is sent to Server A (Figure 2). Server A's Partition record picks up the Last Issued Time Stamp (LIT) and then implements these timestamps on each of the affected attributes.

  2. This information is then copied to the LRUT in Replica A on Server A. These changes occur at Time = time(10).

    Note: The only timestamp values that a server changes are those in its own time vector. It will never change the values of the other replicas time vectors.

    Server A synchronizing with inbound data

    Server A's LRUT at Time = time(10)


    Time Vector Timestamp
    Server
    Replica A
    Replica B
    Replica C

    time(0)

    Server A

    time(0)

    time(0)

    time(0)

  3. At Synchronization time, Server A copies the information in its LRUT to its Transitive Vector in preparation for outbound synchronization. The three servers' Transitive Vectors look like this:

Server A's Transitive Vector at Time = time(10)


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(0)

Server A

time(0)

time(0)

time(0)

time(0)

Server B

time(0)

time(0)

time(0)

time(0)

Server C

time(0)

time(0)

time(0)

Server B's Transitive Vector at Time = time(10)


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(0)

Server A

time(0)

time(0)

time(0)

time(0)

Server B

time(0)

time(0)

time(0)

time(0)

Server C

time(0)

time(0)

time(0)

Server C's Transitive Vector at Time = time(10)


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(0)

Server A

time(0)

time(0)

time(0)

time(0)

Server B

time(0)

time(0)

time(0)

time(0)

Server C

time(0)

time(0)

time(0)

Since we haven't synchronized with Server B or C, all of their times are still at Time = time(0). At this point, Server B's LRUT looks like this:


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(0)

Server B

time(0)

time(0)

time(0)

Server A synchronizing with server B

Time = time(11)

Server A synchronizes the changes to Server B (Figure 3). The following steps occur on Server B:

  1. An in-bound change request is sent from Server A from Server B. Server B's Partition record picks up the Last Issued Time Stamp (LIT) and then implements the timestamps on each of the affected attributes.

  2. This information is then copied to the LRUT in Replica A on Server B. These changes occur at Time = time(11).

    Server A's LRUT at Time = time(11)


    Time Vector Timestamp
    Server
    Replica A
    Replica B
    Replica C

    time(11)

    Server A

    time(11)

    time(0)

    time(0)

  3. At Synchronization time, Server B copies the information in its LRUT to its Transitive Vector in preparation for out-bound synchronization. The three servers' Transitive Vectors look as follows:

Server A's Transitive Vector at Time = time(11)


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(11)

Server A

time(11)

time(0)

time(0)

time(0)

Server B

time(0)

time(0)

time(0)

time(0)

Server C

time(0)

time(0)

time(0)

Server B's Transitive Vector at Time = time(11)


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(11)

Server A

time(11)

time(0)

time(0)

time(0)

Server B

time(0)

time(0)

time(0)

time(0)

Server C

time(0)

time(0)

time(0)

Server C's Transitive Vector at Time = time(11)


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(0)

Server A

time(0)

time(0)

time(0)

time(0)

Server B

time(0)

time(0)

time(0)

time(0)

Server C

time(0)

time(0)

time(0)

(Since we haven't synchronized with Server C, all of its times are still at Time = time(0)). At this point, Server B's LRUT looks like this:


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(11)

Server B

time(11)

time(0)

time(0)

Server B synchronizing with server C

Time = time(12)

Server B synchronizes the changes to Server C (Figure 4). The following steps occur on Server C:

  1. An in-bound change request is sent from Server B to Server C. Server C's Partition Record picks up the Last Issued Time Stamp (LIT) and then implements the timestamps on each of the affected attributes.

  2. This information is then copied to the LRUT in Replica C on Server C. These changes occur at Time = time(12).

    Server B's LRUT at Time = time(12)


    Time Vector Timestamp
    Server
    Replica A
    Replica B
    Replica C

    time(12)

    Server B

    time(11)

    time(12)

    time(0)

  3. At Synchronization time, Server C copies the information in its LRUT to its Transitive Vector in preparation for outbound synchronization. The three servers' Transitive Vectors now look like this:

Server A's Transitive Vector at Time = time(12)


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(11)

Server A

time(11)

time(0)

time(0)

time(0)

Server B

time(0)

time(0)

time(0)

time(0)

Server C

time(0)

time(0)

time(0)

Server B's Transitive Vector at Time = time(12)


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(11)

Server A

time(11)

time(0)

time(0)

time(12)

Server B

time(11)

time(12)

time(0)

time(0)

Server C

time(0)

time(0)

time(0)

Server C's Transitive Vector at Time = time(12)


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(11)

Server A

time(11)

time(0)

time(0)

time(12)

Server B

time(11)

time(12)

time(0)

time(12)

Server C

time(0)

time(0)

time(0)

At this point, Server C's LRUT looks like this:


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(12)

Server C

time(11)

time(12)

time(0)

Server C synchronizing with server A

Time = time(13)

Server C gets ready to synchronize with Server A (Figure 5). The following steps occur on Server A:

  1. An in-bound change request is sent from Server C to Server A. Server C's Partition Record picks up the Last Issued Time Stamp (LIT) and then implements the timestamps on each of the affected attributes.

  2. This information is then copied to the LRUT in Replica C on Server C. These changes occur at Time = time(13).

    Server C's LRUT at Time = time(13)


    Time Vector Timestamp
    Server
    Replica A
    Replica B
    Replica C

    time(13)

    Server C

    time(11)

    time(12)

    time(13)

  3. At Synchronization time, Server A copies the information in its LRUT to its Transitive Vector in preparation for outbound synchronization. See the following tables for the three servers' Transitive Vectors.

Server A's Transitive Vector


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(11)

Server A

time(11)

time(0)

time(0)

time(12)

Server B

time(11)

time(12)

time(0)

time(13)

Server C

time(11)

time(12)

time(13)

Server B's Transitive Vector


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(11)

Server A

time(11)

time(0)

time(0)

time(12)

Server B

time(11)

time(12)

time(0)

time(0)

Server C

time(0)

time(0)

time(0)

Server C's Transitive Vector


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(11)

Server A

time(11)

time(0)

time(0)

time(12)

Server B

time(11)

time(12)

time(0)

time(13)

Server C

time(11)

time(12)

time(13)

To complete the cycle, Server A's LRUT now looks like this at Time=time(13):


Time Vector Timestamp
Server
Replica A
Replica B
Replica C

time(13)

Server A

time(11)

time(12)

time(13)

Synchronization will then continue until all replicas agree with each other. Of course, when another change is made to NDS, the whole process starts over again.

The previous example shows how one update would be propagated through a replica ring. It has been simplified to show only one change at a time. In reality, many updates will typically happen at the same time.

Thanks to the Novell eDirectory Core Development Team for providing critical information for this column

* Originally published in Novell AppNotes

Disclaimer

The origin of this information may be internal or external to Novell. While Novell makes all reasonable efforts to verify this information, Novell does not make explicit or implied claims to its validity.

© Copyright Micro Focus or one of its affiliates