The development of data analytics services has fueled many optimizations in data scans, and indexes are one of the most important techniques to improve scan efficiency. Meanwhile, block-based data organization has become standard practice in these services, providing an opportunity for more fine-grained index selection at the block level. However, today’s systems ignore data distribution differences among blocks and usually tune indexes over the entire database table, leading to unnecessary storage costs and potential degradation in query performance. To bridge this gap, we propose BISLearner, a fast, block-aware index selecting approach based on reinforcement learning. One major challenge lies in differentiating the data distribution among data blocks. To solve this problem, BISLearner maintains simplified histograms that represent the data distribution of each block. When a query is issued, BISLearner leverages the query predicate and histogram-based block summaries to generate a specific workload representation for each block. However, such block-aware workload representation leads to an excessive number of input features, resulting in a slow or even incorrect convergence of neural networks. Inspired by the human-learning process, where more attention is devoted to the important parts of data, we design an attention-based neural model to efficiently handle the high volume of input features caused by table partitioning and select the best-suited index combinations at the block level. Additionally, to handle the expensive search space caused by attribute combinations and data partitioning, we employ heuristic-based invalid action masking at the block level to accelerate the training process. Our evaluation using PostgreSQL and Greenplum database systems demonstrates BISLearner is able to reduce job completion time by up to 28.45% compared to its best counterparts.

Cloud Block Storage (CBS) relies on Cloud Virtual Disks (CVDs) to provide block interfaces to Cloud Virtual Machines. The process of allocating user-subscribed CVDs to physical storage warehouses in cloud data centers, known as CVD placement, significantly impacts resource utilization, load balancing, and I/O performance. However, previous works have failed to account for temporal fluctuations in cloud loads, resulting in imbalanced loads, low resource utilization, and frequent warehouse overloads.

Cloud Block Storage (CBS) systems underpin modern cloud infrastructures by decoupling storage from computation and enabling resource pooling for elasticity and cost efficiency. However, CBS faces two persistent challenges: load imbalance across storage nodes and network & storage amplification caused by redundancy mechanisms. While recent hybrid-redundancy block storage (HRBS) architectures combine replication caches with EC layers to reduce amplification, their static cache admission policies fail to adapt to dynamic cluster conditions, especially during node failures, leading to severe load imbalance and degraded throughput.

While Miss Ratio Curve (MRC) profiling methods based on spatial sampling are effective in modeling cache behaviors, previous MRC studies lack in-depth analysis of profiling errors and primarily target homogeneous object-size scenarios. This has caused imbalanced errors of existing MRC approaches when employed in heterogeneous object-size caches. For instance, in CDN traces, the error of the Byte Miss Ratio Curve (BMRC) could be two orders of magnitude larger than that of the Object Miss Ratio Curve (OMRC).

In modern cloud block storage systems, the routing layer bears the task of slicing and distributing application requests to the underlying storage engine and thus becomes the critical path. However, skewed application traffic leads to load imbalance among routing servers, causing severe performance bottlenecks and hurting the quality of service. Existing load balancing methods typically employ static allocation strategies without considering the access pattern of individual virtual disks. They are not well suited to deal with the highly dynamic loads in production. In this paper, we first collect and analyze 7-day workload traces of 130k virtual disks from a commercial cloud block storage system. Based on several observations, we propose VDMig, an adaptive virtual disk migration scheme. VDMig initially divides virtual disks into two types of access patterns, then uses application-level semantics to characterize the load of virtual disks, and finally implements predictive migrating strategies adaptively to achieve dynamic load balancing. Extensive experiments demonstrate that VDMig can achieve fine-grained virtual disk management, effectively balancing the load among routing servers. Compared to the static methods widely deployed in the industry, VDMig can reduce the imbalance by 82.38 % on average.

Cloud object storage systems provide massive data storage capabilities where data is stored in different storage clusters. Storing data according to access characteristics efficiently in different clusters is a challenging task. Methods considering past data access frequency bring the problem of low storage utilization and load imbalance. We propose a Cost-Aware Migration Scheme for cloud object storage systems(CAMS) based on object hotness and life cycle to improve the utilization of cloud object storage systems and reduce the Total Cost of Ownership(TCO). CAMS establishes an accurate object hotness standard, it uses object hotness and lifecycle prediction to guide data migration. CAMS was tested using real-world datasets from production cloud object storage system, the results show that CAMS strategies outperform Cold, CoinFlip and RejectX strategies with gains of up to 19.79% on the estimated TCO.

