When to use ETS and 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.

Read the ETS docs for more info.

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.

In this case, would gc on a process cause the process to pause while cleanup took place?

It does seem like ETS really is the only native solution here, with a pool of GenServers adding/cancelling orders.

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

Howdy @chrism2671

I would also love to know the answer to this!!

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!

@chrism2671 I replaced my Map based order book with an ETS ordered set implementation and the difference in performance is huge.

The burst and large order book performance is far more consistent.

The scheduler utilization is consistently far lower (which I assume is due to the lower overhead from garbage collection).

The standard deviation during worst case performance is ~100x lower

Old Map based order book

map-order-book-perf799×594 116 KB

New ETS ordered set order book:

ets-order-book-perf840×733 129 KB

https://github.com/fremantle-capital/tai/pull/113

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.

Cheers @dimitarvp

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.

I am working on that every now and then. I also think the Elixir ecosystem will gain a lot when I am ready with the Ecto 3 sqlite adapter.

Not necessarily. sqlite3 is very mature. But it also has an in-memory mode.