Contribution evaluation is essential for incentivizing high-quality data sharing in federated learning (FL), yet existing Shapley-value-based methods are prohibitively expensive and overlook temporal influence propagation. In this paper, we propose Ripple Shapley, a novel attribution framework that enables accurate, real-time data valuation within a single federated training run. Our method decomposes each sample’s impact into an instantaneous drop term and a recursive ripple term, the latter capturing downstream influence via a Jacobian chain over global updates. To scale computation, we introduce a low-rank approximation of the Jacobian product and construct a shared subspace for efficient ripple accumulation. Extensive experiments on CIFAR-10 and MNIST show that Ripple Shapley achieves up to 62× speedup over existing Shapley-based FL methods while maintaining high attribution fidelity, significantly improving efficiency, robustness, and fairness in federated environments. We further demonstrate its effectiveness in dynamic federated learning scenarios and its potential for real-time data pricing.

With the rapid growth of data, redundancy among different users in cloud environments has become increasingly prominent. Detecting and removing these redundant parts can effectively improve storage efficiency. But these processes may dramatically degrade the system performance, especially when dealing with similar data. Although deduplication and delta compression are common data reduction techniques, their high overhead can outweigh the benefits. As a result, users often cannot determine in advance whether compression is worthwhile for their datasets. Some approaches have attempted to solve this, but each has important limitations. Danny Harnik et al. proposed a sampling-based deduplication estimation method using linear programming, which efficiently estimates redundancy from exact duplicates. However, it fails to capture redundancy arising from similar data, thus underestimating the full compression potential. To address this limitation, we propose Smart-to-Compress, a predictive compression decision framework. We introduce the Super Feature Frequency Histogram (SFH) to capture redundancy among similar data. Combined with the Duplication Frequency Histogram (DFH), our method estimates the overall Data Reduction Ratio (DRR) without scanning the entire dataset. Furthermore, we design a game-theoretic decision model to weigh compression benefits against predicted costs, providing users with guidance on whether compression should be applied. Experiments on real-world datasets show that our method accurately predicts compression value, reduces unnecessary overhead, and offers reliable decision-making support for users.

Detecting similar data is crucial for optimizing file storage and transmission in HTTP protocols and Content Delivery Networks. Traditional MinHash methods encounter significant efficiency challenges due to their reliance on K-shingle structures, resulting in high computational costs and storage requirements. Additionally, these methods expose privacy risks in cloud environments, where sensitive information can be inferred from MinHash signatures. To address both efficiency and security concerns, we propose Horse-MinHash, which integrates a fast, content-defined feature extraction scheme with a non-interactive zero-knowledge proof-based similarity estimation method. Our approach significantly enhances computational efficiency while ensuring robust privacy protection by preventing plaintext exposure. Experimental results demonstrate that Horse-MinHash achieves lower mean squared error in Jaccard similarity estimation and reduces time overhead for average block sizes of 16 KB or more, outperforming state-of-the-art methods.

Recently, Oblivious Storage has been proposed to prevent privacy leakage from user access patterns, which obfuscates and makes it computationally indistinguishable from the random sequences by fake accesses and probabilistic encryption. The same data exhibits distinct ciphertexts. Thus, it seriously impedes cloud providers’ efforts to improve storage utilization to remove user redundancy, which has been widely used in the existing cloud storage scenario. Inspired by the successful adoption of removing duplicate data in cloud storage, we attempt to integrate obliviousness, remove redundancy, and propose a practical oblivious storage, PEO-Store. Instead of fake accesses, introducing delegates breaks the mapping link between a valid access pattern and a specific client. The cloud interacts only with randomly authorized delegates. This design leverages non-interactive zero-knowledge-based redundancy detection, discrete logarithm problem-based key sharing, and secure time-based delivery proof. These components collectively protect access pattern privacy, accurately eliminate redundancy, and prove the data delivery among delegates and the cloud. Theoretical proof demonstrates that, in our design, the probability of identifying the valid access pattern with a specific client is negligible. Experimental results show that PEO-Store outperforms state-of-the-art methods, achieving an average throughput of up to 3 times faster and saving 74% of storage space.

With the prevalence of cloud storage, people prefer to outsource their data to the cloud for flexibility and reliability. Undoubtedly, there are lots of redundancy among these data. However, high-end storage with deduplication costs heavy computation and increases the data management complexity. Potential customers need the redundancy proportion information of their outsourced data to decide whether high-end storage with deduplication is worthwhile. Thus, many researchers have previously attempted to predict the redundant ratio. However, existing mechanisms ignore the redundancy proportion among similar chunks containing many duplicate data. Although resemblance detection, detecting the duplicate parts among similar data, has become a hot issue, it is hardly applied to the conventional deduplication ratio estimation because of unacceptable calculation cost. Therefore, we analyze the limitations and challenges of deduplication ratio prediction in prediction scope and response time and further propose a novel prediction scheme. By leveraging the context-aware resemblance detection, and confidence interval theory, our method can achieve faster estimation speed with higher accuracy in deduplication ratio compared with the state-of-the-art work. Finally, the results show that our method can efficiently and effectively estimate the proportion of duplicate chunks and redundant data among similar chunks by conducting experiments on real workloads.

