feat: Simplified Dueling Dags: Implement lazy kv store for memdag

[grgbkr]

An implementation of kv.Store specifically for the needs of memdag in the Simplified Dueling Dags design. This is exactly like kv.MemStore except that the keys under c/ are lazy-loaded from the perdag's kv.Store These keys may be evicted at any time as long as they have been persisted to the perdag.

LazyStore lazily loads values from a base store and then caches them in memory. In practice this base store will all be the IDBStore (i.e. the perdag in the Dueling Dags design).

Writes only manipulate the in memory cache (thus values must be persisted to the base store through a separate process).

The memory caches size is limited to cacheSizeLimit, and values are evicted in an LRU fashion.

shouldBePinned enables exempting some keys from eviction. This mechanism should be used to prevent values not persisted to the base store from being lost. Values whose keys are pinned cannot be evicted, and their sizes are not included in the current cache size. In practice Dueling Dags will use an implementation of shouldBePinned which returns true for head keys (because heads are not persisted to the perdag), and for chunk keys containing temp hashes (because the temp hashes tell us they have not yet been persisted). We use a pluggable predicate to avoid LazyStore having to know about head and chunk key structure. LazyStore is in the kv store layer and should not know about chunks and heads which are concepts from the higher level dag layer.

Once a value is persisted to the base store, it's temp key for which shouldBePinned is true can be deleted, and it can be re-put with a key for which shouldBePinned is false (making it subject to cache eviction, which is safe since it is now persisted). In practice this will happen as part of the Dueling Dag persist process. Once the persist process persists chunks with temp hashes to the perdag, it will put chunks with the permanent hashes into the LazyStore, and dag gc will delete the chunks with the temp hashes from the LazyStore.

See larger design at https://www.notion.so/Simplified-DD1-1ed242a8c1094d9ca3734c46d65ffce4#25008ba7094a472c98259b4c0f380301

Part of #671

[vercel[bot]]

This pull request is being automatically deployed with Vercel (learn more).
To see the status of your deployment, click below or on the icon next to each commit.

🔍 Inspect: https://vercel.com/rocicorp/replicache/29BtANvUiDKhgRYgcvKNUJm5vvue
✅ Preview: https://replicache-git-grgbkr-sdd-lazy-kv-store-rocicorp.vercel.app

[grgbkr]

Abandoning in favor of lazy dag store approach see https://github.com/rocicorp/replicache/pull/758