Is the MST necessary to the protocol? Or is it an implementation detail?

[snarfed]

Hi all! I've been slowly implementing the different parts of a PDS, and I'm curious about the MST.

I get that the repo commit chain itself and its history and self-authentication is important, especially since it's replicated across different parts of the system. I also get how the MST is useful in that it lets you efficiently determine whether and where a user's data has changed, add new data, etc.

The docs on https://atproto.com/guides/data-repos currently imply that the MST is a necessary part of the protocol. I wonder though: is it really? If you could provide the same functionality, invariants, and efficient operations (eg all of the com.atproto.sync.* XRPC methods) with some other underlying data structure(s), would everything still work fine?

I ask because while the MST is obviously useful and a good choice for a number of reasons, it's a nontrivial burden on implementors. Am I missing some reason that it's actually necessary and not just a good option?

[dholms]

Yup you're right that the MST is not strictly necessary. The current version of the repo (v2) is defined as an MST. I've considered that we may support other datastore types down the line for sure. Specific type of data may benefit from different datastore shapes. Because of the complexity overhead of multiple datastore types, we only want to support one right now.

Benefits of an MST

• ordered keys
• deterministic construction regardless of insertion order (it's actually a CRDT)
• probabilistically balanced

The only other data structure I know of like that would be a Prolly tree (which I think is actually more difficult to implement).

[snarfed]

Thanks for the response! Makes sense.