‘‘Learned” admission policies have shown promise in improving Content Delivery Network (CDN) cache performance and lowering operational costs. Unfortunately, existing learned policies are optimized with a few fixed cache sizes while in reality, cache sizes often vary over time in an unpredictable manner. As a result, existing solutions cannot provide consistent benefits in production settings. We present SLAP , a learned CDN cache admission approach based on segmented object reuse time prediction. SLAP predicts an object’s reuse time range using the Long-Short-Term-Memory model and admits objects that will be reused (before eviction) given the current cache size. SLAP decouples model training from cache size, allowing it to adapt to arbitrary sizes. The key to our solution is a novel segmented labeling scheme that makes SLAP without requiring precise prediction on object reuse time. To further make SLAP a practical and efficient solution, we propose aggressive reusing of computation and training on sampled traces to optimize model training, and a specialized predictor architecture that overlaps prediction computation with miss object fetching to optimize model inference. Our experiments using production CDN traces show that SLAP achieves significantly lower write traffic (38%-59%), longer SSDs lifetime (104%-178%), a consistently higher hit rate (3.2%-11.7%), and requires no effort to adapt to changing cache sizes, outperforming existing policies.

Content delivery networks (CDNs) caching systems usually use multi-tenant shared caching due to their operational simplicity. However, this approach often results in interference among applications. Dynamic cache allocation schemes based on miss ratio curve (MRC) could be a good choice except for its high computational overheads and performance fluctuations. In this paper, we propose a lightweight and adaptive cache allocation scheme for CDNs (LACA). Rather than searching near-optimal configurations for each tenant, LACA detects in real time whether any tenants are using cache space inefficiently (named abnormal tenants), and then adjusts space restricted within these abnormal tenants by constructing their local MRCs instead of the global ones. We have deployed LACA in Tencent's CDN system and LACA can reduce the miss ratio by 27.1 % and reduce the average user access latency by 28.5 ms. Compared with the-state-of-the-art schemes, LACA also achieves a higher-accuracy local MRC with marginal overhead.

Cloud block storage systems rely heavily on the cache server to guarantee system performance. Cache servers serve multi-tenants simultaneously, and the workload of each tenant changes at any time, together with its changed demand for the cache capacity. How to dynamically re-allocate the cache space for each tenant to achieve overall high performance is a crucial problem. The mainstream cache space allocations are usually based on miss ratio curve (MRC) construction. Although it can achieve on-demand allocation, it is not designed for optimal performance: it only considers the performance in a single period, but this does not mean that all periods can achieve optimization.In this paper, we propose a search framework for allocation schemes based on a policy tree, where a path from the root to a tree node corresponds to an allocation scheme from the initial period to that period. We aim to explore the tree nodes in the policy tree to find the optimal allocation scheme. To achieve this, we design an offline cache space allocation method using Monte Carlo Tree Search (Opt-CA) to approach the optimal algorithm, which provides better performance than the MRC method. Guided by Opt-CA, we implement an online Learned Monte Carlo Tree Search based cache allocation scheme (LMCTS-CA) which uses a learning-based model to estimate the hit ratio of each allocation scheme. The experiments with MSR traces show that LMCTS-CA enhances the hit ratio of the cache by 4.55% and reduces the total number of misses by 16.60% compared to the MRC method.

"Learned" admission policies have shown promise in improving Content Delivery Network (CDN) cache performance and lowering operational costs. Unfortunately, existing learned policies are optimized with a few fixed cache sizes while in reality, cache sizes often vary over time in an unpredictable manner. As a result, existing solutions cannot provide consistent benefits in production settings.We present SLAP, a learned CDN cache admission approach based on segmented object reuse time prediction. SLAP predicts an object’s reuse time range using the Long-Short-Term-Memory model and admits objects that will be reused (before eviction) given the current cache size. SLAP separates model training from cache size, allowing it to adapt to arbitrary sizes. The key to our solution is a novel segmented labeling scheme that enables SLAP to precisely predict object reuse time. To further make SLAP a practical and efficient solution, we propose aggressive reusing of computation and training on sampled traces to optimize model training, and a specialized predictor architecture that overlaps prediction computation with miss object fetching to optimize model inference. Our experiments with production CDN traces show that SLAP achieves significantly lower write traffic (38%-59%), longer SSDs service life (104%-178%), a consistently higher hit rate (3.2%-11.7%), and requires no effort to adapt to changing cache sizes, outperforming existing policies.

