Implementing ETS

[bcardarella]

Implementing ETS

Erlang Term Storage (ETS) is built on top of two data structures (depending on the options passed to ets:new/2) - an AVL tree in the general case (based on the paper by Adelson-Velski and Landis), and a CA tree [1][2] for ordered sets with write concurrency enabled. For our purposes, we aim to build our ETS implementation on top of WAVL trees [3]. Some interesting references are included below [4][5][6]. Work on the compiler has kept us from building this yet, so this is a great way to get involved with the project!

Goals

• Implement ETS as a library in Rust that can be plugged in to our runtime by writing BIFs that interact with the implementation. Ideally the implementation shouldn't be dependent on runtime specifics like the scheduler, processes, or term representation. If it turns out that such specifics are critical to the implementation though, we can revisit
• Should make use of safe Rust abstractions where possible
• Should provide futures-based APIs for long-running functions (e.g. ets:insert/2 with a list of objects to insert). Functions which are "short enough" don't need to be written as futures, but if implementation is easier that way, it's fine. NOTE: It is essential that these futures do not attempt to hold locks across yield points, if Rust will even allow that in its type system.
• ETS tables should be reference counted, and likely the values they contain as well, so that access by multiple processes is safe, and garbage collection of the tables and their contents can happen naturally.
• While correctness is the most important property, attempts should be made to keep the implementation as performance-sensitive as possible, since ETS is so heavily relied upon.

References

1. A Contention Adapting Approach to Concurrent Ordered Sets, 2018
2. More Scalable Ordered Set for ETS Using Adaptation, 2014
3. WAVL Trees
4. Immutable AVL Trees
5. ERTS AVL Tree
6. ERTS CA Tree

[josuesantos1]

can i make this issue?

[bcardarella]

@josuesantos1 sure!

[josuesantos1]

@ josuesantos1 com certeza!

I can call rets? (Rust-ets)

Can I change one thing or the other or does it need to be 100% equal to ets?

[bcardarella]

I'll let @bitwalker weigh in on that

[hailelagi]

hi there! 👋🏽

I've been looking at lumen for a while, really great project! I wonder is the work on this issue still desired? If so I would love to take a stab at it, I've been actively learning rust and I'm fairly confident in my elixir - it might take me a few weeks but I'm pretty sure I can crack it. Thanks!

cc: @bitwalker , @bcardarella

[bcardarella]

@hailelagi we'd welcome all contributions! @KronicDeth would be the best best to weigh in on this ticked I think

[bitwalker]

@hailelagi There are a few things we need to get sorted internally with the runtime before we'll be ready to implement ETS, but I'm working hard to get that stuff done as soon as possible. I'll ping you here as soon as we're ready to begin implementation, and I'd be happy to let you work on that :).

The main outstanding things I'm working out are how runtime functions need to integrate with the garbage collector, and additionally how runtime functions should be written to support yielding during expensive operations. Both of those are tricky in Rust, so I'm researching an approach via async Rust that ideally will provide a uniform solution to both of those questions. The trouble with going too far with implementation until those are pinned down, is that they will have a very significant impact on the APIs and implementation of their functionality, so it's not really worth going too deep on it until then.

That said, if you wanted to take a crack at a standalone implementation of ETS in Rust, and then work on integrating that into the runtime once we're ready, that might be a viable approach for development - but I suspect that there will be so many runtime-specific idiosyncracies that you'd largely end up reimplementing most of it anyway.

[hailelagi]

I see, thanks for the heads up! For now, I'd be fine with trying the library approach, and eventually when the runtime api is stable, doing a re-write, I don't mind honestly and looking forward to it :)

[bitwalker]

See #8 as well