4 ms·
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
by HyperSane 4y ago
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.
- deleted 4y ago[deleted]
- preseinger 4y agoconflict 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
- HyperSane 4y agomy 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/update-sequence-number-USN https://www.techtarget.com/searchwindowsserver/definition/up...
- preseinger 4y agoyes. this is my point. "highest usn" is arbitrary.
- HyperSane 4y agoIt 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.
- preseinger 4y agolww 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.
- drewpc 4y agoThe 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-server/identity/fsmo-roles https://learn.microsoft.com/en-us/troubleshoot/windows-serve...
- HyperSane 4y agoFSMO 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.
- preseinger 4y agoif you define your data model to exclude the conditions where consistency is relevant, it's not particularly interesting, is it?
- HyperSane 4y agoOr it is a reasonable engineering compromise.