Abstract Better duplicate elimination performance causes higher fragmentation which leads to degraded restore performance. As a result, restore performance needs to be optimized either through strengthening locality by selective rewriting and/or making the best use of the limited available memory through cache optimization. In this paper, we explore SACRO, SSD Assitsted Chunk Caching for Restore Optimization. It avoids the need to repetitively access chunk containers in disk by using SSD (Solid State Drives) as a secondary chunk cache. An FRT (Future Reference Table) is constructed from the recipe of a backup stream and a Future Reference Count entry in the FRT is utilized to assign priorities to chunks as they are accessed during restoration. These priority values coupled with access distances are used to decide to cache a chunk either in memory or the SSD. The restore performance of SACRO is shown to significantly outperform other restoring approaches which utilize chunk caching. For one dataset, at 4 MB cache size and 4 MB Look Ahead Window size its restore factor is 3.5 MB/container_access while ALACC and LRU record 3.4 MB/container_access and 0.9 MB/container_access respectively. Moreover, SACRO can be integrated to already existing deduplication systems with very limited amount of modification done on the deduplication system.

Modern data analytics services are coupled with external data storage services, making I/O from remote cloud storage one of the dominant costs for query processing. Techniques such as columnar block-based data organization and compression have become standard practices for these services to save storage and processing cost. However, the problem of effectively skipping irrelevant blocks at low overhead is still open. Existing data-skipping efforts maintain lightweight summaries (e.g., min/max, histograms) for each block to filter irrelevant data. However, such techniques ignore patterns in real-world data, enabling ineffective use of the storage budget and may cause serious false positives. This paper presents Sieve, a learning-enhanced index designed to efficiently filter out irrelevant blocks by capturing data patterns. Specifically, Sieve utilizes piece-wise linear functions to capture block distribution trends over the key space. Based on the captured trends, Sieve trades off storage consumption and false positives by grouping neighboring keys with similar block distributions into a single region. We have evaluated Sieve using Presto, and experiments on real-world datasets demonstrate that Sieve achieves up to 80% reduction in blocks accessed and 42% reduction in query times compared to its counterparts.

Hardware prefetching is an important DRAM latency hiding technology. Designing prefetchers to maximize system performance often requires a delicate balance between coverage and accuracy. As the number of cores increases, the accuracy of the prefetching algorithm becomes more important. Separating streams based on memory access instructions is an effective way to improve accuracy. However, this technique may lose prefetch opportunities by losing cross-PC relationships, and even reduce algorithm coverage.

File storage system (FSS) uses multi-caches to accelerate data accesses. Unfortunately, efficient FSS cache allocation remains extremely difficult. First, as the key of cache allocation, existing miss ratio curve (MRC) constructions are limited to LRU. Second, existing techniques are suitable for same-layer caches but not for hierarchical ones.

Modern data analytics platforms are often coupled with external data storage services such as Amazon S3, resulting in storage bottlenecks. Existing caching and prefetching solutions use higher-level information from data analytics frameworks, such as job dependency graphs(e.g., DAGs) and historical run time information, to predict future data accesses and then prefetch data into the cache and manage the cache contents based on those predictions.However, in doing so, they are not taking advantage of a fundamental opportunity: rather than caching data given a prediction of job execution, we can actually influence the job execution order to enable more effective caching and prefetching. With this key insight, we devise a set of novel heuristics and then design a system Tripod, which harmonizes job scheduling and data caching for analytics frameworks. With the higher-level information from analytics frameworks, Tripod explores a best-suited job execution order for prefetching and caching guided by the devised heuristics.We have implemented Tripod as extensions to Apache YARN and Tez. Our evaluation using standard analytic benchmarks (TPC-H and TPC-DS) shows that Tripod achieves up to 1.7x speedup over state-of-the-art approaches.

