Hacker News Reader

Comment by HyperSane | Hacker News Reader

Active Directory is the most wildly used multi-master distributed database in the world and it uses update sequence numbers.

An update sequence number (USN) is a 64-bit number in Active Directory that increases as changes occur. Local counters on every domain controller assign USNs.

Whenever an object is changed, its USN is incremented. When replication occurs, only the version of the object with the greatest USN is retained.

Local counters for USNs are considered reliable because they never decrease or "run backward." USNs are also always unique, making it easier for domain controllers to never use the same USNS at the same time.

View on HN

The documentation that Microsoft puts out regarding its "multi-master" features basically advises against using "multi-master" mode and leveraging the Flexible Single Master Operation (FSMO) Roles to ensure consistency across the domain and forest because its conflict resolution is not comprehensive [1]. FSMO roles were created decades ago as a transition from Windows NT's Primary Domain Controller (PDC) model to avoid some of these complexities around changes in a large distributed system. Its a decent solution that has its own pros/cons, but AD is not something I would use as a good example of a multi-master distributed database.

1. https://learn.microsoft.com/en-us/troubleshoot/windows-serve...

FSMO roles are only used for the tasks which are not suited to multi-master replication. The vast majority of data can be mutated on any domain controller.

if you define your data model to exclude the conditions where consistency is relevant, it's not particularly interesting, is it?

Or it is a reasonable engineering compromise.

conflict resolution for concurrent modifications of the same object on different domain controllers are resolved first by local timestamp (unreliable) and then by GUID order (arbitrary) and in both cases mean that it's possible for someone to make a change to an object that is reflected in local reads for a period of time, but then "erased" and forgotten after replication, tl;dr: this approach provides basically no meaningful consistency at all

my understanding is that conflict resolution is done by all domain controllers comparing the USN of each object and replicating the object with the highest USN.

https://www.techtarget.com/searchwindowsserver/definition/up...

yes. this is my point. "highest usn" is arbitrary.

It isn't arbitrary, it is last writer wins, which is reasonable enough to me. How SHOULD conflicts be resolved?

Active Directory is eventually consistent, so it is expected that not all nodes will see changes immediately and could operate on stale data.

lww is arbitrary, because (a) it's unknowable if some local state is actually valid, and (b) resolving conflicts is destructive

conflicts cannot be resolved in general without additional information from the application

in an lww system if a bit of data loses in an lww contest, that data was not just stale, it actually becomes invalid

if you set a=1 and then do a bunch of operations based on the idea that a=1, and i set a=2 and then do a bunch of operations based on the idea that a=2, and lww resolves that my a=2 wins over your a=1, then after that merge, your a=1 is not just stale, it's entirely invalid, erased from history. at no point did a ever equal 1. anything you did with that assumption is similarly invalid. and lww provides no way to manage the causality implications of that decision.

it's fine for many use cases but it's not a general-purpose solution.

Reply on news.ycombinator.com