Synchronously logging updates to persistent storage first and then asynchronously committing these updates to their rightful storage locations is a well-known and heavily used technique to improve the sustained throughput of write-intensive disk-based data processing systems, whose latency and throughput accordingly are largely determined by the latency and throughput of the underlying logging mechanism. The conventional wisdom is that logging operations are relatively straightforward to optimize because the associated disk access pattern is largely sequential. However, it turns out that to achieve both high throughput and low latency for fine-grained logging operations, whose payload size is smaller than a disk sector, is extremely challenging. This paper describes the experiences and lessons we have gained from building a disk logging system that can successfully deliver over 1.2 million 256-byte logging operations per second, with the average logging latency below 1 msec.

Very large block-level data backup systems need scalable data deduplication and garbage collection techniques to make efficient use of the storage space and to minimize the performance overhead of doing so. Although the deduplication and garbage collection logic is conceptually straight-forward, their implementations pose a significant technical challenge because only a small portion of their associated data structures could fit into memory. In this paper, we describe the design, implementation and evaluation of a data deduplication and garbage collection engine called Sungem that is designed to remove duplicate blocks in incremental data backup streams. Sungem features three novel techniques to maximize the deduplication throughput without compromising the deduplication ratio. First, Sungem puts related fingerprint sequences, rather than fingerprints from the same backup stream, into the same container in order to increase the fingerprint prefetching efficiency. Second, to make the most of the memory space reserved for storing fingerprints, Sungem varies the sampling rates for fingerprint sequences based on their stability. Third, Sungem combines reference count and expiration time in a unique way to arrive at the first known incremental garbage collection algorithm whose bookkeeping overhead is proportional to the size of a disk volume's incremental backup snapshot rather than its full backup snapshot. We evaluated the Sungem prototype using a real-world data backup trace, and showed that the average throughput of Sungem is more than 200,000 fingerprint lookups per second on a standard X86 server, including the garbage collection cost.

Traditional storage systems provide a simple read/write interface, which is inadequate for low-locality update-intensive workloads because it limits the disk scheduling flexibility and results in inefficient use of buffer memory and raw disk bandwidth. This paper describes an update-aware disk access interface that allows applications to explicitly specify disk update requests and associate with such requests call-back functions that will be invoked when the requested disk blocks are brought into memory. Because call-back functions offer a continuation mechanism after retrieval of requested blocks, storage systems supporting this interface are given more flexibility in scheduling pending disk update requests. In particular, this interface enables a simple but effective technique called Batching mOdifications with Sequential Commit (BOSC), which greatly improves the sustained throughput of a storage system under low-locality update-intensive workloads. In addition, together with a space-efficient low-latency disk logging technique, BOSC is able to deliver the same durability guarantee as synchronous disk updates. Empirical measurements show that the random update throughput of a BOSC-based B+ tree is more than an order of magnitude higher than that of the same B+ tree implementation on a traditional storage system.

This paper proposes efficient indexing and querying services on encrypted user documents stored in the cloud. We develop few sophisticated techniques to ensure that any network intruder or even the cloud service provider itself is oblivious to both user data content and the type of operations performed over the data. All data operations, including encryption and decryption of data are performed in the client environment, thereby guaranteeing complete data security. By providing, such a secure system to store and access data on the cloud, end users will be free of any security concerns and hence can easily migrate their data to the cloud. We have implemented an Encryption Domain Text Retrieval (EDTR) System that has a server positioned in the cloud to provide indexing, storage and querying services and a client tool on the end user system that processes the user documents. In order to enable the cloud server to work on encrypted data, the client tool orchestrates the user data into sets of keywords which are again encrypted. We further provide an unique measurement technique to identify unfaithful execution of user requested services by the cloud service provider. Our experiments demonstrate the practical applicability of such a sophisticated system. Though we logically explain the security implications and how the EDTR system overcomes typical cloud security issues, we do not focus on providing concrete, theoretical security proofs.

A block-level continuous data protection (CDP) system logs every disk update to a network storage server it protects, so as to support more flexible recovery time objective (RTO) and recovery point objective (RPO). To provide efficient access to historical snapshots, block-level CDP systems maintain multiple index structures, each of which needs to be updated whenever a disk block update operation is logged. Because these index structures are too large to be held in memory, updating their on-disk versions in real time becomes a major performance bottleneck that prevents existing CDP systems from scaling to large data backup applications. This paper describes the design and implementation of a high-performance index update mechanism that logs index updates, batches them in memory, and commits them using mostly sequential disk I/O. Sequential commit greatly reduces the cost of bringing in and writing back each on-disk index page. Update batching further amortizes this cost over multiple index update operations. Empirical performance measurements demonstrate that the proposed technique improves the index update throughput by more than an order of magnitude and reduces the performance overhead associated with index updates from 95% to under 15%.