Cloud disk provided to users by cloud providers has been a prevalent form of cloud storage. Assigning disk storage space for cloud disks among available data warehouses remains a challenging task, as the load characteristics of cloud disks are not known at the time of disk creation. Methods considering only subscribed capacity could be prone to result in resource under-utilization and load imbalance among warehouses. We propose a Smart Cloud Disk Allocation (S-CDA) approach, which uses clustering and classifying to predict the load information for new cloud disks, and then realizes multi-dimensional allocation based on Manhattan distance. Experimental results with realistic cloud workloads show that, compared with the existing one-dimensional allocation scheme, S-CDA increases the overall space/IOPS/disk bandwidth utilization, while decreasing the load imbalance.

Nowadays, SSD cache plays an important role in cloud storage systems. The associated write policy, which enforces an admission control policy regarding filling data into the cache, has a significant impact on the performance of the cache system and the amount of write traffic to SSD caches. Based on our analysis on a typical cloud block storage system, approximately 47.09% writes are write-only, i.e., writes to the blocks which have not been read during a certain time window. Naively writing the write-only data to the SSD cache unnecessarily introduces a large number of harmful writes to the SSD cache without any contribution to cache performance. On the other hand, it is a challenging task to identify and filter out those write-only data in a real-time manner, especially in a cloud environment running changing and diverse workloads.In this paper, to alleviate the above cache problem, we propose an ML-WP, Machine Learning Based Write Policy, which reduces write traffic to SSDs by avoiding writing write-only data. The main challenge in this approach is to identify write-only data in a real-time manner. To realize ML-WP and achieve accurate write-only data identification, we use machine learning methods to classify data into two groups (i.e., write-only and normal data). Based on this classification, the write-only data is directly written to backend storage without being cached. Experimental results show that, compared with the industry widely deployed write-back policy, ML-WP decreases write traffic to SSD cache by 41.52%, while improving the hit ratio by 2.61% and reducing the average read latency by 37.52%.

The SSD has been playing a significantly important role in caching systems due to its high performance-to-cost ratio. Since the cache space is typically much smaller than that of the backend storage by one order of magnitude or even more, write density (defined as writes per unit time and space) of the SSD cache is therefore much more intensive than that of HDD storage, which brings about tremendous challenges to the SSD’s lifetime. Meanwhile, under social network workloads, quite a lot writes to the SSD cache are unnecessary. For example, our study on Tencent’s photo caching shows that about 61% of total photos are accessed only once, whereas they are still swapped in and out of the cache. Therefore, if we can predict these kinds of photos proactively and prevent them from entering the cache, we can eliminate unnecessary SSD cache writes and improve cache space utilization. To cope with the challenge, we put forward a “one-time-access criteria” that is applied to the cache space and further propose a “one-time-access-exclusion” policy. Based on these two techniques, we design a prediction-based classifier to facilitate the policy. Unlike the state-of-the-art history-based predictions, our prediction is non-history oriented, which is challenging to achieve good prediction accuracy. To address this issue, we integrate a decision tree into the classifier, extract social-related information as classifying features, and apply cost-sensitive learning to improve classification precision. Due to these techniques, we attain a prediction accuracy greater than 80%. Experimental results show that the one-time-access-exclusion approach results in outstanding cache performance in most aspects. Take LRU, for instance: applying our approach improves the hit rate by 4.4%, decreases the cache writes by 56.8%, and cuts the average access latency by 5.5%.

Solid State Drives (SSDs) are popularly used for caching in large scale cloud storage systems nowadays. Traditionally, most cache algorithms make replacement upon each miss when cache space is full. However, we observe that in a typical Cloud Block Storage (CBS) system, there is a great percentage of blocks with large reuse distances, which would result in large number of blocks being evicted out of the cache before they ever have a chance to be referenced while they are cached, significantly jeopardizing the cache efficiency. In this article, we propose LEA, Lazy Eviction cache Algorithm, for cloud block storage to efficiently remedy the cache inefficiencies caused by cache blocks with large reuse distances. LEA mainly employs two lists, Lazy Eviction List (LEL) and Block Identity List (BIL), which keep track of two types of victim blocks respectively based on their cache duration when replacements occur, to improve cache efficiency. When a cache miss happens, if the victim block has not resided in cache for longer than its reuse distance, LEA inserts the missed block identity into BIL. Otherwise, it inserts the missed block entry into LEL. We have evaluated LEA by using IO traces collected from Tencent, one of the largest network service providers in the world, and several open source traces. Experimental results show that LEA not only outperforms most of the state-of-the-art cache algorithms in hit ratio, but also greatly reduces the number of SSD writes.

