3.1.1.1.9 DCs, usn Counters, and the Originating Update Stamp

The model defines the state of a DC as a tuple of type DC.


type DC = [
    serverGuid: GUID,
    usn: 64-bit integer,
    prefixTable: PrefixTable,
    defaultNC: full domain NC replica,
    configNC: config NC replica,
    schemaNC: schema NC replica,
    partialDomainNCs: set of partial domain NC replica,
    appNCs: set of application NC replica,
    pdcChangeLog: PDCChangeLog
    nt4ReplicationState: NT4ReplicationState
    ldapConnections: LDAPConnections,
    replicationQueue: ReplicationQueue,
    kccFailedConnections: KCCFailedConnections,
    kccFailedLinks: KCCFailedLinks,
    rpcClientContexts: RPCClientContexts,
    rpcOutgoingContexts: RPCOutgoingContexts
 ]

The variable dc is the only global variable in this specification. It contains the state of the DC.


dc: DC

serverGuid is initialized to a fresh GUID when the dc is created and does not change thereafter. Section 7.1.1.2.2.1.2.1.1 describes the nTDSDSA object; serverGuid equals the objectGUID of the DC's nTDSDSA object. serverGuid is independent of the specific machine playing the role of this DC.

usn is a counter used in assigning replication metadata to every originating update to an NC replica in the DC, as detailed later in this section. The invocationId of dc's nTDSDSA object is an "epoch number" for usn; if an observer reads a dc at times t1 and t2 with t1 < t2, and invocationId is the same, then usn at time t1 is less than or equal to usn at time t2.

prefixTable is the PrefixTable used to translate all ATTRTYP values stored in this DC's NC replicas; section 3.1.1.2.6 specifies the translation process.

The default NC replica of an AD DS DC, modeled as dc.defaultNC, is a full domain NC replica of some domain NC in the forest. This is the only full domain NC replica in the state of a DC. In an AD LDS DC, dc.defaultNC is null.

The fields dc.configNC and dc.schemaNC contain replicas of the forest's config NC and schema NC.

If dc is not an AD DS GC server (determined by state in the config NC as specified in section 7.1.1.2.2.1.2.1.1), then dc.partialDomainNCs is null. Otherwise it contains a partial domain NC replica for each domain NC in the forest, excluding the default domain NC of dc.

The field dc.appNCs contains replicas of any subset of the application NCs in the forest.

An AD DS DC can be an RODC; [MS-DRSR] section 5:AmIRODC specifies how this is determined by state in the config NC. All NC replicas of an RODC are read-only; that is, they do not accept originating writes. In other DCs, all NC replicas are writable except for dc.partialDomainNCs.

The nt4ReplicationState and pdcChangeLog variables contain state used by the IDL_DRSGetNT4ChangeLog method ([MS-DRSR] section 4.1.11.3). Section 3.1.1.7 specifies the format of these variables and how they are maintained during state changes in AD DS.

The ldapConnections, replicationQueue, kccFailedConnections, kccFailedLinks, rpcClientContexts, and rpcOutgoingContexts fields of a DC are volatile state. Each volatile field is set to the empty sequence on server startup. The other fields are persistent state, updated using transactions.

The construction of the kccFailedConnections and kccFailedLinks fields of a DC are discussed in section 7.2. The construction of the replicationQueue, kccFailedConnections, and rpcOutgoingContexts fields are discussed in [MS-DRSR].

Each originating update on a DC creates replication metadata values (AttributeStamp and LinkValueStamp values), as will now be described.

AttributeStamp and LinkValueStamp values contain times read from the system clock of the server creating the value. If clocks on different DCs disagree by a significant fraction of the tombstone lifetime, then it is probable that different DCs will eventually disagree about whether some objects have been deleted or not; see section 3.1.1.1.15. DCs use Kerberos for mutual authentication, and Kerberos refuses to mutually authenticate two DCs whose clocks are more than 5 minutes out of sync. The tombstone lifetime is generally several months, so synchronization within 5 minutes is much better than required to avoid object lifetime issues.

The type AttributeStamp is defined authoritatively in [MS-DRSR] section 5:AttributeStamp. In summary, it is the following tuple.


AttributeStamp: [
    dwVersion: 32-bit Integer;
    timeChanged: 64-bit number of seconds
                 since January 1, 1601, 12:00:00am;
    uuidOriginating: GUID;
    usnOriginating: 64-bit Integer]

Similarly, the type LinkValueStamp is defined authoritatively in [MS-DRSR] section 5:LinkValueStamp. In summary, it is an AttributeStamp tuple extended on the bottom with the following fields:

  • timeCreated: 64-bit number of seconds since January 1, 1601, 12:00:00am;

  • timeDeleted: 64-bit number of seconds since January 1, 1601, 12:00:00am;