In this paper, we propose a novel chunk-context-aware resemblance detection al-gorithm called CARD. By introducing machine learning into deduplication, the chunk feature will embed the chunk-context information after the N-sub-chunk shingles based initial feature extraction and BP-Neural network training. In the predicting process, each chunk's initial feature corresponds to a chunk-context feature. Finally, the cloud calculates the different part among resemblance chunks based on these feature by delta encoding. Only the different part is stored. The basic workflow corresponds to Figure 1. For more detailed illustrations, please see our full paper here

Recently, cloud storage has been widely used in our daily life. And there are lots of redundancy among these outsourced data. Conventional deduplication technology efficiently splits these data at the chunk level and removes the duplicate chunks to save the network bandwidth and improve the cloud storage utility. But it ignores the redundancy among similar chunks. Resemblance detection has recently become a hot issue with detecting these redundant parts among similar data. CARD, the state-of-the-art work, can efficiently and effectively remove these redundancies by introducing the neural network with resemblance detection. However, the source domain of the CARD model may have an explicitly different input distribution. The cloud cannot deal with the possible future domain data based on CARD design. This cross-domain setting may serials degrades the performance of CARD. To overcome this problem, we propose a cross-domain resemblance detection scheme called MetaContext. Integrating the chunk-context aware model and the learn-to-learn idea can produce a more robust chunk feature than CARD. As a byproduct, it also outperforms the CARD in speed. Finally, we implement the MetaContext and conduct serial experiments on real workloads. The results show that our method can efficiently and effectively detect and remove the redundancy among similar data.

Multilevel cell (MLC) NAND flash memory uses the voltages of the memory cells to represent bits, but high voltages cause much more damage on the cells than low voltages. Free space in MLC can be leveraged to reduce the usage of the high voltages and thus extend the lifetime of MLC. However, limited by the conventional data representation rule that represents bits by the voltage of one single cell, the high voltages are used in a high probability. To fully explore the potential of the free space on reducing the usage of high voltages without changing the total density of MLC, we propose a novel data representation aware of damage, named DREAM. DREAM uses the low voltage combinations of multiple cells instead of the voltage of one single cell to represent bits. It enables to represent the same bits through flexibly replacing the high voltages in some cells with the low voltages in other cells when free space is available. Hence, high voltages which cause more damage are less used and the lifetime of the MLC memory is extended. In addition, complementary techniques are proposed to mitigate performance loss induced by DREAM. Theoretical analysis and simulation results demonstrate the effectiveness and efficiency of DREAM.

With the growing popularity of cloud storage, how to prevent information leakage from cloud access patterns attracts great attention. Oblivious RAM is proposed for this purpose. It is designed for the memory system, and most existing work focused on improving performance in the main memory. Recently, ORAM has been extended to the cloud environment, and it is called Oblivious Data Storage. TaoStore, the state-of-the-art oblivious data storage system, integrates the ORAM technology with synchronous I/O technology to reduce the mean response time. As we observed, there is a strong locality existing in user accesses. However, existing Oblivious Storage research did not consider this. In this article, we propose Loco-Store, an oblivious data storage. In Loco-Store, we design a novel stash controller scheme that can dynamically group relevant blocks during the oblivious I/O processes. We also propose a locality-based eviction algorithm to keep the security guarantee. The theoretical proof proves that our scheme keeps the security definition of ORAM. Finally, we implement a prototype and conduct extensive experiments on real-world datasets. The results show that Loco-Store can save the network bandwidth consumption up to 39.19 percent, and reduce the overall access time by 26.17 percent

With the prevalence of cloud storage, data deduplication has been a widely used technology by removing cross users’ duplicate data and saving network bandwidth. Nevertheless, traditional data deduplication hardly detects duplicate data among resemblance chunks. Currently, a resemblance data deduplication, called Finesse, has been proposed to detect and remove the duplicate data among similar chunks efficiently. However, we observe that the chunks following the similar chunk have a high chance of resembling data locality property, and vice versa. Processing these adjacent similar chunks in small average chunk size level increases the metadata, which deteriorates the deduplication system performance. Moreover, existing resemblance data deduplication schemes ignore the performance impact from metadata. Therefore, we propose a fast variable-grained resemblance data deduplication for cloud storage. It dynamically combines the adjacent resemblance chunks or unique chunks or breaks those chunks, located at the transition region between resemblance chunks and unique chunks. Finally, we implement a prototype and conduct a serial of experiments on real-world datasets. The results show that our method dramatically reduces the metadata size while achieving the high deduplication ratio.

