serialization?

[awaited-hare]

Currently there's no way to save the hashmap nor iterate through all key value pairs.

[Gregory-Meyer]

Very true. Do you want:

1. Concurrent iteration, but with the possibility of repeated keys?
2. Concurrent iteration with no repeated keys, but with space/allocation overhead to track that?
3. Serialized iteration over mutable references only, but iterators walk the table an extra time to force a migration?
4. Serialized iteration over immutable references, but iterators hold a lock and probably walk the table one more time to ensure migrations have occured?

[awaited-hare]

For my current project, repeated keys are not an issue as long as each key (and value) at least appears once. The faster the better.

Given such a iteration method, it can be easy to implement serialization based on it.

[Gregory-Meyer]

I've been thinking on this and there are a few potential pain points:

• Do you need to be able to iterate while modifying the table? If yes, ouch. If no, do you mind locking? With a spinlock or mutex?
• For serde integration -- is it acceptable to allocate during serialization and deserialization? Should the amount of memory be constant, or can it grow linearly (I can't imagine it growing superlinearly) with the size of the table?

I can visualize at least three APIs here. Which fits your needs best?

• fn serializable(&mut self) -> impl Serialize + Clone + Send + Sync // runtime grows linearly with the size of the hash table
• impl Serialize for HashTable { fn serialize(&self, serializer: S) { // will cause writers to block, either with a spinlock or a mutex } }
• impl Serialize for HashTable { fn serialize(&self, serializer: S) { // won't block writers, but may serialize duplicate keys and may not return keys that are being inserted concurrently } }

As I see it, there are tradeoffs with each implementation method.

• Iteration only over mutable references is very simple for me to implement, but will be a bit painful because you'll probably end up passing around Arc<RwLock>. A bit silly
• Iteration over immutable references, but with blocking writers, avoids this, but then I the library writer decide for you whether you're going to get a spinlock, std::sync::Mutex, or parking_lot::Mutex. There will probably be a condition variable in there too - lots of synchronization primitives are being thrown into a lockfree algorithm.
• Iteration over immutable references has no synchronization decisions on my end, which is nice. If I add a force_grow function or something, then users of the library can layer on their own synchronization devices to avoid writer/serializer interference and ensure that iteration has a) no repeated keys and b) does not allocate to avoid repeated keys.

[awaited-hare]

Thanks for your detailed response.

impl Serialize for HashTable { fn serialize(&self, serializer: S) { // won't block writers, but may serialize duplicate keys and may not return keys that are being inserted concurrently } } looks best for me. Locking the whole hashtable will be a deal breaker for my current use case (I need to maintain a huge hashtable with concurrent reads and writes, and periodically dump the whole hashtable to disk without blocking the reads and writes).

[Gregory-Meyer]

Would something like Redis' serialization model be suitable? As in, fork the process and use copy-on-write memory mappings to get exclusive access to the hash table? This could also be done without OS support using some kind of copy on write marker bit in the hash table.

[awaited-hare]

I'm not familiar with Redis's serialization model, but it sounds like it solves the serialization problem in an elegant way. However, when we want to iterate through the values (and possibly do some updates on some entries), the COW behavior cannot help.

[Gregory-Meyer]

OK, try it out on the branch iteration-seralization and let me know what you think. Iteration is honestly pretty unergonomic, but offers good flexibility and exposes entirely too much information to the user. Iteration won't return stale or duplicated entries, but you'll have to restart it if the table resizes while your iterator is taken out.