\documentclass[12pt,a4paper]{report}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{booktabs}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{fancyhdr}
\usepackage{titlesec}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{tabularx}
\usepackage{float}
\usepackage{microtype}
\usepackage{caption}

\definecolor{codeblue}{HTML}{2E86C1}
\definecolor{codebg}{HTML}{F4F6F7}
\definecolor{codegreen}{HTML}{27AE60}
\definecolor{codegray}{HTML}{7F8C8D}
\definecolor{headerblue}{HTML}{1B3A5C}

\hypersetup{
  colorlinks=true,
  linkcolor=headerblue,
  citecolor=codeblue,
  urlcolor=codeblue
}

\lstset{
  basicstyle=\ttfamily\small,
  backgroundcolor=\color{codebg},
  keywordstyle=\color{codeblue}\bfseries,
  commentstyle=\color{codegreen}\itshape,
  stringstyle=\color{red!60!black},
  numberstyle=\tiny\color{codegray},
  frame=single,
  rulecolor=\color{codegray!50},
  breaklines=true,
  numbers=left,
  tabsize=2,
  showstringspaces=false
}

% Chapter heading style
\titleformat{\chapter}[display]
  {\normalfont\LARGE\bfseries\color{headerblue}}{\chaptertitlename\\ \thechapter}{16pt}{\Huge}
\titlespacing*{\chapter}{0pt}{-10pt}{25pt}

% Header/footer
\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\small\color{codegray}\textit{Technical Report TR-2025-003}}
\fancyhead[R]{\small\color{codegray}\nouppercase{\leftmark}}
\fancyfoot[C]{\thepage}
\renewcommand{\headrulewidth}{0.4pt}

\begin{document}

% ──── Title Page ────
\begin{titlepage}
\centering
\vspace*{1cm}

{\color{headerblue}\rule{\textwidth}{2pt}}\\[1cm]

{\small\color{codegray} TECHNICAL REPORT TR-2025-003}\\[1cm]
{\fontsize{28}{34}\selectfont\bfseries\color{headerblue}
  Distributed Key--Value Store\\with Consensus-Based Replication\\[0.3cm]
  Design, Implementation, and\\Performance Analysis}\\[1.5cm]

{\Large
  \textbf{Michael Torres}, \textbf{Ananya Krishnan}, \textbf{Erik Johansson}}\\[0.5cm]
{\large Infrastructure Engineering Team\\Distributed Systems Division}\\[1.5cm]

{\color{headerblue}\rule{0.6\textwidth}{0.5pt}}\\[1cm]

{\large
\begin{tabular}{ll}
\textbf{Document ID:} & TR-2025-003 \\
\textbf{Version:} & 2.1 \\
\textbf{Date:} & February 10, 2025 \\
\textbf{Classification:} & Internal -- Engineering \\
\textbf{Status:} & Final \\
\end{tabular}}

\vfill

{\large Acme Cloud Systems, Inc.\\
1200 Technology Drive, San Jose, CA 95134}

\end{titlepage}

% ──── Revision History ────
\chapter*{Revision History}
\addcontentsline{toc}{chapter}{Revision History}

\begin{table}[H]
\centering
\begin{tabular}{@{}llll@{}}
\toprule
\textbf{Version} & \textbf{Date} & \textbf{Author} & \textbf{Changes} \\
\midrule
1.0 & 2024-11-15 & M.\\ Torres & Initial draft \\
1.5 & 2024-12-20 & A.\\ Krishnan & Added benchmarks and security analysis \\
2.0 & 2025-01-28 & E.\\ Johansson & Performance tuning and final benchmarks \\
2.1 & 2025-02-10 & M.\\ Torres & Minor corrections, final review \\
\bottomrule
\end{tabular}
\end{table}

% ──── Executive Summary ────
\chapter*{Executive Summary}
\addcontentsline{toc}{chapter}{Executive Summary}

This report presents the design, implementation, and performance evaluation of \textbf{AcmeKV}, a distributed key--value store with strong consistency guarantees based on the Raft consensus protocol. AcmeKV is designed to serve as the foundational storage layer for Acme Cloud Systems' next-generation microservices platform, replacing the existing Cassandra-based infrastructure which has proven difficult to maintain and reason about under our strong consistency requirements.

Key findings of this report include:
\begin{itemize}[itemsep=4pt]
  \item AcmeKV achieves \textbf{285,000 reads/sec} and \textbf{142,000 writes/sec} on a 5-node cluster with p99 latencies under 5ms for reads and 12ms for writes.
  \item The system correctly maintains linearizable consistency under all tested failure scenarios, including leader failure, network partitions, and disk failures.
  \item Compared to our existing Cassandra deployment, AcmeKV provides a \textbf{2.3$\times$} improvement in write latency and a \textbf{40\%} reduction in operational complexity as measured by incident response time.
  \item The system is ready for production deployment with the caveats noted in Section~5.3.
