Tracking Updates

Some directory services use timestamps to determine what changes need to be propagated. In these systems, it is important to keep the clocks on all directory servers synchronized. But keeping time closely synchronized in a large network is essentially impossible. Network links fail and clocks drift. And with some systems, unless time is perfectly synchronized among all copies of the directory, there is a chance for data loss or directory corruption.

Active Directory replication does not depend on time to determine what changes need to be propagated. It relies instead on the use of update sequence numbers (USNs) that are assigned by a counter that is local to each domain controller. Because these USN counters are local, it is easy to ensure that they are reliable and never "run backward" (that is, decrease in value). The trade-off is that it is meaningless to compare a USN assigned on one domain controller to a USN assigned on a different domain controller. The replication system is designed with this restriction in mind.

Some directory services use timestamps as the primary mechanism to determine what updates "win" (are preserved) in a conflict resolution. The typical policy is "last writer wins." Again, this leads to problems when clocks are inaccurate. For example, suppose that you set the clock forward to December 31, 9999, to perform Year 10,000 testing. As part of the testing, you update an attribute of some object. Then you set the clock back again. If the directory service employs a "last writer wins" policy, the update that you performed during the test cannot be overwritten until the year 10,000.

Active Directory replication does not use timestamps as the primary mechanism to determine what updates "win" (are preserved) in a conflict resolution. Instead, Active Directory uses volatility (number of changes) as the first element of the per-attribute "stamps" that are compared during conflict resolution. The second element is a timestamp. So if an attribute is updated once on domain controller A and once on domain controller B, the last writer's update wins. But if the attribute is updated twice on domain controller A and once on domain controller B, the update of domain controller A wins even if the clock of domain controller B is set forward to December 31, 9999. With Active Directory, clock skew can never prevent a value from being overwritten.

Deciding What Changes to Replicate: Update Sequence Numbers

The current USN is a 64-bit counter that is maintained by each Active Directory domain controller. At the start of each update transaction (originating or replicated) on a domain controller, the domain controller increments its current USN and associates this new value with the update request. This USN value is stored on an updated object in two ways for a replicated write and three ways for an originating write.

• The update's USN value is stored with each attribute changed by the update as the local USN of that attribute (originating and replicated writes). You can use the Repadmin command-line tool to view the local USN. Type repadmin /showmeta <object_DN > at a command prompt and view the column labeled "Loc. USN" in the output. (To use Repadmin, install the Support Tools that are located in the Support\Tools folder on the Windows 2000 Server installation CD. To install the tools, double-click the Setup icon in that folder. For information about installing and using the Windows 2000 Support Tools and Support Tools Help, see the file Sreadme.doc in the Support\Tools folder of the Windows 2000 operating system CD. For information about using Repadmin, see Windows   2000 Support Tools Help.)

• The maximum local USN among all of an object's attributes is stored as the object's usnChanged attribute (originating and replicated writes). You can use Ldp or ADSI Edit to examine an object's usnChanged value. Ldp is a graphical tool that you can use to perform connect, bind, search, modify, and delete operations against any LDAP-compliant directory. ADSI Edit is an MMC snap-in that you can install and use to manage Active Directory objects, including viewing and editing attributes. (To use Ldp and ADSI Edit, install the Support Tools that are located in the Support\Tools folder on the Windows 2000 Server installation CD. For more information about using Ldp and ADSI Edit, see Windows   2000 Support Tools Help.)

• For an originating write, the update's USN value is stored with each updated attribute as the originating USN of that attribute. Unlike the local USN and usnChanged , the originating USN travels with the attribute's value as it replicates. You can see the originating USN as the column labeled "Org. USN" in the output from the repadmin /showmeta command.

Note

The usnChanged attribute is indexed, which allows objects to be enumerated efficiently in the order of their most recent attribute write.

You can use Ldp or ADSI Edit to read the current USN of a domain controller. These tools use LDAP to read the highestCommittedUsn attribute on the rootDSE object for the domain controller. (For information about using ADSI Edit and Ldp to read rootDSE attributes, see "Active Directory Data Storage" in this book.)

