Timeline for Concurrent fault-safe data structure
Current License: CC BY-SA 4.0
48 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 11, 2022 at 16:28 | comment | added | SmartArray | The performance of the setup achieved more than 10M, depending on the data distribution. The best case was 16M, the worst was 500k using NVMe SSDs | |
| Oct 11, 2022 at 15:26 | comment | added | gapsf | Did you manage to process 10M items per second? | |
| Oct 11, 2022 at 14:25 | comment | added | SmartArray | @gapsf Thank you for telling my something so clear. I thought on byte is 16 bit. May bad. Moreover, the heading says "concurrent". | |
| Oct 11, 2022 at 14:23 | comment | added | SmartArray | @gapsf I don't know what you meant to say with your last comment but in case you were trying to say anything negative, please consult this link: softwareengineering.stackexchange.com/conduct | |
| Oct 9, 2022 at 7:26 | comment | added | gapsf | Smartarray is "blockchain expert" - so yammy softwareengineering.stackexchange.com/users/320132/smartarray | |
| Oct 9, 2022 at 5:58 | comment | added | gapsf | (4 gigahertz) / (10 megahertz) = 400 So all you want (ALL code that fully process one item) must be done in 400 cpu cycles per item on 4Ghz core | |
| Oct 9, 2022 at 5:52 | comment | added | gapsf | >The key is 4 byte (uint64_t)!? 4*8=32 | |
| Oct 9, 2022 at 1:04 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Sep 13, 2022 at 4:38 | comment | added | Jason Weber | is there a natural partition key e.g. vehicle id? Or more than one? If so, this may open up additional possibilities not yet discussed. Hard to know from the details provided so far. | |
| Jun 11, 2022 at 0:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Feb 11, 2022 at 0:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 14, 2021 at 0:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 11, 2021 at 3:54 | comment | added | Michael Shaw | I'm wondering if you have tunnel vision on the problem that you need to solve. There is not enough here to think about the wider problem and bounce some thought through ideas back at you, but this looks like the kind of problem that having a singleton in your infrastructure is a poor choice. you lose the instance, you then have to both recovery and then catchup.... | |
| Jun 15, 2021 at 23:06 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 16, 2021 at 22:22 | answer | added | Chaplin Marchais | timeline score: 1 | |
| Feb 25, 2020 at 11:16 | history | protected | gnat | ||
| Feb 25, 2020 at 10:10 | review | Close votes | |||
| Mar 1, 2020 at 3:05 | |||||
| Dec 9, 2018 at 14:40 | comment | added | SmartArray | 6GB limit was an approximate. Somewhere I mentioned that I also delete items (or alter them). But the max memory usage would be 6GB according to my calculations. Actually yes, the data is extremely critical and must be persisted on disk, no item must get ever lost... I know that all sounds weird, but the question was already solved myself; I am going to use BzTree (which is a bit difficult to implement, but I think I am going to succeed!). | |
| Dec 9, 2018 at 14:36 | comment | added | amon | If the data structure never grows beyond 6GB, that's a mere 15s at this rate. So you only have to sustain the 10M/s rate for a few seconds, not continuously? If so, just stream the raw entries to disk and afterwards sort out any metadata. Also rethink whether you really have to avoid any data loss within that timeframe. If you do need to maintain this rate continuously, where does the 6GB limit come from? | |
| Nov 15, 2018 at 17:36 | comment | added | SmartArray | What isn‘t answered yet? I don‘t get it 😅 „Transactional“ does not answer your question? | |
| Nov 15, 2018 at 16:48 | comment | added | JimmyB | @candied_orange 42 bytes is not the answer?! ;-) | |
| Nov 15, 2018 at 16:44 | comment | added | candied_orange | @JimmyB that factor you think I'm off by is exactly what I'm asking the OP to add to the question. Telling me the item is 42 bytes long isn't enough to answer that. | |
| Nov 15, 2018 at 16:29 | comment | added | SmartArray | Kafka seemed to be too slow... is it capable to process 10M messages per second in realtime? I think of the following: Every time an element changes it will emit events to another system. These will come directly into a DB. There is no real retrieval. To be honest, I was searching for a data structure, because I have a lot of interest in them | |
| Nov 15, 2018 at 16:17 | comment | added | JimmyJames | @SmartArray The simplest option I could see would be to have actors that work from oldest to newest to clean things up. This is pretty standard stuff e.g. Kafka. The advantage is that your inserts and your cleanup are looking at completely different elements so there's no contention. To get the current state you work from newest to oldest events to find relevant data. If you want to speed up the retrieval of the current state, you could maintain an index. If you can provide a little more detail on retrieval requirements, it would give a fuller picture of the problem space. | |
| Nov 15, 2018 at 16:05 | comment | added | SmartArray | @JimmyJames Thank you for that. I did not know that the English term "velocity" is describing a vector :-) You're right, the history would be indeed very interesting, but I decided to do it because it fits better into memory and it would become too big over the years. I want it to be loaded very quickly when the applications starts | |
| Nov 15, 2018 at 15:57 | comment | added | JimmyJames | It's still not clear why it's required to update in place. It will greatly complicate any sort of concurrency and likely slow things down a lot. You also lose the history which would seem to be interesting. Seems like a lose-lose to me. The only advantage is space savings. With 64 architecture, you can use a lot memory and it's cheap these days. | |
| Nov 15, 2018 at 15:39 | history | edited | SmartArray | CC BY-SA 4.0 |
deleted 568 characters in body
|
| Nov 15, 2018 at 15:32 | history | edited | SmartArray | CC BY-SA 4.0 |
deleted 568 characters in body
|
| Nov 15, 2018 at 15:32 | comment | added | SmartArray | @Kain0_0 yes, data must be transactional. It‘s not too critical that a previous write is overseen, but it should not happen. Sorting is important, imagine the following: 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 (This is not what I am doing but you should get a feel why it must be sorted) | |
| Nov 15, 2018 at 15:31 | comment | added | SmartArray | @Blrfl sorry, I can‘t tell you much about it. Please read the following example | |
| Nov 15, 2018 at 15:31 | comment | added | SmartArray | @JimmyB That is generally true, but look into the last paper. It‘s really amazing what it promises!! | |
| Nov 15, 2018 at 15:26 | history | edited | SmartArray | CC BY-SA 4.0 |
added 606 characters in body
|
| Nov 15, 2018 at 14:31 | comment | added | JimmyB | "which means the total data rate will not be big 420 MB/s" - That's not a meaningful number here. Whatever data structure you use to organize the data into, it will almost certainly result in a big relative overhead in I/O (because your data items are so small) of maybe 100-200%; then add to that that your data structure will likely require random reads/writes at different locations of some page size number of bytes and your required 'bandwidth' will multiply. If you really need transactionality, or 'fail-safe', every write multiplies again and gets throttled by synchronization to disk. | |
| Nov 15, 2018 at 14:23 | comment | added | JimmyB | @candied_orange "My 8088 could handle that on one CPU back in the 80s" - No way. This would assume you could perform the sort or other computation on an element in a single clock cycle. I think you're off by a factor of 50-100 here. | |
| Nov 15, 2018 at 5:57 | comment | added | Kain0_0 | 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). | |
| Nov 14, 2018 at 21:02 | comment | added | JimmyJames | 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? | |
| Nov 14, 2018 at 17:35 | history | edited | SmartArray | CC BY-SA 4.0 |
answer some questions; new research results
|
| Nov 14, 2018 at 17:30 | history | edited | SmartArray | CC BY-SA 4.0 |
answer some questions; new research results
|
| Nov 14, 2018 at 12:39 | comment | added | Blrfl | What is it about a database that precludes doing math on the data? | |
| Nov 14, 2018 at 9:20 | comment | added | candied_orange | Nope sorry I still don't understand your determination to go with concurrency. ~10M items per second is ~10 MHz. My 8088 could handle that on one CPU back in the 80s. If all you want to do is sort all you have to move around are references so 42 bytes isn't a size issue. The question then becomes what weird kinda comparisons you're doing that take thousands of CPU clock cycles each time. | |
| Nov 14, 2018 at 9:00 | history | tweeted | twitter.com/StackSoftEng/status/1062631329358102528 | ||
| Nov 14, 2018 at 4:59 | comment | added | Kain0_0 | So the stream is serialising all interactions with this data-structure, including its responses? ie: >> lookup << result >> insert << added>> delete << done >> lookup << not found. I'm using the word in the sense of a database with concurrent transactions. | |
| Nov 14, 2018 at 4:32 | comment | added | SmartArray | @Kain0_0: No serialization, it‘s already serialized within my C programm. The key is 4 byte (uint64_t). Actually there is no tolerance in data loss. Although I did not mention that I have an input stream (using NATS), which is able to buffer the input data and also offers replaying of input data. On exit, I can start ingesting data from a certain offset. I could for example do batch inserts (100k items) and then save the stream offset. If after that, the application exits, I can replay the data. Yes, sorting is required at this application, because I have to do arithmetics as fast as possible | |
| Nov 14, 2018 at 4:21 | comment | added | SmartArray | @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 | |
| Nov 14, 2018 at 4:15 | comment | added | Kain0_0 | 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? | |
| Nov 14, 2018 at 2:33 | comment | added | candied_orange | "In order to achieve ~10M input entries I will have to use concurrent operations." Why? | |
| Nov 13, 2018 at 21:30 | review | First posts | |||
| Nov 19, 2018 at 7:15 | |||||
| Nov 13, 2018 at 21:28 | history | asked | SmartArray | CC BY-SA 4.0 |