5 ms·

Time Structured Merge Tree: From LSM Tree to B+Tree and Back Again

97 points by pauldix 11y ago

kbody 11y ago
So, we were using InfluxDB on v0.8.x but had two data corruption incidents. Both times I tried the recovery utilities with no luck. Even with some data loss, it was time to move to another db. We were only getting ~1k tps with some spikes of 10k tps. I hope for the rest of the users, there was some work done of that front. Maybe in the future we will revisit out of curiosity, since we have no issues at the moment.
- gtrubetskoy 11y ago
  Curious - what db did you move to?
  - kbody 11y ago
    kdb+ pricey for sure, so it's not a fair fight but you gain the power of q and amazing performance.
gtrubetskoy 11y ago
IMHO if your volume is not in 300K data points per second, there is still plain old PostgreSQL, which is perfectly suitable for storing time-series and is time-tested and very reliable, allowing you to keep your TS data alongside your other (business) data so that you can analyze it all together without having to extract out of unfamiliar storage. I've hacked a project which demonstrates how it can be done, see https://github.com/grisha/timeriver https://github.com/grisha/timeriver and my blog explaining the technique http://grisha.org/blog/2015/09/23/storing-time-series-in-postgresql-efficiently/ http://grisha.org/blog/2015/09/23/storing-time-series-in-pos...
- dkhenry 11y ago
  Even at 300k points per second, PostgreSQL or MySQL can easily service your needs. The scheme that this article presents is really about batching writes to disk to get high throughput. mysql> CREATE TABLE test.polls_memory ( id INT(11) PRIMARY KEY AUTO_INCREMENT, poll_id INT(11), time DOUBLE, value INT(11)) ENGINE MEMORY; mysql> CREATE TABLE test.polls_disk (id INT(11) PRIMARY KEY AUTO_INCREMENT, poll_id INT(11), time DOUBLE, value INT(11)) ENGINE MyISAM; #> for i in `seq 1 500000`; do echo "INSERT INTO test.polls_memory (poll_id,time,value) VALUES ($i,UNIX_TIMESTAMP(),$RANDOM);" ; done | mysql -uroot mysql> INSERT INTO test.polls_disk SELECT * from test.polls_memory; Query OK, 510001 rows affected (0.95 sec) Records: 510001 Duplicates: 0 Warnings: 0 And this was just on my laptop. I know that on enterprise grade hardware I can get that write rate up to millions per second. The question isn't getting it to disk in batches. Its the read patterns you can support once you decide you are going to batch your writes.
  - weddpros 11y ago
    Yet your measurement includes no networking, no parsing of statements, no concurrency... Repeat the experiment with 200 different clients hitting the server via networking with 1500 insert statements, each second. Then you can compare MySQL with the InfluxDB use case cited as an example in the article. And don't forget the index on the timestamp.
    - dkhenry 11y ago
      The whole point was if you are going to batch writes to disk to get high thoughput then PostgreSQL or MySQL can easily sustain the same rates as InfluxDB ( which my little example shows ). I wouldn't have MySQL parse 500,000 insert statements per second, but I would have a proxy in front of it that could take in 500,000 data packets per second and then at some defined interval write them to MySQL. I know its not as sexy as InfluxDB, but the old work horses are tried and true and if you use them right they are as good as if not better then some of the shiny new toys.
      - weddpros 11y ago
        Can you time the copy again, with an index on the timestamp this time? just out of curiosity. Also, not sure it's wise to build system software (proxy) just to log data instead of using what already exists. Because that proxy you write will not be an old work horse either.
        dkhenry 11y ago
        So I added an index on (poll_id,time) since thats a more likely index for various reasons. mysql> ALTER TABLE polls_disk ADD INDEX `timestamp` (poll_id,time); mysql> INSERT INTO test.polls_disk SELECT * from test.polls_memory; Query OK, 510001 rows affected (1.78 sec) Records: 510001 Duplicates: 0 Warnings: 0 So the index takes me down to 286k points per second. Again this is just on my laptop, but it shows a great point. I can write stuff down to disk super fast ( especially if I can batch it ), but reading it back out is where the problems are. As far as a proxy in front of the datastore, the amount of effort to batch up data packets to hand them off to the data store is several orders of magnitude less complexity then a really well designed data store, so where do I want to custom roll software and where do I want to leverage the broader community. I don't think there isn't a place for the new tools, but I think we jump to them much more quickly then we should in a lot of situations.