High-Watermark

The high-watermark is a value that the destination domain controller maintains to keep track of the most recent change that it has received from a specific source domain controller for an object in a specific directory partition. The source domain controller uses this value to filter the objects that it considers for replication to the destination.

When a destination domain controller requests changes to a directory partition from a source domain controller, the source domain controller provides the changes in increasing order of the usnChanged attribute value. The usnChanged values from the source domain controller are not stored on objects at the destination domain controller, but the destination domain controller keeps track of the usnChanged value of the most recent object it successfully received from the source domain controller for a specific directory partition. This USN is called the destination's high-watermark with respect to the directory partition and the source domain controller.

When requesting changes, the destination domain controller sends its high-watermark value to the source domain controller. The source domain controller uses the information in the high-watermark to reduce the set of objects that it must consider for replication to the destination. No object whose usnChanged value is less than or equal to the high-watermark value can hold updates that the destination domain controller has not already received.

The high-watermark serves to decrease the CPU time and number of disk I/O operations that would otherwise be required to send only the changes that the destination domain controller has not yet received.

You can see the high-watermark in the output of the repadmin /showreps /verbose command. Look for lines that begin with "USNs:". The high-watermark USN is the number that is followed by "/OU".

Up-to-Dateness Vector

The up-to-dateness vector is a value that the destination domain controller maintains for tracking the originating updates that are received from all source domain controllers. The source domain controller uses this value to reduce the set of attributes that it sends to the destination domain controller.

When a destination domain controller requests changes for a directory partition, it provides its up-to-dateness vector to the source domain controller. On the basis of this value, the source domain controller can determine that the destination does or does not have an up-to-date value (or multivalue) for an attribute, and it sends updates accordingly. If the destination already has an up-to-date value, the source domain controller does not send that attribute. If the source has no attributes to send for an object, it sends no information at all about that object.

The up-to-dateness vector can contain an entry for each domain controller that holds a full replica of the directory partition. If the up-to-dateness entry that corresponds to source domain controller X contains the USN  n , the destination domain controller guarantees that it holds all updates to a specific directory partition that originated at domain controller X and that have an originating USN value of less than or equal to  n .

The up-to-dateness vector and the high-watermark are complementary filter mechanisms that work together to decrease replication latency. Whereas the high-watermark prevents irrelevant objects from being considered by the source domain controller with respect to a single destination, the up-to-dateness vector helps the source domain controller to filter irrelevant attributes (and entire objects if all attributes are filtered) on the basis of the relationships between all sources of originating updates and a single destination.

For a specific directory partition, a domain controller maintains a high-watermark value for only those domain controllers from which it requests changes, but it maintains an up-to-dateness vector entry for every domain controller that has ever performed an originating update, which is typically every domain controller that holds a full replica of the directory partition.

You can see the up-to-dateness vector in the output of the repadmin /showvector command. (For more information about using Repadmin, see Windows   2000 Support Tools Help.)

Resolving Conflicts: Stamps

Suppose that an attribute of some object is changed on domain controller X. Then before the change on domain controller X has replicated, the same attribute of the same object is changed on domain controller Y. Active Directory must ensure that when replication has occurred, all replicas agree on the value of the updated attribute.

Active Directory ensures agreement by attaching a unique stamp to each replicated attribute value (or multivalue) during an originating update. This stamp travels with the value as the value replicates. If the stamp of the value that was replicated is larger than the stamp of the current value, the current value (including the stamp) is replaced; otherwise, the current value (including the stamp) is left alone.

The stamp has the following three components:

• The version is a number that is incremented for each originating write. That is, when performing an originating write, the version of the new value is one larger than the version of the value that is being overwritten. If the attribute was never written before, the version that was assigned to its first originating write is 1.

• The originating time is the time of the originating write, to a one-second resolution, according to the system clock of the domain controller that performed the write.

• The originating DSA is a GUID that identifies the domain controller that performed the originating write.

