4 ms·

I don't think you want to measure your timeseries datastructure against LSM-trees because the latter is inherently a pretty bad structure to use for timeseries

by eis 9y ago

I don't think you want to measure your timeseries datastructure against LSM-trees because the latter is inherently a pretty bad structure to use for timeseries (which are mostly append-only) as a few projects painfully found out. Anyways, I'm interested in timeseries so I read the article and tried to understand the datastructure but to be honest it opens up more questions than it answers. I applaud people though who try to describe their datastructures that are core to the app. Thanks for that. 1. What is the exact datastructure of a leaf? You mention a leaf node can hold 1000 datapoints. 2. Why is using a WAL impossible? That should be possible for any datastructure. 3. In your example if level 3 is full and everything gets merged into level 4, there are no levels 1-3. How does one query the datastructure? Does it maintain a pointer from the root to level 4? 4. Related to above: if I want to query all data from last month until now which happens to be the start of level 4, it will first go to root, then to the level 2 Leaf, from there to the level 2 SBlock, from there to the level 3 Leaf, then level 3 SBlock, then level 4 Leaf, then level 4 Sblock, then the first level 4 leaf? That seems a lot of random access. How many iops does a lookup need? 5. SBlocks need to be kept in memory. If I have ten million timeseries (not uncommon, can be much more), each with 3 levels, then upon startup the app has to load 30M SBlocks into memory? 6. You say that several trees can be interleaved in a single file, how does that not break the linear IO advantage of columnar layouts? 7. How do you store information in the "inner nodes" (SBlocks?) to speed up aggregation? Do you store every possible aggregation in there? E.g. sum, avg, min, max, stddev, ... 8. Storage format of an individual time series is only a part of what a TSBD needs to do, another part is how to find all the timeseries for a particular query. How does that work? And in general I think you can't have all three: A) good write performance B) no write amplification C) low RAM usage ... because you have to either write data out immediately (and get either 2x+ write amplification or lots of random writes/reads) or buffer it in RAM to batch linear writes. I think there are some interesting ideas in this structure, it looks to me more like a Linked List of one level deep B+Trees, not a big overall tree.

chaotic-good 9y ago
1. Each leaf node is a fixed size block that contains compressed values and timestamps. 1000 values is just an example, number of values in one leaf node is variable. 2. Because there is a lot of data-structures. I'm using tree per series. The database can simply store hundreds of thousends of series. Creating WAL per series is not feasible. 3. It maintains a list of roots. 4. One I/O operation per node. You will fetch a leaf node for every ~1000 data points and a superblock for every 32 leaf nodes. It's not as bad as it sounds because you will read data for one series only. To span over 4 levels the series should contain tens of millions of points. 5. Yes. You will need a beefy machine for this with a lot of RAM. 6. Random reads are fast on modern SSDs. It's optimized for SSD (I simply don't have a computer with HDD). 7. It stores only composable aggregations - min, max, count, sum, min/max timestamps. 8. All series names is stored in memory. During the query time this memory is scanned using regexp to find relevant series names and they ids. This is a kind of a temporary solution. It works good enough for the datasets with small cardinality (around 100K series).
chaotic-good 9y ago
Akumuli is desinged for an SSD and NVMe drives so I chose to have a lot of random reads and writes. My laptop's NVMe drive have a random write througphut around 400MB/s (AFAIR) and my most havy performance test wrote data at rate about 70MB/s (16M data points per second).
- ChuckMcM 9y ago
  This is perhaps the most interesting aspect of it to me. When we relax the constraint that 'mass storage access must be a linear and infrequent as possible' what sort of possibilities does that open up in the design space that were previously untenable. Nice work and thank you for sharing it.
  - ehsanu1 9y ago
    My understanding is that even SSDs perform somewhat better sequentially (throughput-wise), though the difference isn't quite as dramatic as with HDDs. That said, the 400 mb/s random write speed for nvme mentioned is plenty faster than sequential write speeds most people had access to until recently with SSDs, so that's pretty interesting.
  - chaotic-good 9y ago
    It's not that easy, actually. The simplest method that can utilize the full throughput of the drive is to use large writes (1MB or larger). This is the fastest possible way to write data to the SSD, period. This method also creates the simplest possible FTL mapping table. Random reads and writes are significantly slower if you write everything from one thread. To speed everything up you should write in parallel (for example using Linux AIO + O_DIRECT, or libuv + O_DIRECT). OS level buffering and many OS threads will deliver good random write throughput as well. There are other effects to consider, e.g. read-write interference.
    - ChuckMcM 9y ago
      I understand. I would expect that you will get an additional boost if you target Intel's 'Optane' technology which, by its design, allows for a much faster channel turnaround and so less interference. And in the fairly recent past other vendors like Texas Memory systems developed strategies which were all RAM and a bit of cleverness to snapshot to HD when the power fails. The point being that with enough money you could brute force the solution, but now the money required it decreasing and so new strategies are opening up.