In recent years, the heterogeneous distributed platform integrating with FPGAs to accelerate computation tasks has been widely studied to deal with the deluge of data. However, most of current works suffer from poor universality and low resource utilization that run specific algorithms with the highly customized structure. Moreover, there are still many challenges, such as data curation, task scheduling, and resource management, which further limit the scalability of a CPU-FPGA distributed platform. In this paper, we present HeteroYARN, an FPGA-accelerated heterogeneous architecture based on YARN platform, which provides resource management and programming support for computing-intensive applications using FPGAs. In particular, the HeteroYARN abstracts FPGA accelerators as general resources and provides programming APIs to utilize those accelerators easily. Our HeteroYARN simplifies the request and usage of FPGA resources to enhance the efficiency of the heterogeneous framework while maintaining previous workflow unchanged. Experimental results using two representative algorithms, K-means and Naive Bayes classifier, which are accelerated by FPGAs, demonstrate the usability of the HeteroYARN framework and show performance speedup improvement by 7.5x (K-means) and 2.3x (Naive Bayes) respectively compared to conventional CPU-only applications provided by Mahout.

Traditional DRAM-based memory systems are facing two major scalability issues. First, the memory wall problem becomes a major performance bottleneck. Second, conventional memory systems consume increasing power as the capacity increases, which could be as much as 40% of the total system power. These issues hinder the scaling of DRAM-based memory systems. Fortunately, emerging memory technologies, such as high bandwidth memory (HBM) and phase change memory (PCM), have the potential to solve these scalability issues. However, there is no single memory technology that can overcome these issues together. Therefore, a hybrid memory system could be a promising way to build a high-performance, large-capacity, and energy-efficient memory system. To achieve this goal, we propose a cost-effective and energy-efficient architecture for HBM/PCM memory systems, called Dual Role HBM (DR-HBM). In DR-HBM, the HBM plays two roles and is divided into two parts. A small portion of which, called HBM cache, is used as a cache for the PCM. The remaining HBM is used as a part of main memory. Furthermore, the HBM cache is also used to track page hotness without additional hardware support. Hot pages will be migrated to HBM when they are evicted from the HBM cache. The experimental results show DR-HBM outperforms two state-of-the-art hybrid memory systems, CAMEO [1] and RaPP [2]. Compared to the baseline in which both HBM and PCM are architected as a part of main memory without page migration, DR-HBM improves the performance by 63% on average.

Pushing NAND flash memory to higher density, manufacturers are aggressively enlarging the flash page size. However, the sizes of I/O requests in a wide range of scenarios do not grow accordingly. Since a page is the unit of flash read/write operations, traditional flash translation layers (FTLs) maintain the page mapping regularity. Hence, small random write requests become common, leading to extensive partial logical page writes. This write inefficiency significantly degrades the performance and increases the write amplification of flash storage. In this paper, we first propose a configurable mapping layer, called minipage, whose size is set to match I/O request sizes. The minipage-level mapping provides better flexibility in handling small writes at the cost of sequential read performance degradation and a larger mapping table. Then, we propose a new FTL, called PM-FTL, that exploits the minipage-level mapping to improve write efficiency and utilizes the page-level mapping to reduce the costs caused by the minipage-level mapping. Finally, trace-driven simulation results show that compared to traditional FTLs, PM-FTL reduces the write amplification and flash storage response time by an average of 33.4% and 19.1%, up to 57.7% and 34%, respectively, under 16KB flash pages and 4KB minipages.

Summary As social networks such as micro‐blogging sites rapidly grow, deciding whom to follow (followee recommendation) becomes a significantly important problem. Most existing works exclusively rely on two traditional factors: the proximity between two users in the network topology or the similarity of the user‐generated contents in the social network, disregarding the effect of users' following behaviors. The challenge of how to effectively combine these two factors remains largely open. Moreover, most research studies simply sort the scores to find top‐k users, which is time‐consuming, especially for large‐scale networks. In this paper, we propose the idea that “predict users' following behaviors by following behaviors themselves.” We consider a user's following to others as a normal process of dynamic and coherent behavior, and we model the potential propagation of the users' following behaviors. Furthermore, based on our previous research on top‐k selection problem, we propose an effective top‐k followee recommendation algorithm, called FRFB. FRFB has low complexity and high scalability and, moreover, good adaptability to real‐life dynamic social networks. We conduct extensive experiments, with two real social network data sets (Wiki and Twitter), which show that FRFB outperforms the well‐known topology‐based followee recommendation algorithms.

