Final Solidification of the Data Model

[halgari]

Data Model Solidification

As part of our upcoming "Data Model migration support" issues, there is a small list of things that are way easier to change now than in the future. For these issues we should do some investigation into our needs and not just decided if we want to change them, but if we will ever want to change them. We'll have the ability to make significat changes to the datamodel in the future, but fundamental changes like the ones listed below will be hard if not impossible to change.

List of "hard to change in the future" features

• [ ] Hashing Algorithm
  • We curently use xxHash64. We have reasons in the docs why we chose this algorithm but 2 years later I think we may want to change this for a very small cost to code size and complexity.
  • Use xxHash3 instead as we'd take on about 200 lines of code for a 2x performance increase and the ability to leverage SIMD operations.
  • Another option is GxHash, it's only 2 years old and exists only in Rust it appears but is about 4x faster than xxHash3 although it requires certain intrinsics to work properly
  • WE CANNOT EVER CHANGE THIS ALGORITHM AFTER WE LAUNCH this is important, choosing a hash algorithm will be a never changable option. So in that regards maybe xxHash3 is safer.
• [ ] MnemonicDB storage model
  • Currently we store data in MnemonicDB as raw tuples inside RocksDB. This works well enough but requires us to load data into IndexSegment objects and to track segments of the index data separately from Rocks's caches. This means that all loaded data is essentially duplicated in memory. Due to the way C interop works in C# we cant cleanly use RocksDB iterators directly and have IndexSegments be RocksDB iterator ranges.
  • A option here is to instead store large blocks of tuples in RocksDB.
  • In this model we would organize datoms into a B+ tree where we store the nodes of the blocks in RocksDB.
  • This is the model Datomic uses, datoms are stored in a B+ tree no deeper than 3 levels where the two lower nodes old 10-20k datoms and the top level node grows forever (20k 20K 20k or 8 Trillion datoms before the top node gets oversized)
  • the backend datastore (RocksDB) becomes KV store of GUIDs to large blocks of datoms (20k-30k datoms or <16MB chunks of data). Moving to this model would give us the following features:
  • Caching becomes much simpler as we end up caching large blocks of datoms
  • IndexSegments are replaced with highly efficient, resettable iterators that scan ranges of blocks
  • We can reduce (or remove) the RocksDB memory cache size as we'd be loading blocks a lot less frequently
  • A fully loaded Cyberpunk list in the App is currently ~24MB of data, meaning it's highly likely that the entire state of the app for most people will exist in a few dozen blocks. This means that "loading" the data for the app would go from 5k range queries in RocksDB to 12 KV lookups in RocksDB followed by a B-tree search on memory that exists inside the app itself.
  • Another option is to take this approach but store the blocks as raw files on disk. Since these blocks are in the 16MB range this may not actually be slow on Windows even with it's pitiful filesystem performance. These blocks could be compressed (to reduce filesyste) or not (to allow for mmaping).
  • This isn't impossible to change after the release of the app, but it would be hard as data would have to be converted to the new format somehow.

• [ ] Window Serialization Data

  • The final holdout of my (@halgari) polymorphic JSON serializer is the window state. I'd really like to kill that code (and optimally burn it with fire).
  • Technically not a "never able to fix" thing as we could just distch the window data if we ever change the serialization state and tell users "sorry you have to reconfigure your workspaces", but I'd like to avoid that if possible.
  • I'd like to move this to native MnemonicDB attributes
  • I'd also like to look into removing the need to have a Context object in addition to the page type in the window code...I'll write up a different issue for this

[Sewer56]

In NX 2.0 (my enhanced Rust port), I'm planning to leverage xxHash3.

I would love to use GxHash, but there's some catches:

• Hashes are not stable; a hash is only guaranteed to remain stable within a given library version.
• There's no fallback for hardware without the relevant instructions.

The combination of the two means that if, for example RISC-V started to infiltrate the PC market eventually, we wouldn't be able to support it, unless we contribute an implementation or fallback ourselves. And that would be problematic, because we'd be using a version of GxHash which would be years out of date at that point. Because we're assuming the algorithm to be immutable (not changeable) that rules GxHash out. Same with t1ha0 and other similar algorithms in class.

Misc Note: As for hardware availability, GxHash should be supported on all x86 CPUs since 2015 (Skylake), and on some machines between 2010-2015 (depending on class).

[Al12rs]

• [ ] Add a test that outputs the format of the datamodel and uses verify or similar to detect any changes.
• [ ] Look into compartmentalization, to allow some parts of the db to just be discarded during update, where we don't really care about migrating the data in any way, like window position, or ui state.