by eis 9y ago

chaotic-good 9y ago

1. Each leaf node is a fixed size block that contains compressed values and timestamps. 1000 values is just an example, number of values in one leaf node is variable. 2. Because there is a lot of data-structures. I'm using tree per series. The database can simply store hundreds of thousends of series. Creating WAL per series is not feasible. 3. It maintains a list of roots. 4. One I/O operation per node. You will fetch a leaf node for every ~1000 data points and a superblock for every 32 leaf nodes. It's not as bad as it sounds because you will read data for one series only. To span over 4 levels the series should contain tens of millions of points. 5. Yes. You will need a beefy machine for this with a lot of RAM. 6. Random reads are fast on modern SSDs. It's optimized for SSD (I simply don't have a computer with HDD). 7. It stores only composable aggregations - min, max, count, sum, min/max timestamps. 8. All series names is stored in memory. During the query time this memory is scanned using regexp to find relevant series names and they ids. This is a kind of a temporary solution. It works good enough for the datasets with small cardinality (around 100K series).

chaotic-good 9y ago

Akumuli is desinged for an SSD and NVMe drives so I chose to have a lot of random reads and writes. My laptop's NVMe drive have a random write througphut around 400MB/s (AFAIR) and my most havy performance test wrote data at rate about 70MB/s (16M data points per second).

ChuckMcM 9y ago
This is perhaps the most interesting aspect of it to me. When we relax the constraint that 'mass storage access must be a linear and infrequent as possible' what sort of possibilities does that open up in the design space that were previously untenable. Nice work and thank you for sharing it.
- ehsanu1 9y ago
  My understanding is that even SSDs perform somewhat better sequentially (throughput-wise), though the difference isn't quite as dramatic as with HDDs. That said, the 400 mb/s random write speed for nvme mentioned is plenty faster than sequential write speeds most people had access to until recently with SSDs, so that's pretty interesting.
- chaotic-good 9y ago
  It's not that easy, actually. The simplest method that can utilize the full throughput of the drive is to use large writes (1MB or larger). This is the fastest possible way to write data to the SSD, period. This method also creates the simplest possible FTL mapping table. Random reads and writes are significantly slower if you write everything from one thread. To speed everything up you should write in parallel (for example using Linux AIO + O_DIRECT, or libuv + O_DIRECT). OS level buffering and many OS threads will deliver good random write throughput as well. There are other effects to consider, e.g. read-write interference.
  - ChuckMcM 9y ago
    I understand. I would expect that you will get an additional boost if you target Intel's 'Optane' technology which, by its design, allows for a much faster channel turnaround and so less interference. And in the fairly recent past other vendors like Texas Memory systems developed strategies which were all RAM and a bit of cleverness to snapshot to HD when the power fails. The point being that with enough money you could brute force the solution, but now the money required it decreasing and so new strategies are opening up.