Data chunking is one of the most important issues in a deduplication system, which not only determines the effectiveness of deduplication such as deduplication ratio, but also impacts the modification overhead. It breaks the file into chunks to find out the redundancy by fingerprint comparisons. The content-defined chunking algorithms such as TTTD, BSW CDC, and RC, can resist the boundary shift problem caused by small modifications. However, we observe that there exist a lot of consecutive maximum chunk sequences in various benchmarks. These consecutive maximum chunk sequences will lead to local boundary shift problem when facing small modifications. Based on this observation, we propose a new chunking algorithm, Elastic Chunking. By leveraging dynamic adjustment policy, elastic chunk can quickly find the boundary to remove the consecutive maximum chunk sequences. To evaluate the performance, we implement a prototype and conduct extensive experiments based on synthetic and realistic datasets. Compared with TTTD, BSW CDC and RC algorithms, proposed chunking algorithm can achieve the higher deduplication ratio and throughput.

Die-stacked DRAM (a.k.a., on-chip DRAM) provides much higher bandwidth and lower latency than off-chip DRAM. It is a promising technology to break the "memory wall". Die-stacked DRAM can be used either as a cache (i.e., DRAM cache) or as a part of memory (PoM). A DRAM cache design would suffer from more page faults than a PoM design as the DRAM cache cannot contribute towards capacity of main memory. At the same time, obtaining high performance requires PoM systems to swap requested data to the die-stacked DRAM. Existing PoM designs fall into two categories – line-based and page-based. The former ensures low off-chip bandwidth utilization but suffers from a low hit ratio of on-chip memory due to limited temporal locality. In contrast, page-based designs achieve a high hit ratio of on-chip memory albeit at the cost of moving large amounts of data between on-chip and off-chip memories, leading to increased off-chip bandwidth utilization and significant system performance degradation.To achieve a similar high hit ratio of on-chip memory as page-based designs, and eliminate excessive off-chip traffic involved, we propose SELF, a high performance and bandwidth efficient approach. The key idea is to SElectively swap Lines in a requested page that are likely to be accessed according to page Footprint, instead of blindly swapping an entire page. In doing so, SELF allows incoming requests to be serviced from the on-chip memory as much as possible, while avoiding swapping unused lines to reduce memory bandwidth consumption. We evaluate a memory system which consists of 4GB on-chip DRAM and 12GB off-chip DRAM. Compared to a baseline system that has the same total capacity of 16GB off-chip DRAM, SELF improves the performance in terms of instructions per cycle by 26.9%, and reduces the energy consumption per memory access by 47.9% on average. In contrast, state-of-the-art line-based and page-based PoM designs can only improve the performance by 9.5% and 9.9%, respectively, against the same baseline system.

The adoption of small geometries and multi-level cell (MLC) technologies significantly expands the capacity and drops the price of flash memory, which, at the same time, noticeably degrades the performance and reliability of the devices. As incremental-step pulse programming (ISPP) scheme is used to increase the programming accuracy for MLC cells, there is a trade-off between the SSD write performance and raw storage reliability. What's more, ECC is widely used in SSDs to provide error-tolerance ability. Therefore, if we could use stronger ECC to increase error correction strength, a low-cost write with coarser step sizes could be applied in the ISPP scheme to promote the write performance. However, stronger ECC scheme may hurt the read performance due to the increased decoding complexity and latency. In this paper, we propose a workload-aware differentiated ECC scheme to improve the SSD write performance without sacrificing the read performance. The main idea is to dynamically classify the logical pages into three categories: write-only, readonly, and overlapped part. For write-only logical pages, low-cost write with strong ECC scheme will be applied to increase the write performance. For write logical pages in the overlapped part, the low-cost writes with strong ECC will be selectively used based on their relative write and read hotness. While for any read logical pages encoded with a stronger ECC, we will rewrite them with the normal-cost write and ECC scheme if their hotness exceed a pre-defined threshold. The evaluation results show that our workload-aware differentiated ECC scheme could reduce the write and read response times by 48% and 11% on average, respectively. Even compared with the latest previous work, our workload-aware design can still gain about 4% write performance and 11% read performance improvements.