\end{itemize}

% ──── TOC ────
\tableofcontents
\listoftables

% ════════════════════════════════════════════
\chapter{Introduction}
\label{ch:introduction}
% ════════════════════════════════════════════

\section{Motivation}

Acme Cloud Systems' microservices platform currently relies on Apache Cassandra as its primary key--value store. While Cassandra provides excellent horizontal scalability and availability, its eventual consistency model has been a persistent source of bugs and operational complexity. Over the past 18 months, our incident reports show that 34\% of P1 incidents were attributable to stale reads or write conflicts arising from Cassandra's eventual consistency guarantees.

As our platform has evolved, we have identified a growing set of use cases that require strong consistency:
\begin{enumerate}[itemsep=4pt]
  \item \textbf{Configuration management}: Service configurations must be read with linearizable guarantees to prevent inconsistent behavior across replicas.
  \item \textbf{Distributed locking}: Leader election and distributed locks require consensus to function correctly.
  \item \textbf{Financial transactions}: Payment processing requires serializable isolation to prevent double-spending.
  \item \textbf{Metadata catalogs}: Dataset and schema registries must reflect the latest state to avoid data corruption.
\end{enumerate}

\section{Requirements}

Based on stakeholder interviews and workload analysis, we established the following requirements for AcmeKV:

\begin{table}[H]
\centering
\caption{System requirements for AcmeKV.}
\label{tab:requirements}
\begin{tabular}{@{}llc@{}}
\toprule
\textbf{ID} & \textbf{Requirement} & \textbf{Priority} \\
\midrule
R1 & Linearizable read/write consistency & Must \\
R2 & $\geq$100K writes/sec (5-node cluster) & Must \\
R3 & p99 read latency $<$ 10ms & Must \\
R4 & Automatic leader failover $<$ 5 seconds & Must \\
R5 & Online cluster membership changes & Should \\
R6 & Point-in-time snapshots for backup & Should \\
R7 & TLS encryption for all communication & Must \\
R8 & Role-based access control (RBAC) & Should \\
R9 & Observability (metrics, tracing, logging) & Must \\
R10 & Cross-datacenter replication & Could \\
\bottomrule
\end{tabular}
\end{table}

\section{Scope}

This report covers the design and implementation of AcmeKV version 1.0, addressing requirements R1--R9. Cross-datacenter replication (R10) is deferred to version 2.0 and will be covered in a subsequent report.

% ════════════════════════════════════════════
\chapter{System Design}
\label{ch:design}
% ════════════════════════════════════════════

\section{Architecture Overview}

AcmeKV follows a replicated state machine architecture built on the Raft consensus protocol. The system consists of the following core components:

\begin{description}[style=nextline, leftmargin=2em]
  \item[Raft Consensus Module] Implements leader election, log replication, and safety guarantees per the Raft specification. Our implementation extends the basic protocol with pre-vote, leadership transfer, and joint consensus for membership changes.
  \item[Storage Engine] A log-structured merge-tree (LSM-tree) storage engine optimized for write-heavy workloads. The engine uses a two-level compaction strategy with bloom filters for efficient point lookups.
  \item[API Gateway] gRPC-based API layer that routes client requests to the appropriate cluster node. Read requests can be served by any node (with a consistency check), while writes are forwarded to the leader.
  \item[Snapshot Manager] Handles periodic snapshots of the state machine for log compaction and backup/restore operations.
\end{description}

\section{Consensus Protocol}

We implement the Raft consensus protocol with several optimizations for production use:

\begin{enumerate}[itemsep=4pt]
  \item \textbf{Batched log replication}: Multiple client requests are batched into a single AppendEntries RPC, amortizing the cost of consensus across multiple operations.
  \item \textbf{Pipeline replication}: The leader sends the next batch of entries before receiving acknowledgment for the previous batch, improving throughput on high-latency networks.
  \item \textbf{Lease-based reads}: The leader maintains a time-based lease that allows it to serve linearizable reads without requiring a round of consensus, reducing read latency significantly.
\end{enumerate}

The correctness of our implementation is verified through a combination of property-based testing (using Jepsen) and TLA+ model checking of the core consensus logic.

\section{Data Model}

AcmeKV supports a simple key--value data model with the following operations:

\begin{lstlisting}[language=Go, caption={AcmeKV core API definition.}]
service AcmeKV {
  // Put stores a key-value pair.
  rpc Put(PutRequest) returns (PutResponse);

  // Get retrieves the value for a key.
  rpc Get(GetRequest) returns (GetResponse);

  // Delete removes a key-value pair.
  rpc Delete(DeleteRequest) returns (DeleteResponse);

  // Scan returns key-value pairs in a range.
  rpc Scan(ScanRequest) returns (stream ScanResponse);

  // Txn executes a multi-key transaction.
  rpc Txn(TxnRequest) returns (TxnResponse);
}
\end{lstlisting}

