I find that the design is more memory efficient because of these constraints, for example, our new storage engine can address 100 TiB of storage using only 1 GiB of RAM. Latency is predictable and gloriously smooth, and the system overall is much simpler and fun to program.
[1] “Let's Remix Distributed Database Design” https://www.youtube.com/channel/UC3TlyQ3h6lC_jSWust2leGg
This has also been my experience building a database in Zig. It's such a joy.
I’m a little confused by this statement. I assume by “address” you mean indexing, and the size of an index is related to the number of entries, not the amount of data being indexed. (For example, you could trivially address 100TiB using 1 address width of memory if all 100TiB belongs to the same key).
Thanks for the question!
What's in view here is an LSM-tree database storage engine. In general, these typically store keys between 8 and 32 bytes and values up to a few MiB.
In our case, the question is how much memory is required for the LSM-tree to be able to index 100 TiB worth of key/value storage, where:
* keys are between 8 and 32 bytes,
* values are between 8 and 128 bytes,
* keys and values are stored in tables up to 64 MiB,
* each table requires between 128 and 256 bytes of metadata to be kept in memory,
* auxiliary data structures such as a mutable/immutable table must be kept in memory, and where
* all memory required by the engine must be statically allocated.
Typically, a storage system might require at least an order of magnitude more than 1 GiB of memory to keep track of that many keys using an LSM-tree as index, even using dynamic allocation, which only needs to allocate as needed.
Another way to think of this is as a filesystem, since it's a very similar problem. Imagine you stored 100 TiB worth of 4096 byte files in ZFS. How much RAM would that require for ZFS to be able to keep track of everything?
The array-centric approach is indeed more applicable at the high levels of the program.
Sometimes I wonder if a language could use an array-centric approach at the high levels, and then an arena-based approach for all temporary memory. Elucent experimented with something like this for Basil once [1] which was fascinating.
First off, thank you for posting all your great articles on Vale!
Second off, I just read the generational references blog post for the 3rd time and now it makes complete sense, like stupid obvious why did I have problems understanding this before sense. (PS: The link to the benchmarks is dead :( )
I hope some of the novel ideas in Vale make it out to the programming language world at large!
I'm pretty excited about all the memory safety advances languages have made in the last few years. Zig is doing some really interesting things (see Andrew's thread above), D's new static analysis for zero-cost memory safety hit the front page yesterday, we're currently prototyping Vale's region borrow checker, and it feels like the space is really exploding. Good time to be alive!
This means we lose thread safety and functions become non-reentrant (but easy to prove safe - make sure graph of A-calls-B is a acyclical).
How frequently does this happen in real software? I learned not to return pointers to stack allocated variables when I was 12 years old.
> There's no way around having a proper lifetime system, or a GC, if you want memory safety.
If you're building an HTTP caching program where you know the expiration times of objects, a Rust-style borrow-checker or garbage collector is not helping anyone.
> How frequently does this happen in real software? I learned not to return pointers to stack allocated variables when I was 12 years old.
This happens rarely. However, the reason it isn't an issue is because C programmers are (and have to be) extremely paranoid about this kind of thing.
Rust, however, lets you recklessly pass around pointers to local variables while guaranteeing that you won't accidentally use one as a return value. One example is scoped thread pools which let you spawn a bunch of worker threads and then pass them pointers to stack allocated variables that get concurrently accessed by all the threads. The Rust type system/borrow checker ensures both thread safety and memory safety.
Would you trust a novice C programmer to use something like that?
So, if you slip while walking today, does that mean you didn't learn to walk when you were one year old?
You do bring up a valid broader concern. Ironically, this is a reason that GC'd systems can sometimes be better for privacy than Ada or Rust which uses a lot more Vec+indexes. An index into a Vec<UserAccount> is riskier than a Java List<UserAccount>; a Java reference can never suddenly point to another user account like an index could.
But that aside, we're talking about memory safety, array-centric approaches in Zig and Rust can be appropriate for a lot of use cases.
There are dedicated data structures for this [1] that will not let you access another item by mistake.
One of my favorite alternatives is generational_arena [0] which also happens to be the library that inspired Vale's generational references!
[0] https://docs.rs/generational-arena/latest/generational_arena...
There seems to be no practical difference here. Rust can do a reference to UserAccount, and Java can do an index into an ArrayList of UserAccounts. Or vice versa. As you wish.
The borrow checker, however, forces you to hold onto an index instead.
Programs often require inherent state with data that refers to other data. In these cases, one must circumvent the borrow checker, whether it be with indices, IDs, Rc, or whatever. The borrow checker simply does not allow changing data when someone has a reference to it (except for the rare case where we can use Cell).
It's a myth that we can rewrite any program to not circumvent the borrow checker.
It doesn't, however, prevent you from accidentally scribbling over your own memory (buffer overflow, for example) or from scribbling over someone else's memory.
This is also a popular approach in games, especially ones with entity-component-system architectures.
I'm excited about Zig for these use cases especially, it can be a much easier approach with much less complexity than using a borrow checker.