research-article

Caribou: intelligent distributed storage

Authors:

Gustavo AlonsoAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 10, Issue 11

Pages 1202 - 1213

https://doi.org/10.14778/3137628.3137632

Published: 01 August 2017 Publication History

Abstract

The ever increasing amount of data being handled in data centers causes an intrinsic inefficiency: moving data around is expensive in terms of bandwidth, latency, and power consumption, especially given the low computational complexity of many database operations.

In this paper we explore near-data processing in database engines, i.e., the option of offloading part of the computation directly to the storage nodes. We implement our ideas in Caribou, an intelligent distributed storage layer incorporating many of the lessons learned while building systems with specialized hardware. Caribou provides access to DRAM/NVRAM storage over the network through a simple key-value store interface, with each storage node providing high-bandwidth near-data processing at line rate and fault tolerance through replication. The result is a highly efficient, distributed, intelligent data storage that can be used to both boost performance and reduce power consumption and real estate usage in the data center thanks to the micro-server architecture adopted.

References

[1]

A. Acharya, M. Uysal, and J. Saltz. Active disks: Programming model, algorithms and evaluation. ACM SIGPLAN Notices, 33(11), 1998.

Digital Library

[2]

J. Ahn, S. Hong, S. Yoo, et al. A scalable processing-in-memory accelerator for parallel graph processing. In ACM SIGARCH Computer Architecture News, volume 43, pages 105--117, 2015.

Digital Library

[3]

D. G. Andersen, J. Franklin, M. Kaminsky, et al. FAWN: A fast array of wimpy nodes. In SOSP'09. ACM.

Digital Library

[4]

B. Atikoglu, Y. Xu, E. Frachtenberg, et al. Workload analysis of a large-scale key-value store. In SIGMETRICS'12.

Digital Library

[5]

P. A. Bernstein, C. W. Reid, and S. Das. Hyder: A transactional record manager for shared flash. In CIDR, volume 11, pages 9--20, 2011.

[6]

M. Bjorling, P. Bonnet, L. Bouganim, and N. Dayan. The necessary death of the block device interface. In CIDR'13.

[7]

M. Blott, K. Karras, L. Liu, et al. Achieving 10gbps line-rate key-value stores with FPGAs. In HotCloud'13.

[8]

M. Blott, L. Liu, K. Karras, and K. Vissers. Scaling out to a single-node 80gbps memcached server with 40Terabytes of memory. In Usenix HotStorage'15.

Digital Library

[9]

L. Braun, T. Etter, G. Gasparis, et al. Analytics in motion: High performance event-processing and real-time analytics in the same database. In SIGMOD'15.

Digital Library

[10]

A. De, M. Gokhale, R. Gupta, et al. Minerva: Accelerating data analysis in next-generation SSDs. In FCCM'13.

[11]

C. Dennl, D. Ziener, and J. Teich. Acceleration of SQL restrictions and aggregations through FPGA-based dynamic partial reconfiguration. In FCCM'13.

Digital Library

[12]

C. Dennl, D. Ziener, and J. Teich. On-the-fly composition of FPGA-based SQL query accelerators using a partially reconfigurable module library. In FCCM'12.

Digital Library

[13]

C. Diaconu, C. Freedman, E. Ismert, et al. Hekaton: SQL server's memory-optimized OLTP engine. In SIGMOD'13.

Digital Library

[14]

J. Do, Y.-S. Kee, J. M. Patel, et al. Query processing on smart SSDs: opportunities and challenges. In SIGMOD'13.

Digital Library

[15]

A. Dragojević, D. Narayanan, O. Hodson, and M. Castro. Farm: Fast remote memory. In NSDI'14.

Digital Library

[16]

B. Fan, D. G. Andersen, and M. Kaminsky. Memc3: Compact and concurrent memcache with dumber caching and smarter hashing. In NSDI'13.

Digital Library

[17]

M. Gao and C. Kozyrakis. Hrl: Efficient and flexible reconfigurable logic for near-data processing. In HPCA'16.

[18]

Z. István, G. Alonso, M. Blott, and K. Vissers. A hash table for line-rate data processing. ACM TRETS, 8(2), Mar. 2015.

Digital Library

[19]