Photo service providers are facing critical challenges of dealing with the huge amount of photo storage, typically in a magnitude of billions of photos, while ensuring national-wide or world-wide satisfactory user experiences. Distributed photo caching architecture is widely deployed to meet high performance expectations, where efficient still mysterious caching policies play essential roles. In this work, we present a comprehensive study on internet-scale photo caching algorithms in the case of QQPhoto from Tencent Inc., the largest social network service company in China. We unveil that even advanced cache algorithms can only perform at a similar level as simple baseline algorithms and there still exists a large performance gap between these cache algorithms and the theoretically optimal algorithm due to the complicated access behaviors in such a large multi-tenant environment. We then expound the reasons behind this phenomenon via extensively investigating the characteristics of QQPhoto workloads. Finally, in order to realistically further improve QQPhoto cache efficiency, we propose to incorporate a prefetcher in the cache stack based on the observed immediacy feature that is unique to the QQPhoto workload. The prefetcher proactively prefetches selected photos into cache before they are requested for the first time to eliminate compulsory misses and promote hit ratios. Our extensive evaluation results show that with appropriate prefetching we improve the cache hit ratio by up to 7.4 percent, while reducing the average access latency by 6.9 percent at a marginal cost of 4.14 percent backend network traffic compared to the original system that performs no prefetching.

Solid State Drives (SSDs) are popularly used for caching in large scale cloud storage systems nowadays. Traditionally, most cache algorithms make replacement at each miss when cache space is full. However, we observe that in a typical Cloud Block Storage (CBS), there is a great percentage of blocks with large reuse distances, which would result in large number of blocks being evicted out of the cache before they ever have a chance to be referenced while they are cached, significantly jeopardizing the cache efficiency. In this paper, we propose LEA, Lazy Eviction cache Algorithm, for cloud block storage to efficiently remedy the cache inefficiencies caused by cache blocks with large reuse distances. Specifically, LEA uses two lists, Lazy Eviction List (LEL) and Block Identity List (BIL). When a cache miss happens, if the candidate evicted-block has not resided in cache for longer than its reuse distance, LEA inserts the missed block identity into BIL. Otherwise, it inserts the missed block entry into LEL. We have evaluated LEA by using IO traces collected from Tencent, one of the largest network service providers in the world, and several open source traces. Experimental results show that LEA not only outperforms most of the state-of-the-art cache algorithms in hit ratio, but also reduces the number of SSD writes greatly.

Distributed deduplication overcomes, to some extent, index-lookup disk bottleneck problem by dividing deduplication tasks among many nodes. However, the task of selecting these nodes is an important challenge because it could result in high communication cost and the storage node island effect problem. Moreover, intelligent data routing is required to exploit the peculiar nature of data from different applications which share insignificant amount of content. In this paper, we explore CACH-Dedup, a content aware clustered and hierarchical deduplication system, which exploits the negligibly small amount of content shared among chunks from different file types to create groups of files and storage nodes with out loss of deduplication effectiveness. It uses hierarchical deduplication to reduce the size of fingerprint indexes at the global level, where only files and big sized segments are deduplicated. It also makes advantage of locality first using the big sized segments deduplicated at the global level and second by routing a set of consecutive files together to one storage node. Furthermore, it exploits similarity by making use of similarity bloom filters of streams for stateful routing which results in duplicate elimination rate in a par with single node deduplication with a minimal cost of computation and communication. CACH-Dedup is evaluated using a prototype deployed on windows server environment distributed over four separate machines. It is shown to have duplicate elimination effectiveness in a par with a single node deduplication system, with a minimal communication overhead and an acceptable deduplication throughput.

