Reconsider Value implementation

[ed255]

Related to #409

#409 proposes refactoring the Value implementation to better use Arc so that using the underlying types is more ergonomic and cloning all kinds of Value becomes cheap because the inner data is under Arc.

This solves ergonomic problems and cloning problems; but we still have a remaining problem in serialization and storage.
The benefit of the Arc disappears once we serialize and deserialize (either for sending over the network or storing to disk), because upon deserialization we don't deduplicate Arced things (or skip serialization when the same value under the Arc was already serialized).

I would like to propose a redesign where in Value we only keep references to "big" types, and store the data in a shared structure.
For example, we could just store the value type and the raw_value; and then have a shared map of raw_value to the String, Dict, Set, ....

Then cloning a Value would be cheap because it would just copy the raw_value and type and reuse the entry in the shared map.

Challenges:

• Serializing and deserializing become more tricky (but more optimal). First we'd serialize all structures with the value references (without dereference) while noting the references that have been seen. Then we'd serialize all the associated data of seen references during serialization.
• Garbage collection: we may need to implement a reference counting mechanism to this shared map so that we can delete entries if no reference is using them
• Error handling: where do we keep this shared map? Is it a parameter that we need to pass everywhere? Or does each value keep a pointer to this map? If it's the second case, what happens if we mix values that use different maps?

We could also use this shared map to store custom predicate batches.

Note that this is a big refactor.

[robknight]

I think this could probably be done without a major refactor.

Assume we have some global singleton store, of type OnceCell<RwLock<HashMap<RawValue, Weak<Arc<TypedValue>>>>.

OnceCell ensures initialization. RwLock makes the map thread-safe.

The HashMap is keyed by the RawValue (hash). The elements are weak references to the Arc<TypedValue>. std::sync::Weak references don't increment the refcount, so the map won't keep values in memory if there are no external references to them.

[Weak::upgrade()](https://doc.rust-lang.org/std/sync/struct.Weak.html#method.upgrade) returns an Option<Arc<TypedValue>>, which is None if the Arc went to zero. We would need to periodically clean up entries in the HashMap whose weak references point to Arcs with refcounts of zero.

Value::new() currently takes a TypedValue, then hashes it and returns a Value struct with the hash and a new Arc<TypedValue>. Instead of returning a new Arc, we could look up the existing one from the map, and use that. If none exists, then we create a new one and store that in the map. This would avoid holding duplicate copies in memory. This would not involve any API changes.

We could probably optimize a bit further by changing how deserialization works. When deserializing, we have both a hash and a JSON representation of the typed value. Instead of deserializing the typed value, we could deserialize just the hash and first check to see if we already have the TypedValue in the interning map. If we do, we can skip some deserialization and hashing. However, this creates a risk: if the serialized data is invalid, containing a serialized value which does not match the hash, then by skipping the deserialization and hashing we would ignore this problem and use the valid data we got from a previous deserialization. Possibly we could think about this in #435 instead, as the deserialization/hashing overhead is only ever significant for Merkle trees, and maybe persistence gives us the ability to store the fact that we've already verified that some serialized data is valid? We only need to double-check the hashing on the first time we see a new piece of serialized data.

This also does not address the problem of duplicated work when serializing the same data multiple times. I wonder if that's better solved in #435 which seems like a natural place to store a copy of serialized data, which can be re-used later?

[artwyman]

@robknight's approach seems sound to me. I used a similar weak-cache approach when bridging objects between Java and C++ many years ago. A few thoughts on tricky bits and gotchass to keep in mind when implementing:

• We need to be careful to still distinguish values of different types with the same hash. In particular, there might be a value which is are meant to be an opaque Merkle root (Hash/RawValue) mixed in the same POD as the preimage (Dict/Set). You don't want to accidentally end up revealing the preimage on a public statement because it was used in a private statement.
• Rob already called out the need to garbage-collect the weak references. I think it's probably fine to do that anytime you grab the write lock to the cache, perhaps subject to some high/low watermark or cooldown so you don't do it every time.
• Agreed that verifying hashes when deduping or deserializing is important for verifiability. This is why POD1 never serialized the ContentID, only the contents. (POD1 had much less of a size issue due to lack of nesting and fewer reasons to duplicate values.) I think verification might not need to be done automatically during deserialization, so long as it's handled properly by a later call to verify().
• I think deduping at serialization time is another good thing which could come out of this approach (I'm not sure that's quite what Persistent MerkleTree storage #435 is meant to cover but it seems related). If you serialize one Value you have no choice but to write the full contents, but doing that for every repeated value, particularly Merkle trees is part of what makes a serialized MainPOD large and unreadable. Maybe a serialized MainPOD should be structured so that values are represented by their type & hash, and there's a separate section for hash -> full-value mappings which is deduplicated.