- math 11y ago
  These guys seem to think relational databases are a valid alternative in the process automation world, and seem to have made a successful business around the idea: https://inductiveautomation.com/news/process-historians-vs-sql-relational-databases https://inductiveautomation.com/news/process-historians-vs-s... [I have no data on how well their product performs in practice]
  - chaotic-good 11y ago
    SCADA systems usually handles small amount of data (because data comes from real sensors, this sensors is expensive and you simply can't have millions of them).
    - math 11y ago
      yeah. I actually suggested that to someone who sells an industrial historian and his response (believe it or not!) was that no, there is too much data, a relational database solution is no good (and by the way! the business model of inductive automation will never work!) I'm sure writing would be no problem, the only thing I wonder about are complex (aggregating) queries in situations where you care about delays (interactive visualization perhaps).
- kbody 11y ago
  It's not just about inserting data fast enough, you could save the data in-memory and batch-insert them for max performance to a text file. But time-series databases often come for certain needs, most commonly aggregation operations over time windows.
- acconsta 11y ago
  Yeah, but... Need replication? Gotta write your own sharding logic or set up pg_shard. Need aggregations? Gotta write your own logic. Will you do them on the fly? Use triggers? On demand? Need to remove old data? Gotta set up a cron job. But wait, what if I want to age different series at different rates? Now you need a policy system. Sigh. Not saying Postgres can't be the storage engine, but there's a lot of work to do on top of that.
  - gtrubetskoy 11y ago
    I believe that what you're referring to as "a lot work to do on top of that" is the correct solution, the ultimate OSS project. The fallacy of the many time series db's out there is that they discarded the relational database as a viable storage option prematurely and are now trapped solving the very hard problem of horizontally scalable distibuted storage that takes many years to solve instead of focusing on the time-series aspect of it. Sooner or later something along the lines of pg_shard will become standard in PostgreSQL and other databases, thus you don't really need to write your own sharding logic, you just have to wait. OR you can write it if you want. You have options. Aggregations is what GROUP BY is for. Removing old data is a non-issue if you're using a round-robin approach (see my blog link), it also makes aging different series at different rates easy.
    - acconsta 11y ago
      It's good to have competition in this area. Influx is giving me whiplash (it's on its third database engine in six months!) The circular buffer approach is fine, but it does have the drawback of being unable to represent variable-length data (like key-value pairs). It's also harder to compress the data. Can a GROUP-BY do windowed aggregations? Like, take an average over ten-minute windows? My SQL knowledge is not great.
- chaotic-good 11y ago
  You can't compare this solution to InfluxDB or other time-series databases out there because you're loosing information here. You can't store timestamps with arbitrary precision, and all the data is resampled, there is no way to store raw data. This is not acceptable in many cases.
shubhra51 11y ago
Woot! Nice throughput improvement over traditional LSM types with both read and write accelerated.
skybrian 11y ago
I'm wondering if a new low-level db will come out of this as an alternative to LevelDB, BoltDB, and so on? Or do you have to use InfluxDB?
- btrask 11y ago
  We definitely need more and better low level key-value stores, especially write-optimized ones. It sounds like InfluxDB has correctly identified the pain points with LevelDB and LMDB, but it's yet to be seen whether they've succeeded in addressing them. The article kind of petered out without a proper conclusion. The people who are talking about Postgres in this thread are thoroughly confused. This isn't a competitor to Postgres, this is a platform for building a competitor to Postgres (or, hypothetically, something Postgres itself could use). I guess maybe they mean InfluxDB rather than the subject of the article.
  - robochat42 11y ago
    seriously? I'm always confused by the large number of different low level key-value stores on offer. All claiming to be the fastest, with benchmarks to back it up. Reading the article, it seems that they could have contributed some development to Rocksdb and saved themselves a lot of time rather than implementing their own system.
    - btrask 11y ago
      RocksDB has the same problems as LevelDB (uses large numbers of file descriptors, considerable read overhead compared to LMDB), plus it's even more complex and harder to configure. I had high hopes for the LSM tree from SQLite4[1], but last I checked development was stalled. [1] https://www.sqlite.org/src4/doc/trunk/www/lsmusr.wiki https://www.sqlite.org/src4/doc/trunk/www/lsmusr.wiki