Keys are limited to 256 bytes and values to 1MB. The system supports optional TTL (time-to-live) on keys and atomic multi-key transactions with serializable isolation using optimistic concurrency control.

% ════════════════════════════════════════════
\chapter{Performance Evaluation}
\label{ch:performance}
% ════════════════════════════════════════════

\section{Test Environment}

All benchmarks were conducted on a 5-node cluster with the following hardware configuration:

\begin{table}[H]
\centering
\caption{Hardware configuration for benchmark cluster.}
\begin{tabular}{@{}ll@{}}
\toprule
\textbf{Component} & \textbf{Specification} \\
\midrule
CPU & Intel Xeon Gold 6348 (28 cores, 2.6 GHz) \\
Memory & 256 GB DDR4-3200 ECC \\
Storage & 2$\times$ Intel Optane P5800X 1.6TB (NVMe) \\
Network & 25 Gbps Ethernet (Mellanox ConnectX-6) \\
OS & Ubuntu 22.04 LTS (kernel 5.15) \\
\bottomrule
\end{tabular}
\end{table}

\section{Throughput Results}

Table~\ref{tab:throughput} summarizes the throughput results under various workload configurations.

\begin{table}[H]
\centering
\caption{Throughput (operations/second) under different workload mixes.}
\label{tab:throughput}
\begin{tabular}{@{}lccc@{}}
\toprule
\textbf{Workload} & \textbf{AcmeKV} & \textbf{etcd v3.5} & \textbf{Cassandra (QUORUM)} \\
\midrule
100\% Read          & 285,000 & 142,000 & 310,000 \\
100\% Write         & 142,000 & 48,000  & 165,000 \\
95\% Read / 5\% Write  & 271,000 & 128,000 & 295,000 \\
50\% Read / 50\% Write & 198,000 & 85,000  & 225,000 \\
\bottomrule
\end{tabular}
\end{table}

AcmeKV achieves approximately 2$\times$ the throughput of etcd while providing the same linearizable consistency guarantees. Cassandra achieves slightly higher raw throughput, but this comes at the cost of weaker consistency (quorum reads/writes provide only regular register semantics, not linearizability).

\section{Latency Results}

\begin{table}[H]
\centering
\caption{Latency percentiles (milliseconds) for read and write operations.}
\label{tab:latency}
\begin{tabular}{@{}lcccc@{}}
\toprule
\textbf{Operation} & \textbf{p50} & \textbf{p90} & \textbf{p99} & \textbf{p99.9} \\
\midrule
Read (lease-based)  & 0.8 & 1.5 & 3.2 & 8.1 \\
Read (consensus)    & 2.1 & 3.8 & 7.4 & 15.3 \\
Write               & 3.5 & 6.2 & 11.8 & 28.4 \\
Transaction (2-key) & 5.2 & 9.1 & 18.5 & 42.7 \\
\bottomrule
\end{tabular}
\end{table}

% ════════════════════════════════════════════
\chapter{Conclusion and Recommendations}
\label{ch:conclusion}
% ════════════════════════════════════════════

\section{Summary}

AcmeKV successfully meets all ``Must'' and ``Should'' priority requirements established in Section~1.2. The system provides linearizable consistency with production-grade performance, achieving 285K reads/sec and 142K writes/sec with sub-5ms p99 read latency on lease-based reads. Jepsen testing confirms correctness under all tested failure scenarios.

\section{Recommendations}

Based on our evaluation, we recommend the following deployment plan:

\begin{enumerate}[itemsep=4pt]
  \item \textbf{Phase 1 (Q1 2025)}: Deploy AcmeKV for configuration management and distributed locking workloads, which are currently the largest sources of consistency-related incidents.
  \item \textbf{Phase 2 (Q2 2025)}: Migrate the metadata catalog service to AcmeKV after completing integration testing with the data platform team.
  \item \textbf{Phase 3 (Q3 2025)}: Evaluate AcmeKV for financial transaction workloads, pending completion of the compliance audit and penetration testing.
\end{enumerate}

\section{Known Limitations}

\begin{itemize}[itemsep=4pt]
  \item \textbf{Value size}: The 1MB value size limit may be insufficient for some use cases. We are investigating chunked storage for larger values.
  \item \textbf{Cross-DC replication}: Not yet implemented. The current system is limited to a single datacenter.
  \item \textbf{Range queries}: Scan performance degrades for ranges exceeding 10,000 keys due to LSM compaction overhead. We plan to implement a read cache to address this.
\end{itemize}

\end{document}