Z. István, G. Alonso, M. Blott, and K. A. Vissers. A flexible hash table design for 10Gbps key-value stores on FPGAs. In FPL'13.

[20]

Z. István, D. Sidler, and G. Alonso. Runtime parameterizable regular expression operators for databases. In FCCM'16.

[21]

Z. Istvan, D. Sidler, G. Alonso, and M. Vukolic. Consensus in a box: Inexpensive coordination in hardware. In NSDI'16.

Digital Library

[22]

Z. István, L. Woods, and G. Alonso. Histograms as a side effect of data movement for big data. In SIGMOD'14.

Digital Library

[23]

I. Jo, D.-H. Bae, A. S. Yoon, et al. YourSQL: a high-performance database system leveraging in-storage computing. VLDB'16.

Digital Library

[24]

S.-W. Jun, M. Liu, K. E. Fleming, et al. Scalable multi-access flash store for big data analytics. In FPGA'14.

[25]

S.-W. Jun, M. Liu, S. Lee, et al. BlueDBM: an appliance for big data analytics. In ISCA'15.

[26]

F. P. Junqueira, B. C. Reed, et al. Zab: High-performance broadcast for primary-backup systems. In DSN'11.

Digital Library

[27]

R. Kallman, H. Kimura, J. Natkins, et al. H-store: a high-performance, distributed main memory transaction processing system. VLDB'08.

Digital Library

[28]

Y. Kaneta, S.-i. Minato, and H. Arimura. Fast bit-parallel matching for network and regular expressions. In Proc. 17th SPIRE. Springer, 2010.

Digital Library

[29]

K. Kara and G. Alonso. Fast and robust hashing for database operators. In FPL'16.

[30]

K. Kara, J. Giceva, and G. Alonso. FPGA based data partitioning. In SIGMOD'17.

Digital Library

[31]

F. Klein, K. Beineke, and M. Schöttner. Memory management for billions of small objects in a distributed in-memory storage. In IEEE CLUSTER'14.

[32]

J. J. Levandoski, D. B. Lomet, and S. Sengupta. The bw-tree: A b-tree for new hardware platforms. In ICDE'13.

Digital Library

[33]

J. J. Levandoski, D. B. Lomet, S. Sengupta, et al. High performance transactions in Deuteronomy. In CIDR'15.

[34]

S. Li, H. Lim, V. W. Lee, et al. Architecting to achieve a billion requests per second throughput on a single key-value store server platform. In ACM SIGARCH Computer Architecture News, volume 43. ACM, 2015.

Digital Library

[35]

H. Lim, D. Han, D. G. Andersen, and M. Kaminsky. MICA: a holistic approach to fast in-memory key-value storage. In NSDI'14.

Digital Library

[36]

S. Loesing, M. Pilman, T. Etter, and D. Kossmann. On the design and scalability of distributed shared-data databases. In SIGMOD'15.

Digital Library

[37]

D. Makreshanski, J. Giceva, C. Barthels, and G. Alonso. BatchDB: Efficient isolated execution of hybrid OLTP+OLAP workloads for interactive applications. SIGMOD'17.

Digital Library

[38]

M. Najafi, M. Sadoghi, and H.-A. Jacobsen. Flexible query processor on FPGAs. VLDB'13.

Digital Library

[39]

M. Oskin, F. T. Chong, and T. Sherwood. Active pages: a computation model for intelligent memory, volume 26. IEEE Computer Society, 1998.

Digital Library

[40]

J. Ousterhout, P. Agrawal, D. Erickson, et al. The case for RAMClouds: scalable high-performance storage entirely in DRAM. ACM SIGOPS Operating Systems Review, 2010.

Digital Library

[41]

R. Pagh and F. F. Rodler. Cuckoo hashing. In European Symposium on Algorithms. Springer, 2001.

Digital Library

[42]

M. Pilman. Tell: An elastic database system for mixed workloads (PhD Dissertation No. 24147), ETH Zürich, Switzerland, 2017. https://www.systems.ethz.ch/sites/default/files/file/UpcomingPublications/PilmanMarkus2016.pdf.

[43]

C. Plattner and G. Alonso. Ganymed: Scalable replication for transactional web applications. In Middleware, 2004.

Digital Library

[44]

