Let’s a consider a theoretical case of building an in-memory stock exchange on Elixir.

A stock exchange has a limit order book, which is a list of all the orders submitted, and then it has to match buyers & sellers.

In this case:

1. The main activity is going to be people submitting and cancelling orders, where we just need to look up by the order_id. Changes here need to be atomic.
2. We need to be able to continuously scan the orders and find the ones with the best prices, so we can match those.

How do we store this order book to get the best performance?

Notes:

• According to the docs, Map KV lookup is O(log N), whereas ETS is O(1).
• Everything I’ve read in benchmarks indicate that Map is approximately 2x faster than ETS for a r/w cycle, but then they’re probably wrong.
• Maps are enumerable, which should help with (2), whereas I don’t believe ETS tables are (but can we query them in a clever way?). An Enum.filter/reduce would be O(N)
• Let’s assume there are N=1,000,000 orders, and we are receiving 1000 new orders/cancellations per second.

I’m curious to know what the right way to structure such a thing would be. Does keeping all the orders in a single GenServer process create a bottleneck? Does it really matter whether we use ETS or Map?