Generally, cache is a bridge between CPU and main memory in order to narrow the gap of performance. As a throughput-oriented device, Graphics Processing Unit(GPU) has already integrated with cache, which is similar to CPU cores in order to exploit the locality of memory accesses. However, the applications in GPGPU computing exhibit distinct memory access patterns compared to the multi-core counterparts. Normally, the cache, in GPU cores, suffers from threads contention and resources over-utilization and few detailed works excavate the root of this phenomenon. It is significant for us to have a profound understanding of these behaviors. In this work, we adequately analyze the memory accesses from twenty benchmarks based on reuse distance theory and quantify their patterns. As a metric, the reuse distance can be employed to evaluate the cache performance and predict the access behaviors. We calculate the reuse distance for each memory access and plot them into different distributions according to the cache configuration. Through the analysis, we discover that most benchmarks either access cache in a streaming manner or reuse previous cache line in a short reuse distance. Streaming accesses barely benefit from cache since they have no data reuse. For the accesses with a short reuse distance, they can exploit the data locality in current cache design. Additionally, we discuss the optimization suggestions for all benchmarks which could improve their cache performance.

Summary Singular value decomposition (SVD) shows strong vitality in the area of information analysis and has significant application value in most of the scientific big data fields. However, with the rapid development of Internet, the information online reveals fast growing trend. For a large‐scale matrix, applying SVD computation directly is both time consuming and memory demanding. There are many works available to speed up the computation of SVD based on the message passing interface model. However, to deal with large‐scale data processing, a MapReduce model has many advantages over a message passing interface model, such as fault tolerance, load balancing and simplicity. For a MapReduce environment, existing approaches only focus on low rank SVD approximation and tall‐and‐skinny matrix SVD computation, and there are no implementations of full rank SVD computation. In this paper, we propose a MapReduce‐based implementation for solving divide‐and‐conquer SVD algorithm. To achieve high performance, we design a two‐stage task scheduling strategy based on the mathematical characteristics of divide‐and‐conquer SVD algorithm. To further strengthen the performance, we propose a row‐index‐based divide algorithm, a pipelined task scheduling method, and revised block matrix multiplication in MapReduce framework. Experimental result shows the efficiency of our algorithm. Our implementation can accommodate full rank SVD computation of large‐scale matrix very efficiently. Copyright © 2014 John Wiley & Sons, Ltd.

Flash-based SSDs are widely used as storage caches, which can benefit from both the higher performance of SSDs and lower price of disks. Unfortunately, issues of reliability and lifetime limit the use of flash-based cache. One way to solve this problem is to use the flash memory as read cache and use other devices like nonvolatile memory for write buffering. In this paper, we propose a new flash-aware read cache design, which leverages out-of-place update property of SSDs to improve both cache hit ratio and lifetime. Due to the out-of-place update property, when a cache entry is evicted from the flash cache, the eviction only removes the metadata, while the real data is still accessible and resides in the physical flash page until the whole flash block being erased. The main idea of our flash-aware cache is to reuse these evicted but still available data, when a request for the previously evicted data page arrives, instead of accessing underlying storage to fetch the data and rewriting it into fash cache, our design just needs to revive the evicted data. To evaluate the benefits of flash-aware cache design, we implemented the normal LRU, normal ARC, flash-aware LRU (FLRU), and flashaware ARC (FARC) cache algorithms on the Disksim simulator with SSD extension. Our simulation results demonstrate that our flashaware cache can improve the cache hit ratio by up to 28 percent, reduce the average response time by up to 40 percent with higher performance stability, and alleviate the lifetime limitation of flash cache by reducing the erase count by up to more than 70 percent. Besides of the flash-aware design, we also propose a new zero-migration garbage collection scheme to further extend the lifetime of flash cache. Our experiments show that the combination of our flash-aware cache design and the zero-migration garbage collection scheme reduces the erase count by up to nearly 90 percent.

General-Purpose Graphic Processing Units (GPGPU) have been widely used in high performance computing as application accelerators due to their massive parallelism and high throughput. A GPGPU generally contains two layers of schedulers, a cooperative-thread-array (CTA) scheduler and a warp scheduler, which administer the thread level parallelism (TLP). Previous research shows the maximized TLP does not always deliver the optimal performance. Unfortunately, existing warp scheduling schemes do not optimize TLP at runtime, which is impossible to fit various access patterns for diverse applications. Dynamic TLP optimization in the warp scheduler remains a challenge to exploit the GPGPU highly-parallel compute power.

Flash-based SSDs are widely used as storage caches, which can benefit from both the higher performance of SSDs and lower price of disks. Unfortunately, issues of reliability and limited lifetime limit the use of Flash-based cache. One way to solve this problem is to use the flash memory as read cache and use other devices like nonvolatile memory for write buffering. In this paper, we propose a new flash-aware read cache architecture, which leverages out-of-place update property of flash memory to improve both cache hit ratio and lifetime. Due to the out-of-place update property, when a cache entry is evicted from the flash cache, the eviction only removes the metadata, while the real data is still accessible and resides in the physical flash page until the whole flash block being erased. The main idea of our flash-aware cache is to reuse these evicted but still available data, when a request for the previously evicted data arrives, instead of accessing underlying storage to fetch the data and rewriting it into flash cache, we just need to revive the evicted data. To evaluate the benefits of flash-aware cache design, we implemented the normal LRU and flash-aware LRU (FLRU) cache algorithms on the Disksim simulator with an SSD extension. Our simulation results demonstrate that our flash-aware cache can improve the cache hit ratio by up to 28% and alleviate the lifetime limitation of flash cache by reducing the erase count by up to 70%.