SSD has been playing a significantly important role in caching systems due to its high performance-to-cost ratio. Since cache space is much smaller than that of the backend storage by one order of magnitude or even more, write density (writes per unit time and space) of SSD cache is therefore much higher than that of HDD storage, which brings about great challenges to SSD's lifetime. Meanwhile, under social network workloads, quite a few writes on SSD are unnecessary, e.g., Tencent's photo caching shows that about 61% of total photos are just accessed once whereas they are still swapped in and out of the cache. Therefore, if we can predict this kind of photos proactively and prevent them from entering the cache, we can eliminate unnecessary SSD cache writes and improve cache space utilization.

Photo service providers are facing critical challenges of dealing with the huge amount of photo storage, typically in a magnitude of billions of photos, while ensuring national-wide or world-wide satisfactory user experiences. Distributed photo caching architecture is widely deployed to meet high performance expectations, where efficient still mysterious caching policies play essential roles. In this work, we present a comprehensive study on internet-scale photo caching algorithms in the case of QQPhoto from Tencent Inc., the largest social network service company in China. We unveil that even advanced cache algorithms can only perform at a similar level as simple baseline algorithms and there still exists a large performance gap between these cache algorithms and the theoretically optimal algorithm due to the complicated access behaviors in such a large multi-tenant environment. We then expound the behind reasons for that phenomenon via extensively investigating the characteristics of QQPhoto workloads. Finally, in order to realistically further improve QQPhoto cache efficiency, we propose to incorporate a prefetcher in the cache stack based on the observed immediacy feature that is unique to the QQPhoto workload. Evaluation results show that with appropriate prefetching we improve the cache hit ratio by up to 7.4%, while reducing the average access latency by 6.9% at a marginal cost of 4.14% backend network traffic compared to the original system that performs no prefetching.

Log-Structured Merge Trees (LSM) based key-value (KV) stores such as LevelDB and HyperLevelDB, use a compaction strategy which brings frequent compaction operations, to store key-value items in sorted order. However, large numbers of compactions impose a negative impact on write and read performance for random data-intensive workloads. To remedy this problem, this paper presents OHDB, an optimization of HyperLevelDB for random data-intensive workloads. OHDB implements two stand-alone techniques in the disk component of LSM structure to optimize the concurrent compactions. One is dividing KV items by prefix at the first level in the disk component, to reduce the frequency of overlapping in key range among data files, and thus reduces the amount of compactions. The other is separating the first level in the disk component from the rest levels, and organizing them in two disks individually, to increase parallelism of disk writes of compactions. We evaluate three OHDBs which are OHDB with each of the technique and OHDB with the combination of both respectively, using micro-benchmarks with random write- intensive and read-intensive workloads. Experimental results show that OHDB reduces the amount of compactions by a factor of up to 4x, and improves the write and read performance for random data-intensive workloads under various settings.

Many online social networks can be described by signed networks, where positive links signify friendships, trust and like; while negative links indicate enmity, distrust and dislike. Predicting the sign of the links in these networks has attracted a great deal of attentions in the areas of friendship recommendation and trust relationship prediction. Existing methods for sign prediction tend to rely on path-based features which are somehow limited to the sparsity problem of the network. In order to solve this issue, in this paper, we introduce a novel sign prediction model by exploiting cluster-based meta paths, which can take advantage of both local and global information of the input networks. First, cluster-based meta paths based features are constructed by incorporating the newly generated clusters through hierarchically clustering the input networks. Then, the logistic regression classifier is employed to train the model and predict the hidden signs of the links. Extensive experiments on Epinions and Slashdot datasets demonstrate the efficiency of our proposed method in terms of Accuracy and Coverage.

Data deduplication, a data redundancy elimination technique, has been employed in almost all kinds of application environments to reduce storage space. However, one of the main challenges facing deduplication technology is to provide a fast key-value fingerprint index for large datasets, as the index performance is critical to the overall deduplication performance. This paper proposes RMD, a resemblance and mergence based deduplication scheme, which aims to provide quick responses to fingerprint queries. The key idea of RMD is to leverage a bloom filter array and the data resemblance algorithm to dramatically reduce the query range for deduplication. Moreover, RMD utilizes mergence based approach to merge resemblance segments to relevant bins, and exploits frequency-based Fingerprint Retention Policy to reduce the bin capacity to improve query throughput and improve data deduplication ratio. Extensive experimental results with real-world datasets have shown that RMD is able to achieve pretty high query performance and outperforms several state-of-the-art deduplication schemes.

