Paged Results

From SambaWiki

For Samba 4.10, the behaviour of the paged results control (1.2.840.113556.1.4.319, RFC2696) has been changed to more closely match Windows servers, to improve memory usage. Paged results may be used internally (or is requested by the user) by LDAP libraries or tools that deal with large result sizes, for example, when listing all the objects in the database.

Previously, results were returned as a snapshot of the database but now, some changes made to the set of results while paging may be reflected in the responses. If strict inter-record consistency is required in answers (which is not possible on Windows with large result sets), consider avoiding the paged results control or alternatively, it might be possible to enforce restrictions using the LDAP filter expression.

Comparison of behaviour

Paging works by splitting the result set into pages of a certain size, specified in the control. As long as there is a new page, a cookie is returned to the client and the client must provide the cookie in order to continue to search.

Previous behaviour

Prior to Samba 4.10, only one search to the underlying database is performed at the time it receives the very first search providing a paged results control. This search was stored in memory and the LDAP server walked through the remaining queue of results to send without performing any additional work on subsequent requests. This led to a highly consistent view of the database (although it may have been quickly made out of date), but could cause memory issues. Notably RFC2696 does not specify how an implementation should behave in the case of simultaneous modification. Microsoft has also never described in detail their paging behaviour or any associated consistency requirements, besides referencing this RFC.

New behaviour

To implement paging in Samba 4.10, instead of performing the entire search during the initial request, we form a list of objects (referenced by objectGUID) to be fetched at a later point. The order is determined by this first search, but the attribute values are determined when the appropriate page has been reached for the object to be returned. This list of objects also remains fixed and no new objects can be added to it (which is how Windows behaves with a sort control specified). However, deletions cause objects in later pages to be dropped from the responses. This is quite similar to how virtual-list-view functions in both Samba and Windows (except no sort is required or implied).

Real world example

Although the consistency has been changed, realistically most clients will not see any impact. Paged results normally cause a stream of requests to happen in rapid succession, leaving little time to modify the database in between. Besides full searches, attributes of interest should not be changed all that frequently to begin with and smaller sets of results are not broken across pages either.

There are not that many ways to correlate data across the directory by default, and maintaining this data is quite difficult because of the lack of transactions over LDAP and the requirement for clients to perform constrained LDAP modification consistently in every case. One obvious example of data which refers to multiple records is a linked attribute relationship, like member. Performing paged results while updating group memberships may produce stale memberships (which would have also been the case before 4.10), a mix of old and newer relationships, but also you might find a mismatch in member and memberOf links (and relationships to objects which may not be returned during a paged search because they were removed). Without paging enabled, a single search which returns all the groups and users will have a consistent pairing of member and memberOf. With paging enabled, this consistency might be lost due to concurrent changes. Tools that use paging should be aware of a potentially changing LDAP database underneath.

Quirks and oddities (also in Windows)

Moving an object in the result list

Renaming an object or moving an object to another OU for instance, returns the object with a DN which may not match the original DN subtree scoping. This is a behaviour shared with Windows (and likely their virtual-list-view implementation as well). Modification of an object to no longer match the filter expression is forbidden however.

Making changes to search requests during paging

Before Samba 4.10, because only the first search did any work, any subsequent controls and changes to the expression or attribute lists had no effect.

Modification of controls and controls data

With Samba 4.10, it now tries to detect if there are any changes and if there are, it sends an error to the client. (Samba only checks for presence, but Windows could be checking for more specific details of the controls data).

Modification of the filter expression or attribute list

With Samba 4.10, it now tries to detect if there are any changes and if there are, it sends an error to the client.

Modification of DN scope

There aren't currently tests for this behaviour, but Samba 4.10 only uses the original GUID list and never rechecks the subtree scoping (which Windows seems to do as well).

Excessive modification of the database

This behaviour only happens under Windows, as Windows appears to rely on some form of underlying database index to implement paged results. If you delete too much, these indexes appear to cause the search to fail with a variety of errors (LDAP_UNAVAILABLE_CRITICAL_EXTENSION, LDAP_OPERATIONS_ERROR).

Modifications sometimes can cause the search to be retriggered and presumably the underlying indexes to be rebuilt.

Differences in behaviour with the sort control

In Windows, paged results appear to be sorted implicitly via the DN / CN attribute (when an LDAP sort control is not specified). When running adding against Windows, additions are added to the end (of pages not yet returned) in the unsorted case but are not added at all in the sorted case. Modifications cause objects to move the end (of pages not yet returned) in the unsorted case, while they are modified in-place with the sort control. In Samba 4.10, the (add) behaviour remains the same regardless of whether or not a sort control is specified and all objects are modified in-place.

Related issues

External race conditions

Even without these changes to the paged results control, it is still relatively easy to introduce a race condition using LDAP search results. Performing a read without properly validating a later write (to check if any other changes have already occurred). Normally the way to guard against this is by using an LDAP constrained modification to delete the old value, and possibly retry if the sequence of operation fails.