Research Of A Migration-Friendly Key-Value Storage System With Delta Trees

Distributed databases have been widely used in big data scenarios due to their good write performance and scalability.The key-value storage system based on Log-Structured-Merge Tree(LSM-Tree)is the most common storage engine in the database.When there is skewed access or node scaling,data migration is performed between nodes of the distributed database in units of data shards,which usually changes the stable tree structure of LSM-Tree.To maintain a stable structure,LSM-Tree must perform a large number of compaction operations in the background,which uses a lot of CPU and storage device bandwidth,resulting in a decrease in the foreground read and write performance.In order to address the regression of read and write performance caused by a large number of unnecessary compactions in the process of data migrations in distributed databases,a migration-friendly key-value storage system DeltaDB is proposed.DeltaDB divides LSM-Tree vertically from top to bottom into several triangular Delta Trees similar in shape to the overall shape to ensure equal distribution of data at each layer,and then performs data migrations in units of Delta Tree without changing the stability of LSM-Tree structure to avoid compaction overhead caused by data migrations.A dynamic compaction strategy is designed inside Delta Tree to ensure the data ratio between layers,perform compaction operations in the data writing phase to construct stable Delta Trees,and transfer part of the compaction overhead during data migration.In addition,in order to further limit the number of compaction tasks during data migration,a thread scheduling and input/output limiting scheme is designed.The background compaction operations are scheduled according to the level of urgency,and the token bucket algorithm is used to limit the device bandwidth utilization of the compaction operation and reduce write stalls to stabilize foreground read and write performance.DeltaDB is implemented based on Ti KV and RocksDB,and it is deployed on the cloud platform as the storage engine of TiDB,and the performance is tested to compare with the original TiDB and its RocksDB storage engine.The results show that DeltaDB successfully reduces the number of compaction operations during migration by 31%～60%,and thus reduces the number of write stalls by 45%～63%,which in turn reduces TiDB latency caused by write stalls by 34%～67%.The number of queries per second has increased by 10% to 107%,which effectively alleviates the problem of TiDB’s read and write performance regression in migration scenarios.