You can see all three components of the stamp in output from the repadmin /showmeta command. The column labeled "Ver" contains the version, the column labeled "Org. Time/Date" contains the originating time, and the column labeled "Originating DSA" contains the originating DSA (expressed as "site\server" rather than GUID).

When stamps are compared, the version is the most significant, followed by the originating time and then the originating DSA. So if two stamps have the same version, the originating time almost always breaks the tie. In the extremely rare event that the same attribute is updated on two different domain controllers during the same second, the originating DSA breaks the tie in an arbitrary fashion.

Two different originating writes of a specific attribute of a particular object cannot assign the same stamp because each originating write advances the version at a specified originating DSA. (Notice that the originating time does not contribute to uniqueness.) Replicated writes cannot decrease the version because values with smaller versions lose during conflict resolution.

For more information about using Repadmin, see Windows   2000 Support Tools Help.

Originating Add

An Add request makes a new object with a unique objectGuid . The values of all replicated attributes that are set by the Add request are stamped Version = 1.

The Add request fails immediately if the parent object does not exist or if the originating domain controller does not contain a master replica of the parent object's directory partition.

Originating Modify

All Modify requests can be reduced to requests to replace the current value of an attribute with a new value as follows:

• A Modify request might specify that an attribute be deleted from the object. Attribute deletion is best thought of as replacing the attribute value with NULL. The NULL value occupies no storage of its own but does carry a stamp, as does any value that is stored as a directory attribute.

• A Modify request might specify that a value be added to the current value of an attribute. (This is most useful with an attribute that can have multiple values.) The effect is the same as the equivalent replace request (that is, replace the current values with the current values plus the added value).

For each attribute in the request, a Modify request compares the new value in the request with the existing value in the object. If the values are the same, the request to modify that attribute is ignored. If the resulting Modify request doesn't change any attributes, the entire request is ignored.

Otherwise, a Modify request computes a stamp for each new replicated attribute value by reading the version from the existing value (version=0 for an attribute that has never been written) and then adding 1 to this value. The Modify request replaces the old stamp values with new stamp values.

Originating Move

A Move request is essentially a special Modify request for a single attribute, the name attribute. The operation proceeds as described for the Modify request.

Originating Delete

A Delete request is essentially a special Modify request that does the following:

1. Sets the isDeleted attribute to TRUE.

2. Marks the object as a tombstone , which is an object that has been deleted but not fully removed from the directory.

3. Changes the relative distinguished name to a value that is otherwise impossible (cannot be set by an LDAP application).

4. Strips all attributes that are not needed by Active Directory. A few key attributes, including objectGuid , objectSid , distinguishedName , nTSecurityDescriptor , and usnChanged , are preserved on the tombstone.

5. Moves the tombstone to the Deleted Objects container, which is a hidden container within the directory partition.

Object deletions are replicated by replicating tombstones. A tombstone is invisible to normal LDAP searches. (A tombstone is visible to searches that use the special LDAP control 1.2.840.113556.1.4.417.) Object references that formerly referred to the deleted object now refer to the tombstone. Therefore, reading such a reference returns the distinguished name of the tombstone, not the distinguished name of the object prior to the object's deletion.

Garbage Collection: Deleting Tombstones

Although they represent deleted objects, tombstones take up space in every directory partition replica; so eventually the tombstones themselves must be deleted to keep the directory database from growing without limit. The garbage collection mechanism deletes tombstones.

Two settings on the object cn=Directory Service,cn=Windows NT,cn=Service,cn=Configuration,dc=ForestRootDomain determine how often garbage collection occurs and which tombstones are deleted:

• The garbage collection interval determines the number of hours between garbage collection on a domain controller. The default setting is 12 hours, and the minimum setting is 1 hour.

• The tombstone lifetime determines the number of days that tombstones persist before they are vulnerable to garbage collection. The default setting is 60 days, and the minimum setting is 2 days.

Garbage collection runs independently on each domain controller. When garbage collection occurs, it finds the set of tombstones whose originating delete occurred more than a tombstone lifetime ago. Garbage collection deletes each tombstone in the set.

