Lumen project seeking help implementing ETS Support

bcardarella · April 7, 2021, 4:37pm

The Lumen project (Elixir/Erlang compiled to WASM) is seeking community help to start implementing certain Erlang features. The first is ETS. We have a detailed explanation of what will be required to implement ETS in Lumen:

github.com/lumen/lumen

Implementing ETS

opened 04:29PM - 07 Apr 21 UTC

bcardarella

help wanted

# Implementing ETS Erlang Term Storage (ETS) is built on top of two data struct…ures (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](https://doi.org/10.1016/j.jpdc.2017.11.007) 2. [More Scalable Ordered Set for ETS Using Adaptation, 2014](https://doi.org/10.1145/2633448.2633455) 3. [WAVL Trees](https://en.m.wikipedia.org/wiki/WAVL_tree) 4. [Immutable AVL Trees](https://github.com/alefore/weblog/blob/master/immutable-avl-trees.md) 5. [ERTS AVL Tree](https://github.com/erlang/otp/blob/master/erts/emulator/beam/erl_db_tree.c) 6. [ERTS CA Tree](https://github.com/erlang/otp/blob/master/erts/emulator/beam/erl_db_catree.c)

If you have Rust experience all help would be greatly appreciated!

dimitarvp · April 7, 2021, 6:06pm

Thanks for the call! I could help but I am not seeing it happen in the next month at least, if not 2-3 even. But I subscribed to the issue nonetheless.

There’s a number of in-memory caches already implemented in Rust. If I were to help with this issue I’d start by evaluating several of the most popular ones.

Just a small tidbit and a note for the near future. Again, thanks for calling on the community!

EDIT: Is there a test harness in place that could validate a Rust implementation complies with the original Erlang/C implementation?

bcardarella · April 7, 2021, 6:50pm

I pinged Paul to see if he can provide more details but there is no formal Erlang/BEAM spec and the team is having to dig through Erlang source to ensure compatibility. The Lumen test suite is asserting the behavior as we understand it as things go along.