How the Active Directory–Data Store Really Works (Inside NTDS.dit)–Part 4

How deletion/removal of data really works in Active Directory
This is the fourth post in a series of articles that will describe what’s really inside NTDS.dit and how Active Directory works on the database layer, the past three articles has been about:

• Explains the tables within NTDS.dit in detail as far as what they are used for, in which release of Active Directory (Windows Server) they were introduced in, as well any major changes being added in later versions: How the Active Directory – Data Store Really Works (Inside NTDS.dit) – Part 1
• Explains how the object tree hierarchy is maintained at the database layer and the concept of DNTs and PDNTs and how they make up the relation between parent and descendent objects: How the Active Directory – Data Store Really Works (Inside NTDS.dit) – Part 2
• Explains the “Ancestors_col” that supports subtree searches and the security propagation (SDProp) – Part 3

This blog article will not cover the following scenarios:

1. Deletions of DSAs (Domain Controllers) cause it involves SAM and NETLOGON
2. The Foreign-Security-Principal Cleanup task – as it cleans and removes duplicate SIDs that only can end up in your directory in very rare scenarios and involves SAM – to – AD Upgrades.

This blog article wouldn’t have been possible without:

1. The ESEDump utility that I’ve developed together with my very good friend Stanimir Stoyanov – His contribution to the code has been invaluable.
2. Countless of sleepless nights and the support from my team at Enfo Zipper.

What you need as a prerequisites before reading this blog article:

1. Basic understanding of Active Directory at the database layer, that can be found at this blog:
   1. How the Active Directory – Data Store Really Works (Inside NTDS.dit) – Part 1:
      http://blogs.chrisse.se/2012/02/11/how-the-active-directory-data-store-really-works-inside-ntds-dit-part-1/
   2. How the Active Directory – Data Store Really Works (Inside NTDS.dit) – Part 2:

      http://blogs.chrisse.se/2012/02/15/how-the-active-directory-data-store-really-works-inside-ntds-dit-part-2/

   3. How the Active Directory – Data Store Really Works (Inside NTDS.dit) – Part 3

      http://blogs.chrisse.se/2012/02/20/how-the-active-directory-data-store-really-works-inside-ntds-dit-part-3/

Basic understanding of deletions in Active Directory

When an object is deleted in Active Directory (this is referred to as a logical deletion), the object is not immediately removed from Active Directory, and instead the object is flagged/marked for deletion by defining two or three attributes on the object depending on if the Active Directory feature “Recycle-Bin” is enabled and if there is Windows Server 2008 R2 or later DSAs that host a writeable instance of the object – see ‘Table 1.’

There are a few exceptions where deletions are trying to be physically deleted immediately (the row representing the object is being deleted from the database) without ever transit to the intermediate state of being a tombstone, deleted object or recycled object:

1. Dynamic-Objects, object that have the auxiliary class dynamic-Object present – those are physically removed once their time-to-live has passed; eventually they remain as phantom’s in the database until all references pointing towards them have been cleared.
2. Placeholder object’s that are in the distribution NTDS.dit – Deleted by DCPROMO.
3. A read-only naming context (NC) is being removed from a replica (e.g. a Global Catalog (GC) demotion)
4. Removal of lingering objects – using the operational attribute ‘removeLingeringObject’: http://msdn.microsoft.com/en-us/library/cc223303(v=prot.10).
5. Removal of an object as a result of being cross-domain moved.

   Table 1: Logical deletion sets the following attributes
   

Once objects are being logically deleted and transformed into tombstones, they lose most of their attributes – unless the Recycle Bin is enabled (and is as a result of a logical deletion being transformed into a “deleted object” rather than a tombstone).

The following attributes are always preserved (during a logical delete, regardless the state of the Recycle Bin) until the object (row in the database) is either

1. Physically deleted – (The object isn’t referenced by any other object within the database) the row representing the object can now safely be deleted.
   
2. The object (row) remains represented as a phantom to satisfy reference integrity (e.g. there is other objects (rows) in the database that reference the object and prevent the row from being physically deleted). Please see Phantoms and reference integrity below.
   

Attributes preserved on logical deletion