Since NAND flash cannot be updated in place, SSDs must perform all writes in pre-erased pages. Consequently, pages containing superseded data must be invalidated and garbage collected. This garbage collection adds significant cost in terms of the extra writes necessary to relocate valid pages from erasure candidates to clean blocks, causing the well-known write amplification problem. SSDs reserve a certain amount of flash space which is invisible to users, called over-provisioning space, to alleviate the write amplification problem. However, NAND blocks can support only a limited number of program/erase cycles. As blocks are retired due to exceeding the limit, the reduced size of the over-provisioning pool leads to degraded SSD performance.

Phase change memory (PCM) is a promising technology to solve energy and performance bottlenecks for memory and storage systems. To help understand the reliability characteristics of PCM devices, we present a simple fault model to categorize four types of PCM errors. Based on our proposed fault model, we conduct extensive experiments on real PCM devices at the memory module level. Numerical results uncover many interesting trends in terms of the lifetime of PCM devices and error behaviors. Specifically, PCM lifetime for the memory chips we tested is greater than 14 million cycles, which is much longer than for flash memory devices. In addition, the distributions for four types of errors are quite different. These results can be used for estimating PCM lifetime and for measuring the fabrication quality of individual PCM memory chips.

Large-scale search engines use hard disk drives (HDD) to store the mass index data for their capacity, whose performances are limited by the relatively low I/O performance of HDD. Caching is an effective optimization, and many caching algorithms have been proposed to improve retrieval performance. Considering the high cost of memory and huge amounts of data, the limited capacity of cache in memory cannot resolve the above problem thoroughly. In this paper, we adopt a solid state disk (SSD) based storage architecture, which uses SSD as a secondary cache for memory. We analyze the I/O patterns of search engines and propose SSD-based data management policies based on the hybrid storage architecture, including data selection, data placement and data replacement. Our main goal is to improve the performance of search engines while reducing operation cost inside SSD. The experimental results demonstrate the proposed architecture improves the hit ratio by 13.31%, the performance by 41.05%, the average access time inside SSD by 43.83%, and reduces block erasure operations by 71.52%.

Recent advances in flash memory show great potential to replace traditional hard drives (HDDs) with flash-based solid state drives (SSDs) from personal computing to distributed systems. However, it is still a long way to go before completely using SSDs for enterprise data storage. Considering the cost, performance, and reliability of SSDs, a practical solution is to combine both SSDs and HDDs together. This paper proposes a hybrid storage system named PASS (Performance-dAta Synchronization - hybrid storage System) to tradeoff between I/O performance and data discrepancy between SSDs and HDDs. PASS includes a high-performance SSD and a traditional HDD to store mirrored data for reliability. All of the I/O requests are redirected to the primary SSD first and then the updated data blocks are copied to the backup HDD asynchronously. In order to hide the latency of copying operations, we use an I/O window to coalesce write requests and maintain an ordered I/O queue to shorten the HDD seek and rotation times. Depending on the charateristics of different I/O workloads, we develop an adaptive policy to dynamically balance the foreground I/O processing and background mirroring. We implement a prototype system of PASS by developing a Linux device driver and conduct experiments on the IoMeter, PostMark, and TPCC benchmarks. Our results show that PASS can achieve up to 12 times the performance of a RAID1 storage system for the IoMeter and PostMark workloads while tolerating less than 2% data discrepancy between the primary SSD and the backup HDD. More interestingly, while PASS does not produce any performance benefit for the TPC-C benchmark, it does allow the system to scale to larger sizes than when using an HDD-based RAID system alone.

Given an N-point sequence, finding its k largest components in the frequency domain is a problem of great interest. This problem, which is usually referred to as a sparse Fourier Transform, was recently brought back on stage by a newly proposed algorithm called the sFFT. In this paper, we present a parallel implementation of sFFT on both multi-core CPUs and GPUs using a human voice signal as a case study. Using this example, an estimate of k for the 3dB cutoff points was conducted through concrete experiments. In addition, three optimization strategies are presented in this paper. We demonstrate that the multi-core-based sFFT achieves speedups of up to three times a single-threaded sFFT while a GPU-based version achieves up to ten times speedup. For large scale cases, the GPU-based sFFT also shows its considerable advantages, which is about 40 times speedup compared to the latest out-of-card FFT implementations [2].