philsnow 11y ago
typo in the article's headline: Strucutred -> Structured

97 points by pauldix 11y ago

kbody 11y ago

So, we were using InfluxDB on v0.8.x but had two data corruption incidents. Both times I tried the recovery utilities with no luck. Even with some data loss, it was time to move to another db. We were only getting ~1k tps with some spikes of 10k tps. I hope for the rest of the users, there was some work done of that front. Maybe in the future we will revisit out of curiosity, since we have no issues at the moment.

gtrubetskoy 11y ago
Curious - what db did you move to?
- kbody 11y ago
  kdb+ pricey for sure, so it's not a fair fight but you gain the power of q and amazing performance.

gtrubetskoy 11y ago

IMHO if your volume is not in 300K data points per second, there is still plain old PostgreSQL, which is perfectly suitable for storing time-series and is time-tested and very reliable, allowing you to keep your TS data alongside your other (business) data so that you can analyze it all together without having to extract out of unfamiliar storage. I've hacked a project which demonstrates how it can be done, see https://github.com/grisha/timeriver https://github.com/grisha/timeriver and my blog explaining the technique http://grisha.org/blog/2015/09/23/storing-time-series-in-postgresql-efficiently/ http://grisha.org/blog/2015/09/23/storing-time-series-in-pos...

dkhenry 11y ago
Even at 300k points per second, PostgreSQL or MySQL can easily service your needs. The scheme that this article presents is really about batching writes to disk to get high throughput. mysql> CREATE TABLE test.polls_memory ( id INT(11) PRIMARY KEY AUTO_INCREMENT, poll_id INT(11), time DOUBLE, value INT(11)) ENGINE MEMORY; mysql> CREATE TABLE test.polls_disk (id INT(11) PRIMARY KEY AUTO_INCREMENT, poll_id INT(11), time DOUBLE, value INT(11)) ENGINE MyISAM; #> for i in `seq 1 500000`; do echo "INSERT INTO test.polls_memory (poll_id,time,value) VALUES ($i,UNIX_TIMESTAMP(),$RANDOM);" ; done | mysql -uroot mysql> INSERT INTO test.polls_disk SELECT * from test.polls_memory; Query OK, 510001 rows affected (0.95 sec) Records: 510001 Duplicates: 0 Warnings: 0 And this was just on my laptop. I know that on enterprise grade hardware I can get that write rate up to millions per second. The question isn't getting it to disk in batches. Its the read patterns you can support once you decide you are going to batch your writes.
- weddpros 11y ago
  Yet your measurement includes no networking, no parsing of statements, no concurrency... Repeat the experiment with 200 different clients hitting the server via networking with 1500 insert statements, each second. Then you can compare MySQL with the InfluxDB use case cited as an example in the article. And don't forget the index on the timestamp.
  - dkhenry 11y ago
    The whole point was if you are going to batch writes to disk to get high thoughput then PostgreSQL or MySQL can easily sustain the same rates as InfluxDB ( which my little example shows ). I wouldn't have MySQL parse 500,000 insert statements per second, but I would have a proxy in front of it that could take in 500,000 data packets per second and then at some defined interval write them to MySQL. I know its not as sexy as InfluxDB, but the old work horses are tried and true and if you use them right they are as good as if not better then some of the shiny new toys.
    - weddpros 11y ago
      Can you time the copy again, with an index on the timestamp this time? just out of curiosity. Also, not sure it's wise to build system software (proxy) just to log data instead of using what already exists. Because that proxy you write will not be an old work horse either.
      - dkhenry 11y ago
        So I added an index on (poll_id,time) since thats a more likely index for various reasons. mysql> ALTER TABLE polls_disk ADD INDEX `timestamp` (poll_id,time); mysql> INSERT INTO test.polls_disk SELECT * from test.polls_memory; Query OK, 510001 rows affected (1.78 sec) Records: 510001 Duplicates: 0 Warnings: 0 So the index takes me down to 286k points per second. Again this is just on my laptop, but it shows a great point. I can write stuff down to disk super fast ( especially if I can batch it ), but reading it back out is where the problems are. As far as a proxy in front of the datastore, the amount of effort to batch up data packets to hand them off to the data store is several orders of magnitude less complexity then a really well designed data store, so where do I want to custom roll software and where do I want to leverage the broader community. I don't think there isn't a place for the new tools, but I think we jump to them much more quickly then we should in a lot of situations.
