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:
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.
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?
Why limit yourself only between those two options? A member of this community created a K/V store (@lucaong: CubDB). Additionally, you can go all-in SQL with an in-memory sqlite3 DB as well.
The key thing is performance; obviously if you’re going to step outside the existing tools, you’d use something built bespoke or on top of kdb+ that’s fit for purpose.
The question really surrounds the suitability of elixir in-memory storage mechanisms for certain tasks.
I would add, CubDB does look interesting in its own right, thanks for posting it!
One thing to take into account is the size of the datastore, the number of orders. If you keep it in a map then the size of the process heap could become very large will can noticeably affect the gc. With ETS the data is stored off-process heap so its size will never affect a process. This one reason to use ETS.
ETS lookup can be O(1) but it does depend on how you define the table and how you are searching in it. There are different ways to search through a ETS table, :ets.match and :ets.select, so speed again depends on how you search. ETS tables are stored off process heaps which this means data will be copied from ETS memory to/form process heaps when the tables are accessed which affects access times. But ETS works with BIG tables.
Do not underestimate sqlite3. That thing is fast. It obviously cannot be faster than ETS in this case but as @rvirding said, please be aware of the tradeoffs: ETS always copies data when you fetch data from it, and its searching capabilities are much inferior to those of an SQL database.
I’d say that in your case you have to take into account exactly this one thing: how complex will your queries be? Don’t get worried about storage speed just yet, IMO.
EDIT: Check out Ane. It’s a mix of several in-memory storage capabilities of Erlang/Elixir and I found it quite nice to work with when I needed it once.
As you might know I’ve built an order book mirror using a Struct in a GenServer process where the price points for bids/asks are stored in 2 separate maps. It works reasonably well for small order books (<= 25 price points on each bid/ask). But has terrible performance as the size of the order book increases (both memory usage & CPU usage causing back pressure problems).
I’ve been meaning to do a deep dive to compare & contrast the various approaches and data structures available within the Erlang/Elixir/OTP ecosystem so thank you @dimitarvp & @rvirding for some of the new suggestions that I didn’t know exist.
I did a quick investigation into what might be the cause of the problem in my architecture as the order book grows, and narrowed it down to a GC problem as I pass the full order book to another process which takes a smaller snapshot so that insert/update/delete performance remains fast.
My assumption is that the best approach will be highly dependent on how it’s used. i.e.
do you want async/sync reads
do you want reads? or do you want to pass the result to another process as a message?
do you need to transform the data in some way after insert/update/delete?
It’ll be very interesting to see whether or not that assumption holds with some data!
I am glad you are making progress and are finding ways to make your storage needs faster.
That being said, if you have to reach for ETS then I’d say that it’s possible that you might also be better served by a native map structure implemented in Rust; integrating that with Elixir (with rustler) is quite easy.
I’ll also remind that sqlite3 is always used in-process so there’s no inter-process communication overhead. Depending on your usage there might not even be data copying involved (although that strongly depends on the queries).
But hey, I am not criticising your hard work; I also used ETS with crushing success in the past.
That being said, if you have to reach for ETS then I’d say that it’s possible that you might also be better served by a native map structure implemented in Rust; integrating that with Elixir (with rustler ) is quite easy.
I’m going to add support for order book adapters for exactly this reason! I’d like to be able to configure the different order book implementations so that I can benchmark them together easily + track their performance over time as I make changes to the rest of the codebase. I don’t know Rust but it’s on the list of things to learn…
I’ll also remind that sqlite3 is always used in-process so there’s no inter-process communication overhead. Depending on your usage there might not even be data copying involved (although that strongly depends on the queries).
I’d like to also try out this approach but the lack of ecto 3 adapter support has kept me away so far. I would assume that the overhead of writing to disk would be slower than ETS though.
Do you need to continuously try to match orders ? I would assume that you’d only have to match new orders with existing ones once and then handle matches and store the order with remaining quantity.
So I actually did knock this up with a map, and left it in such a way that it can be refactored as an ETS table! This is interesting though, I might just go-ahead and change it to ETS. I’m actually surprised there was so much difference, I’d have expected Map to be equally quick (heck, it’s surprising to me that Map isn’t ETS under-the-hood, but then again, maybe I don’t know enough about BEAM to understand why it isn’t).
I read that most high performance orderbooks are done with AVL trees. The closest native thing is gb_trees in Erlang, which should do the trick.
The link posted by @dom is exactly what pushed me to try out the ETS implementation. The gb_trees data structure sounds interesting but there’s no information on it’s doc page as to whether or not it’s stored in ETS. I’m going to assume that it’s not stored in ETS as other data structures such as digraph do mention it https://erlang.org/doc/man/digraph.html.
You have a few other options as well. The creator of Hackney has some great bindings for RocksDB https://gitlab.com/barrel-db/erlang-rocksdb a wicked fast and stable KV store from Facebook.
You’re using ordered set which is relatively slow compared to other types. Could you use regular set? Also if the table is accessed from other processes, provide the read_concurrency: true option (but in your case you don’t need write_concurrency, b/c the table is protected, so it’s written to from a single process.
You already answered it yourself:
So basically, measure twice, cut once
Can you elaborate why? I’d be surprised if that solution would be significantly faster than ETS, if faster at all, b/c I think (but not completely sure) that the same limitations apply (data still has to be copied in/out).
I have lost the links to several Map implementations in pure Rust and now can’t answer factually. Sorry about that. I seem to remember that one of them could have managed without copying – only the return values of the functions for fetching and putting values from/to the Map.
You’re very likely correct that it won’t be an improvement over ETS though. I’d try it it if I had the free time but can’t claim anything for a fact currently.
For my particular case I need to read the first N values from each set. If I was to use a regular set I would have to read all of the values from each set, order them, then take the first N values. I would assume that would have similar performance characteristics to the Map implementation.
I’ve built an order book mirror using a 
I also think the Elixir ecosystem will gain a lot when I am ready with the Ecto 3 sqlite adapter.
