11

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 420 MB/s.

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 4-6 GB.

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.

Important:

I can't use a standard database because I have to apply arithmetics and additional calculations.

EDIT:

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 balanced workload.

10 MHz won't be enough to perform ~10 MIOPS. It's about

  1. processing the data
  2. modifying the data structure (removes, insertions)
  3. 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 ~10 MIOPS.

Amazing Papers

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.

  1. 33 mp/h | additional metadata
  2. 34 mp/h | additional metadata
  3. 38 mp/h | additional metadata
  4. 51 mp/h | additional metadata
  5. 53 mp/h | additional metadata ....

Now an input message contains a velocity of 50 mp/h. I need to iterate from the first item (1) to (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)

Improve this question
32
  • 3
    "In order to achieve ~10M input entries I will have to use concurrent operations." Why?
    – candied_orange
    Commented Nov 14, 2018 at 2:33
  • 1
    How many operation sources are there? What are the serialisation requirements? Are some of these operations transactional? Are dirty reads, or writes permitted? What is the tolerance on data lose? What is the permissible recovery window? Is sorting strictly required at the data-structure level, or is merely the appearance of sortedness to an observer required? Are keys a piece of domain knowledge or can the data structure generate them? Are keys apart of the 48 bytes? How long are the keys?
    – Kain0_0
    Commented Nov 14, 2018 at 4:15
  • 2
    @candied_orange: One single core would not be fast enough. I already tried a simple insert (withiut arithmetics) with one core and the best I could achieve was 1M. Sure I could optimize it even more, but I won‘t be able to handle 10 million data items per second
    – SmartArray
    Commented Nov 14, 2018 at 4:21
  • 3
    I may have missed something but what I think is missing here is what the retrieval requirements are. It's easy to make the inserts and updates fast if retrieval doesn't have any time constraints. You just keep adding each new thing to the end of your data. You also haven't clarified why you think that it will never be more than 4-6 GB. 6GB is a little less than 15 seconds of data. If I've done my math right, that means you will not have much more than 150 million different keys. Correct?
    – JimmyJames
    Commented Nov 14, 2018 at 21:02
  • 2
    So again to clarify, do the reads need to see the write made just before it? Do the writes need to see the write made just before it? These have large consequences on the data-structure, and algorithms used with it. Also you have not clarified the sorting requirement, you indicate that sorting is important to the maintenance of the data-structure (which is not necessarily so), so what is the O(?) requirement for data-access from the perspective of your algorithm. It appears from your suggested trees that O(log(n)) is okay, but a hash table can provide O(1) or even O(k).
    – Kain0_0
    Commented Nov 15, 2018 at 5:57

1 Answer 1

Reset to default
1

I think that you should look at using the TPL (Task Parallel Library by Microsoft). If I am correctly understanding the scenario outlined in your question, then this would provide you with the low level concurrency primitives which will be needed to implement your solution.

I would suggest that you start by taking a look at Processing Pipelines Series - TPL which outlines a scenario strikingly similar to your own!

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.