Today, P2P system is one of the largest Internet bandwidth consumers. In order to relieve the burden on Internet backbone and improve the user access experience, efficient caching strategies should be applied. However, due to its autonomous nature, a fully distributed caching scheme is very difficult to design and implement. Most current P2P caching approaches are using Client/Server architecture by deploying dedicated proxy servers on the edge of networks. Such architecture is expensive. It also incurs single point of failure and hot spot problems. Furthermore, it violates P2P principle and failed to utilize vast available resources on individual peers. In this paper, we investigate the techniques for efficient distributed P2P caching. We propose novel placement and replacement algorithms to make caching decisions. For each object, an adequate number of copies are generated and disseminated on topologically distant locations. Combined with the underlying hierarchical query infrastructure, our strategies relieve the over-caching problems for popular objects, and provide more cache space for other objects. This resolution greatly reduces WAN traffic for P2P applications. We conduct simulation experiments to compare our approaches with several common caching strategies. The results show that our algorithms can achieve higher cache hit rates and superior load balance property.

Data deduplication has recently become commonplace in most secondary storage and even in some primary storage for the capacity optimization purpose. Aside from its write performance, read performance of the deduplication storage has been gaining in significance with a wide range of its deployments. In this paper, we emphasize the importance of read performance in reconstituting a data stream from its unique and shared chunks physically dispersed over deduplication storage. We newly introduce a read performance indicator called Chunk Fragmentation Level (CFL). We also validate that the CFL is very effective to indicate read performance of deduplication storage through a developed theoretical performance model and extensive experiments. Finally, we articulate further research issues.

Existing garbage collection algorithms for the flash-based storage use score-based heuristics to select victim blocks for reclaiming free space and wear leveling. The score for a block is estimated using metadata information such as age, block utilization, and erase count. To quickly find a victim block, these algorithms maintain a priority queue in the SRAM of the storage controller. This priority queue takes O(K) space, where K stands for flash storage capacity in total number of blocks. As the flash capacity scales to larger size, K also scales to larger value. However, due to higher price per byte, SRAM will not scale proportionately. In this case, due to SRAM scarcity, it will be challenging to implement a larger priority queue in the limited SRAM of a large-capacity flash storage. In addition to space issue, with any update in the metadata information, the priority queue needs to be continuously updated, which takes O(lg(K)) operations. This computation overhead also increases with the increase of flash capacity. In this paper, we have taken a novel approach to solve the garbage collection metadata management problem of a large-capacity flash storage. We propose a sampling-based approach to approximate existing garbage collection algorithms in the limited SRAM space. Since these algorithms are heuristic-based, our sampling-based algorithm will perform as good as unsampled (original) algorithm, if we choose good samples to make garbage collection decisions. We propose a very simple policy to choose samples. Our experimental results show that small number of samples are good enough to emulate existing garbage collection algorithms.

Network coding has been demonstrated to be able to improve the performance of P2P content distribution. However, it is vulnerable to pollution attacks, leading to substantial performance degradation. Moreover, existing corruption detection schemes for network coding are not applied well to P2P systems. More efficient scheme based on attacker identification is required to thwart such attacks. In this paper, we propose an integrated system solution for secure P2P content distribution based on network coding, referred to as ISNC. In ISNC, we first design our system architecture based on extended uniform bipartite networks that can achieve high throughput with network coding. Based on the architecture, we present a secure network coding signature scheme and an identity-based malicious peer identification scheme. The two schemes can cooperate to thwart pollution attacks effectively in P2P network, not only detecting corrupted blocks, but also identifying all the malicious peers. Simulation results show that ISNC can effectively limit the pollution spread and identify malicious peers quickly, even when they collude to launch attacks. Compared with existing related schemes, ISNC is especially applicable for P2P content distribution, and can achieve both high security and overall efficiency.

This paper presents a comprehensive study on implementations and performance evaluations of two snapshot techniques: copy-on-write snapshot and redirect-on-write snapshot. We develop a simple Markov process model to analyze data block behavior and its impact on application performance, while the snapshot operation is underway at the block-level storage. We have implemented the two snapshots techniques on both Windows and Linux operating systems. Based on our analytical model and our implementation, we carry out quantitative performance evaluations and comparisons of the two snapshot techniques using IoMeter, PostMark, TPC-C, and TPC-W benchmarks. Our measurements reveal many interesting observations regarding the performance characteristics of the two snapshot techniques. Depending on the applications and different I/O workloads, the two snapshot techniques perform quite differently. In general, copy-on-write performs well on read-intensive applications, while redirect-on-write performs well on writeintensive applications.