The chunk fragmentation problem inherently associated with deduplication systems significantly slows down the restore performance, as it causes the restore process to assemble chunks which are distributed in a large number of containers as a result of storage indirection. Existing solutions attempting to address the fragmentation problem either sacrifice deduplication efficiency or require additional memory resources. In this work, we propose a new restore cache scheme, which accelerates the restore process using the same amount of cache space as that of the traditional LRU restore cache. We leverage the recipe knowledge to recognize the containers which will soon be accessed for restoring a backup version and classify those containers into bursty containers which are differentiated from other regular containers. Bursty and regular containers are then put in two separate caches, respectively. Bursty containers, containing many chunks that will be needed for restore within a short period of time, are put in a smaller cache managed at the container granularity. On the contrary, regular containers are put in the other bigger cache managed at the chunk granularity, with chunks which will not be used dropped off at the time when the containers are brought in. In doing so, bursty containers have better chances to be quickly evicted from the restore cache, avoiding their unnecessarily occupying cache space for too long. Our evaluation results have demonstrated that our proposed cache scheme can improve restore speed factor by up to 3.05X and reduce the number of container reads by 67.3% on average, relative to a conventional LRU restore cache.

This paper presents a novel block I/O scheduler specifically for SSDs. The scheduler leverages the internal rich parallelism resulting from SSD's highly parallelized architecture. It speculatively divides the entire SSD space into different subregions and dispatches requests into those subregions in a round-robin fashion at the Linux kernel block layer. In the meanwhile, to reduce the severe read-write interference problem associated with SSDs, the scheduler only dispatches a batch of unidirectional requests to the disk driver for each subregion's scheduling opportunity. Furthermore, to take advantage of SSD'S better sequential performance over random patterns, the scheduler sorts the pending requests while they are awaiting in the dispatching queues as those HDD-oriented schedulers do. The experimental results with a variety of workloads have demonstrated that the new I/O scheduler not only improves the user-perceived performance, but also enhances the underlying SSD's lifetime via reducing the block erase operations during the running processes.

Flash-based SSDs are becoming increasingly popular in modern storage systems, especially in high-performance computing infrastructures. However, several inherent technical limitations still remain to prevent their widespread deployment. One of the critical concerns is their limited lifetime, which is directly relevant to the total writes experienced by SSDs. In this paper, we present a Content and semantics Aware File System (CSA-FS) which is able to reduce write traffic to SSDs. It employs deduplication and delta-encoding techniques to file system data blocks and semantic blocks, respectively. It is motivated by two important observations: (1) there exists a huge amount of content redundancy within primary storage systems, and (2) semantic blocks are visited much more frequently than data blocks, with each update bringing very minimal changes. By separately deduplicating redundant data blocks and delta-encoding similar semantic blocks, CSA-FS can significantly reduce the total write traffic to SSDs and greatly improve their lifetime correspondingly, at an acceptable cost of at most 7% performance degradation across a variety of workloads.

This study presents a comprehensive empirical investigation on the interplay between actively-deployed file systems and an SSD. We test and analyze the performance of four widely used Linux file systems, which are ext2, ext3, XFS and Reiserfs, on an SSD with a range of different workloads. It is primarily intended to serve two purposes. One is that considering its widespread adoption trend, we are realistically motivated to have first-hand numbers of the actual performance of the emerging storage technology, especially in the contexts of daily deployment scenarios. The other goal is that we attempt to disclose the internal details behind the SSD's thin interface from a high-level perspective, totally different than those previous studies, which are typically micro-testonly. As a result of this study, we obtain several interesting and useful findings: (1) Generally, different file systems perform disparately on the SSD due to their various design principles, sometimes even with up to one order of magnitude of performance discrepancy. (2) File system format/mount options and workload characteristics have significant impacts on performance. (3) SSD would deliver optimal performance if used in a friendly manner. (4) Workloads, file systems and SSD interact in an intrinsically complicated way and in order to have optimal synergistic performance anticipation, users should seriously consider all of the three factors together, when setting up their SSD-based storage systems.