M. Poke and T. Hoefler. DARE: high-performance state machine replication on RDMA networks. In HPDC'15.

Digital Library

[45]

B. Salami, G. A. Malazgirt, O. Arcas-Abella, et al. AxleDB: A novel programmable query processing platform on FPGA. Elsevier Microprocessors and Microsystems, 51, 2017.

[46]

S. Seshadri, M. Gahagan, S. Bhaskaran, et al. Willow: a user-programmable SSD. In OSDI'14.

Digital Library

[47]

J. Shute, M. Oancea, S. Ellner, et al. F1-the fault-tolerant distributed RDBMS supporting Google's Ad business. In SIGMOD'12.

Digital Library

[48]

D. Sidler, G. Alonso, M. Blott, et al. Scalable 10Gbps TCP/IP stack architecture for reconfigurable hardware. In FCCM'15.

Digital Library

[49]

D. Sidler, Z. István, and G. Alonso. Low-latency TCP/IP stack for data center applications. In FPL'16.

[50]

D. Sidler, Z. István, M. Owaida, and G. Alonso. Accelerating pattern matching queries in hybrid CPU-FPGA architectures. In SIGMOD'17.

Digital Library

[51]

B. Sukhwani, H. Min, M. Thoennes, et al. Database analytics acceleration using FPGAs. In PACS'12.

Digital Library

[52]

Y. Sun, Z. Wang, S. Huang, et al. Accelerating frequent item counting with FPGA. In FPGA'14.

Digital Library

[53]

S. Tanaka and C. Kozyrakis. High performance hardware-accelerated flash key-value store. In Non-volatile Memories Workshop (NVMW), 2014.

[54]

J. Teubner and L. Woods. Data processing on FPGAs. Morgan & Claypool Synthesis Lectures on Data Management, 2013.

Digital Library

[55]

J. Teubner, L. Woods, and C. Nie. Skeleton automata for FPGAs: reconfiguring without reconstructing. In SIGMOD'12.

Digital Library

[56]

D. Tong and V. Prasanna. High throughput sketch based online heavy hitter detection on FPGA. ACM SIGARCH Computer Architecture News, 43, 2016.

Digital Library

[57]

A. Trivedi, P. Stuedi, B. Metzler, et al. Rstore: A direct-access DRAM-based data store. In ICDCS'15. IEEE.

[58]

R. van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. In OSDI'04.

Digital Library

[59]

Z. Wang, B. He, and W. Zhang. A study of data partitioning on opencl-based fpgas. In FPL'15.

[60]

Z. Wang, J. Paul, H. Y. Cheah, B. He, and W. Zhang. Relational query processing on opencl-based fpgas. In FPL'16, 2016.

Digital Library

[61]

M. Wei, J. D. Davis, T. Wobber, et al. Beyond block I/O: implementing a distributed shared log in hardware. In Proceedings of the 6th International Systems and Storage Conference. ACM, 2013.

Digital Library

[62]

R. Weiss. A technical overview of the oracle exadata database machine and exadata storage server. Oracle White Paper. Oracle Corporation, Redwood Shores, 2012.

[63]

L. Woods, G. Alonso, and J. Teubner. Parallelizing data processing on FPGAs with shifter lists. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 8(2), 2015.

Digital Library

[64]

L. Woods, Z. István, and G. Alonso. Ibex - an intelligent storage engine with support for advanced SQL off-loading. PVLDB, 7(11), July 2014.

Digital Library

[65]

L. Woods, J. Teubner, and G. Alonso. Complex event detection at wire speed with FPGAs. VLDB'10.

Digital Library

[66]

S. L. Xi, O. Babarinsa, M. Athanassoulis, and S. Idreos. Beyond the wall: Near-data processing for databases. In DAMoN'15. ACM.

Digital Library

[67]

S. Xu, S. Lee, S.-W. Jun, et al. Bluecache: A scalable distributed flash-based key-value store. In VLDB'16.

Digital Library

[68]

J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on information theory, 23(3), 1977.

Digital Library

Cited By

