Separation or Not: On Handing Out-of-Order Time-Series Data in Leveled LSM-Tree

Abstract

LSM-Tree is widely adopted for storing time-series data in Internet of Things. According to conventional policy (denoted by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\pi_{c}$</tex> ), when writing, the data will first be buffered in MemTable in memory. When it is full, the data will be written to the disk to form SSTables. Compaction is triggered to sort the data in each layer of the LSM-Tree on the disk. However, the arrival of data can be unordered due to reasons such as transition delay. Apache IoTDB uses in-order and out-of-order MemTables to separately buffer the in-order and out-of-order data to accelerate queries, namely the separation policy (denoted by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\pi_{s}$</tex> ). However, given a specific space of memory budget to buffer the data, write amplification (WA) of the leveled LSM-Tree will be influenced by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\pi_{s}$</tex> . Whether the influence by separation is positive or negative, and how intense WA is influenced, depend on the properties of workloads and the capacity of the in-order and out-of-order MemTables. It is highly demanded to build robust models for estimating the expected amount of data rewritten in each compaction, and predicting the WA under <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\pi_{c}$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\pi_{s}$</tex> . Note that as an industrial paper, rather than proposing novel techniques for research problems, we focus on the practice of whether separating or not for lower write amplification. Experiments on synthetic and real-world datasets show that the models for estimating WA are accurate under various delay distributions. In addition, based on the estimation models, we implement an analyzer module in the open-source Apache IoTDB, for choosing the policy with lower WA. We apply the method in the use case of our industrial partner, a service provider of engineering machinery. The use case verifies the effectiveness of deciding whether separation or not by WA estimation.