How we achieved write speeds of 1.4M rows per second(questdb.io)
questdb.io
How we achieved write speeds of 1.4M rows per second
https://questdb.io/blog/2021/05/10/questdb-release-6-0-tsbs-benchmark
40 comments
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.
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.
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.
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.
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.
> 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
Elasticsearch, IIRC, does this.
See also: https://www.youtube-nocookie.com/embed/b6SI8VbcT4w
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.
Using index would have been much simpler but also slower.
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).
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).
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.
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.
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.
Did you consider using an B-epsilon-tree [1] ? This is a B-tree, but each node has a staging area for new writes. In practice, incoming writes get added to the staging area of the root node, and once a staging area is full, it gets propagated down. This results in write performance that is similar to append-only. For reads, you get the performance of a regular B-tree. Sounds like a good match for your use case.
[1] http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf
[1] http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf
I have not had any experience with these trees, but I will try to read and make sense of this paper, thanks! There is C++ implementation here is someone else is interested: https://github.com/rahulyesantharao/b-epsilon-tree
[deleted]
To the QuestDB founders - thanks for the blog post & benchmarks!
I had a question about this part:
> We found out that this model does not fit all data acquisition use cases, such as out-of-order data
I know the whole blog post is about how you're now able to handle out-of-order data, but I'm curious - what use cases is QuestDB best for? Can you provide some concrete examples of where customers have ordered data and need QuestDB?
I had a question about this part:
> We found out that this model does not fit all data acquisition use cases, such as out-of-order data
I know the whole blog post is about how you're now able to handle out-of-order data, but I'm curious - what use cases is QuestDB best for? Can you provide some concrete examples of where customers have ordered data and need QuestDB?
Thanks for the kind words! QuestDB co-founder here - one example in fintech where you are polling multiple end points simultaneously for market data acquisition. You can think of multiple financial exchanges sending the data, but the latency varies for each venue. This is a great article written by one of our contributors about ingesting data from multiple crypto exchanges at the same time [1]. Many firms in financial services and fintech use QuestDB [2]
Another would be a manufacturing firm with thousands of sensors sending data to the database continuously, latency and delivery mechanism mean that timestamps often arrive out of order. There is a case study we did with CNC machines manufacturer DATRON [3].
Tracking moving vehicles (say cars, ships, drones, planes) on a map where the two primary axis are time and space - if you want to see the position of those vehicles in the past, you want to have the timestamps ordered.
Finally you can think of typical devops/monitoring/alerting use cases. Verizon uses QuestDB to monitor metrics for autoscaling decision to their Vespa engine that provides search, recommendation, and personalization to their users [4]. Here you want the series to be ordered by time.
[1] https://levelup.gitconnected.com/tracking-multiple-cryptocur...
[2] https://www.tradersinsight.news/ibkr-quant-news/optimizing-t...
[3] https://questdb.io/case-study/datron/
[4] https://questdb.io/customers
Another would be a manufacturing firm with thousands of sensors sending data to the database continuously, latency and delivery mechanism mean that timestamps often arrive out of order. There is a case study we did with CNC machines manufacturer DATRON [3].
Tracking moving vehicles (say cars, ships, drones, planes) on a map where the two primary axis are time and space - if you want to see the position of those vehicles in the past, you want to have the timestamps ordered.
Finally you can think of typical devops/monitoring/alerting use cases. Verizon uses QuestDB to monitor metrics for autoscaling decision to their Vespa engine that provides search, recommendation, and personalization to their users [4]. Here you want the series to be ordered by time.
[1] https://levelup.gitconnected.com/tracking-multiple-cryptocur...
[2] https://www.tradersinsight.news/ibkr-quant-news/optimizing-t...
[3] https://questdb.io/case-study/datron/
[4] https://questdb.io/customers
It's in their tag line
> QuestDB is the fastest open source time series database
Time series data is any type of data that always has a timestamp attached to it, such as logging, metrics, telemetry, etc.
> QuestDB is the fastest open source time series database
Time series data is any type of data that always has a timestamp attached to it, such as logging, metrics, telemetry, etc.
You get similar functionality to QuestDB if you take a traditional database, make all of your tables clustered by datetime fields.
The advantage advertised by QuestDB is that it is optimized specifically for this common use-case. The disadvantage of this being that it only allows clustered indexes for timestamp columns.
The advantage advertised by QuestDB is that it is optimized specifically for this common use-case. The disadvantage of this being that it only allows clustered indexes for timestamp columns.
I agree, you can use traditional RDBMS like Postgresql or MySQL for almost every use cases. It's just that purpose-built DBs like QuestDB can be multi-magnitude faster if your problem fit their niche.
By reading their home page, I thought QuestDB could be very useful for audit logs in an application where we need a picture of journey line for every entity we care.
Indeed! One can think of time series data as consecutive events happening such as logs, where the series is going to give the historical evolution over time.
I've achieved over 2 million inserts per second (to SSD) using a simple splay tree, append-only log, and a ring buffer abstraction (for serializing access).
Writing in batches of sizes dynamically determined by the backpressure mechanism seems to bring incredible performance benefits. Both SSDs and CPUs benefit hugely from any technique that can batch transactions at any level.
To the user of your database, what's the difference between 1-10ms best case, or 5-20ms average? To your CPU and flash, that 10ms extra batch width can mean the difference between 5000 and 500k inserts per second.
Writing in batches of sizes dynamically determined by the backpressure mechanism seems to bring incredible performance benefits. Both SSDs and CPUs benefit hugely from any technique that can batch transactions at any level.
To the user of your database, what's the difference between 1-10ms best case, or 5-20ms average? To your CPU and flash, that 10ms extra batch width can mean the difference between 5000 and 500k inserts per second.
This suggests you don't commit transactions individually, but buffer them for some time and then write them to disk at once. There are plenty scenarios where you don't need all ACID properties, but in many cases what makes databases slow is adhering stringently to those ACID constraints.
Correct. I can achieve multiple transactions per I/O. I do not believe this actually breaks any ACID properties. Reads and writes are serialized to a single thread for all processing.
>I do not believe this actually breaks any ACID properties.
You must send the write ACK after your transaction has been written, which could increase latency in the worst case but you will still have much higher throughput.
You must send the write ACK after your transaction has been written, which could increase latency in the worst case but you will still have much higher throughput.
ACID is what makes it possible to write parallel applications and stay sane. I'm always in awe when I realize how crucial it is.
Is there any stable application for this? I do have an application with varying very high and very low incoming data packets I need to save. They can be really small json documents or have larger files attached (up to 10mb). Kafka would be a perfect fit, but the file size is too big, and saving every attachment first to a cloud storage bucket will cost a lot because of many STORE commands (i would like to merge the files before storing to reduce the cost).
I am using it as the backend for a custom database engine. Key-value is the foundation. When you can transact millions of them per second, it gets easy to try crazy new things on top.
Not really used to doing low level programming but how would you assess back pressure for I/O ops on SSDs or disks?
Are you only evaluating running OPs rates compared to a theoretical maximum?
Are you only evaluating running OPs rates compared to a theoretical maximum?
> how would you assess back pressure for I/O ops on SSDs or disks
I am not attempting to do anything like this. The back pressure is an inherent property of the ring buffer abstraction I have selected for serializing transactions.
Batch size is effectively determined by how long the previous batch takes to complete. So, if one batch takes a little while, but is not at RingBufferMaximum, the next batch will be a bit larger (assuming constant system load), thus extracting a little bit more uplift from the benefits of running everything on hot cache lines. The maximum size of the ring buffer prevents things from getting out of control. You simply test for the best batch size and set that as the max for the buffer.
Best case scenario, your system is fully loaded and slamming through 4k+ batch sizes all day long. Worst case, you are doing a transaction per IO. I.e., what everyone else on earth is doing right now.
I am not attempting to do anything like this. The back pressure is an inherent property of the ring buffer abstraction I have selected for serializing transactions.
Batch size is effectively determined by how long the previous batch takes to complete. So, if one batch takes a little while, but is not at RingBufferMaximum, the next batch will be a bit larger (assuming constant system load), thus extracting a little bit more uplift from the benefits of running everything on hot cache lines. The maximum size of the ring buffer prevents things from getting out of control. You simply test for the best batch size and set that as the max for the buffer.
Best case scenario, your system is fully loaded and slamming through 4k+ batch sizes all day long. Worst case, you are doing a transaction per IO. I.e., what everyone else on earth is doing right now.
Ah right, I see. Thanks!
Any resources you would recommend about this kind of low level I/O programming and tuning?
Any resources you would recommend about this kind of low level I/O programming and tuning?
In the benchmark it says they are using an m5.8xlarge, which don't have locally attached SSDs. So presumably this is against gp3 or io2 volume. In which case I am surprised that wasn't the bottle neck of the test. Do none of these databases under test call fsync?
Great write up and congrats on the results. I think one of my takeaways from this is also how well rounded Clickhouse is. That fact that it is also so performant against timeseries datasets + databases is very surprising.
Is this for data streams where you are merely storing event-based data with time stamps . loT devices come to mind for this sort of database , but this is just a shot in the dark.
Would like to see time series comparisons to m3 as well. https://m3db.io/
This is something we can eventually do, it seems that m3 position themselves as long term storage for Prometheus first and foremost.
Imagine if they used Apple M1 for QuestDB, should be at least 1.5mil
This is something we should try :)
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?