I am building an application that aims to process
~10M data items per second.
Each item is exactly
42 bytes small (including a sorting key) which means the total data rate will not be big
The data structure entries are supposed to be sorted (either descending or ascending). Duplicate keys will be possible (multiset).
Depending on the input data, items are either inserted, deleted or modified (which I could basically do using delete & insert, but a direct modification would be desirable). Modifications do not alter the primary key; the item's position within the sorted set will not change.
In order to achieve
~10M input entries I will have to use concurrent operations.
I am not sure about the distribution of search/insert/delete, but let's assume they are all equally distributed.
Most importantly: The complete data structure will always fit into the memory. It won't usually exceed
I considered using a lock-free B+tree which could handle the desired data rate and it would be very good in terms of searching data.
It is extremely important that there isn't any data loss on unexpected shutdowns, etc. I could not find anything about making the B+tree fail-safe.
I have also read a lot about the log structured merge-trees (LSM), which look very promising regarding fail-safety. Its advantage is its writing performance, but searching would be bit slower. Here I could not find anything on how to make a LSM work in a concurrent environment.
After reading through a lot of papers I actually prefer LSMs, as they give faster write access and fail-safety. The only downside is that I can't use multithreading, can I?
I would of course be very pleased if someone could recommend other data structures that could possibly fulfill my needs.
I can't use a standard database because I have to apply arithmetics and additional calculations.
I am sorry that I wasn't precise enough. The following depicts the data flow:
NATS ---> Application ---> event-based messages
I am not using Kafka for several reasons, I use NATS as a streaming pipeline instead, which in my experience performs way better and its features are sufficient for my needs.
The event based messages will be sent to a real database.
I said I want to process
~10 million messages per second. It's not about just parsing the
42-byte small messages, it's about comparing some of them against the big (sorted) list in memory, but only the first
<20 entries. Furthermore one single input message may modify
1..* database entries, which depends on the contents of the input message. I think you would call that
10 MHz won't be enough to perform
~10 MIOPS. It's about
- processing the data
- modifying the data structure (removes, insertions)
- put the message into a large sorted multiset (insertion)
while maintaining "transactional" states.
If you look into papers that compare B+tree, LSM, etc. they are using powerful multicore systems and only reach
~1 MIOPS under balanced workload. That is far away from my desired
I am sorry that I wasn't precise enough in my first StackExchange question, thanks for all your answers, I really appreciate it.
In the following I am going to tell you about data structures I encountered in the past hours. Perhaps some of you find it very interesting.
Bw-Tree by Microsoft Research: a b-tree that was optimized to be used with modern hardware. Sounded very promising, but I could only reach
~3M inserts/deletes, but insane
~40M reads on my machine using 32 cores using a 30 million item-sized tree.
This patent by Google Inc. looked also very promising, although there are not very much measurements on it.
And the one that looks the best is: Bz-tree. It is very recent work by some very smart people. In the following days I am going to implement that data structure (there is no public implementation) and see what it does. I like the fact that my server will use NVMe SSDs, which is supported by the Bz-tree.
Still, I would like to hear other alternatives, if you happen to know something new.
An example about what I am trying to achieve
We have measurements of mp/h and additional metadata (daytime for example). I have to start searching from the lowest and do some calculations and alter some data for each and every item until I reach a specific value in the list.
- 33 mp/h | additional metadata
- 34 mp/h | additional metadata
- 38 mp/h | additional metadata
- 51 mp/h | additional metadata
- 53 mp/h | additional metadata ....
Now an input message contains a velocity of
I need to iterate from the first item
(3) and do some calculations on the metadata and alter all of them.
After that the data (50 mp/h) is added to the list, which is why a simple vector would not be enough.
(This is not what I am doing but you should get a feel why it must be sorted)