An AttributeStamp stamp is associated with all replicated attributes, except forward link attributes updated when the forest functional level is greater than DS_BEHAVIOR_WIN2000, that have ever had values on an object. For forward link attributes updated when the forest functional level is greater than DS_BEHAVIOR_WIN2000, a LinkValueStamp stamp is associated with each value of the attribute, both current link values and tombstoned link values. More details on tombstoned link values are given later in this section.

Let o!a.stamp denote the AttributeStamp associated with replicated attribute a on object o. When an originating update creates or modifies replicated attribute a on object o, the value of o!a.stamp is determined as follows:

  • dwVersion: If the attribute did not exist on this object before the originating update (that is, an LDAP Add operation of this object, or an LDAP Modify operation creating the initial value of this attribute on this object), dwVersion equals one. Otherwise dwVersion equals o!a.stamp.dwVersion before the update, plus one.

  • timeChanged: The time of the originating update, according to the system clock on this DC.

  • uuidOriginating: the invocationId of the dc's nTDSDSA object.

  • usnOriginating: dc.usn.

Once a replicated attribute exists on an object, it will continue to exist for the lifetime of the object, in order to carry the stamp. If all values have been removed from the attribute, the attribute will be absent from the LDAP perspective, but it remains present in the state model in order to preserve the stamp. If a value is added to o!a and o!a.stamp exists, even if o!a had no values before the addition, the value of o!a.stamp.dwVersion is used as described previously in creating the new stamp's dwVersion.

Let o!a.r denote a single link value r that is part of a replicated forward link attribute a, and let o!a.r.stamp denote the LinkValueStamp associated with this value. An originating update cannot modify a single link value r that is part of a forward link attribute, except to delete it or to re-create it. A link value r is deleted, but exists as a tombstone, if r.stamp.timeDeleted ≠ 0. When the current time minus r.stamp.timeDeleted exceeds the tombstone lifetime, the link value r is garbage-collected; that is, removed from its containing forward link attribute.

When an originating update creates a link value r of a forward link attribute a of object o, the LinkValueStamp o!a.r.stamp is computed as follows:

  • dwVersion: 1.

  • timeChanged: The time of the originating update, according to the system clock on this DC.

  • uuidOriginating: the invocationId of dc's nTDSDSA object.

  • usnOriginating: dc.usn.

  • timeCreated: The time of the originating update, according to the system clock on this DC.

  • timeDeleted: Zeros.

When an originating update re-creates a link value r of a forward link attribute a of object o, that is, a create occurs when the same link value exists as a tombstone, the LinkValueStamp o!a.r.stamp is computed as follows:

  • dwVersion: o!a.r.stamp.dwVersion before the originating update, plus one.

  • timeChanged: The time of the originating update, according to the system clock on this DC.

  • uuidOriginating: the invocationId of dc's nTDSDSA object.

  • usnOriginating: dc.usn.

  • timeCreated: o!a.r.stamp.timeCreated before the originating update.

  • timeDeleted: Zeros.

When an originating update deletes a link value r of a forward link attribute a of object o, the LinkValueStamp o!a.r.stamp is computed as follows:

  • dwVersion: o!a.r.stamp.dwVersion before the originating update, plus one.

  • timeChanged: The time of the originating update, according to the system clock on this DC.

  • uuidOriginating: the invocationId of dc's nTDSDSA object.

  • usnOriginating: dc.usn.

  • timeCreated: o!a.r.stamp.timeCreated before the originating update.

  • timeDeleted: The time of the originating update, according to the system clock on this DC.

The stamp values created by originating updates are used by protocols described in [MS-DRSR]. Some stamp values maintained in this state model are not used by those protocols; see [MS-DRSR] section 4.1.10.5.5 (FilterAttribute) for specifics on the stamps that are filtered out.

When all updates associated with an originating update request are complete, the variable dc.usn is increased by at least one. Between originating updates, the variable dc.usn does not decrease.

The effects of an originating update are captured in the state model by committing a transaction before sending the response. The transaction has the ACID properties [GRAY] and provides at least degree 2 isolation of concurrent read and update requests [GRAY].

Each read request is performed as a transaction. When multiple read requests are used to retrieve a large set of results, each request is its own transaction. Section 3.1.1.5 specifies the transaction boundaries that are used for all originating updates. To preview: An originating update is almost always performed as a single transaction; a few are processed as multiple transactions. In some cases, an originating update request will cause transactions to occur after the response has been sent; section 3.1.1.5 specifies all cases where processing of an update continues after the response.

