X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing

ABSTRACT

Alibaba runs the largest e-commerce platform in the world serving more than 600 million customers, with a GMV (gross merchandise value) exceeding USD 768 billion in FY2018. Online e-commerce transactions have three notable characteristics: (1) drastic increase of transactions per second with the kickoff of major sales and promotion events, (2) a large number of hot records that can easily overwhelm system buffers, and (3) quick shift of the "temperature'' (hot v.s. warm v.s. cold) of different records due to the availability of promotions on different categories over different short time periods. For example, Alibaba's OLTP database clusters experienced a 122 times increase of transactions on the start of the Singles' Day Global Shopping Festival in 2018, processing up to 491,000 sales transactions per second which translate to more than 70 million database transactions per second. To address these challenges, we introduce X-Engine, a write-optimized storage engine of POLARDB built at Alibaba, which utilizes a tiered storage architecture with the LSM-tree (log-structured merge tree) to leverage hardware acceleration such as FPGA-accelerated compactions, and a suite of optimizations including asynchronous writes in transactions, multi-staged pipelines and incremental cache replacement during compactions. Evaluation results show that X-Engine has outperformed other storage engines under such transactional workloads.

References

1. Steve Abraham. 2018. Introducing the Aurora Storage Engine. https://aws.amazon.com/cn/blogs/database/ introducing-the-aurora-storage-engine/.
2. Mehmet Altinel, Christof Bornhövd, Sailesh Krishnamurthy, C. Mohan, Hamid Pirahesh, and Berthold Reinwald. 2003. Cache Tables: Paving the Way for an Adaptive Database Cache. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB '03), Vol. 29. VLDB Endowment, 718--729.
3. Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul, and Jelani Nelson. 2007. Cacheoblivious Streaming B-trees. In Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '07). ACM, New York, NY, USA, 81--92.
4. Wei Cao, Zhenjun Liu, Peng Wang, Sen Chen, Caifeng Zhu, Song Zheng, Yuhui Wang, and Guoqing Ma. 2018. PolarFS: an ultra-low latency and failure resilient distributed file system for shared storage cloud database. Proceedings of the VLDB Endowment 11, 12 (2018), 1849--1862.
5. Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin Levandoski, James Hunter, and Mike Barnett. 2018. FASTER: A Concurrent Key-Value Store with In-Place Updates. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD '18). ACM, New York, NY, USA, 275--290.
6. Shimin Chen, Phillip B. Gibbons, and Todd C. Mowry. 2001. Improving Index Performance Through Prefetching. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data (SIGMOD '01). ACM, New York, NY, USA, 235--246.
7. Niv Dayan, Manos Athanassoulis, and Stratos Idreos. 2018. Optimal Bloom Filters and Adaptive Merging for LSM-Trees. ACM Transactions on Database Systems (2018).
8. Niv Dayan and Stratos Idreos. 2018. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD '18). ACM, New York, NY, USA, 505--520.
9. Siying Dong, Mark Callaghan, Leonidas Galanis, Dhruba Borthakur, Tony Savor, and Michael Strum. 2017. Optimizing Space Amplification in RocksDB. In The biennial Conference on Innovative Data Systems Research (CIDR), Vol. 3. 3.
10. Klaus Elhardt and Rudolf Bayer. 1984. A Database Cache for High Performance and Fast Restart in Database Systems. ACM Transactions on Database Systems (TODS) 9, 4 (Dec. 1984), 503--525.
11. Facebook. 2018. MyRocks. https://github.com/facebook/mysql-5.6/releases/tag/fb-prod201803.
12. Facebook. 2018. RocksDB MemTable. https://github.com/facebook/rocksdb/wiki/MemTable.
13. Facebook. 2018. RocksDB Pipelined Write. https://github.com/facebook/rocksdb/wiki/Pipelined-Write.
14. Facebook. 2018. RocksDB Release v5.17.2. https://github.com/facebook/rocksdb/releases/tag/v5.17.2.
15. Facebook. 2019. RocksDB: A persistent key-value store for fast storage environments. https://rocksdb.org/.
16. Sanjay Ghemawat and Jeff Dean. 2011. LevelDB. URL: s://github.com/google/leveldb,% 20http://leveldb. org (2011).
17. Goetz Graefe and Harumi Kuno. 2010. Self-selecting, Self-tuning, Incrementally Optimized Indexes. In Proceedings of the 13th International Conference on Extending Database Technology (EDBT '10). ACM, New York, NY, USA, 371--381.
18. Sándor Héman, Marcin Zukowski, Niels J. Nes, Lefteris Sidirourgos, and Peter Boncz. 2010. Positional Update Handling in Column Stores. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD '10). ACM, New York, NY, USA, 543--554.
19. H. V. Jagadish, P. P. S. Narayan, S. Seshadri, S. Sudarshan, and Rama Kanneganti. 1997. Incremental Organization for Data Recording and Warehousing. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB '97). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 16--25.
20. Alexey Kopytov. 2019. Scriptable database and system performance benchmark. https://github.com/akopytov/sysbench.
21. Tobin J. Lehman and Michael J. Carey. 1986. AStudy of Index Structures for Main Memory Database Management Systems. In Proceedings of the 12th International Conference on Very Large Data Bases (VLDB '86). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 294--303.
22. Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 38--49.
23. Justin Levandoski, David Lomet, and Sudipta Sengupta. 2013. LLAMA: A Cache/Storage Subsystem for Modern Hardware. Proceedings of the VLDB Endowment 6, 10 (Aug. 2013), 877--888.
24. Justin J Levandoski, David B Lomet, and Sudipta Sengupta. 2013. The Bw-Tree: A B-tree for new hardware platforms. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 302--313.
25. MemSQL. 2019. Database Benchmark Tool. https://github.com/memsql/dbbench.
26. MySQL. 2018. Introduction to InnoDB. https://dev.mysql.com/doc/refman/8.0/en/innodb-introduction.html.
27. Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. 1996. The log-structured merge-tree (LSM-tree). Acta Informatica 33, 4 (1996), 351--385.
28. Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. PebblesDB: Building Key-Value Stores Using Fragmented Log-Structured Merge Trees. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17). ACM, New York, NY, USA, 497--514.
29. Kai Ren, Qing Zheng, Joy Arulraj, and Garth Gibson. 2017. SlimDB: A Space-efficient Key-value Storage Engine for Semi-sorted Data. Proceedings of the VLDB Endowment 10, 13 (Sept. 2017), 2037--2048.
30. Mendel Rosenblum and John K. Ousterhout. 1992. The Design and Implementation of a Log-structured File System. ACM Transactions on Computer Systems (TOCS) 10, 1 (Feb. 1992), 26--52.
31. Russell Sears and Raghu Ramakrishnan. 2012. bLSM: A General Purpose Log Structured Merge Tree. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). ACM, New York, NY, USA, 217--228.
32. Dejun Teng, Lei Guo, Rubao Lee, Feng Chen, Siyuan Ma, Yanfeng Zhang, and Xiaodong Zhang. 2017. LSbM-tree: Re-enabling buffer caching in data management for mixed reads and writes. In 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). IEEE, 68--79.
33. Alexandre Verbitski, Anurag Gupta, Debanjan Saha, Murali Brahmadesam, Kamal Gupta, Raman Mittal, Sailesh Krishnamurthy, Sandor Maurice, Tengiz Kharatishvili, and Xiaofeng Bao. 2017. Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases. In Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD '17). ACM, New York, NY, USA, 1041--1052.
34. Hoang Tam Vo, Sheng Wang, Divyakant Agrawal, Gang Chen, and Beng Chin Ooi. 2012. LogBase: A Scalable Log-structured Database System in the Cloud. Proceedings of the VLDB Endowment 5, 10 (June 2012), 1004--1015.

Index Terms

• Information systems

  • Data management systems

    • Data structures

      • Data access methods

    • Database management system engines

      • Database transaction processing

      • DBMS engine architectures