Faghih FZiegler TIstván ZBinnig CBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)SmartNICs in the Cloud: The Why, What and How of In-network Processing for Data-Intensive ApplicationsCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654690(556-560)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654690
Maschi FAlonso G(2024)Strega: An HTTP Server for FPGAsACM Transactions on Reconfigurable Technology and Systems10.1145/361131217:1(1-27)Online publication date: 27-Jan-2024
https://dl.acm.org/doi/10.1145/3611312
Lim KGiordano MStavrinos TZhang INelson JKasikci BAnderson T(2024)Beehive: A Flexible Network Stack for Direct-Attached Accelerators2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO61859.2024.00037(393-408)Online publication date: 2-Nov-2024
https://doi.org/10.1109/MICRO61859.2024.00037
Show More Cited By

Recommendations

Higher reliability redundant disk arrays: Organization, operation, and coding

Parity is a popular form of data protection in redundant arrays of inexpensive/independent disks (RAID). RAID5 dedicates one out of N disks to parity to mask single disk failures, that is, the contents of a block on a failed disk can be reconstructed by ...
Flash-Aware RAID Techniques for Dependable and High-Performance Flash Memory SSD

Solid-state disks (SSDs), which are composed of multiple NAND flash chips, are replacing hard disk drives (HDDs) in the mass storage market. The performances of SSDs are increasing due to the exploitation of parallel I/O architectures. However, ...
HPDA: A hybrid parity-based disk array for enhanced performance and reliability

Flash-based Solid State Drive (SSD) has been productively shipped and deployed in large scale storage systems. However, a single flash-based SSD cannot satisfy the capacity, performance and reliability requirements of the modern storage systems that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 10, Issue 11

August 2017

432 pages

ISSN:2150-8097

Editors:
Peter Boncz
CWI
,
Ken Salem
University of Waterloo

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2017

Published in PVLDB Volume 10, Issue 11

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

72
Total Citations
View Citations
623
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)5

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Faghih FZiegler TIstván ZBinnig CBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)SmartNICs in the Cloud: The Why, What and How of In-network Processing for Data-Intensive ApplicationsCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654690(556-560)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654690
Maschi FAlonso G(2024)Strega: An HTTP Server for FPGAsACM Transactions on Reconfigurable Technology and Systems10.1145/361131217:1(1-27)Online publication date: 27-Jan-2024
https://dl.acm.org/doi/10.1145/3611312
Lim KGiordano MStavrinos TZhang INelson JKasikci BAnderson T(2024)Beehive: A Flexible Network Stack for Direct-Attached Accelerators2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO61859.2024.00037(393-408)Online publication date: 2-Nov-2024
https://doi.org/10.1109/MICRO61859.2024.00037
López-Paradís GHair IKannan SRabbat RMurray PLopes AZahedi RZuo WBalkind J(2024)The Case For Data Centre Hyperloops2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00026(230-244)Online publication date: 29-Jun-2024
https://doi.org/10.1109/ISCA59077.2024.00026
Lerner AAlonso G(2024)Data Flow Architectures for Data Processing on Modern Hardware2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00439(5511-5522)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00439
Wang RGao CWang JKadam PTamerÖzsu MAref W(2024)Optimizing LSM-based indexes for disaggregated memoryThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-024-00863-y33:6(1813-1836)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1007/s00778-024-00863-y
Lerner ABonnet PLerner ABonnet P(2024)Computational StoragePrinciples of Database and Solid-State Drive Co-Design10.1007/978-3-031-57877-9_4(59-74)Online publication date: 7-Dec-2024
https://doi.org/10.1007/978-3-031-57877-9_4
Wang KChen F(2023)Catalyst: Optimizing Cache Management for Large In-memory Key-value SystemsProceedings of the VLDB Endowment10.14778/3625054.362506816:13(4339-4352)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.14778/3625054.3625068
Trivedi ABrunella MBaumann ACrooks NSchwarzkopf M(2023)CPU-free Computing: A Vision with a BlueprintProceedings of the 19th Workshop on Hot Topics in Operating Systems10.1145/3593856.3595906(1-14)Online publication date: 22-Jun-2023
https://dl.acm.org/doi/10.1145/3593856.3595906
Maschi FKorolija DAlonso GUstiugov DBruno RFonseca PGrot BBarbalace A(2023)Serverless FPGA: Work-In-ProgressProceedings of the 1st Workshop on SErverless Systems, Applications and MEthodologies10.1145/3592533.3592804(1-4)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3592533.3592804
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents