search

jlongster / crdt-example-app

A full implementation of CRDTs using hybrid logical clocks and a demo app that uses it
https://crdt.jlongster.com
611 stars 79 forks source link

Merkle tree size #11

Open ntoljic opened 3 years ago

ntoljic commented 3 years ago

First of all thank you for providing this insightful example. One thing I cannot quite wrap my head around is the merkle tree used for data consistency. The way I understand it is that the tree contains hashes for all events from all clients ever. Wouldn't this lead to an ever growing data structure which is passed back and forth on each sync? Or am I missing something and the size of the tree is somehow bounded?

ntoljic commented 3 years ago

One more observation: There is a prune method on the merkle tree but it seems it is never used...

lcarrasco commented 3 years ago

Hey @ntoljic we had the same question regarding merkle tree sizes but after adding 10,000 messages the tree didn't grow much. I am still trying to understand it since I think its the more complex part of the project to understand. If it helps this fork helped me understand it better:

https://github.com/clintharris/crdt-example-app_annotated/ https://github.com/clintharris/crdt-example-app_annotated/blob/master/NOTES.md