5 ms·

I used to work with a system that sent a good amount of real time updates like these and with a lot of jitter. What I don’t get from this blog post (which is ve

I used to work with a system that sent a good amount of real time updates like these and with a lot of jitter. What I don’t get from this blog post (which is very well written, by the way. Thank you!), is if you have all these constraints on your data why do you need to create a system this complicated? Your incoming data array lives purely in memory and you create a local B-tree (or any other index type you like) also in memory. You don’t need to move anything because once you need to read the data, you just read the index. Every 10 seconds a process or a thread reads the ordered data with a FLUSH bit set which tells this merge queue to empty everything out. The process that calls the FLUSH simply appends more data to a file, relying on tunable mechanics the OS provides (i.e. the commit interval). The reader of the data that is responsible for querying the data based on user requests would then have to use some kind of an index to locate the correct range of data from the appended-to files. A radix seems to be an excellent choice here. Any data that arrives more than 10 seconds late is discarded. This would of course have or be a tunable parameter. Isn’t that all you need from a system like this?

bluestreak 5y ago
Reading data via index would lead to scattered memory reads on actual data, which is a dead-end from an optimisation standpoint unfortunately. Using index would have been much simpler but also slower.
- IgorPartola 5y ago
  That’s assuming you’ll constantly be doing reads of only the last 10 seconds of data. If that’s the case, this isn’t the database you should use (or even the data model). If you are tracking vehicles or IoT devices or whatnot the reason you’d do those kinds of reads is because you want to know where things are right now, so using a data store optimized for knowing where they used to be at some arbitrary point in time is not the right tool. If you want to keep track of the latest state all the time store it in a another data structure instead. Once you flush your input buffer, everything becomes sequential so after your 10 second window you no longer have this problem. And even for the latest 10 seconds reading an index won’t be terrible as far as performance because your input buffer is relatively small (compared to your huge dataset).
  - jstrong 5y ago
    the design you propose is to write 10sec chunks of data to an append-only log, which will contain chunks from multiple tables/series? if so, then reading larger ranges than 10sec requires scattered reads of a bunch of small chunks interspersed in the log file. that doesn't sound like it will be fast? the other big tradeoff is compression ratio, which writing data in 10sec chunks (as its final form) would be terrible for.
    - IgorPartola 5y ago
      How you actually write data to the files is mostly irrelevant. You could write each column of each table into a separate file or a file per table. I would probably further partition each file by date with some relatively large range (day or week or month). I don’t see why you’d ever want to write multiple tables into one file. Not sure why you’d think of this as chunks of 10 seconds, that’s just the size of the input buffer. The records aren’t related to each other beyond that or grouped in any way. As far as compaction, I suspect for the kinds of workloads you are using this kind of storage for you won’t get much in terms of deduplication. IoT devices sending sensor readings are unlikely to produce loads of stable readings and the time stamps will be ever increasing.
dikei 5y ago
You just described basically how almost every write-heavy database work: write to a memory buffer then asynchronously flush the buffer to disk when convenient. From what I read in the article, it's how QuestDB works as well. The devil, however, is in the details: * What kind of in-memory buffer to use ? QuestDB doesn't want to use LSM or BTree, but its own data structure. * How to flush the buffer ? Based on how you maintain your in-mem buffer, memcpy might not be good enough. * When to flush the buffer ? You describe a tumbling window of 10 seconds, yet a sliding window might be more appropriate when dealing with late data, etc... * Do you need background compaction ? Many write-optimize DB need background compaction to optimize for the read path. * Do you need MVCC, ACID, etc... ? I'm not sure if QuestDB provides any of these, but it'll also affect how you design a DB storage engine.
- IgorPartola 5y ago
  Incoming buffer is a flat array, the index is whatever you choose. You can use the same time stamp radix the system on disk uses if you’d like. You flush it by resetting the root node of your index. You don’t need to actually zero out the whole memory structure. You can actually initialize two different buffers and when the writer says FLUSH it’s simply handed the buffer to read while the input processor uses the other one to collect the next 10 seconds of data. Since writing the data to disk should take less than 10 seconds (or the whole thing doesn’t work anyways), this would again mean no memcpy at all. Based on the problem description in TFA a tumbling window is perfectly appropriate here. Compaction/deduplication wasn’t discussed in TFA, so I can’t tell if it is something that was a part of the 65k lines of code or not but would assume it wasn’t. You can do compaction within your input buffer easily enough and depending on the kind of data you store it might not be all that useful anyways (vehicle tracking comes to mind where compaction is basically useless because you are storing continuous values and time stamps will keep changing too). You don’t need MVCC because this is essentially an append-only log file with an index. There aren’t multiple versions, it’s an event log (unless of course we are getting signals from the multiverse :)). You might or might not want ACID. The design QuestDB outlines, if I’m reading it correctly, basically drops inserts that are too old. That means that if you lose your input buffer because of a power outage, or simply restart the process, you can just wait for future updates from your inputs. Again, vehicle tracking comes to mind. Losing a late arriving packet from a minute ago doesn’t matter if you’ve gotten position updates since then. This means that the D part of ACID can be relaxed in that you’ll lose at most 10 seconds of data (or whatever tunable value you set), if you lose the buffer. The other properties are built into the design by the fact that your data structure is append-only: it’s atomic because you don’t have duplicate arrivals of the inserts (and if you do, that’s fine), it’s consistent because there is only one source of truth for it all at any given time and the whole thing is just a append-only file, it’s isolated because as soon as a write is inserted into the input buffer it’s available for the reader process, and it’s as durable as just writing to a file with OS primitives with an built-in in-memory buffer enabled.