The following example illustrates the effects of originating updates on stamp values. In this example, the forest functional level is assumed to be greater than DS_BEHAVIOR_WIN2000, so LinkValueStamps are used for updates to forward link attributes. In the example, stamp values are represented as lists whose elements are the elements of the stamp, in the order listed in the type definition. Thus dwVersion is always first, and timeDeleted is last in a LinkValueStamp. An AttributeStamp is placed between the attribute's lDAPDisplayName and the first value, if any. A LinkValueStamp is placed immediately following the link value.

This example shows the stamp values on two attributes of a single group object: the description attribute and the member attribute (a forward link attribute). In the initial state neither attribute is present.


(
  "<GUID=5>;<SID=0x0105...94E1F2E6>;dc=microsoft,dc=com"
  . . .
  ( (objectGUID 6) (parent 2) (cn "DSYS")
    (objectClass top ... group) 
    (name "DSYS") (rdnType cn)
    (objectSid 0x0105...94E1F2E60B080000)
  )
)

An LDAP Modify adds a value for description. This DC's invocationId is 103, and its usn is 501 at the time of the originating update.


(
  "<GUID=5>;<SID=0x0105...94E1F2E6>;dc=microsoft,dc=com"
  . . .
  ( (objectGUID 6) (parent 2) (cn "DSYS")
    (objectClass top ... group) 
    (name "DSYS") (rdnType cn)
    (objectSid 0x0105...94E1F2E60B080000)
    (description (1 0x2FA9A74EA 103 501) "QWERTY")
  )
)

An LDAP Modify adds a value for member. This originating update occurred one second after the previous one, with no updates in between. This pattern continues for the rest of this example.


(
  "<GUID=5>;<SID=0x0105...94E1F2E6>;dc=microsoft,dc=com"
  . . .
  ( (objectGUID 6) (parent 2) (cn "DSYS")
    (objectClass top ... group) 
    (name "DSYS") (rdnType cn)
    (objectSid 0x0105...94E1F2E60B080000)
    (description (1 0x2FA9A74EA 103 501) "QWERTY")
    (member
      "<GUID=9>;<SID=0x0105...07080000>;
       cn=Peter Houston,ou=NTDEV,dc=microsoft,dc=com" 
      (1 0x2FA9A74EB 103 502 0x2FA9A74EB 0) )
  )
)

An LDAP Modify removes the values of both description and member.


(
  "<GUID=5>;<SID=0x0105...94E1F2E6>;dc=microsoft,dc=com"
  . . .
  ( (objectGUID 6) (parent 2) (cn "DSYS")
    (objectClass top ... group) 
    (name "DSYS") (rdnType cn)
    (objectSid 0x0105...94E1F2E60B080000)
    (description (2 0x2FA9A74EC 103 503) )
    (member
      "<GUID=9>;<SID=0x0105...07080000>;
       cn=Peter Houston,ou=NTDEV,dc=microsoft,dc=com" 
      (2 0x2FA9A74EC 103 503 0x2FA9A74EB 0x2FA9A74EC) )
  )
)

An LDAP Modify sets member back to the value it had before the previous update. The stamp it receives is not what it had before.


(
  "<GUID=5>;<SID=0x0105...94E1F2E6>;dc=microsoft,dc=com"
  . . .
  ( (objectGUID 6) (parent 2) (cn "DSYS")
    (objectClass top ... group) 
    (name "DSYS") (rdnType cn)
    (objectSid 0x0105...94E1F2E60B080000)
    (description (2 0x2FA9A74EC 103 503) )
    (member
      "<GUID=9>;<SID=0x0105...07080000>;
       cn=Peter Houston,ou=NTDEV,dc=microsoft,dc=com" 
      (3 0x2FA9A74ED 103 504 0x2FA9A74EB 0) )
  )
)

Finally, an LDAP Modify sets description to a new value.


(
  "<GUID=5>;<SID=0x0105...94E1F2E6>;dc=microsoft,dc=com"
  . . .
  ( (objectGUID 6) (parent 2) (cn "DSYS")
    (objectClass top ... group) 
    (name "DSYS") (rdnType cn)
    (objectSid 0x0105...94E1F2E60B080000)
    (description (3 0x2fa9a74ee 103 505) "SHRDLU")
    (member
      "<GUID=9>;<SID=0x0105...07080000>;
       cn=Peter Houston,ou=NTDEV,dc=microsoft,dc=com" 
      (3 0x2FA9A74ED 103 504 0x2FA9A74EB 0) )
  )
)

Show: