cloud storage engineers

Abstract: MDS array codes achieve optimal storage efficiency in distributed storage systems, but their repair bandwidth depends critically on the sub-packetization level. While the theoretically optimal repair bandwidth (i.e., cut-set bound) of a high-rate exact-repair MDS array code is attainable with sufficiently large sub-packetization, the fundamental limits for fixed sub-packetization remain poorly understood. We study this problem for centralized linear exact repair of $h$ failures from $d$ helper nodes over a fixed finite field. We show that the rank profile of any linear repair scheme is constrained by two auxiliary mixed-alphabet codes. The first code is formed from the kernels of the helper projections and exists for all repair degrees; the second is formed from their row spaces and applies in the full-helper regime when $d\ge r$. These codes have complementary alphabet profiles, and their size and minimum-distance requirements are forced solely by the MDS property and repair correctness. This gives a unified route from classical coding-theoretic upper bounds to repair-bandwidth lower bounds. As a consequence, we obtain several explicit lower bounds via Singleton, Hamming, Plotkin, and Griesmer arguments, including known bounds as corollaries. We further formulate a Delsarte-type support-enumerator LP for mixed-alphabet codes and give an exact type-compressed implementation. For fixed sub-packetization \(\ell\), this yields a polynomial-time procedure for evaluating the resulting finite-parameter lower bound.

Abstract: Data encrypted today with classical public-key algorithms could be decrypted once large quantum computers exist. Cloud object stores keep data for years, so the client-side encryption that protects it must move to post-quantum algorithms such as ML-KEM, which adds a key-encapsulation step and a larger ciphertext to every stored object. So far, the cost of ML-KEM has been measured for the algorithm on its own and for securing network connections, but not for encrypting each object in a storage system that serves many clients at once. It has therefore been unclear whether ML-KEM slows such a system, under which conditions, and why. We address this problem by measuring per-object ML-KEM against classical key exchange on an S3-compatible object store, with two client implementations, two processor types and up to 500 concurrent workers, using pre-registered experiments and statistical equivalence tests. ML-KEM reduced throughput only when the client's processor was at or near full load, with one unexplained exception, and then by 4.0 to 4.9% in our main client. Controlled experiments on one processor type traced most of that loss to the way the software library was called, and a second, native client showed that the size of the loss depends on the implementation. The lasting cost is storage: 1,056 more bytes per object than with classical key exchange. The results cover two clients, one single-node store and one cloud provider.

Abstract: The problem of Private Information Retrieval (PIR) across graph-based replicated systems has seen a surge of interest in recent literature. In such systems, servers are modeled as the vertices of a graph, and each file is represented by an edge connecting the pair of servers that store it. While previous research on Graph-PIR (G-PIR) has focused mostly on perfect information-theoretic privacy, relaxing this constraint has the potential for significantly higher retrieval rates. In this work, we consider the setting of Graph-based Weak Private Information Retrieval (G-WPIR), under an $ε$-privacy metric. We adapt an existing G-WPIR scheme for arbitrary graphs to analyze its performance under the $ε$-privacy metric. Additionally, we establish a lower bound on the expected download cost for arbitrary graphs under the $ε$-privacy metric and derive from it an explicit rate upper bound for complete graphs. Finally, we show the achievable rate-privacy trade-offs for two specific graph classes---complete graphs and complete bipartite graphs.

Abstract: Data deduplication relies on content-defined chunking (CDC) algorithms to decide where data is split. We observe that most CDC algorithms are modular: a base chunking algorithm fixes the byte-level cut-point condition, while high-level techniques (size normalization, min/max thresholds, caching) layer on top. Existing benchmarks conflate the two, obscuring which design choices actually drive performance. We isolate and evaluate eight state-of-the-art base chunking algorithms across four realistic workloads and four metrics: throughput, deduplication ratio, mean chunk size, and chunk-size variance. Further, we derive new formulas relating algorithm parameters to expected chunk size for AE, RAM, and MII. In doing so, we uncover a longstanding error in the widely-used AE parameterization reproduced across multiple papers and evaluation tools that produces chunks 13-39% smaller than intended and inflates AE's reported deduplication. Across our evaluation, AE is the most balanced base chunking algorithm across all four metrics, RAM's similarity to AE does not carry over to low-entropy data, and MII and PCI show limited advantages over simpler alternatives in storage-oriented workloads. We release all implementations, datasets, and analysis scripts as open source.

Abstract: SSD-resident approximate nearest-neighbor search is essential when vector collections exceed DRAM capacity. The challenge is to reduce SSD reads and hide I/O latency through concurrent reads and overlap with computation. However, for graph-based search, progressive candidate discovery limits advance I/O planning while IVF search reads inverted lists in full, incurring unnecessary SSD reads. In this paper, we present RaBitQ-SSD, an extension of IVF-RaBitQ for SSD-resident vector search. Specifically, we propose Split-RaBitQ, which retains a configurable prefix of each binary code in DRAM, allowing in-memory code storage below one bit per dimension. Using this partial representation, it provides an unbiased distance estimator with a probabilistic error bound. Once the in-memory coarse quantizer identifies candidate lists, this bound supports pruning individual candidates within them, enabling finer-grained SSD access. We also design an asynchronous search pipeline that coordinates candidate pruning with SSD read scheduling to reduce unnecessary reads while overlapping I/O with computation. On datasets ranging from $5$ million to $1$ billion vectors, RaBitQ-SSD delivers up to $1.74\times$ the throughput of graph-based baselines at $90\%$ recall, while reducing SSD page reads by up to $3.8\times$. Its on-SSD indexes are up to $7.0\times$ smaller and $10.0\times$ faster to build than DiskANN. We also build and search an index of $10$ billion vectors on a single machine with one SSD, achieving over $3{,}000$ queries per second at $90\%$ recall.