Abstract — This paper presents a study of data storages for continuous data protection (CDP). After analyzing the existing data protection technologies, we propose a new disk array architecture that provides Timely Recovery to Any Point-in-time, referred to as TRAP-Array. TRAP-Array stores not only the data stripe upon a write to the array, but also the time-stamped Exclusive-ORs of successive writes to each data block. By leveraging the Exclusive-OR operations that are performed upon each block write in today’s RAID4/5 controllers, TRAP does not incur noticeable performance overhead. More importantly, TRAP is able to recover data very quickly to any point-in-time upon data damage by tracing back the sequence and history of Exclusive-ORs resulting from writes. What is interesting is that TRAP architecture is very space-efficient. We have implemented a prototype TRAP architecture using software at block level and carried out extensive performance measurements using TPC-C benchmarks running on Oracle and Postgress databases, TPC-W running on MySQL database, and file system benchmarks running on Linux and Windows systems. Our experiments demonstrated that TRAP is not only able to recover data to any pointin-time very quickly upon a failure but it is also space efficient. Compared to the state-of-the-art continuous data protection technologies, TRAP saves disk storage space by one to two orders of magnitude with a simple and a fast encoding algorithm. In addition, TRAP can provide two-way data recovery with the availability of only one reference image in contrast to the one-way recovery of snapshot and incremental backup technologies.

This paper presents a theoretical and experimental study on the limitations of copy-on-write snapshots and incremental backups in terms of data recoverability. We provide mathematical proofs of our new findings as well as implementation experiments to show how data recovery is done in case of various failures. Based on our study, we propose a new system architecture that will overcome the problems of existing technologies. The new architecture can provide two-way data recovery capability with the same storage overheads and can be implemented fairly easily on existing systems. We show that the new architecture has maximum data recoverability and is practically feasible.

Distributed storage systems employ replicas or erasure code to ensure high reliability and availability of data. Such replicas create great amount of network traffic that negatively impacts storage performance, particularly for distributed storage systems that are geographically dispersed over a wide area network (WAN). This paper presents a performance study of our new data replication methodology that minimizes network traffic for data replications. The idea is to replicate the parity of a data block upon each write operation instead of the data block itself. The data block will be recomputed back at the replica storage site upon receiving the parity. We name the new methodology PRINS (Parity Replication in IP-Network Storages). PRINS trades off highspeed computation for communication that is costly and more likely to be the performance bottleneck for distributed storages. By leveraging the parity computation that exists in common storage systems (RAID), our PRINS does not introduce additional overhead but dramatically reduces network traffic. We have implemented PRINS using iSCSI protocol over a TCP/IP network interconnecting a cluster of PCs as storage nodes. We carried out performance measurements on Oracle database, Postgres database, MySQL database, and Ext2 file system using TPC-C, TPC-W, and Micro benchmarks. Performance measurements show up to 2 orders of magnitudes bandwidth savings of PRINS compared to traditional replicas. A queueing network model is developed to further study network performance for large networks. It is shown that PRINS reduces response time of the distributed storage systems dramatically.

RAID architectures have been used for more than two decades to recover data upon disk failures. Disk failure is just one of the many causes of damaged data. Data can be damaged by virus attacks, user errors, defective software/firmware, hardware faults, and site failures. The risk of these types of data damage is far greater than disk failure with today's mature disk technology and networked information services. It has therefore become increasingly important for today's disk array to be able to recover data to any point in time when such a failure occurs. This paper presents a new disk array architecture that provides timely recovery to any point-in-time, referred to as TRAP-array. TRAP-array stores not only the data stripe upon a write to the array, but also the time-stamped exclusive-ORs of successive writes to each data block. By leveraging the exclusive-OR operations that are performed upon each block write in today's RAID4/5 controllers, TRAP does not incur noticeable performance overhead. More importantly, TRAP is able to recover data very quickly to any point-in-time upon data damage by tracing back the sequence and history of exclusive-ORs resulting from writes. What is interesting is that TRAP architecture is amazingly space-efficient. We have implemented a prototype TRAP architecture using software at block device level and carried out extensive performance measurements using TPC-C benchmark running on Oracle and Postgress databases, TPC-W running on MySQL database, and file system benchmarks running on Linux and Windows systems. Our experiments demonstrated that TRAP is not only able to recover data to any point-in-time very quickly upon a failure but it also uses less storage space than traditional daily differential backup/snapshot. Compared to the state-of-the-art continuous data protection technologies, TRAP saves disk storage space by one to two orders of magnitude with a simple and a fast encoding algorithm. From an architecture point of view, TRAP-array opens up another dimension for storage arrays. It is orthogonal and complementary to RAID in the sense that RAID protects data in the dimension along an array of physical disks while TRAP protects data in the dimension along the time sequence