About this opportunity:

ETS (“Erlang Term Storage”) is a module in Erlang/OTP which allows long-term storage of terms outside of a process, which can be used by several processes as a shared in-memory key-value storage. Users can choose between several different underlying data structures depending on which trade-offs they would like to make.

At the moment, the data structures involved are protected by ordinary locks. While they are very cleverly used, even going so far as to being contention-adapting in some cases, they do not scale as well as the number of threads grows. Furthermore, the nature of locking prevents the affected thread from doing useful work on contention (“try-locks” are impractical for various reasons), and the cost of context switching is becoming increasingly high over time.

We have experimented with using Concurrent Tries (Propopek et al, DOI 10.1145/2145816.2145836) for a certain ETS table type, and the results were quite promising. However, many challenges remain before ETS can be made lock-free. For starters, the programming interface allows queries to be executed over the whole table (“select all objects matching pattern X”), and some of these whole-table operations are guaranteed to be atomic.

The main subject of the thesis would be to explore:

Whether it is possible to provide a practical lock-free implementation underneath the current ETS interface, and if not, how the design of a new interface should look: what facilities does it make sense to provide?

What data structures should be used? In addition to Concurrent Tries, we’re also glancing at:
* LFCAs (Winblad et al, DOI 10.1145/3210377.3210413), to provide support for ordered sets.

* Non-blocking Patricia Tries (Shafiei, DOI 10.1007/s00446-019-00347-1), to provide atomic replace operations and better performance with a low number of keys.

The skills you bring:

– Students of: computer science, computer engineering, or similar program

– Familiarity and interest