search

dao-xyz / peerbit

P2P database framework with encryption, sharding and search
https://peerbit.org
Apache License 2.0
191 stars 15 forks source link

DString implementation needs rework #27

Open marcus-pousette opened 1 year ago

marcus-pousette commented 1 year ago

The current implementation of DString is like a canvas. Anyone can write anywhere on the canvas by inserting string at an offset with length. The current implementation does not support efficient deletion by pruning the DAG, the operation data type itself does not out of the box support this.

Consider instead the xi-editor that uses the rope data structure

Regarding xi-editor, here is some interesting discussion/critique on the implementation that xi-editor brings forward.

Erudition commented 1 year ago

Consider also the approach taken by Diamond Types: https://github.com/josephg/diamond-types

As seen in https://josephg.com/blog/crdts-go-brrr/

and the deletion strategy used by Replicated Object Notation: http://replicated.cc/rdts/rga/

marcus-pousette commented 1 year ago

Yea! I have going back and forth through all these for some time.. In order to get it to work with Diamond types one need to find a nice integration with the log implementation that already exist in this repo (which has many very nice memory optimizations for recovering from disc, especially in the browser).

marcus-pousette commented 1 year ago

and the deletion strategy used by Replicated Object Notation: http://replicated.cc/rdts/rga/

Have not seen this, interesting!