Honors Theses and Capstones

Date of Award

Spring 2023

Project Type

Senior Honors Thesis

College or School

CEPS

Department

Computer Science

Program or Major

Computer Science

Degree Name

Bachelor of Science

First Advisor

Aleksey Charapko

Abstract

As the world generates more data, the demand to be able to store that data also grows. Additionally, this has led to a requirement for databases to be fault-tolerant distributed systems. Traditionally, distributed databases are leader-based. The leader communicates with clients and ensures the data replication to at least a quorum of other peers for fault tolerance. Additionally, the leader can order all client requests into a coherent single history of changes, which significantly simplifies the reasoning about the causality of changes in the applications using the database. Traditionally, databases use TCP, a reliable data streaming protocol, to communicate between nodes. The built-in reliability forces the leader to send data to each node individually and it also does extra ordering work that is already handled by the consensus algorithm. Metronome takes advantage of UDP multicast to allow a small set of proxy clients to transmit all required data to the database servers at approximately the same time bypassing the need for a leader This, combined with network layer integrity hashes, means that database servers do not need to share any data items between them outside of failure scenarios. Metronome orders operations only after their replications with the help of consensus protocol. This enables the consensus protocol to agree on the order of batches of operations, like '[client 1, data items 42-2000], [client 2, data items 314-159200], ...', meaning that a single round of consensus can order an arbitrary number of data items. After consensus has been reached, the cpu cores dedicated to data handling will process those items without interruption while the next round of consensus begins for new data. This approach means that, instead of being limited by rounds of consensus per second as is typical, Metronome's throughput is limited by one of the following; The ability to store all of the data while it is being agreed on (a problem for other databases), the speed at which it is possible to process the data, or the ability to ingest data. To aid in the ingestion of data, we use DPDK, a kernel bypass framework. The experiments conducted show that, with hardware accelerated packet distribution among cores, modern servers should be capable of processing millions of data items per second. Furthermore, our comparison shows that DPDK-based data ingestion performs up to 11x faster than an equivalent socket implementation while using less hardware acceleration. Further work includes tolerance for non-ideal networks, enabling hardware packet distribution, and evaluation of consensus algorithms.

Download

Available for download on Monday, May 08, 2028

Share

COinS