math 11y ago
These guys seem to think relational databases are a valid alternative in the process automation world, and seem to have made a successful business around the idea: https://inductiveautomation.com/news/process-historians-vs-sql-relational-databases https://inductiveautomation.com/news/process-historians-vs-s... [I have no data on how well their product performs in practice]
- chaotic-good 11y ago
  SCADA systems usually handles small amount of data (because data comes from real sensors, this sensors is expensive and you simply can't have millions of them).
  - math 11y ago
    yeah. I actually suggested that to someone who sells an industrial historian and his response (believe it or not!) was that no, there is too much data, a relational database solution is no good (and by the way! the business model of inductive automation will never work!) I'm sure writing would be no problem, the only thing I wonder about are complex (aggregating) queries in situations where you care about delays (interactive visualization perhaps).
kbody 11y ago
It's not just about inserting data fast enough, you could save the data in-memory and batch-insert them for max performance to a text file. But time-series databases often come for certain needs, most commonly aggregation operations over time windows.
acconsta 11y ago
Yeah, but... Need replication? Gotta write your own sharding logic or set up pg_shard. Need aggregations? Gotta write your own logic. Will you do them on the fly? Use triggers? On demand? Need to remove old data? Gotta set up a cron job. But wait, what if I want to age different series at different rates? Now you need a policy system. Sigh. Not saying Postgres can't be the storage engine, but there's a lot of work to do on top of that.
- gtrubetskoy 11y ago
  I believe that what you're referring to as "a lot work to do on top of that" is the correct solution, the ultimate OSS project. The fallacy of the many time series db's out there is that they discarded the relational database as a viable storage option prematurely and are now trapped solving the very hard problem of horizontally scalable distibuted storage that takes many years to solve instead of focusing on the time-series aspect of it. Sooner or later something along the lines of pg_shard will become standard in PostgreSQL and other databases, thus you don't really need to write your own sharding logic, you just have to wait. OR you can write it if you want. You have options. Aggregations is what GROUP BY is for. Removing old data is a non-issue if you're using a round-robin approach (see my blog link), it also makes aging different series at different rates easy.
  - acconsta 11y ago
    It's good to have competition in this area. Influx is giving me whiplash (it's on its third database engine in six months!) The circular buffer approach is fine, but it does have the drawback of being unable to represent variable-length data (like key-value pairs). It's also harder to compress the data. Can a GROUP-BY do windowed aggregations? Like, take an average over ten-minute windows? My SQL knowledge is not great.
chaotic-good 11y ago
You can't compare this solution to InfluxDB or other time-series databases out there because you're loosing information here. You can't store timestamps with arbitrary precision, and all the data is resampled, there is no way to store raw data. This is not acceptable in many cases.

shubhra51 11y ago

Woot! Nice throughput improvement over traditional LSM types with both read and write accelerated.

skybrian 11y ago

I'm wondering if a new low-level db will come out of this as an alternative to LevelDB, BoltDB, and so on? Or do you have to use InfluxDB?

btrask 11y ago
We definitely need more and better low level key-value stores, especially write-optimized ones. It sounds like InfluxDB has correctly identified the pain points with LevelDB and LMDB, but it's yet to be seen whether they've succeeded in addressing them. The article kind of petered out without a proper conclusion. The people who are talking about Postgres in this thread are thoroughly confused. This isn't a competitor to Postgres, this is a platform for building a competitor to Postgres (or, hypothetically, something Postgres itself could use). I guess maybe they mean InfluxDB rather than the subject of the article.
- robochat42 11y ago
  seriously? I'm always confused by the large number of different low level key-value stores on offer. All claiming to be the fastest, with benchmarks to back it up. Reading the article, it seems that they could have contributed some development to Rocksdb and saved themselves a lot of time rather than implementing their own system.
  - btrask 11y ago
    RocksDB has the same problems as LevelDB (uses large numbers of file descriptors, considerable read overhead compared to LMDB), plus it's even more complex and harder to configure. I had high hopes for the LSM tree from SQLite4[1], but last I checked development was stalled. [1] https://www.sqlite.org/src4/doc/trunk/www/lsmusr.wiki https://www.sqlite.org/src4/doc/trunk/www/lsmusr.wiki

philsnow 11y ago

typo in the article's headline: Strucutred -> Structured