The tombstone lifetime must be larger than the worst-case replication latency for any directory partition. Otherwise, a tombstone might be deleted before it has replicated to every directory partition replica. A directory partition replica that fails to replicate the tombstone would never delete the object, so it would be inconsistent with those replicas that had deleted the object.

Tombstone Lifetime Effect on Restore from Backup

A restore from backup creates a directory partition replica that has not performed replication since the time of backup (or earlier). If the backup was taken more than a tombstone lifetime before the restore, objects deleted in the meantime have no tombstones. The new directory partition replica never learns about these deletions. For this reason, a restore from backup refuses to restore a backup that was taken more than one tombstone lifetime before the time of the restore.

For more information about tombstones and garbage collection, see "Active Directory Data Storage" in this book. For information about restoring Active Directory from backup, see "Active Directory Backup and Restore" in this book.

Tracking Object Creation, Replication, and Change

The following series of diagrams illustrates the replication-related data for a single object and its attributes as it goes from creation through replication.

Figure 6.1 shows the replication-related data for the user object when it is first created on domain controller DC1.

Figure 6.1 Replication-related Data on DC1 When a User Object Is Created

Figure 6.2 shows the change to the destination domain controller when the new user object is replicated. The object is created as a replicated update on DC2. Notice that the per-attribute originating USN and stamp (version, originating time, originating DSA) are replicated from DC1 to DC2, but the per-attribute local USN and per-object usnChanged are unique to DC2.

Figure 6.2 Replication-related Data on DC2 When a New User Object Is Replicated from DC1

Figure 6.3 illustrates the change in the replicated object on DC2 when someone changes the password ( userPassword propertyin the diagram) of the object on that domain controller. By this time, the current USN on DC2 has increased from 1746 to 2001. The update request that changes the password increments the current USN to 2002 on DC2. The request also sets the password attribute's originating USN and local USN to 2002 and creates a new stamp for the password value. The version number of this password's stamp is 2, which is one version number higher than the version of the previous password.

Figure 6.3 Replication-related Data on DC2 After the User Password Value Has Been Changed on DC2

In Figure 6.4, the changed password is now replicated back to the original domain controller, whose current USN has increased to 5039. The replicated update increments the current USN to 5040. The per-attribute originating USN and stamp (version, originating time, originating DSA) are replicated from DC2 to DC1, and the per-attribute local USN and per-object usnChanged values are set to 5040.

Figure 6.4 Replication-related Data on DC1 After the Password Change Has Been Replicated to DC1

Propagation Dampening

Multiple replication paths can exist between a pair of domain controllers. Multiple paths provide fault tolerance and can reduce latency. However, when multiple paths exist, you might expect the same change to be sent along each path to a specific domain controller. You might even be concerned that a change might replicate in an endless loop. Active Directory prevents these potential problems with multiple paths by using the up-to-dateness vector described earlier.

The following is an example of how ordinary replication occurs:

1. DC A updates a password attribute. The originating USN of the attribute is set to 3.

2. Destination DC B requests changes from source DC A and sends its high-watermark and up-to-dateness vector to DC A.

3. According to the high-watermark that was passed by DC B, source DC A examines one or more objects, one of which contains the changed password. When DC A encounters the changed password attribute, it proceeds as follows:

   • First, DC A finds that the originating DSA of the password attribute is DC A.

   • Therefore, DC A reads the up-to-dateness vector supplied by DC B and finds that DC B is guaranteed to be up-to-date with updates that originated at DC A and that have an originating USN of less than or equal to 2.

   • DC A then finds that the originating USN of the password attribute is 3.

   • Because 3 is greater than 2, DC A sends the changed password attribute to DC B.

To illustrate propagation dampening, suppose that DC B had already received the password update from DC C, which had received it from DC A. In this case, the entry in the up-to-dateness vector of DC B for DC A would contain the USN value 3, not 2. Therefore, DC A would not send the changed password to DC B.