oatmeal_croc 5y ago
That's kind of how writes in Cassandra (and a lot of databases) works. We've been using Cassandra for Time Series with our own schema and it works fine for out of order inserts. We deal with industrial IoT and incoming data is almost always out of order.
ignoramous 5y ago
> You don’t need to move anything because once you need to read the data, you just read the index. Every 10 seconds a process or a thread reads the ordered data with a FLUSH bit set which tells this merge queue to empty everything out. Elasticsearch, IIRC, does this. See also: https://www.youtube-nocookie.com/embed/b6SI8VbcT4w https://www.youtube-nocookie.com/embed/b6SI8VbcT4w

bluestreak 5y ago

Reading data via index would lead to scattered memory reads on actual data, which is a dead-end from an optimisation standpoint unfortunately. Using index would have been much simpler but also slower.

IgorPartola 5y ago
That’s assuming you’ll constantly be doing reads of only the last 10 seconds of data. If that’s the case, this isn’t the database you should use (or even the data model). If you are tracking vehicles or IoT devices or whatnot the reason you’d do those kinds of reads is because you want to know where things are right now, so using a data store optimized for knowing where they used to be at some arbitrary point in time is not the right tool. If you want to keep track of the latest state all the time store it in a another data structure instead. Once you flush your input buffer, everything becomes sequential so after your 10 second window you no longer have this problem. And even for the latest 10 seconds reading an index won’t be terrible as far as performance because your input buffer is relatively small (compared to your huge dataset).
- jstrong 5y ago
  the design you propose is to write 10sec chunks of data to an append-only log, which will contain chunks from multiple tables/series? if so, then reading larger ranges than 10sec requires scattered reads of a bunch of small chunks interspersed in the log file. that doesn't sound like it will be fast? the other big tradeoff is compression ratio, which writing data in 10sec chunks (as its final form) would be terrible for.
  - IgorPartola 5y ago
    How you actually write data to the files is mostly irrelevant. You could write each column of each table into a separate file or a file per table. I would probably further partition each file by date with some relatively large range (day or week or month). I don’t see why you’d ever want to write multiple tables into one file. Not sure why you’d think of this as chunks of 10 seconds, that’s just the size of the input buffer. The records aren’t related to each other beyond that or grouped in any way. As far as compaction, I suspect for the kinds of workloads you are using this kind of storage for you won’t get much in terms of deduplication. IoT devices sending sensor readings are unlikely to produce loads of stable readings and the time stamps will be ever increasing.

dikei 5y ago

You just described basically how almost every write-heavy database work: write to a memory buffer then asynchronously flush the buffer to disk when convenient. From what I read in the article, it's how QuestDB works as well. The devil, however, is in the details: * What kind of in-memory buffer to use ? QuestDB doesn't want to use LSM or BTree, but its own data structure. * How to flush the buffer ? Based on how you maintain your in-mem buffer, memcpy might not be good enough. * When to flush the buffer ? You describe a tumbling window of 10 seconds, yet a sliding window might be more appropriate when dealing with late data, etc... * Do you need background compaction ? Many write-optimize DB need background compaction to optimize for the read path. * Do you need MVCC, ACID, etc... ? I'm not sure if QuestDB provides any of these, but it'll also affect how you design a DB storage engine.

IgorPartola 5y ago
Incoming buffer is a flat array, the index is whatever you choose. You can use the same time stamp radix the system on disk uses if you’d like. You flush it by resetting the root node of your index. You don’t need to actually zero out the whole memory structure. You can actually initialize two different buffers and when the writer says FLUSH it’s simply handed the buffer to read while the input processor uses the other one to collect the next 10 seconds of data. Since writing the data to disk should take less than 10 seconds (or the whole thing doesn’t work anyways), this would again mean no memcpy at all. Based on the problem description in TFA a tumbling window is perfectly appropriate here. Compaction/deduplication wasn’t discussed in TFA, so I can’t tell if it is something that was a part of the 65k lines of code or not but would assume it wasn’t. You can do compaction within your input buffer easily enough and depending on the kind of data you store it might not be all that useful anyways (vehicle tracking comes to mind where compaction is basically useless because you are storing continuous values and time stamps will keep changing too). You don’t need MVCC because this is essentially an append-only log file with an index. There aren’t multiple versions, it’s an event log (unless of course we are getting signals from the multiverse :)). You might or might not want ACID. The design QuestDB outlines, if I’m reading it correctly, basically drops inserts that are too old. That means that if you lose your input buffer because of a power outage, or simply restart the process, you can just wait for future updates from your inputs. Again, vehicle tracking comes to mind. Losing a late arriving packet from a minute ago doesn’t matter if you’ve gotten position updates since then. This means that the D part of ACID can be relaxed in that you’ll lose at most 10 seconds of data (or whatever tunable value you set), if you lose the buffer. The other properties are built into the design by the fact that your data structure is append-only: it’s atomic because you don’t have duplicate arrivals of the inserts (and if you do, that’s fine), it’s consistent because there is only one source of truth for it all at any given time and the whole thing is just a append-only file, it’s isolated because as soon as a write is inserted into the input buffer it’s available for the reader process, and it’s as durable as just writing to a file with OS primitives with an built-in in-memory buffer enabled.

oatmeal_croc 5y ago

That's kind of how writes in Cassandra (and a lot of databases) works. We've been using Cassandra for Time Series with our own schema and it works fine for out of order inserts. We deal with industrial IoT and incoming data is almost always out of order.

ignoramous 5y ago

> You don’t need to move anything because once you need to read the data, you just read the index. Every 10 seconds a process or a thread reads the ordered data with a FLUSH bit set which tells this merge queue to empty everything out. Elasticsearch, IIRC, does this. See also: https://www.youtube-nocookie.com/embed/b6SI8VbcT4w https://www.youtube-nocookie.com/embed/b6SI8VbcT4w