We present sec-cs, a hash-table-like data structure for contents on untrusted storage that is provably secure and storage-efficient. We achieve authenticity and confidentiality with zero storage overhead using deterministic authenticated encryption. State-of-the-art data deduplication approaches prevent redundant storage of shared parts of different contents irrespective of whether relationships between contents are known a priori.,,,,Instead of just adapting existing approaches, we introduce novel (multi-level) chunking strategies, ML-SC and ML-CDC, which are significantly more storage-efficient than existing approaches in presence of high redundancy.,,,,We prove sec-cs's security, publish an implementation, and present evaluation results indicating suitability for, e.g., future backup systems that should preserve many versions of files on little available storage.
@cite_12: A horizontal circulating carbonizer comprising an annular horizontally rotatable circulating hearth disposed rotatably, a carbonizer body covering said hearth, a coal feeder equipped on the carbonizer body, a preheating zone disposed in the vicinity of said feed coal supply opening, a carbonizing zone connected to said preheating zone, a cooling zone connected to the carbonizing zone, and a discharger of cooled coke, and a process for the preparation of coke using this horizontal circulating carbonizer.
@cite_17: Explosion of data growth and duplication of data in enterprises has led to the deployment of a variety of deduplication technologies. However not all deduplication technologies serve the needs of every workload. Most prior research in deduplication concentrates on fixed block size (or variable block size at a fixed block boundary) deduplication which provides sub-optimal space efficiency in workloads where the duplicate data is not block aligned. Workloads also differ in the nature of operations and their priorities thereby affecting the choice of the right flavor of deduplication. Object workloads for instance, hold multiple versions of archived documents that have a high degree of duplicate data. They are also write-once read-many in nature and follow a whole object GET, PUT and DELETE model and would be better served by a deduplication strategy that takes care of nonblock aligned changes to data. In this paper, we describe and evaluate a hybrid of a variable length and block based deduplication that is hierarchical in nature. We are motivated by the following insights from real world data: (a) object workload applications do not do in-place modification of data and hence new versions of objects are written again as a whole (b) significant amount of data among different versions of the same object is shareable but the changes are usually not block aligned. While the second point is the basis for variable length technique, both the above insights motivate our hierarchical deduplication strategy. We show through experiments with production data-sets from enterprise environments that this provides up to twice the space savings compared to a fixed block deduplication.
This problem is solved by our proposals ML-SC ML-CDC: Due to a specific, multi-level application of SC CDC, we achieve logarithmic metadata costs, allowing high storage efficiency even for small chunk sizes, independent from content sizes. To the best of our knowledge, our strategy is unique. @cite_12 apply CDC recursively to enable efficient replication of files over a network (assuming the receiver has a similar file to the one being transferred), but they do not target storage systems and fail to achieve logarithmic costs due to a fixed recursion depth. Further, their approach is different to ours: Instead of breaking large chunks recursively into smaller ones, they generate the smallest chunks first and use CDC recursively to break lists of chunk references into smaller parts---requiring multiple passes. Yasa and Nagesh @cite_17 employ hierarchical chunking starting with CDC at the highest level as we do, but they use only two levels (SC at second level), so storage overhead is still linear.