hsanjuan
commented
2 years ago Some real-world metrics show the improvement here went from being able to list 11000 keys/s to 29000 keys/s, which is not all bad but ver far from the x1000 improvement using the in-mem datastore. That means much of the slowless there is probably due to locking contention.
Fixes #109.
When working with millions of keys, and trying to list them all, each key would trigger a subquery to verify that at least one of the CRDT-blocks in which the key was added as not been tombstoned (if all were tombstoned, then the key is considered removed).
Benchmarking suggests this subquery to the underlying datastore is very expensive to make for each element and skipping it results in large improvements.
We cannot avoid this subquery whenever an element has been deleted at some point (and potentially re-added), but we can skip it when that has not happened at all. In our usage of go-ds-crdt in cluster, it is quite uncommon to delete items, and most items would have never been delete.
We can determine which items have ever been deleted by checking all the keys in the tombstone namespaces. This allows us to initialize and introduce a bloom filter which can tell us which items have never been deleted. Thus, we can skip tombstone-checking altogether.
With in-mem benchmarking, this reduces the time to list items that have never been deleted from 2211563 ns/item to 3912 ns/op. That sounds very very good (1000x improvement), and I hope that it translates to badger/leveldb well enough.