1. Attribute-ID (http://msdn.microsoft.com/en-us/library/ms675655(v=VS.85).aspx)
2. Attribute-Syntax (http://msdn.microsoft.com/en-us/library/windows/desktop/ms675236(v=vs.85).aspx)
3. DN-Reference-Update (http://msdn.microsoft.com/en-us/library/windows/desktop/ms675521(v=vs.85).aspx)
4. DNS-Host-Name (http://msdn.microsoft.com/en-us/library/windows/desktop/ms675524(v=vs.85).aspx)
5. Flat-Name (http://msdn.microsoft.com/en-us/library/windows/desktop/ms675678(v=vs.85).aspx)
6. Governs-ID (http://msdn.microsoft.com/en-us/library/windows/desktop/ms675721(v=vs.85).aspx)
7. Group-Type (http://msdn.microsoft.com/en-us/library/windows/desktop/ms675935(v=vs.85).aspx)
8. Instance-Type (http://msdn.microsoft.com/en-us/library/windows/desktop/ms676204(v=vs.85).aspx)
9. Is-Deleted (http://msdn.microsoft.com/en-us/library/windows/desktop/ms676802(v=vs.85).aspx)
10. Last-Known-Parent (http://msdn.microsoft.com/en-us/library/windows/desktop/ms676821(v=vs.85).aspx)
11. ms-DS-Last-Known-RDN (http://msdn.microsoft.com/en-us/library/windows/desktop/hh339647(v=vs.85).aspx)*
12. LDAP-Display-Name (http://msdn.microsoft.com/en-us/library/windows/desktop/ms676828(v=vs.85).aspx)
13. Legacy-Exchange-DN(http://msdn.microsoft.com/en-us/library/windows/desktop/ms676830(v=vs.85).aspx)
14. MS-DS-Creator-SID (http://msdn.microsoft.com/en-us/library/windows/desktop/ms678637(v=vs.85).aspx)
15. ms-DS-NC-Type (http://msdn.microsoft.com/en-us/library/windows/desktop/hh338635(v=vs.85).aspx)
16. MSMQ-Owner-ID (http://msdn.microsoft.com/en-us/library/windows/desktop/ms677886(v=vs.85).aspx)
17. NC-Name (http://msdn.microsoft.com/en-us/library/windows/desktop/ms678699(v=vs.85).aspx)
18. NT-Security-Descriptor (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679006(v=vs.85).aspx)
19. Object-Class (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679012(v=vs.85).aspx)
20. Obj-Dist-Name (http://msdn.microsoft.com/en-us/library/ms675516(v=VS.85).aspx)
21. Object-GUID (http://msdn.microsoft.com/en-us/library/ms679021(v=VS.85).aspx)
22. Object-SID (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679024(v=vs.85).aspx)
23. OM-Syntax (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679072(v=vs.85).aspx)
24. Proxied-Object-Name (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679423(v=vs.85).aspx)
25. Repl-Property-Meta-Data (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679448(v=vs.85).aspx)
26. RDN (http://msdn.microsoft.com/en-us/library/windows/desktop/ms678697(v=vs.85).aspx)
27. SAM-Account-Name (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679635(v=vs.85).aspx)
28. Security-Identifier (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679768(v=vs.85).aspx)
29. SID-History (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679833(v=vs.85).aspx)
30. Sub-Class-Of (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679891(v=vs.85).aspx)
31. System-Flags (http://msdn.microsoft.com/en-us/library/windows/desktop/ms680022(v=vs.85).aspx)
32. Trust-Attributes (http://msdn.microsoft.com/en-us/library/windows/desktop/ms680325(v=vs.85).aspx)
33. Trust-Direction (http://msdn.microsoft.com/en-us/library/windows/desktop/ms680334(v=vs.85).aspx)
34. Trust-Partner (http://msdn.microsoft.com/en-us/library/windows/desktop/ms680337(v=vs.85).aspx)
35. Trust-Type (http://msdn.microsoft.com/en-us/library/windows/desktop/ms680342(v=vs.85).aspx)
36. User-Account-Control (http://msdn.microsoft.com/en-us/library/windows/desktop/ms680832(v=vs.85).aspx)
37. Obj-Dist-Name (http://msdn.microsoft.com/en-us/library/ms675516(v=VS.85).aspx)
38. Object-GUID (http://msdn.microsoft.com/en-us/library/ms679021(v=VS.85).aspx)
39. USN-Changed (http://msdn.microsoft.com/en-us/library/ms680871(v=VS.85).aspx)
40. When-Changed (http://msdn.microsoft.com/en-us/library/ms680921(v=VS.85).aspx)
41. USN-Created (http://msdn.microsoft.com/en-us/library/ms680924(v=VS.85).aspx)
42. When-Created (http://msdn.microsoft.com/en-us/library/windows/desktop/ms680924(v=vs.85).aspx)

Additionally the attribute that serves as the RDN of the object being logically deleted is also always preserved. (E.g. CN/O/OU/DC)

Attributes that in the schema are defined to be preserved on deletion by having their searchFlags attribute containing bit 8 (0x00000008 = fPRESERVEONDELETE) are also preserved during a logical delete, unless they are linked attributes or a constructed attribute that drives it’s data from an attribute that is also not preserved.

Linked attributes are removed (Both forward links and backlinks) on logical deletions unless if the Recycle-Bin is enabled, then the links are deactivated instead.

To view deactivated links if the Recycle-Bin is enabled above the database layer, the following control can be used:

Table 2: LDAP controls to make deactivated links visible to LDAP

Note: See ‘The removal of linked attribute values’ – below for the behavior of removing a link value rather than a link value being removed as a part of a logical deletion.

You can read more about the searchFlags attribute here: http://msdn.microsoft.com/en-us/library/windows/desktop/ms679765(v=vs.85).aspx

The following attributes will always be removed (during a logical delete) regardless of searchFlags (0x00000008 = Preserve on delete) and regardless of the Recycle Bin state.

1. Object-Category (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679012(v=vs.85).aspx)
   1. During re-animation or undelete (if not supplied by the end-user) the objectCategory are driven back and set to the objectCategory of the objects most specific ObjectClass.
2. SAM-Account-Type (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679637(v=vs.85).aspx)
   1. During reanimation or undelete :
      1. If the object is a user, this is computed back to its original state by using the userAccountControls attribute.
      2. If the object is a group, this is computed back to its original state by using the groupType attribute.

Logical Deletion introduces the following internal columns to the database (NTDS.dit)

The following ‘internal’ columns (those are internal to the DSA only and are not real attributes) in addition with the attributes set in Table 1: ‘Logical deletion sets the following attributes’ represents the support on the database level for logical deletions of objects.

Table 3: datatable – Simplified for logical deletion

Sample NTDS.dit representing the state of a logically deleted object:

Once the deleted objects life time (DOL) has passed since the object was logically deleted, ‘recycle_time_col’ and ‘isRecycled’ will be set. See ‘Deleted objects lifetime and deleted objects’ below for more information.

Originating logical deletion constraints

1. The object has to reside in a writable naming context (NC) on the DSA where the logical deletion originates.
2. If the object being deleted has the following characteristics within the Security Descriptor:
   
   

   

   More exactly when the Sbz1 field has the value of 0x1 and the Control (RM control) field has the value (SECURITY_PRIVATE_OBJECT bit) of 0x1 and
   when deleting an object that resides within the schema naming context (NC) or the configuration naming context (NC) the following conditions have to be meet:

• The Domain Controller (DC) (where the originated delete is taking place) must be a member of the root domain in the forest, or
• The Domain Controller (DC) (where the originated delete is taking place) must be a member of the same domain where the current object owner belongs.

1. If the FLAG_DISALLOW_DELETE bit is set in the ‘systemFlags’ attribute of the object being deleted, the delete is being rejected by the DSA.
2. If the object being deleted is a tombstone e.g. has the ‘isDeleted’ attribute set to True and the Recycle Bin isn’t enabled, the delete is being rejected by the DSA.
3. If the object being deleted is recycled e.g. has the ‘isRecycled’ attribute se to True and the Recycle Bin is enabled, the delete is being rejected by the DSA.
4. If the object being deleted has descendants/child objects, the delete operation is being rejected by the DSA unless the requester has passed the LDAP_SERVER_TREE_DELETE_OID control.
   The following constraints applies to Tree-Deletes as well:
   1. The requester must have the RIGHT_DS_DELETE_TREE on the object being deleted. Note that no additional permissions are required on the descendants of the object.
   2. The tree-delete operation cannot be applied to a naming context (NC) root.
   3. Objects with the ‘isCriticalSystemObject’ attribute equal to true and which is not Security Account Manager (SAM) specific objects cannot be deleted by the tree-delete operation. This constraint is checked object-by-object, and deletion stops at the first deletion attempt that violates the constraint. If deletion stops, the resultant tree might not be the same as the original tree because some objects might have been deleted prior to the failure.
5. If the object being deleted resides within the schema naming context (NC) and the “Schema Devil” hasn’t been invoked, the delete is being rejected by the DSA.
6. If the object being deleted is the DC’s nTDSDSA object (representing the DSA where the delete operation is taking place) or any of its ancestors, the delete is being rejected by the DSA.
7. If the object being deleted is a crossRef object corresponding to the DC’s (The DSA where the delete operation is taking place) configuration, schema, or default domain naming contexts (NCs), the delete is being rejected by the DSA.
8. If the object being deleted is protected, the delete is being rejected by the DSA.
9. If the delete operation would require delayed link processing or link clean up (please see the section below: The link cleaner and the delayed link processing mechanism) and such processing is already taking place on the object that is about the be deleted, the DSA may or may not proceed with the requested delete operation depending on the following:
   1. The DSA is running Windows Server 2008 R2 or later and are subject to “Delayed Link Processing” and the object being deleted is already being processed by the “Delayed Link Processing” mechanism in a such way that the current processing can’t be merged with the requested operation (To remove forward or backward links associated with the object being deleted) – that is if:
      1. The ongoing link processing is performing any of the following operations:
         1. Processing Physical Link Deletions (Can be merged with the delete operation if the Recycle-Bin is absent, otherwise the delete is being rejected by the DSA)
         2. Processing Logical Link Deletions (Can be merged with the delete operation if the Recycle-Bin is present, otherwise the delete is being rejected by the DSA)
         3. Processing Logical Link Un-Deletions (Can’t be merged with the delete operation, the delete is being rejected by the DSA)
         4. Processing/Touching MetaData for groupType change (Can’t be merged with the delete operation, otherwise the delete is being rejected by the DSA)
      2. If the current operation implicit force processing on a specific attribute, a merge can only take place if the requested operation is about to perform processing on the same attribute, otherwise the delete is being rejected by the DSA.
      3. If the current operation implicit force processing bound by a specific update sequence (USN), a merge can only take place if the requested operation is about to perform processing bound to the same USN, otherwise the delete is being rejected by the DSA.
   2. The DSA is running Windows Server 2003 or Windows Server 2008 and are therefore subject to “Link Cleaner” – However the Link Cleaner has the ability for any object being processed to determine the required work to perform by the objects current state (instead of from a work list), that is if the delete operation requires processing (To remove forward or backward links associated with the object being deleted) – and the object already is under link cleanup, the current link cleanup task will pick up the requirement just made by the delete operation.

The Deleted Objects (DO) containers

When an object is logically deleted, they are eventually moved into something referred to as the “Deleted Objects Container” (DO container) – Each and every naming context (NC) in Active Directory has by default a deleted objects container except the Schema naming context (NC).

The deleted objects container(s) are not visible to ADSI or LDAP by default- However they can be made visible to LDAP by specifying a server control. (The deleted objects container(s) are marked as deleted themselves by having the “isDeleted” attribute set to: True) and are therefore by default invisible as any other deleted object.

The following controls make the deleted objects container(s), the deleted objects and eventually recycled objects visible.

Table 4: LDAP controls to make tombstones, deleted objects and recycled objects visible to LDAP

The deleted objects container(s) are referenced as well-known objects on each naming context (NC) head they belong to by the “wellKnownObjects” attribute, the reference is stored with the syntax binary distinguished name (Binary-DN) where the DN portion must be the DN of the deleted objects container ex: “CN=Deleted Objects,CN=Configuration,DC=X” and the binary portion must contain a well-known GUID (identifying that the DN represent a deleted objects container) “18E2EA80684F11D2B9AA00C04F79F805” if no such entry is present in the “wellKnownObjects” attribute on the naming context (NC) head the NC is considered to not having a deleted objects container.

Logically deleted objects are moved into the “Deleted Objects” container except in the following cases:

1. There is no “Deleted Objects” container in the NC the object resides in
2. The object has the SystemFlags bit: FLAG_DISALLOW_MOVE_ON_DELETE
3. The object is a naming context (NC) head.
4. The object is being removed as a part of the removal of an entire read-only naming context (NC)

If the object can’t for some reason be moved into a deleted objects container, the object is deleted anyway (The attributes in Table 1: ‘Logical deletion sets the following attributes’ are still set) but without being moved, additionally objects that are immediately physically deleted (e.g. objects that never transit to the phases of tombstones, deleted objects or recycled objects, such as dynamic objects for example) are never moved into a deleted objects container.

The Deleted Objects (DO) containers implements the following semantics to the database (NTDS.dit)

Note: ‘time_col’ is set to “9999-12-29 23:59:59” – pretty far from now right? As mentioned above the ‘Deleted Objects’ container(s) them self are having ‘isDeleted’ true making them invisible to LDAP except when the LDAP_SERVER_SHOW_DELETED_OID control is passed – this comes with another problem. What prevents the ‘Deleted Objects’ container(s) from being garbage collected? Well they are on the index and appear as a deleted object, it’s just that it won’t happen until “9999-12-29 23:59:59”

I did a test and actually changed this to something (not that far) away in time:

Name mangling for deletion

When an object is logically deleted, they are eventually relative distinguished name (RDN) mangled for deletion – that is to enforce an unique relative distinguished name (RDN) when and if the object is being moved into the deleted objects container (Please see the: ‘The Deleted Objects (DO) containers’ above for constraints when the object moves)

An relative distinguished name (RDN) is mangled for deletion as follows:
<RDN>0x0ADEL:<GUID>
Note: The <RDN> might be truncated to ensure the whole new RDN isn’t larger than 255 characters.
Sample: “CN=Christoffer Andersson\0ADEL:1e5f5da7-af10-4d69-9c06-491c79659116”

If the Recycle-Bin is enabled, the original relative distinguished name (RDN) is stored in the msDs-LastKnownRDN before it’s mangled for deletion.

Logically deleted objects are relative distinguished name (RDN) mangled except the following cases:

1. The object is a naming context (NC) head.
2. The object is being removed as a part of the removal of an entire read-only naming context (NC).

Objects that are immediately physically deleted (e.g. objects that never transit to the phases of tombstones, deleted objects or recycled objects, such as dynamic objects for example) – don’t have their names mangled for deletions either.

The removal of linked attribute values

Prior to Windows Server 2003 and Linked Value Replication (LVR) – Linked values where removed instantly from the ‘link_table’ on each DSA.

Linked value replication (LVR) allows individual values of a multivalued attribute to be replicated separately. In Windows 2000 Server, when a change was made to a member of a group (one example of a multivalued attribute with linked values) the entire group had to be replicated including all linked values. With linked value replication (LVR), only the group member that has changed is replicated, and not the entire group. Linked valued replication (LVR) was introduced in Windows Server 2003 and requires all DSAs in the forest to run at least Windows Server 2003 and the forest functional level (FFL) to be Windows Server 2003 or later, other than those requirements linked value replication requires replication metadata peer value in addition to replication metadata peer attribute to track changed values.

Starting with linked value replication (LVR) the state of a deleted (ABSENT) value has to be replicated and received by all DSAs within the tombstone lifetime (TSL) just like logically deleted objects – after that a value has been deleted (marked as ABSENT) it will be garbage collected and physically removed once a tombstone lifetime (TSL) has elapsed since the date if the delete – Please see ‘Tombstones and tombstone lifetime’ and ‘The Garbage collector process’ below for more information.

The following events are logged if an ABSENT linked value is garbage collected (physically deleted from the database):

Table 5: ABSENT Linked Value being Garbage Collected

Note: The following event is only logged if the logging level for ‘Garbage Collection’ is set to at least ‘basic’ level ‘2’
http://technet.microsoft.com/en-us/library/cc961809.aspx

Linked Value Replication (LV) introduces the following internal columns to the database (NTDS.dit)

The following ‘internal’ columns (those are internal to the DSA only and are not real attributes)

Table 6: link_table – Simplified for linked value replication (LVR)

Let’s have a look at the ‘link_table’ in NTDS.dit with link values representing the LEGACY, PRESENT and ABSENT states:

The link cleaner and the delayed link processing mechanism

The link cleaner (Present in Windows Server 2003 and later) and the delayed link processing (Present in Windows Server 2008 R2 and later) are mechanisms that continue operations regarding links on objects that needs and have been marked for “cleaning”, objects needs “cleaning” when more than a maximum numbers of links have to change state (only the maximum limit of links are going to change to its desired new state in the original transaction) the remaining links are going to be processed (in batches of the maximum limit in their own transactions) by either the link cleaner or the delayed link processing mechanism that runs as an scheduled task.

The reason for that only a maximum (limit) of links can change state in a single transaction is to avoid ESE version store limits (e.g. the numbers of changes that can be held in the ‘copy buffer’ and commit in a single transaction to the NTDS.dit database) – therefor the remaining links over the maximum limit has to be processed in separate transactions, hence the link cleaner and the delayed link processing mechanism.

The link cleaner was introduced in Windows Server 2003 – the issue was introduced/become more critical with the capability of Linked Value Replication (LVR) that allows a linked attribute to store more than 5000 linked values.

Table 7: Background processing of linked values

The following events will eventually trigger the link cleaner or the delayed link processing mechanism:

Table 8: Events that trigger background processing of linked values

In Windows Server 2008 R2 and later, the amount of links that are processed in a single transaction can be configured by a registry parameter: “Links process batch size”.

‘Links process batch size’ DWORD registry values can be configured within the following key:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\<INSTANCE>\Parameters.
Note: a value of 0 can’t be used – and I strongly don’t recommend anyone to change the default behavior.

The Delayed Link Processing or the Link Cleaner process can be initiated manually by triggering the operational attribute: “doLinkCleanUp”: http://msdn.microsoft.com/en-us/library/cc223304(v=prot.10) on Windows Server 2003 DSAs or later.

The link cleaner and the delayed link processing mechanism implements the following at the database level (NTDS.dit)

Table 9: datatable – Simplified for the link cleaner and the delayed link processing mechanism

Table 10: datatable – Indices required to support the link cleaner or and the delayed link processing mechanism

The following Performance Monitors are available to track Delayed Link Processing:

Table 11: Delayed Link Processing Performance Counters

Tombstones and tombstone lifetime
The object remains in this state (referred to as tombstones) for the period of tombstone lifetime (TSL) that is by default either 60 or 180 days depending on the operating system and service pack level of the first domain controller introduced in the Active Directory forest:

Table 12: tombstoneLifetime (TSL) defaults

The defaults are more specifically defined in the [Directory Service] section of the schema.ini file that is used during the DCPROMO process; table 2 gives you an extract of the schema.ini file:

Table 13: Schema.ini (TSL) defaults

The tombstone lifetime (TSL) is defined in days by the “tombstoneLifetime” attribute on the “CN=Directory Service,CN=Windows NT,CN=Services,CN=Configuration,DC=X” object. However if the attribute doesn’t contain a value e.g. is NULL – tombstone lifetime (TSL) is always 60 days regardless of ‘Table 1.’

If a value of less than 2 days is specified, the tombstone lifetime (TSL) defaults to 60 days, except for Windows Server 2008 R2 and Windows Server 2012, where the tombstone lifetime defaults to 2 days, finally the tombstone lifetime (TSL) can as mentioned in ‘Table 2.’ above be defined in “schema.ini” before the first domain controller is promoted in the forest.

The tombstones remain for as long as the tombstone lifetime (TSL) and are then deleted from the database (this is referred to as physical deletion and happens locally on each DSA by the Garbage Collector), eventually the object (row) remains represented as a phantom that exists in the database to satisfy reference integrity (e.g. other rows in the database that references the row being deleted).

Deleted objects lifetime and deleted objects

The deleted objects lifetime also known as the DOL and was introduced with Windows Server 2008 R2 to support the Recycle Bin feature where it becomes possible to un-delete an already deleted object to its original state, the deleted objects lifetime (DOL) determines the timeframe in days (by default the same as tombstone lifetime), for how long a deleted object is left in a deleted state so that it can be fully restored (un-deleted). Once the object has passed the DOL it’s transformed into a recycled object that reminds of a tombstone and is processed very likely a tombstone.

The deleted objects lifetime is defined in days by the “msDS-DeletedObjectLifetime” attribute on the “CN=Directory Service,CN=Windows NT,CN=Services,CN=Configuration,DC=X” object. However if the attribute doesn’t contain a value e.g. is NULL – the deleted objects lifetime is equal to the tombstone lifetime mentioned above. However the deleted objects lifetime can never be shorter than 2 days.

The deleted objects remain for as long as the deleted object lifetime (DOL) and are then translated into a recycled object, where most information on the object is stripped away.

Dynamic Objects

Dynamic objects were introduced with Windows Server 2003 (by introducing the ability to dynamically linking auxiliary classes to instantiated objects). More specifically the “dynamicObject” auxiliary class that can be added to an object during creation/instantiation of an object and/or added as an objectClass later on to an already existing/instantiated object.

Dynamic objects are objects that are automatically deleted after a period of time. When they are deleted (automatically or manually), they do not transform into any other state, such as a tombstone, deleted-object, or recycled-object (However they may transform into a none-object also known as a phantom to satisfy reference integrity). They are distinguished from regular objects by the presence of the dynamicObject auxiliary class among their objectClass values. The intended time of deletion is specified (in seconds) by the Entry-TTL attribute.

The following requirement applies to Dynamic Objects:

• Most be hosted by a Windows Server 2003 DSA or later
  • Can only be instantiated in a domain naming context (Domain NC) if the forest functional level (FFL) is Windows Server 2003 or later
    Note: This is cause a down-level DSA (earlier than Windows Server 2003) wouldn’t know what dynamic objects are, and wouldn’t delete them). One can first think that a requirement of domain functional level (DFL) would have been more suitable. However the object still has the possibility to be spread to down-level DSAs in other domains thought Global Catalogs (GCs).
  • Can always be instantiated in none-domain naming contexts (NDNCs) – because NDNCs can’t by design ever be fully hosted by a down-level DSA (earlier than Windows Server 2003) nor are they Global Catalog (GC) replicated. (I’ve done several attempts to trick an NDNC into being GC replicated without success)
  • Can never be instantiated in/added to an object at:
    • The Schema naming context (NC)
    • The Configuration naming context (NC)
    • An object that has the FLAG_DISALLOW_DELETE bit present in their systemFlags attribute:
• All if any descendant objects, they must be dynamic objects as well.
• Must be physically deleted by the DSA when all of the following conditions are meet:
  • The current time is greater than or equal to its msDS-Entry-Time-To-Die.
  • There are no descendant objects.
    • In theory there should never be, any descendant objects will have their msDS-Entry-Time-To-Die adjusted by the garbage collector so that they are removed before its parent.
  • There is no simple (none-linked) references to the object (there is no other object referencing the dynamic object)
    • If there are simple (none-linked) references to the object, the object (row) remains represented as a none-object also known as a phantom.
  • The object is not a critical system object (e.g. NOT having the Is-Critical-System-Object or is-Critical-Object set to: True)

Entry-TTL requirements:
The Entry-TTL attribute specifies (in seconds) the intended time-to-live (TTL) for the dynamic (once the time has elapsed the object is being processed for physical deletion by the DSA) and have the following requirements:

 

1. The minimum Entry-TTL that can be configured/set for any dynamic object is the configurable value ‘DynamicObjectMinTTL’ value that’s by default are 900 seconds (15 minutes).
   However the ‘DynamicObjectMinTTL’ default value is configurable and can be changed by modifying the ‘DynamicObjectMinTTL=<seconds>’ value of the “msDS-Other-Settings” attribute on the “CN=Directory Service,CN=Windows NT,CN=Services,CN=Configuration,DC=X” object (The minimum value is 1 and the maximum value is 31557600 (one year).If the ‘DynamicObjectMinTTL’ value isn’t present in the “msDS-Other-Settings” attribute, the default is 900 seconds (15 minutes).
2. The maximum Entry-TTL that can be configured/set for any dynamic object are by default defined by the upper-Range attribute of the Entry-TTL schema object. The default maximum value is 31557600 seconds (one year).
   Note: The upper-Range attribute can’t be modified on a constructed attribute, it is possible to change this default value but it’s not recommended and requires a lot of knowledge.
3. The Entry-TTL can be set during the instantiation/creation of a dynamic object as long as the value is between (1.) and (2.) above.
   However if there is no Entry-TTL attribute specified during the creation of a dynamic object, The DSA will set an default configurable value ‘DynamicObjectDefaultTTL’ value that’s by default are 86400 (one day).However the ‘DynamicObjectDefaultTTL’ default value is configurable and can be changed by modifying the ‘DynamicObjectDefaultTTL =<seconds>’ value of the “msDS-Other-Settings” attribute on the “CN=Directory Service,CN=Windows NT,CN=Services,CN=Configuration,DC=X” object (The minimum value is 1 and the maximum value is 31557600 (one year).

How Dynamic Objects are maintained by the DSA

Dynamic objects are maintained by the DSA (evaluated for deletion once their TTL is expiring) by two different tasks:

1. By its own scheduled task that is initiated and starts 15 minutes after startup – the task then process dynamic objects in the following manner:
   1. Process dynamic objects that match: current time => msDS-Time-To-Die value until all dynamic objects in the range has been processed or > 5000 objects has been processed (ESE version store limit) or abort if a shutdown has been initiated.
      1. If the object found wasn’t able to be deleted because any of the following reasons skip to next candidate:
         1. The object is marked critical. (e.g. the isCriticalSystemObject is set to: TRUE)
         2. The object has backlinks pointing towards it and those can’t be removed.
         3. The object still have descendant / child objects.
         4. The object has simple references pointing towards it and was there for converted into a none-object also known as a phantom instead.
   2. If (.a) complete the task with the following status:
      1. There was more than 5000 object to process (more object’s than can be modified in a single ESE DB transaction to the NTDS.dit with respect to the ESE version store):
         Action: The task is re-scheduled immediately.
      2. If the last object that was evaluated in (a.) and hadn’t reached its expiring time yet, and was about to expire in less than the default configurable ‘Delete expired entryTTL (secs)’ value that’s by default are 900 (15 minutes) then the task is re-scheduled within the default configurable ‘Delete next expired entryTTL (secs)’ value that’s by default are 30 (30 seconds) + the seconds until that object is expiring.

          

         The ‘Delete next expired entryTTL (secs)’ and the ‘Delete next expired entryTTL (secs)’ DWORD registry values can be configured within the following key:
         

         HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\<INSTANCE>\Parameters.

         Note: if those registry values aren’t present the defaults mentioned above will take place, the value can’t be 0 (zero) and the updated values aren’t affected until next reboot.

      3. If (i.) or (ii.) didn’t occur then the task would be re-scheduled to run within the default configurable ‘Delete expired entryTTL (secs)’ value that’s by default are 900 (15 minutes) again.
2. By the garbage collector (Please see the next section: The Garbage collector process)

The Garbage collector process

The Garbage collector process runs by default every 12 hours and 15 minutes after startup independently on each DSA, the garbage collection interval is defined in hours by the: “garbageCollPeriod” attribute on the “CN=Directory Service,CN=Windows NT,CN=Services,CN=Configuration,DC=X” object. (Minimum is one hour and maximum is one week) However if the attribute doesn’t contain a value e.g. is NULL – Then the garbage collection period is always the default 12 hours.

The Garbage Collector process can be initiated manually by triggering the operational attribute: “doGarbageCollection”: http://msdn.microsoft.com/en-us/library/cc223317(v=prot.10)

The following event is logged once the Garbage Collector process is initiated:

Table 14: Garbage Collection Initialization Event

Note: The following event is only logged if the logging level for ‘Garbage Collection’ is set to at least ‘Extensive’ level ‘3’
http://technet.microsoft.com/en-us/library/cc961809.aspx

The Garbage Collector is responsible for the following subtasks:

1. Manage logically deleted objects and phantoms:
   1. Phantoms that is older than the TSL/DOL:
      1. Physically delete: reference countless phantoms that doesn’t appear on the ‘recycle_time_index’ (e.g. has a ‘time_col’ value that has passed TSL/DOL.)
      2. Modify: phantoms with (that has) reference counts and set their ‘time_col’ to the current date, which have expired and doesn’t appear on the ‘recycle_time_index’ (e.g. had a ‘time_col’ value that had passed TSL/DOL.) – So that they won’t be looked at again for another TSL/DOL.
   2. Deleted Objects that is older than the TLS/DOL:
      1. Physically delete: All Deleted Objects if the schema doesn’t have the ‘IsRecycled’ attribute *Only happens on a Windows Server 2008 R2 DSA or later
         Note: Can happen in AD LDS
      2. Physically delete: All Deleted Objects in none-writable naming contexts (NCs) if the recycle bin is in the off state
      3. Recycle: Deleted Objects in writable naming contexts (NCs)*Only happens on a Windows Server 2008 R2 DSA or later and schema has ‘isRecycled’
      4. Physically delete: All boot-strap objects from the distribution database (NTDS.dit)
   3. Recycled-Objects that is older than the TSL:
      1. Physically delete: All Recycled-Objects regardless of naming context (NC) or state of the recycle bin.
   4. Recycled-Phantoms that is older than the TSL:
      1. Physically delete: All Phantoms that are reference countless and appear on the ‘recycle_time_index’ (e.g. has a ‘recycle_time_col’ value that has passed TSL).
      2. Modify: phantoms with (that has) reference counts and set their ‘recycle_time_col’ to the current date, which have expired and appears on the ‘recycle_time_index’ (e.g. had a ‘recycle_time_col’ value that had passed TSL.) – So that they won’t be looked at again for another TSL.
   5. Deleted Linked-Values that is older than the TSL:
      1. Physically delete: All linked-value replication (LVR) values that are ABSENT and older than the TSL.
   6. Dynamic objects that is older than their ‘msDS-Time-To-Die’:
      1. Physically delete: All dynamic objects that has expired (older than their time to live).
         Note: (For detailed processing, please see the section above: How Dynamic Objects are maintained by the DSA)

   Note: Pre-Windows Server 2008 R2 DSAs (a.) and (b.) above applies to TSL rather than DOL.
   

   Note: Pre-Windows Server 2008 R2 DSAs doesn’t process step (c.) and (d.) above.
   

   Note: Pre-Windows Server 2003 DSAs doesn’t process step (e.) and (f.) above.

   The following is logged once the garbage collection processes successfully removes a tombstone or recycled object (the object is most likely really demoted to a phantom):

   Table 15: Garbage Collection Removal Event
   

Note: The following event is only logged if the logging level for ‘Garbage Collection’ is set to at least ‘Verbose’ ‘4’
http://technet.microsoft.com/en-us/library/cc961809.aspx

 

1. Database maintenance:
   1. Perform online defragmentation of the Active Directory database NTDS.dit – if and only if the following DSA Heuristics flag has not been set:
      DecoupleDefragFromGarbageCollection (0000000001) and the DSA didn’t processed more than 5000 objects or values according to the table below:
      http://support.microsoft.com/kb/871003

      The following event is logged once the online defragmentation has completed:

      Table 16: Online Defragmentation Completed Event
      

Note: The following event is only logged if the logging level for ‘Garbage Collection’ is set to at least ‘Minimal’ level ‘1’
http://technet.microsoft.com/en-us/library/cc961809.aspx

The Garbage Collection process is rescheduled more aggressively than the garbage collection period if there was more than 5000 objects/phantoms and/or values examined:

Table 17: Garbage Collector background task reschedule

The following indices are implemented at the database layer to support the garbage collection tasked described above:

Table 18: datatable – Indices required to support the Garbage Collection Process

The following Performance Monitors are available to track Garbage Collection activity:

Table 19: Garbage Collection Performance Counters

The following event will be logged once the Garbage Collector task has completed:

Table 20: Garbage Collection Completed Event

Note: The following event is only logged if the logging level for ‘Garbage Collection’ is set to at least ‘Extensive’ level ‘3’
http://technet.microsoft.com/en-us/library/cc961809.aspx

Initialization of the Recycle-Bin in the off mode – Introduction of a Windows Server 2008 R2 DSA or later

So turning the Recycle-Bin off is impossible right? We’ll all writable Windows Server 2008 R2 and later DSAs actually will do so on every startup, but not in the way you’re thinking. However they are sort of preparing for someone to eventually turning the feature on in the future (this task can simply be referred to as a cleanup).

This is accomplished by scanning the ‘deltime_not_recycled_index’ for tombstones (excluding phantoms) (e.g. logically deleted objects with ‘isDeleted’ set to ‘1 (True)’) in all writable naming contexts (NCs) present on each writable Windows Server 2008 R2 DSA or later (regardless of functional level) and recycles them, e.g. setting ‘isRecycled’ to ‘1 (True)’ and their ‘recycle_time_col’ so that they instead appear on the ‘recycletime_index‘ and disappears from the ‘deltime_not_recycled_index’ there is however two conditions:

• The ‘isRecycled’ attribute must be present in the schema
• The Recycle-Bin must be off (However it must have been off at some time, the exception here is DSA being built from a Install From Media (IFM) database (NTDS.DIT))

This is required because the garbage collector in Windows Server 2008 R2 or later works with the ‘recycletime_index’ for physically deleting tombstones and recycled objects in writable naming contexts, this is an optimization so that once the Recycle-Bin is enabled; there is no need to simultaneously on all DSAs trying to convert all current tombstones into recycled objects.

The initialization process will process tombstones in batches of 5000 until it re-schedule itself again (as the regular garbage collection process, please see ‘The Garbage collector process’ above) until it has finished processing all tombstones and log the following event for every time it reschedules:

Table 21: Windows Server 2008 R2 DSA still processing initialization of the Recycle-Bin in the off-mode

Note: The following event is only logged if the logging level for ‘Garbage Collection is set to at least ‘basic’ level ‘2’
http://technet.microsoft.com/en-us/library/cc961809.aspx

Once it has completed processing all tombstones the following event will be logged:

Table 21: Windows Server 2008 R2 DSA has completed processing initialization of the Recycle-Bin in the off-mode

Note: The following event is only logged if the logging level for ‘Garbage Collection is set to at least ‘basic’ level ‘2’
http://technet.microsoft.com/en-us/library/cc961809.aspx

This also comes with one disadvantage initially – Temporary Lingering Objects:

Recycle an object (in this case a tombstone) e.g. setting ‘isRecycled’ to ‘1 (True)’ is a replicating event – causing the change to replicate out to other DSAs that host/or has hosted the object in the past (as it is a tombstone) it could already have been physically deleted on some DSAs depending on if/when those DSAs where restarted and when the latest scheduled garbage collection process took place. In the case where the object has already been physically deleted, and an update to the object is being replicated to a now nonexistent object on this DSA (The DRA – Replicator on this DSA is going to treat this as an ‘Add’ for a new object until it realize it’s missing required attributes for an ‘add’ of a new object) – the DSA is going to indicate lingering objects by logging the following event:

Table 21: Lingering Object caused by introduction of a writable Windows Server 2008 R2 or later DSA

The situation is going to resolve itself within a garbage collection interval that is default 12 hours (e.g. all DSAs will have garbage collected the object/Physically deleted the object from the database) – however the issue can be remediated by doing one of the following:

1. Triggering the operational attribute: “doGarbageCollection” to force a Garbage Collection instantly on effected DSAs : http://msdn.microsoft.com/en-us/library/cc223317(v=prot.10)
2. Increase the garbage collection interval prior to the introduction of the first writable Windows Server 2008 R2 DSA or later.

Once this has been performed on a Windows Server 2008 R2 DSA or later for the first time in all writable naming contexts in your forest, it’s unlikely that the initialization of Recycle-Bin in the off mode are going to find any tombstones to convert into recycled objects in the future (although this is checked on every startup), because from now on a logical deletion (while the Recycle-Bin is still off) will have both the ‘isRecycled’ and the ‘isDeleted’ attribute set by the writable Windows Server 2008 R2 and later DSAs.

Phantoms and reference integrity

So what is reference integrity in Active Directory?
References in Active Directory are one object pointing to another object (Or one row that references another row in the database) by an attribute that has one of the following syntaxes:

• Object(DS-DN)
• Object(DN-String)
• Object(DN-Binary)
• Object(Access-Point)
• Object(OR-Name)

The requirement that comes with references is that an object (row in the database) that has other objects (rows in the database) pointing towards it (referencing it) – Can’t be physically removed unless all references are removed first.

Let’s create two objects, where one of the objects references the other object by the attribute ‘seeAlso’:

dn: cn=Christoffer Andersson,cn=ESEDEV,DC=ADAM,DC=chrisse,DC=com
changetype: add
objectClass: user

dn: cn=Jimmy Andersson,cn=ESEDEV,DC=ADAM,DC=chrisse,DC=com
changetype: add
objectClass: user
seeAlso: cn=Christoffer Andersson,cn=ESEDEV,DC=ADAM,DC=chrisse,DC=com

Let’s now logically delete the first created object “CN=Christoffer Andersson” (that the other object “CN=Jimmy Andersson” references) and wait until the object is up for physical deletion (e.g. the tombstone life time has passed since the object was logically deleted) – “CN=Christoffer Andersson” is now about to be physically deleted from the database, but it’s NOT (To satisfy the requirement mentioned above and not leaving the object “CN=Jimmy Andersson” pointing to a none-existing object in its ‘seeAlso’ attribute) instead “CN=Christoffer Andersson” remains represented as a none-object also known as phantom to satisfy the reference integrity and will remain in the database for as long as the reference exists.

Linked vs. none-linked references:

• Simple references – This is none linked attributes as the example described above with the ‘seeAlso’ attribute – those are not removed on the source object (e.g. the object being referenced) and remains until one of the following happens:
  • The object that references the object is being deleted (e.g. in the example described above – The object “CN=Jimmy Andersson” is deleted, this potently frees the last reference to “CN=Christoffer Andersson” as the attribute ‘seeAlso’ is also being deleted as a part of deleting the object.
  • The reference itself is being removed (e.g. in the example described above – The attribute value of ‘seeAlso’ is removed on the object “CN=Jimmy Andersson” this potently frees the last reference to “CN=Christoffer Andersson”)
• Linked references – This is a linked attribute, usually those references are removed during logical deletion (e.g. during transformation into a tombstone or recycled object) – However backlinks are kept during a read-only naming context (NC) tear down.

Demotion from an object to a none-object (phantom):

An object can be converted (demoted) from a real object into a none-object also known has a phantom by two different reasons.

1. The object (e.g. a tombstone or recycled object) has expired (e.g. passed the tombstone lifetime or the deleted object lifetime).

   In this case the following happens:

   1. All attributes are removed except the following:
      1. Is-Deleted (http://msdn.microsoft.com/en-us/library/windows/desktop/ms676802(v=vs.85).aspx)
      2. Object-GUID (http://msdn.microsoft.com/en-us/library/ms679021(v=VS.85).aspx)
      3. Object-SID (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679024(v=vs.85).aspx)
      4. RDN (http://msdn.microsoft.com/en-us/library/windows/desktop/ms678697(v=vs.85).aspx)
   2. In addition to the attributes listed in (a.) any attribute keeping the object (the database row) on the index being garbage collected will preserved (e.g. msDS-Entry-Time-To-Die) – otherwise the object or phantom wouldn’t be up for examination next time the garbage collector process is running.
   3. If there is NO references pointing towards the phantom after performing (a.) then the phantom (the row in the database) is up for being physically deleted – and be will completely removed from the database at the next Garbage Collector cycle (that’s by default runs every 12 hours). However if there ARE still references pointing towards the object – it’s going to remain as a none-object also known as a phantom until all references pointing towards it have been removed.
2. The object is leaving a DSA as a result of a read-only naming context (NC) tear down – but still has references pointing towards it.
   in this case the following happens:
   1. All attributes are removed except the following:
      1. Is-Deleted (http://msdn.microsoft.com/en-us/library/windows/desktop/ms676802(v=vs.85).aspx)
      2. Object-GUID (http://msdn.microsoft.com/en-us/library/ms679021(v=VS.85).aspx)
      3. Object-SID (http://msdn.microsoft.com/en-us/library/windows/desktop/ms679024(v=vs.85).aspx)
      4. RDN (http://msdn.microsoft.com/en-us/library/windows/desktop/ms678697(v=vs.85).aspx)
      5. Backlinks

Parental and self-references

In addition to linked and none-linked attributes there are two other references:

1. If an object has descendant (child) objects and/or phantoms it has one reference pointing towards it for each and every direct descendant (child) object or phantom.
2. All objects (not phantoms) holds a reference to them self’s by the Obj-Dist-Name attribute (http://msdn.microsoft.com/en-us/library/ms675516(v=VS.85).aspx).

References and Reference Counting within NTDS.dit

An object (row) in the database is represented locally and independently (on each DSA) within each database as a DNT – DNT is a short for distinguished name tag. (You need to be familiar with the concept of DNTs in order to understand reference integrity at the database layer in NTDS.dit – I’ve already given an introduction to DNTs in: How the Active Directory – Data Store Really Works (Inside NTDS.dit) – Part 2

Table 22: datatable – Simplified for reference integrity

Simple references in NTDS.dit

Let’s add in a sample NTDS.dit database with a simple reference:

“Elina Andersson” has a reference count “CNT_col” of “2” because of:

1. “Elina Andersson”‘s own self-reference from the “Obj-Dist-Name” attribute.
2. “Lena Andersson” is referencing “Elina Andersson” by the “seeAlso” attribute.

Let’s logically delete “Elina Andersson” and have a look what happens in the database:

Note: X represent when the object was logically deleted ex: 2012-09-09 09:09:09

The only remarkable change to the reference in this state would be that it is represented outside the database as a delete managed RDN in the value of the “seeAlso” attribute at “Lena Andersson” ex:
CN=Elina Andersson\0ADEL:1e5f5da7-af10-4d69-9c06-491c79659116

Let’s pretend that 60/180 days (or the time of tombstone lifetime has elapsed) since X = 2012-09-09 09:09:09 when “Elina Andersson” was logically deleted and have a look at the database again:

The garbage collector would have tried to physically delete “Elina Andersson” now but failed because the reference count “CNT_col” isn’t still yet zero cause “Elina Andersson” is still being referenced by “Lena Andersson”‘s “seeAlso” attribute – instead the object was converted into a none-object also known as phantom – as a result of this note the following:

1. “Elina Andersson” lost the attribute “Obj-Dist-Name” (that referenced “Elina Andersson” self) while it was converted to a none-object (phantom) and therefore dropped its reference count “CNT_col” from 2 to 1.
2. “Elina Andersson”‘s “OBJ_col” was changed from 1 to ‘NULL’ to indicate that the row in the database now represents a none-object (phantom) instead of an object.

Let’s pretend that a few weeks later “Lena Andersson” is logically deleted and have a look at the database again:

Note: Once “Lena Andersson” was being logically deleted and transformed into a tombstone or recycled object, “Lena Andersson” lost the attribute value of the “seeAlso” attribute as it’s not preserved on logical deletion by default:
See Attributes preserved on logical deletion for more information.

This means that “Elina Andersson” now is free to be deleted (No more references to DNT:5524) – as “Lena Andersson” held the last reference towards “Elina Andersson” in the database, “Elina Andersson”‘s reference count “CNT_col” is now 0 , “Elina Andersson” will be deleted immediately when the garbage collector runs next time.

Linked references in NTDS.dit

Let’s add in a sample NTDS.dit database with a linked reference:

“Elina Andersson” is a member of “Group X” (the hosting object) -as the member attribute is the forward link – referencing “Elina Andersson”.
The reference count “CNT_col” is increased with +1 on “Elina Andersson”.

Note: There is no reference count from the backlink towards the forward link – No dangling backlink reference is possible since if the host DN is removed it must have first been logically deleted, which implicitly removes all link attributes and their associated targets’ backlinks.

Logically deleting either “Group X” or “Elina Andersson” would decrease the reference count “CNT_col” with -1 and remove the corresponding row above in the ‘link_table’ as well removing the value “Elina Andersson” from the member attribute at “Group X”.

Cross Naming Context (NC) references

A reference can be made between two objects that reside in different naming contexts (this is regardless if the reference is simple or linked) with the following restrictions:

1. Objects in none domain naming contexts (NDNCs) – can have the following references:
   1. To any object within the configuration naming context (NC).
   2. To any object within the schema naming context (NC).
   3. The naming context head of any none domain naming context (NDNC).
   4. Any object within their own domain naming context (NDC)

   All other references than a, b, c and d is disallowed.

2. Objects in a domain naming context, schema naming context, configuration naming context – can have the following references:
   1. To any objects within any other domain naming context (NC) within the forest.
   2. To any object within the schema naming context (NC).
   3. To any object within the configuration (NC).
   4. To any none domain naming context (NDNC) head.

   All other references than a, b, c and d is disallowed except values of non-replicated linked attributes, that can reference any object/row present in the local database (NTDS.dit) at a given DSA.

Let’s have a look at Cross Naming Context (NC) references in NTDS.dit

First we have to explain one new column and an attribute that plays a major role in cross naming context (NC) references.

Table 23: datatable – Simplified for cross naming context (NC) reference integrity

Let’s add in a sample NTDS.dit database with cross naming context (NC) references from a DSA that’s a GC.

Note: “Elina Andersson” has an instanceType of 0 – that means “Elina Andersson” is a read-only object at this DSA and is part of a read-only naming context, typically that is a global catalog (GC) that hosts the domain naming context (NC) that “Elina Andersson” resides in and some other DSA hosts a writable copy of “Elina Andersson”.

“Lena Andersson” however has an instanceType of 4 – that means “Lena Andersson” is writable on this DSA and is part of a naming context that is authoritatively held on this DSA, typically that is the domain naming context.

The only difference here from other scenarios already mentioned is that if “Elina Andersson” would be logically deleted – it happens (originates) on a DSA that hosts a writable copy of “Elina Andersson”

Let’s have a look at Cross database references (that implicates cross naming context (NC) references) in NTDS.dit

Cross database references are between two objects where one of the object is located in an uninstantiated naming context (NC) e.g. a naming context (NC) not held by the DSA (that’s typically not a global catalog (GC)).

Let’s consider the following scenario – a forest with two domains D1 and D2 where D1 has at least one DC that is NOT a GC e.g. D1-DC01 and D2 has at least one DC that also is a GC e.g. D2-GC1.

Let’s imagine that D1 host the following user object “CN=Gustav Morath,CN=Users,DC=D1,DC=x” that references “CN=Robin Granberg,CN=Users,DC=D2,DC=x” in the ‘seeAlso’ attribute – this relationship causes an issue on D1-DC1: Because D1-DC1 doesn’t host the object being referenced “CN=Robin Granberg,CN=Users,DC=D2,DC=x” cause the D1-DC1 doesn’t hold a copy of the naming context (NC) for the domain D2 as it’s not a global catalog (GC).

Let’s now first look at the database (NTDS.dit) on D2-GC1:

Let’s now look into the database (NTDS.dit) on D1-DC1:

This problem is solved by representing “Robin Granberg” as a none-object also known as phantom to satisfy reference integrity, during the update of the object “Gustav Morath” the distinguishedName (DN) of “Robin Granberg” is requested to be added to the ‘See-Also’ attribute, during this request a few things are validated.

1. Verify that the distinguishedName we’re about the reference really exist:
   1. If the distinguishedName entered matches an existing local object within the local database (NTDS.dit): In this case it dosen’t as we don’t host the object “Robin Granberg” as the object resides in another uninstansiated naming context D2.
   2. If the distinguishedName entered matches any object within the enterprise, this is verified by going off the local machine, in this case D1-DC01 and perform the lookup on a DC that also is a Global Catalog Server (GC) as those host all refrenable objects. If the object exists on the queried GC the objects GUID and SID (if those exists) are retrived as well.
2. Verifying that the reference constraints mentioned above at: Cross Naming Context (NC) references are fullfiled.

If 1b and 2 above are fullfiled, then a phantom for the object being refrenced are created in the local database (NTDS.dit) in this case at D1-DC01 representing the object “Robin Granberg” including any structal phantoms needed to represent the full (DN) of “Robin Granberg”:

Here is a sample on how the represenation of the object “Robin Granberg” as a phantom and needed structual phantoms would look at D1-DC01:

How cross-database references are maintained to not become “stale” (outdated) in NTDS.dit

We have now gone thru how reference phantoms and eventually needed structural phantoms are created on none-GCs (Global Catalog Servers) to satisfy reference integrity – the initial creation of those phantoms are done by the local DSA once a reference is being written and isn’t found within the local database on the given DSA – it performs a “enterprise/forest wide verification” by locating a Global Catalog using the ‘DsGetDCName‘ (DCLocator) API with the flag ‘DS_GC_SERVER_REQUIRED’ to find a suitable GC (Global Catalog Server) to verify names against using the RPC interface method ‘IDL_DRSVerifyNames‘ with the flag ‘DRS_VERIFY_DSNAMES’

Let’s now imagine that the object “Robin Granberg” undergoes one of the following changes:

1. Being logically deleted (The case we’re focusing on in this article)
2. Having its RDN (Relative Distinguished Name) changed. (The object is renamed)
3. Being moved (changes parent) so that the DN (Distinguished Name) is being changed.
4. Had its SID changed.

If one of the cases mentioned above takes place to “Robin Granberg” on D2-GC1 (or another DC that is authoritative/holds a writable copy of the object) the phantom used to represent the reference to “Robin Granberg” from “Gustav Morath”‘s ‘See-Also’ attribute will become outdated (stale) on D1-DC1.

The scenarios described above enter the requirement for the flexible single master operations (FSMO) role ‘Infrastructure Master’ or the “IM” that according to me originally had a better name, the ‘Phantom Master’. The IM (Infrastructure Master) is responsible to maintain phantoms within a given domain and make sure that they don’t become outdated (stale) while the “real” object they represent changes as described above in other domains, the IM (infrastructure Master) is also responsible for spreading the word of any outdated (stale) phantoms and their new state to other DCs that are none GCs (Global Catalog Servers) in their domain except when the Recycle-Bin is on and all DCs that are none GCs (Global Catalog Servers) are responsible on their owns for this task.

The Infrastructure Master (IM) process with the Recycle-Bin Off

So let’s have a look on how the IM (infrastructure Master) will update a phantom in the case if the “real” object is being logically deleted in its own domain, specifically in this case if “Robin Granberg” is being logically deleted in the D2 domain. (For simplifying this scenario we have removed the reference in the ‘see-Also’ attribute from ‘Gustav Morath’ to ‘Robin Granberg’)

1. The IM (Infrastructure Master) in this case (D1-DC1) will periodically run a background task (See The Stale Phantom Background Task ‘ below for details’) that will compare the phantoms within its local database (NTDS.dit) with a GC (Global Catalog Server) in this case (D2-GC1) using the RPC interface method ‘IDL_DRSVerifyNames’ with the flag ‘DRS_VERIFY_DSNAMES’ in this case “Robin Granberg” is one of the phantoms that is being verified, The phantom “Robin Granberg” is matched against the real object representing “Robin Granberg” in the D2 domain by the GUID.
2. The name is bought back over RPC as a return of the ‘IDL_DRSVerifyNames’, The IM (Infrastructure Master) in this case (D1-DC1) will now compare the obtained name of “Robin Granberg” from the GC (Global Catalog Server) in this case (D2-GC1) and determine that the name doesn’t match as “Robin Granberg” now (as a result of the logical deletion on D2-GC1) have a deletion mangled name “Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517”.
3. D1-DC1 will now create a ‘InfrastructureUpdate’ object using a random GUID as RDN as a descendent/child of the “CN=Infrastructure,DC=D1,DC=X” object with the ‘dnReferenceUpdate’ attribute containing the name updated name “Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517”
4. D1-DC1 will now immediately delete the ‘InfrastructureUpdate’ object created above and let it replicate to other DCs within D1.
   Note: That the ‘dnReferenceUpdate’ attribute is preserved during logical deletion (e.g. the attribute is present on the tombstone), see the ‘Attributes preserved on logical deletion ‘section above for more information.
5. The DSAs have special code to detect that a write occurs to the ‘dnReferenceUpdate’ either locally as in this case on (D1-DC1) or via replication, once a write is detected the local phantom is referenced using the GUID and updated accordantly, in this case update the RDN of “Robin Granberg” to “Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517”.Note: An additional check is done to determine if the name is deletion mangled as in the case with “Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517” this will make all DSAs to locally start removing all backlinks pointing to the phantom “CN=Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517”.

   Note: There is no need to set the ‘isDeleted’ attribute as such doesn’t exist on phantoms, the name is already deletion mangled.

   Note: There is no need to set the ‘time_col’ column as all phantoms have such. (The only thing preventing them from being garbage collected or physically deleted are that they are still being referenced to)

However going to stage (7.) in the above sample doesn’t physically remove the database row representing the phantom for “Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517”.
Because it now has a ‘CNT_col’ count of 1 since the ‘InfrastructureUpdate’ object references it.

Note: This means that we will have to wait for a TSL (Tombstone Lifetime) to pass (by default 60/180 days) before the ‘InfrastructureUpdate’ object is being garbage collected, and finally the database row representing the phantom for “Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517” will lose the last reference towards it within the database and have ‘CNT_col’ count of 0, next tine the garbage collector runs (by default every 12h) the row representing the phantom “Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517” can be physically deleted.

Summary: It takes another 60/180 days + 12h before the database row representing “Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517” is gone from D1-DC1 since step (7.) is taken within the sample above.

The Infrastructure Master (IM) process with the Recycle-Bin On

So let’s have a look on how a DC that isn’t a GC (Global Catalog) will update a phantom in the case if the “real” object is being logically deleted in its own domain, specifically in this case if “Robin Granberg” is being logically deleted in the D2 domain. (For simplifying this scenario we have removed the reference in the ‘see-Also’ attribute from ‘Gustav Morath’ to ‘Robin Granberg’)

1. As the Recycle-Bin is enabled in this case, all DCs that isn’t a GC (Global Catalog) are now responsible by their own, more specifically (D1-DC1) to periodically run a background task (See The Stale Phantom Background Task ‘ below for details’) that will compare the phantoms within its local database (NTDS.dit) with a GC (Global Catalog Server) in this case (D2-GC1) using the RPC interface method ‘IDL_DRSVerifyNames’ with the flag ‘DRS_VERIFY_DSNAMES’ in this case “Robin Granberg” is one of the phantoms that is being verified, The phantom “Robin Granberg” is matched against the real object representing “Robin Granberg” in the D2 domain by the GUID.
2. The name is bought back over RPC as a return of the ‘IDL_DRSVerifyNames’, The DC in this case (D1-DC1) will now determine if the state of the object has changed as follows:
   1. If the name obtained from the GC (Global Catalog) in this case (D2-DC1) is different from the name of the local phantom in this case “Robin Granberg” (as a result of the logical deletion on D2-GC1) the name has changed to a deletion mangled name “Robin Granberg\0ADEL:0f09760e-e13b-457a-b207-ddb3d7824517” – this local phantom will be updated to reflect the name change.
   2. If the phantom is logically deleted in the local database (NTDS.dit) in this case (D1-DC1) but the obtained state from the GC (Global Catalog) in this case (D2-GC1) says it isn’t anymore the following actions are taken locally on the DC, in this case (D1-DC1)
      1. Activate Forward Links
      2. Activate Back Links
   3. If the phantom locally represents a live object in the database (NTDS.dit) in this case at (D1-DC1) but the obtained state from the GC (Global Catalog) in this case (D2-GC1) says it’s logically deleted, the following actions are taken locally on the DC, in this case (D1-DC1)
      1. Forward Links are deactivated.
      2. Back Links are deactivated.
   4. If the phantom is recycled locally in the database (NTDS.dit) in this case at (DC1-DC1) but the obtained state from the GC (Global Catalog) in this case (D2-GC1) says it isn’t anymore the following actions are taken locally on the DC, in this case (D1-DC1)
      1. The ‘recycle_time_col’ is set to NULL.
   5. If the phantom isn’t locally recycled in the database (NTDS.dit) in this case at (DC-D1) but the obtained state from the GC (Global Catalog) in this case (D2-GC1) says it is, the following actions are taken locally on the DC, in this case (D1-DC1)
      1. Forward Links are removed
      2. Back Links are removed
      3. The ‘recycle_time_col’ is being set.

 

The Stale Phantom Background Task
The IM (infrastructure Master) will scan its local NTDS.dit database for phantoms used by a rouge estimate of a scan rate on how long it should take to scan and verify all phantoms based on days, by default 2 days, the default value can be configured by a registry parameter: “Days per Database Phantom Scan”.

‘Days per Database Phantom Scan’ DWORD registry values can be configured within the following key:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\<INSTANCE>\Parameters.
Note: a value of 0 can’t be used and a maximum of 365 days.

This means that the DSA acting as the IM (infrastructure Master) or if the Recycle-Bin is enabled all DSAs that isn’t also acting as GCs (Global Catalog Servers) will scan it’s local database (NTDS.dit) more or less aggressively to meet the rate of ‘Days per Database Phantom Scan’ – using the following algorithm:

calculatedDelay =
(((86400 * DaysPerPhantomScan) * PhantomsVisitedInThisPass) / PhantomsInDB)

Make sure that next pass runs no more frequent than 15mins and no less than 1h

1. If calculatedDelay < 900 (15 minutes)

Next Scan will take place within 15min.

2. If calculatedDelay > 86400 (24h)

Next Scan will take place within 24h.

If (calculatedDelay by passes 1. and 2. above)

Next Scan will take place within <calculatedDelay>

Once a local phantom scan on the IM (Infrastructure Master) or if the Recycle-Bin is enabled, on all DSAs that isn’t also acting as a GC (Global Catalog Server) has been initiated (at least every 24 hours) it will scan the local database for phantoms and verify if they are up-to-date or have become outdated (stale) against a Global Catalog Server (GC) until.

1. It made maximum allowed trips (10) to a GC (Global Catalog) to verify phantoms (a maximum of 240 phantoms are verified on each trip) – the requirement of making no more than 10 trips to a GC (Global Catalog) comes from not taking up the DSA’s task queue for too long.
2. The following is only applicable if the Recycle-Bin is off:
   Maximum allowed stale phantoms (720) has been returned by the GC (Global Catalog) and has been identified as stale – the requirements of updating a maximum of 720 stale phantoms comes from the limits on 800~ values in a none-linked multi-valued attribute back in the Windows 2000 days when the stale phantoms are being written to the infrastructureUpdate object (carrier-object)’s dnReferenceUpdate attribute.
3. All phantoms in the database have already been verified by the GC (Global Catalog) without hitting the limits of (1.) or (2.) if the Recycle-Bin is off above.

The task will reschedule itself using the algorithm above.

The following event will be logged once the task is completed:

Table 24: Stale Phantom Cleanup Sucess Event

Note: The following event is only logged if the logging level for ‘Directory Access’ is set to at least ‘verbose’ level ‘4’
http://technet.microsoft.com/en-us/library/cc961809.aspx

The Stale Phantom background task can be initiated manually by triggering the operational attribute: checkPhantoms http://msdn.microsoft.com/en-us/library/cc223316(v=prot.20).aspx
Note: The task can only be trigged on the DC holding the flexible single master operations role: Infrastructure or on all DCs (Not Global Catalog Servers) if the Recycle-Bin is enabled and is still subject to the algorithm above but won’t automatically re-schedule itself. (E.g. you may need to call the operational attribute multiple times to verify all phantoms)

Local Lingering Phantoms

Local lingering phantoms is a phantom that dose exists locally in the database (NTDS.dit) on the IM (Infrastructure Master) or if the Recycle-Bin is enabled, on all DSAs that isn’t also acting as a GC (Global Catalog) but the real object that the local phantom represents can’t be found/verified at a GC (Global Catalog) – reasons for this can be:

1. The object that the phantom represents has been physically deleted (e.g. garbage collected) in its source domain, while the local phantom has not.
   This is common for simple references, that prevents the local phantom from being physically deleted (e.g. garbage collected) because references are pointing towards it.
2. Object’s in the distribution database (NTDS.dit) that are deleted during installation (DCPROMO)

The following events are logged if a local lingering phantom is detected:

Table 25: Local Lingering Phantom Event

Note: The following event is only logged if the logging level for ‘Directory Access’ is set to at least ‘minimal’ level ‘1’
http://technet.microsoft.com/en-us/library/cc961809.aspx

Table 26: datatable – Indices required to support the Infrastructure Master and the Stale Phantom Cleanup

The following Performance Monitors are available to track Stale Phantom Cleanup activity:

Table 27: Stale Phantom Cleanup Performance Counters

I think this is all I can think of for now when it comes to Active Directory and deletions/removal of data – if you have continued to read to the end, you can see it’s pretty much put into the fundamentals of Active Directory and is rather complex.