4 ms·

I know of "persistent" data structures from dabbling in Clojure. Just thinking off the top of my head just from that little bit of knowledge. If the very last t

I know of "persistent" data structures from dabbling in Clojure. Just thinking off the top of my head just from that little bit of knowledge. If the very last thing that happens in an update, is a pointer update that "commits" the new data, it's correct if we assume RAM is dependable and the pointer update is atomic. What if there was a command which updated the value in the persistent store, then coerced a cache miss upwards through all of the cache levels? If the bottom level update at the persistent store is atomic, then it doesn't matter if the propagating cache misses are interrupted by a power failure. EDIT: But oh, the huge latency!

aidenn0 5y ago
Ordering is what kills you there; lets say you have update X and Y both in cache and for correctness they must happen in that order. If you just do a global cache flush, you lose if Y happens before X. So you need to flush after X and after Y. This means that every update to a persistent store involves hitting memory twice. This also means that every implementation of a data structure needs to do all of this work correctly. Filesystems have many fewer data structures than general purpose code, and they still occasionally have correctness bugs here. You might be able to salvage some performance by having a large write queue and running all cache as write-through, but that will make writes, on average, far more expensive than reads. Perhaps a more reasonable option would be to use only static memory for the caches and have a battery-backed coprocessor flush the caches on power-loss.
- arghnoname 5y ago
  Well said. I will just add that there are cache write-through instructions and fence instructions. You can use these for just the pointer swap components the parent was talking about, but absolutely you’re correct, you can just take a naive data structure and have this work out of the box. There is work to make this transparent to existing data structures, but it (of course) imposes its own overhead.
lichtenberger 5y ago
Why not using DAX FS mode for Optane DC memory for instance and serialize the data structure by hand? I'm not sure how much performance you lose. That said the data store I'm working on serializes the huge persistent in-memory index to durable storage in a postorder traversal (mainly changed records in a data page Plus path copies) and atomically sets an offset to the main root, the UberPage to the new revision in a file. So, I'd say it's precisely what you describe :-)

aidenn0 5y ago

Ordering is what kills you there; lets say you have update X and Y both in cache and for correctness they must happen in that order. If you just do a global cache flush, you lose if Y happens before X. So you need to flush after X and after Y. This means that every update to a persistent store involves hitting memory twice. This also means that every implementation of a data structure needs to do all of this work correctly. Filesystems have many fewer data structures than general purpose code, and they still occasionally have correctness bugs here. You might be able to salvage some performance by having a large write queue and running all cache as write-through, but that will make writes, on average, far more expensive than reads. Perhaps a more reasonable option would be to use only static memory for the caches and have a battery-backed coprocessor flush the caches on power-loss.

arghnoname 5y ago
Well said. I will just add that there are cache write-through instructions and fence instructions. You can use these for just the pointer swap components the parent was talking about, but absolutely you’re correct, you can just take a naive data structure and have this work out of the box. There is work to make this transparent to existing data structures, but it (of course) imposes its own overhead.

lichtenberger 5y ago

Why not using DAX FS mode for Optane DC memory for instance and serialize the data structure by hand? I'm not sure how much performance you lose. That said the data store I'm working on serializes the huge persistent in-memory index to durable storage in a postorder traversal (mainly changed records in a data page Plus path copies) and atomically sets an offset to the main root, the UberPage to the new revision in a file. So, I'd say it's precisely what you describe :-)