Transitive Vector: What It Is and How NDS Uses It
Articles and Tips: article
Kevin Burnett
Senior Research Engineer
Novell AppNotes
01 Feb 2002
Novell Directory Services (eDirectory) has had a lifetime of almost ten years if you count its predecessors. For instance, in NetWare 3.x, there were the enhancements to the SYSCON utility called NETCON, which used a form of forced synchronization of user and group objects between servers. In order to overcome the limitations of a patched solution such as NETCON, NDS was born to offer a complete directory solution, designed from the ground up to fulfill that mission.
Initially, NDS was designed with a method of updating information on all servers in the NDS tree. This was called synchronization . Recently synchronization has been improved to handle increased efficiencies that were demanded by the current workforce. One of the updates to synchronization is called Transitive Synchronization. In order to understand Transitive Synchronization, it is important to understand the Transitive Vector.
The Transitive Vector
In order to maintain the synchronization of replicas, NDS needs to keep track of the changes that have been made. This is done by placing a timestamp on a specific attribute of the Partition Root object. This timestamp indicates when the last update was made. By looking at the timestamp, NDS can evaluate whether the most current updates have been received by that replica.
In versions of NDS before NetWare 5, an attribute called "Synchronized Up To" determined when the latest changes were made. The value of this attribute is unique for each replica and is not synchronized to the other servers in the replica ring (tree).
In versions of NDS that shipped with NetWare 5 and greater, NDS uses a Time Vector to track changes to a partition. This Time Vector holds timestamps for all the replicas in the replica ring from each server's perspective. Each server in the NDS Tree has a copy of its own Time Vector; in addition, each server also has copies of the Time Vectors of the other servers in the NDS Tree.
On a single server, these Time Vectors are referred to as the Transitive Vector. The Transitive Vector tracks any changes that occur to the immediate partition.
A multi-valued attribute, the Transitive Vector is added to the Root Partition for each NDS partition in NetWare 5 or greater releases of NDS. Differing from the Synchronized Up To attribute (which only holds one value for each replica in a partition), the Transitive Vector is a multi-valued attribute containing a group of Time Vectors. Each of these Time Vectors contains information about each replica. There is one Transitive Vector for each replica.
The Transitive Vector is synchronized between servers. This means that every server in the replica ring holds a copy of the Transitive Vectors for all other servers in the ring. By synchronizing the Transitive Vector values, all of the replicas can synchronize without having every replica communicate with every other replica.
To see how this works, let's look at file servers DNU1 and DNU2, each of which hold replicas of a partition. DNU1 holds replica 1 and DNU2 holds replica 2. The Transitive Vector stored on DNU1 would be made up of Time Vectors for DNU1 and DNU2. The Transitive Vector would look like the following (as seen by DSTrace):
server name = CN=DNU1
TIMEVECTOR.count = 00000002
TIMEVECTOR[0].timeStamp: 2001/12/18 17:01:05; rep# = 0001; event = 0001
TIMEVECTOR[1].timeStamp: 2001/12/18 17:00:34; rep# = 0002; event = 0001
server name = CN=DNU2
TIMEVECTOR.count = 00000002
TIMEVECTOR[0].timeStamp: 2001/12/18 17:00:34; rep# = 0002; event = 0001
TIMEVECTOR[1].timeStamp: 2001/12/18 17:00:28; rep# = 0001; event = 0001
The following table looks at each line of the transitive vector.
|
Transitive Vector Statement
|
Description
|
|
Server name=CN=DNU1 |
This time vector is for the server DNU1. |
|
TIMEVECTOR.count=00000002 |
This shows the number of replicas in this time vector. The timestamps for 2 replicas are in this time vector. |
|
TIMEVECTOR[0].timeStamp: 2001/12/18 17:01:05; rep# = 0001; event = 0001 |
The most recent update to replica #1 occurred on 2001/12/18 at 17:01:05. Note: Since this file server holds replica #1, this is the most current information about replica #1. |
|
TIMEVECTOR[1].timeStamp: 2001/12/18 17:00:34; rep# = 0002; event = 0001 |
The most recent update on replica #2 that DNU1 knows about occurred on 2001/12/18 at 17:00:34. Note: The actual latest update that occurred on replica #2 is stored on DNU2. This number indicates the last update that DNU1 knows about. |
|
Server name = CN=DNU2 |
This is the last time vector for the server DNU2 which DNU1 knows about. |
|
TIMEVECTOR.count = 00000002 |
The timestamps for 2 replicas are in this time vector |
|
TIMEVECTOR[0].timeStamp: 2001/12/18 17:00:34; rep# = 0002; event = 0001 |
The most recent update to replica #2 that DNU1 knows about occurred on 2001/12/18 at 17:00:34. |
|
TIMEVECTOR[1].timeStamp: 2001/12/18 17:00:28; rep# = 0001; event = 0001 |
The most recent update to replica #1 that DNU2 knows about occurred on 2001/12/18 at 17:00:34. Note: You know from above that the actual last update to replica #1 occurred on 2001/12/18 at 17:01:05. However, that information has not been received by DNU2, so this time vector has not been updated as yet. |
Note: Server DNU2 also has a corresponding Transitive Vector with the information from both servers in the replica ring.
Now that you have a basic understanding of the Transitive Vector, next month we will discuss Transitive Synchronization, what it is, and how it improves NDS.
* 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.