Title

Effective Use Of Non-Blocking Data Structures In A Deduplication Application

Keywords

Concurrent data deduplication; Lock-free synchronization; Multiprocessor software design; Parallel data structures

Abstract

Efficient multicore programming demands fundamental data structures that support a high degree of concurrency. Existing research on non-blocking data structures promises to satisfy such demands by providing progress guarantees that allow a significant increase in parallelism while avoiding the safety hazards of lock-based synchronizations. It is well-acknowledged that the use of non-blocking containers can bring significant performance benefits to applications where the shared data experience heavy contention. However, the practical implications of integrating these data structures in real-world applications are not well-understood. In this paper, we study the effective use of non-blocking data structures in a data deduplication application which performs a large number of concurrent compression operations on a data stream using the pipeline parallel processing model. We present our experience of manually refactoring the application from using conventional lock-based synchronization mechanisms to using a wait-free hash map and a set of lock-free queues to boost the degree of concurrency of the application. Our experimental study explores the performance trade-offs of parallelization mechanisms that rely on a) traditional blocking techniques, b) fine-grained mutual exclusion, and c) lock-free and wait-free synchronization. Copyright © 2013 by the Association for Computing Machinery, Inc. (ACM).

Publication Date

1-1-2013

Publication Title

SPLASH 2013 - Proceedings of the 2013 Companion Publication for Conference on Systems, Programming, and Applications: Software for Humanity

Number of Pages

133-142

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/2508075.2508431

Socpus ID

84888177054 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84888177054

This document is currently not available here.

Share

COinS