Time-traveling ability, which enables storage state to be reverted to any previous timepoints, is a highly desirable functionality in modern storage systems to ensure storage continuity. Continuous Data Protection (CDP) is a typical time-traveling implementation mechanism. CDP can guard well against software bugs, unintentional errors, malicious attacks, all of which are often beyond the capabilities of traditional periodical backup schemes. Broadly speaking, CDP can be implemented in two different ways, i.e., either integrate it seamlessly to the target file systems or more generally make it sit at the device block level. However, the state-of-the-art CDP implementations suffer from various limitations, e.g., huge implementation complexity, non-trivial performance interference. In this study, we introduce BVSSD, a new block level versioning system specifically designed for the emerging flash-based SSD. BVSSD realizes CDP functionality through positively and usefully exploiting the inherent idiosyncrasies of flash, which is the well-known "no-overwritten" property. Specifically, BVSSD simply keeps track of the SSD FTL metadata changes, which essentially represent the dynamics of the SSD storage state, and restores them to past timepoints to perform recoveries. Compared with existing block-level CDP schemes, BVSSD is much more light-weight, less performance-interfering, easier to realize, and more importantly, it requires no intrusive modifications to the upper file systems and applications. Our trace-driven simulation results with a number of different realistic enterprise-scale workload traces have shown that BVSSD only incurs marginal performance overheads, somewhere between 3% and 8% performance degradation, while with minimum additional RAM requirement, which is an acceptable price for the high reliability that BVSSD can provide. Furthermore, given most of the typcial SSDs deployment scenarios and their ever-increasing capacity trend, BVSSD is realistically poised to be feasible to be deployed in actual situations.

Detecting duplicates over sliding windows is an important technique for monitoring and analysing data streams. Since recording the exact information of elements in a sliding window can be RAM-resource-intensive and introduce an unacceptable search complexity, several approximate membership representation schemes have been proposed to build in-memory fast indices. However, various challenges facing RAM utilization and scalability remain. This paper proposes a Detached Counting Bloom filter Array (DCBA) to flexibly and efficiently detect duplicates over sliding windows. A DCBA consists of an array of detached counting Bloom filters (DCBFs), where each DCBF is essentially a Bloom filter that is associated with a detached timer (counter) array. The DCBA scheme functions as a circular FIFO queue and keeps a filling DCBF for accommodating fresh elements and a decaying DCBF for evicting stale elements. DCBA allows the timer arrays belonging to fully filled DCBFs to be offloaded to disks to greatly improve the memory space efficiency. The fully filled DCBFs will remain stable until their elements become stale, which allows a DCBA to be efficiently replicated for the purpose of data reliability or information sharing. Further, DCBA can be cooperatively maintained by clustered nodes, which provides scalable solution for mining massive data streams. Mathematical analysis and experimental results show that a DCBA (containing 64 DCBFs) requires less than 10% of its components to be kept in RAM while maintaining more than 95% of its query performance, which significantly outperforms existing schemes in memory efficiency and scalability.

Online backup service software provides automated, offsite, secure online data backup and recovery for remote computers. How to satisfy functional requirements and guarantee the fault tolerance of online backup service software is a difficult but crucial problem faced by software designers. In this paper, we investigate to incorporate the fault tolerant techniques in the system design, and propose a fault-tolerant online backup service model (FOBSM) to guide the development of online backup service system. The FOBSM comprises four components: backup client (BC), backup server (BS), storage server (SS), and online backup exception handler (OBEH). The first three components constitute three-party functional units, whereas OBEH serves as the centralized exception handling mechanism, which is devised to receive the external exceptions raised by the other entities, transform them into a global exception, and propagate it to the related entities to handle, so as to improve the fault tolerance of the software greatly. In order to provide precise and explicit idioms to system designers, we use Object-Z language to specify the FOBSM. Following the Object-Z reasoning rules, we reason about the fault tolerant properties of FOBSM and demonstrate that it can improve fault tolerance of the online backup service software effectively.