Implement ETS runtime support

[bitwalker]

The importance of ETS in OTP cannot be overstated - it is critical to being even remotely compatible with Erlang and other BEAM languages. As a result, getting this implemented is one of the first runtime features we need to implement.

The design of ETS is based on the concept of tuplespaces, IIRC originating from the Linda programming language, but further explored elsewhere. It may be worth catching up on the research to see what the best implementation strategy may be.

OTP Implementation

In OTP itself, ETS is primarily implemented in C, in the following places:

• erl_db here and here
• erl_db_util here and here
• erl_db_hash here and here
• erl_db_tree here and here
• erl_db_tree_util here
• erl_db_catree here and here

There is also some handling of some ETS BIFs in the bytecode handling.

ETS has a dedicated allocator, ets_alloc, where all tables and terms stored in tables are allocated.

Lumen Implementation

This is up in the air. The runtime will mimic OTP with multiple allocators which are specialized for certain classes of objects, so we should follow suit and build an ETS allocator like OTP. The actual structure of ETS could be a more or less straight port from OTP, but since there are some differences between Lumen and OTP, perhaps there are better approaches which are unclear at this time.

[bitwalker]

I've done some additional research here and I believe I can put together an implementation of this fairly quickly as we get closer to ElixirConf.

Internally, ETS in BEAM has gone through several evolutions of design, so it has accumulated some cruft over the years, but the high-level view is as follows:

• Ordered table types use either an AVL tree, or in more recent versions when conditions are write, a variation of the tree structure that permits concurrent writers using writer lock groups (namely the table must be public, and have write_concurrency: true set).
• All other table types use a hash table data structure
• There are meta tables which map names to table addresses, pids to table addresses, and table ids to addresses, which support checking ownership, and looking up named tables, and looking up tables by id. These are also wrapped in read/write locks.

For our purposes, we have some flexibility in how we approach implementation. Similar to BEAM, we'll want to use some kind of balanced tree like an AVL tree (recent versions called WAVL trees may be a nice improvement) or red/black tree for the ordered tables, and hash tables for the others. The critical choice comes in how we choose to handle concurrency.

Ideally, we want to use lock-free data structures when the table is public, and so concurrent readers/writers are present, and standard non-thread safe data structures when the table is private. BEAM went down the path of using read/write locks when the first SMP-enabled emulator was implemented, but quite a lot has evolved in the world of lock-free data structures since then. Since they went down that path, they ended up having to also implement lock groups, which ensure that contention on the locks is reduced by breaking up scheduler threads across a group of locks, where each thread only acquires the locks necessary to read/write the area of the table it is working in. This is more or less where ETS remains today.

There are a variety of lock-free data structure crates available for Rust, but we'll need to vet them on a few requirements, and potentially fork and modify them to suit our needs:

• How well maintained/used are they
• Do they provide the semantics we require
• Do they support custom allocation or will we need to patch that in
• Do they support dynamic resizing (this is primarily an issue for hash tables)
• Do they provide the necessary primitives we need to implement the Erlang ets module APIs

At least initially though, I believe we can just build on top of hashbrown and some kind of AVL or red/black tree implementation, wrap them in read/write locks, and boom, we have our MVP. Obviously this will suffer in comparision to a properly concurrent implementation, but will suffice under time constraints. This approach would also use the global heap, so we'd lose visibility into where allocations are distributed for ETS, but that is relatively low priority compared to other concerns.

[archseer]

This might be of some help: I have an implementation of PAM (the pattern matching abstract machine ETS uses) written for enigma:

The pattern compiler:

• https://github.com/archseer/enigma/blob/master/enigma/src/ets/pam.rs

The actual matching engine:

• https://github.com/archseer/enigma/tree/master/enigma/src/ets/pam

It's a straight port of the BEAM code.

(I have a partial ETS implementation too, but it uses locking, doesn't provide any of the concurrency guarantees and is held together by duct tape, so I figured PAM might be a bit more useful)