基於快取特性之記憶體式資料庫批次更新

Cache-Aware Batch Update for In-Memory Databases

張庭綱(Ting-Kang Chang)

指導教授 ： 陳銘憲

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201701572

摘要

低延遲、高流通量的記憶體式資料庫管理系統(DBMS)近年來因為硬體的發展，受到了研究與應用領域越來越多的關注。更甚者，有許多因應未來使用非揮發性隨機存取記憶體(NVRAM)之記憶體式儲存系統的研究也被提出。然而這些研究皆沒有對於在低局部性、密集的更新作業負載下的處理器快取利用率進行討論。此類負載容易造成低度的快取利用率，導致不理想的整體效能。我們設計了一個基於快取特性之批次更新架構藉以提升在此類負載下之效能。藉由將更新請求暫存於快取中，此系統可將數個於不同時間到達之相近請求聚合並在同一批次內更新，以避免對記憶體不必要的重複存取，進而減少快取未命中(Cache miss)並提升整體流通量。實驗結果顯示本論文提出的快取模型相對於未考量快取特性的參考模型，能節省最高達75%的末級快取(Last level cache)未命中數，以及達到最大65%的速度提升。

關鍵字

記憶體式資料處理 ； 快取記憶體 ； 低局部性

並列摘要

Low-latency, high throughput in-memory DBMSs have been attracting attention in research and application increasingly in recent years, thanks to hardware evolutions. Furthermore, there are many works proposed to address issues in the upcoming NVRAM era for durable in-memory storage. However, very few of them were focused on cache utilization for low-locality update-intensive workloads, which usually lead to poor cache utilization and undesirable performance. We design a cache-aware batch update model to improve cache efficiency for such workloads. By buffering update requests in cache, the system can aggregate spatially close requests arriving at distant time into one batched update, and avoid unnecessary data re-fetch from memory, thus reducing read latency and improve overall throughput. The experiments show that our proposed cache-aware model can save up to 75\% last-level-cache misses and achieve up to 1.65x speedup over a cache-oblivious reference model.

並列關鍵字

in-memory data processing ； cache memory ； low-locality

參考文獻

[3] S. Chen and Q. Jin. Persistent b+-trees in non-volatile main memory. Proceedings of the VLDB Endowment, 8(7):786–797, 2015.

[5] J. Huang, K. Schwan, and M. K. Qureshi. NVRAM-aware logging in transaction systems. Proceedings of the VLDB Endowment, 8(4):389–400, 2014.

[6] A. Jaleel, K. B. Theobald, S. C. Steely Jr, and J. Emer. High performance cache replacement using re-reference interval prediction (RRIP). In ACM SIGARCH Computer Architecture News, volume 38, pages 60–71. ACM, 2010.

[7] T. Karnagel, R. Dementiev, R. Rajwar, K. Lai, T. Legler, B. Schlegel, and W. Lehner. Improving in-memory database index performance with Intel R Transactional Synchronization Extensions. In High Performance Computer Architecture (HPCA), 2014 IEEE 20th International Symposium on, pages 476–487. IEEE, 2014.

[8] C. Kim, D. Burger, and S. W. Keckler. An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches. In Acm Sigplan Notices, volume 37, pages 211–222. ACM, 2002.