HIODS: hybrid inline and offline deduplication system

Universidade do Minho Escola de Engenharia Departamento de Inform´ atica Carlos Pinto Pedrosa HIODS: Hybrid Inline and Offline Deduplication System March 2021 Universidade do Minho Escola de Engenharia Departamento de Inform´ atica Carlos Pinto Pedrosa HIODS: Hybrid Inline and Offline Deduplication System Master Dissertation Integrated Master in Informatics Engineering Dissertation Supervised By Jo˜ ao Tiago Medeiros Paulo Jos´ e Orlando Pereira March 2021 ABSTRACT Deduplication is a technique that allows finding and removing duplicate data at storage systems. With the current exponential growth of digital information, this mechanism is becoming more and more desirable for reducing the infrastructural costs of persisting such data. Therefore, deduplication is now being widely applied to several storage appliances serving applications with different requirements (e.g., archival, backup, primary storage). However, deduplication requires additional processing logic for each storage request in order to detect and eliminate duplicate content. Traditionally, this processing is done in the I/O critical path (inline), thus introducing a performance penalty on the throughput and latency of requests being served by the storage appliance. An alternative solution is to do this process as a background task, thus outside of the I/O critical path (offline), at the cost of requiring additional storage space as duplicate content is not found and eliminated immediately. However, the choice of what type of strategy to use is typically done manually and does not take into consideration changes in the applications' workloads. This dissertation proposes HIODS, a hybrid deduplication solution capable of automatically changing between inline and offline deduplication according to the requirements (e.g., desired storage I/O throughput goal) of applications and their dynamic workloads. The goal is to choose the best strategy that fulfills the targeted I/O performance objectives while optimizing deduplication space savings. Finally, a prototype of HIODS is implemented and evaluated extensively with different storage workloads. Results show that HIODS is able to change its deduplication mode dynamically, according to the storage workload being served, while balancing I/O performance and space savings requirements efficiently. keywords: deduplication, storage, inline, offline, hybrid i RESUMO A deduplica c¸˜ ao ´ e um t ´ ecnica que permite encontrar e remover dados duplicados guardados nos sistemas de armazenamento. Com o crescimento exponencial da informa c¸˜ ao digital que vivemos atualmente, este mecanismo est ´ a a tornar-se cada vez mais popular para reduzir os custos das infraestruturas onde esses dados se encontram alojados. De facto, a deduplica c¸˜ ao ´ e, hoje em dia, usada numa grande variedade de servi c¸ os de armazenamento que servem diferentes aplica c¸ ˜ oes com requisitos particulares (ex.: arquivo, backup, armazenamento prim´ ario). No entanto, a deduplica c¸˜ ao adiciona uma camada de processamento extra a cada pedido de armazenamento, de modo a conseguir detetar e eliminar o conte ´ udo redundante. Tradicionalmente, este processo ´ e realizado durante o caminho cr ´ ıtico do I/O (inline), causando perdas de desempenho e aumentos na lat ˆ encia dos pedidos processados. Uma alternativa ´ e alterar o processamento para segundo plano, aliviando assim os custos no caminho cr ´ ıtico do I/O (offline). Esta solu c¸˜ ao requer espa c¸ o de armazenamento adicional, visto que os duplicados n ˜ ao s ˜ ao encontrados nem eliminados imediatamente. No entanto, a estrat ´ egia a seguir ´ e escolhida de forma manual, n ˜ ao tendo em considera c¸˜ ao qualquer poss ´ ıvel mudan c¸ a na carga de trabalho das aplicac¸˜ oes. Esta disserta c¸˜ ao prop ˜ oe assim o HIODS, um sistema de deduplica c¸˜ ao h ´ ıbrido capaz de alterar entre o modo inline eoffline de forma autom ´ atica considerando os requisitos (ex.: d ´ ebito do sistema de armazenamento desejado) das aplica c¸ ˜ oes e das suas cargas de trabalho dinˆ amicas. Por fim, um prot ´ otipo do HIODS ´ e implementado e avaliado exaustivamente. Os resultados mostram que o HIODS ´ e capaz de alterar o modo de deduplica c¸˜ ao de forma din ˆ amica e de acordo com a carga de trabalho, considerando os requisitos de desempenho e a elimina c¸˜ ao eficiente dos dados duplicados. palavras-chave: deduplicac¸ ˜ ao, armazenamento, inline, offline, h´ ıbrido ii AGRADECIMENTOS Todo o trabalho desenvolvido durante esta disserta c¸˜ ao n ˜ ao seria poss ´ ıvel sem o apoio de algumas pessoas fundamentais. Assim sendo, gostaria de tirar um momento para expressar o meu mais sincero obrigado para com essas mesmas pessoas. Ao meu orientador, Doutor Jo ˜ ao Tiago Medeiros Paulo, um especial agradecimento por todo o apoio, motiva c¸˜ ao, assist ˆ encia e disponibilidade demonstrada durante todo o processo. Tamb ´ em ao meu co-orientador, Professor Jos ´ e Orlando Pereira, por todo o aux ´ ılio prestado, principalmente nas decis˜ oes mais complexas. Aos meus colegas do Grupo de Sistemas Distribu ´ ıdos do HASLab pelo bom ambiente de trabalho proporcionado e tamb´ em pela assistˆ encia prestada. Por fim, agrade c¸ o aos meus amigos e fam ´ ılia por todo o apoio e motiva c¸˜ ao, n ˜ ao s ´ o durante a realizac¸˜ ao desta dissertac¸˜ ao, mas sim durante todo o meu percurso acad´ emico. iii DIREITOS DE AUTOR E CONDIC¸ ˜ OES DE UTILIZAC¸ ˜ A O D O TRABALHO POR TERCEIROS Este ´ e um trabalho acad ´ emico que pode ser utilizado por terceiros desde que respeitadas as regras e boas pr ´ aticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licen c¸ a abaixo indicada. Caso o utilizador necessite de permiss ˜ ao para poder fazer um uso do trabalho em condi c¸ ˜ oes n ˜ ao previstas no licenciamento indicado, dever ´ a contactar o autor, atrav ´ es do Reposit´ oriUM da Universidade do Minho. iv STATEMENT OF INTEGRITY I hereby declare having conducted this academic work with integrity. I confirm that I have not used plagiarism or any form of undue use of information or falsification of results along the process leading to its elaboration. I further declare that I have fully acknowledged the Code of Ethical Conduct of the University of Minho. v CONTENTS 1 introduction 1 1.1Problem 3 1.2Goals and Contributions 3 1.3Dissertation Structure 4 2 background and state of the art 5 2.1Deduplication 5 2.1.1Basic Architecture 5 2.1.2Deduplication Criteria 7 2.1.3Primary Storage vs Secondary Storage 10 2.2Related Work 11 2.2.1DIODE 11 2.2.2D312 2.2.3HPDedup 13 2.2.4Hybrid Deduplication System 13 2.2.5Discussion 14 3 architecture 16 3.1General Overview 16 3.2Deduplication Workflow - Inline Mode 18 3.3Deduplication Workflow - Offline Mode 20 3.4Deduplication Workflow - Background Processing 21 3.5Deduplication Controller 22 4 prototype 24 4.1SPDK 24 4.2Implementation Details 25 4.3Deduplication Controller 26 4.3.1Feedback Loop Controller 27 5 experimental evaluation 29 5.1Testing Methodology 29 5.2Preliminary Experiments 30 5.2.1Results Analysis 30 5.3Micro Experiments 32 5.3.1Results Analysis 33 5.4Macro Experiments 45 vi contents vii 5.4.1Mountain/Valley 45 5.4.2Stairs 48 5.5Discussion 50 6 conclusion 51 6.1Future Work 52 1.1. Problem 3 concurrently content at the storage medium, thus requiring control access mechanisms to ensure storage consistency and preventing data corruption. 1.1 problem In a general fashion, each deduplication system implements the mode that best fits the requirements of applications being served. This process is done statically and manually and, even for applications whose performance requirements may change over time, it is not possible to change the deduplication settings. Therefore, applications that suddenly contemplate high loads of storage requests and use inline deduplication will experience significant degradation in I/O operations throughput and/or latency. On the other hand, applications working at lower I/O rates, in which inline deduplication could have a minimal impact on I/O performance, may not benefit from additional storage space savings if configured with an offline scheme. However, having a hybrid design that can alternate across both types of deduplication while being aware of workload changes is not a trivial task. Namely, the solution ' s design must be adapted to integrate both schemes seamlessly, and the applications workloads must be monitored to understand what scheme should be applied at each time. Additionally, choosing what scheme to use should be done automatically, thus avoiding users or system administrators from making this decision manually. 1.2 goals and contributions Building on section 1.1, this dissertation has as its primary goal the design of an hybrid deduplication system. The proposed solution must be able to dynamically switch between inline and offline deduplication to best fit different application workloads. For example, if an application requires 1000 I/O operations per second and such an objective is not delivered by inline deduplication, the operation mode should automatically be changed to offline, thus reducing the overhead in the critical I/O path and increasing the overall performance. To achieve the proposed goal, this dissertation ' s first contribution is HIODS, an Hybrid Inline and Offline Deduplication System. HIODS automatically and dynamically ensures that the best deduplication strategy is being applied in order to: i) guarantee the I/O performance goals of different applications; and ii) optimize deduplication space savings. In more detail, inline deduplication is chosen as the preferred method if the targeted I/O performance objective is being guaranteed, thus also maximizing deduplication space savings. When the I/O workload cannot be supported efficiently by inline deduplication, then HIODS changes the scheme to an offline approach, thus promoting storage performance over space savings. Moreover, HIODS is able to throttle the requests of the offline deduplication engine 1.3. Dissertation Structure 4 in cases where concurrent accesses to the storage backend, and the corresponding access control mechanisms, might be affecting the I/O performance of applications. Again, this decision promotes better performance for applications at the cost of extra storage space. As a second contribution, a prototype of HIODS is implemented using SPDK [ 8 ]. SPDK is a framework that provides a wide range of tools and libraries to write high-performance, highly scalable, and user-space storage applications. Finally, the prototype is extensively evaluated and validated with different workloads, including dynamic ones. The results show that HIODS successfully changed its operation mode based on the system workload and performance objective. 1.3 dissertation structure In the following chapter, we present the state of the art for deduplication systems, while explaining core concepts of this field. Chapter III introduces HIODS general architecture, explains all components, and describes the data flow for supported deduplication modes. In Chapter IV, we discuss the implementation of HIODS prototype. In Chapter V, the testing methodology is detailed and the results from the experimental evaluation are discussed. Finally, Chapter VI concludes the dissertation while pointing interesting future work. 2 BACKGROUND AND STATE OF THE ART This chapter starts by presenting an overview of the deduplication field and key concepts. Then, we detail relevant related work on the area and discuss its main differences when compared to the solution proposed by this dissertation. 2.1 deduplication The need to reduce the storage space used by archival and backup systems led the industry to search for a mechanism capable of achieving such goals. Thus arises Deduplication as a process of finding and removing duplicated data. Nowadays, deduplication is used in a larger variety of products and services like, for instance, primary storage, RAM, and SSDs [7]. Despite being used with the same end goal and the main elements remain similar between systems, the fact is that the target systems have, quite often, unique characteristics which demand custom made components for deduplication systems to be deployed. 2.1.1Basic Architecture All deduplication systems aim to reduce the storage space used by applications. To save storage space and reduce the respective costs, the process takes advantage of references and associations, allowing for the elimination of duplicate content without the loss of any information. In order to find redundant data, deduplication systems must know all the information already stored on disk. Therefore, one of the components widely used in all designs is referred as the Index , which indexes all unique data and is instrumental to quickly determine if a piece of information is already in the system. Actually, to improve system performance, a data digest, also called a signature, is often indexed instead of the original data, although the latter can also be used. Furthermore, every entry in the Index is linked with the original data ' s physical location and its number of references. The former is used to locate the data on disk while the latter tracks the number of logical pointers to the unique copy. 5 2.1. Deduplication 6 A second fundamental component is called Metadata . This data structure associates the address where the application intended to store its data, also known as the logical address (LBA), with its actual physical location (PBA) at the persistent storage medium. Figure 2: Architecture and Workflow of a Basic Deduplication System Having shown the essential components, we now introduce the basic workflow of any traditional deduplication system. First, a new storage request containing the data and logical address where it must be stored is intercepted (Figure 21 6 ). The request is then redirected to the Deduplication Engine, which calculates the data digest (digest(A) = aaa). Next, using such a signature, the Index is able to verify if a copy of the data is already stored (Figure 22 ). If such data does not exist in the system (Figure 2a ), an entry that maps to an available physical address is inserted (Figure 23 ). Then, in Metadata, an association between the request ' s logical address and the physical block where the data will be stored is created (Figure 24 ). Finally, the data is written to disk (Figure 25 ), and the storage request is completed. Otherwise, if a copy of the data is already indexed (Figure 2b ), the number of references is incremented (Figure 27 ), and the associated physical address returned. Finally, the association between the request ' s logical offset and the returned physical address is created (Figure 2-8). Suppose now that the system intercepts a read request to a logical offset. In that situation, the physical address linked with the request ' s logical offset in Metadata must be read, and its content returned to the application. 2.1. Deduplication 7 2.1.2Deduplication Criteria A deduplication system can be defined by six fundamental criteria that drive its design and implementation [7]. granularity The first criterion and one of the most important is Granularity. It defines the size of the chunks that are going to be used to identify and remove duplicates. Choosing the chunk size is one of the most significant decisions when implementing a deduplication system since it will directly influence its performance and achievable space savings. When deciding about this criterion, there are three alternatives. The first resorts to whole files (whole file chunking) [ 9 ]. This alternative is often used in file-oriented systems since there is no need to split the data into smaller pieces and, therefore, less processing to do in the I/O critical path [ 10 ]. On the other hand, two very similar files, where only a single byte differs, will not be identified as duplicates, therefore loosing the opportunity to improve space savings. The second alternative and a popular one is chunks with a fixed size (ex: 4KB), which is often used in storage systems that already used a fixed-size unit [ 11 , 12 ]. Unlike the previous alternative, this option can detect redundancy within the file since it compares multiple chunks of the same file. For this very reason, this solution requires extra processing power [10,13]. Figure 3: Fixed-Size Chunking versus Variable-Size Chunking One of the most substantial problems regarding fixed-size chunking is the lack of versatility. For example, let us imagine a base file and a similar second one with an extra 10 bytes added to the beginning. That small 10-byte difference, with the current alternative, will fail to match every single chunk with the original file by 10 bytes (Figure 3a ). As to mitigate 2.1. Deduplication 8 such a problem [ 14 ], a variation using variable size chunks [ 15 ] was designed. Picking up the previous example, if the original file were deduplicated with a 4KB chunk size, the modified file ' s first block could be handled with 4106 bytes. This larger first block would allow the remaining ones to be processed at 4KB granularity, matching the original file blocks (Figure 3-b). timing The next criterion is called Timing, and it decides when to perform deduplication. As previously mentioned, traditional inline deduplication [ 11 , 16 , 17 , 18 ] detects and removes duplicate data before storing it to disk. Thus, when a storage request is intercepted, a signature that represents its data is immediately calculated. Next, the computed signature is used to check if the request ' s data is duplicate and, if so, prevent the write operation to disk. However, this process is performed in the I/O critical path, introducing additional storage performance overhead, which can be critical for some applications [ 19 ]. So that high-performance demanding applications can also take advantage of the process, offline deduplication was proposed. In this new mode, all the processing is moved to a background job, which frees the I/O critical path maintaining the original performance. The process of finding and removing redundant content is executed at an opportune moment. Both options have advantages and disadvantages. The former ' s main downside is that it introduces a latency overhead in the request since some computations are executed in the I/O path before completion. When it comes to offline deduplication, this drawback is not present, although it has a few of its own. As the data needs to be stored before processing, additional resources are required, including storage and processing power. indexing The third criterion is called Indexing. It defines the system index, which is the main structure of any deduplication system since it is in it that the digests will be stored. When it comes to this auxiliary structure, its choice is sometimes overlooked, making it the system ' s bottleneck. There are three alternatives. The first and most used is called Full Index. All distinct data digests are stored with this type, which makes finding all duplicates possible [ 9 , 11 ]. However, this alternative comes with a high potential for growth, which may become unsustainable over time. In fact, this type of Index has the potential to become so big that its maintainability in memory becomes impossible, triggering the need to access the disk. This change will increase the overhead caused by deduplication since disk accesses are considerably slower than memory ones [11]. An alternative to the previously presented and that solves the size problem is called Sparse Index [ 20 , 21 ]. Unlike the previous option, this type is based on similarities among 2.1. Deduplication 9 the chunks. Therefore, the Index does not store signatures representing a single piece of information but referencing a group of similar chunks instead. Finally, a second alternative that also mitigates the size problem is called Partial Index. This option employs the same technique as the Full Index, where each entry represents a unique chunk. However, unlike the first alternative, not all signatures are stored in this solution. In fact, as it can not know all the information already stored on disk, only partial deduplication is achievable [ 22 , 23 , 24 , 25 ]. Regarding how to choose which chunks are indexed, there are many algorithms. One of them is the use of access patterns, where the most recent chunks are indexed, and the older signatures are deleted. locality The fourth criterion is Locality, which is not system-related but instead a storage workload property. On the one hand, Temporal Locality tells us that a percentage of duplicate blocks are expected to be written in a short time period. On the other hand, Spatial Locality explains that if the blocks appeared in a specific order, then they will appear in the same order as before. For example, imagine that the sequence of chunks A, B, C, D, and E enters the system. The spatial locality concept tells us that if a stream formed by A, B, C, and D were intercepted in the future, the next chunk would likely be E. Accepting this property comes with the need to design and implement additional components to take advantage of it [ 11 ]. A component that tries to predict the following intercepted chunk to optimize the index lookups and reduce the overhead is one of many examples of extra complexity in the system. These mechanisms can be quite useful if well designed and implemented and, most of all, when locality is present in the data. However, if the data does not show locality, these mechanisms will not be able to optimize the system, introducing extra overhead. For this reason, many deduplication systems do not take advantage of it [26,27,28], a small group focus on only one type, and very few take advantage of both. technique The penultimate criterion is called Technique, and it determines how data will be stored on disk, with two main alternatives. The first is the use of unique chunks, storing only unique copies. On the other hand, when dealing with similar blocks, it is possible to store only a base chunk and a list of changes that allow recovering the original data. The former is called Chunk-based Deduplication [ 9 , 11 ], and the latter is known as Delta Encoding [ 29 ]. When it comes to advantages and disadvantages, the former requires less processing power and can restore faster [30], while the latter allows saving extra storage space [29,31]. 2.1. Deduplication 10 scope Scope is the sixth and final criterion. It indicates at what level deduplication will be performed in a distributed scenario. On the one hand, finding and removing duplicates can be done at a Local Scope [ 21 , 32 ], meaning that every node performs deduplication on its own. On the other hand, this process can be performed at a Global Scope [ 12 , 26 , 28 , 33 ], allowing deduplication to be performed system-wide where shared structures and locking mechanisms are required at the expense of performance. 2.1.3Primary Storage vs Secondary Storage Deduplication methods are now used in multiple aspects of our lives, particularly in archival/backup and primary storage, among others. Archival and backup storage share similarities regarding the necessary characteristics needed for a deduplication system since the information present is not expected to change, and both prefer throughput over latency. Furthermore, in secondary storage, a 90-95% degree of duplicate information can be found, causing huge storage losses and increasing the storage costs if such redundant content is stored instead of removed. There is primary storage on the other side of the coin, which also has unique requirements, but, in this case, regarding storage operations latency. Therefore, the major challenge of a deduplication system aimed at primary storage is to reduce to the maximum the overhead introduced in I/O critical path. Besides latency requirements, in this type of system, data is expected to change regularly. This new update operation, which does not exist in secondary systems, introduces additional complexity to the deduplication process. There is now the need for mechanisms capable of performing the update and simultaneously maintaining consistency with the other referenced chunks. Furthermore, updating information allows for the number of references of individual blocks to reach zero, meaning that its presence in the system must be erased in order to accommodate a new chunk in its physical address bringing storage waste to a minimum. As a side note, primary storage systems are built on top of state of the art hardware, meaning that any reduction in space is directly translated into financial gains. For all the reasons presented above, the inline mode is often associated with secondary storage and offline deduplication with primary storage. However, many applications require high performance during only a few key moments and could take the overhead of inline deduplication in the remaining occasions. For example, let us imagine an application requiring a high throughput for a few hours every day and that such throughput can only be achieved with offline deduplication. In reality, the application could withstand the overhead introduced by inline deduplication during the remaining hours. However, as 2.2. Related Work 11 the performance for a few hours a day can only be achieved by offline deduplication, a static offline system would probably be implemented. In fact, a hybrid system capable of switching between inline and offline deduplication would be the ideal solution. This way, the system could benefit from inline deduplication during the off-peak hours and switch to offline mode when necessary. 2.2 related work The majority of existing deduplication systems are based on only one timing approach, i.e., they either exploit inline deduplication or perform offline deduplication depending on the workload ' s performance requirements. Recently, hybrid deduplication systems have emerged as a more efficient solution for workloads whose requirements may vary over time or across different groups of data, and where a combination of offline and inline deduplication may be best suitable. 2.2.1DIODE A first system that already implements hybrid deduplication is called Dynamic Inline-Offline Deduplication (DIODE) [ 34 ], and it introduces two new mechanisms. Context-aware Threshold Adjustment (CTA) controls inline deduplication, and Deferred Priority-based Enforcement (DPE) has the goal to monitor and adjust offline deduplication. When a file is intercepted by DIODE, it is immediately classified in one of three types having the file extension as the criterion. The first, Highly-deduplicatable Type (H-Type), comprises file extensions known to have a high deduplication gain. Conversely, files belonging to the Poorly-deduplicatable Type (P-Type) have low deduplication gains. All the other files fit in the Unpredictable Type (U-Type). After this first assessment, the chunks whose original file belonged to the H-Type or U-Type are transferred to DIODE ' s inline deduplication module, iDeduper. However, not all chunks will be processed since it only removes duplicates on redundant chunk sequences higher than CTA ' s current threshold. This threshold defines the minimum size that a redundant chunk sequence must have to be processed by inline deduplication. For example, suppose that the threshold is set to five. Then, inline deduplication will only be chosen on a five or higher sequence if at least five consecutive requests exhibit duplicate data or if their logical addresses are sequential (ex.: 1,2,3,4,5). DIODE ' s choice to only perform inline deduplication to redundant chunk sequences higher than a specific limit allows for improving read efficiency with a slight reduction in redundant data found [19,35]. P-Type files are skipped and will be dealt with offline deduplication. Therefore, when the number of unprocessed files reaches a threshold now set by DPE, offline deduplication 2.2. Related Work 12 is activated. A sorted by priorities and fixed-size list of undealt files is generated, and the files present will be processed, at a block level, by DIODE ' s offline deduplication module, oDeduper. Besides the detailed mechanisms above, DIODE also exploits temporal locality since it assigns lower priorities to the most recent accessed files. Furthermore, the full list of written blocks is only processed by deduplication if the system detects more write requests being intercepted. This way, if the system detects multiple read requests during offline processing, the background task is stopped at half the list in order to reduce interference with the read requests. 2.2.2D3 While the previous system is meant for centralized primary storage, the authors also designed and implemented a distributed version, Dynamic Dual-Phase Deduplication Framework for Distributed Primary Storage (D 3 ) [ 36 ]. D 3 shares the core components with DIODE like the extension-based file classification, CTA to control inline deduplication, and DPE to help adjust offline deduplication. However, since it now targets a distributed scenario, D 3 also introduces new components like the Application Layer, deployed on the client-side, the Coordinator Cluster, and the Storage Node Cluster both on the server-side. In D 3 , the dataflow is quite different from DIODE since the files are intercepted on the Application Layer, which is on the client-side. It is also there where they are classified the same way as before (H-Type, P-Type, and U-Type). One of the main differences is the granularity since P-Type files are treated as a whole, and in the remaining types, chunk level deduplication is performed. One other variation is the fact that all file types can be processed in an inline manner. Once classified, the Application Layer sends the file (P-Type) or the chunks (H-Type and U-Type) to the Coordinator Cluster. In the former, the Coordinator computes its File Fingerprint (FF) and redirects the file to the FF mod n node, where n is the total number of nodes in the system. The node ' s local inline deduplication module, iDeduper, will then search for a duplicate. If such is found, the metadata is updated, and the process is completed. Otherwise, its File Fingerprint is inserted into the File Fingerprint Hash Table, which stores the unique fingerprints for P-Type files only, but the actual process is delayed and performed later by D3's offline deduplication. A signature is also computed with the remaining types, and the blocks are sent to the respective node. Like in DIODE, the inline deduplication module will only process redundant chunk sequences higher than the threshold set by the CTA. All chunks that were not yet processed (P-Type files are later split into chunks) are retrieved by each node ' s offline deduplication module, oDeduper, and sent to the Coordinator 3.2. Deduplication Workflow - Inline Mode 19 physical address where the previous data was written, and present in the DirtyQueue, is returned to FreeBlocks. After the previous verification, the Metadata module is consulted (Figure 53 ) to retrieve information associated with the storage request ' s logical address. This query returns the associated physical address and the respective Copy-on-Write flag, which indicates if the returned address is being shared among multiple logical addresses. If the CoW flag is set, additional steps are required to ensure the deduplication system's consistency. Let us assume that other logical addresses do not share the returned physical address (CoW == 0). It is now necessary to determine if a copy of the request ' s data is already stored on disk. As to ascertain such, a test and increment operation is conducted on the Index (Figure 54 ) with the previously computed digest as key. This operation allows for determining if the digest is already in the Index, indicating whether the data is duplicated. If this is not the case, a new physical address is requested from FreeBlocks (new phy addr) (Figure 55 ). Next, the pair (digest, new phy addr) is inserted into the Index (Figure 56 ) and the reverse pair into the Reverse Index (Figure 57 ). Finally, Metadata is updated (Figure 58 ) with the logical address associated with the request now pointing to the new physical address. Also, the CoW flag is set, indicating that, from now on, the beforementioned physical address is being shared. On the other hand, if the digest already exists in the Index, the test and increment operation previously performed increments the associated number of references and returns the physical address where the data is stored (phy addr). In this case, the last step is to point the logical offset in Metadata (Figure 58 ) to the physical address where the copy of the request ' s data is stored (phy addr), also activating the CoW flag. In the case where the data is already being shared (CoW == 1), the same operations are performed. However, it is also necessary to check if the data there stored is still referenced by any other logical address (nRef > 0). With that in mind, the Reverse Index is consulted (Figure 59 ), with the physical address returned by the Metadata module as the key, retrieving the digest of the data there stored. Next, its number of references is decremented and returned by the Index (Figure 510 ). Suppose the returned value equals zero, indicating that the data is no longer being used by any logical address. In that case, the digest is removed from the Index (Figure 511 ), and the physical address returned by Metadata is removed from Reverse Index (Figure 512 ). This phase ' s final step is to return to Freeblocks (Figure 5-13 ) the same physical address removed from Reverse Index. Finally, if the data has to be written to disk, the physical address provided by Freeblocks is returned to the Interceptor. This component then calculates the timestamp and sends the previous timestamp along with the recently calculated one to the Deduplication Controller. At last, the data is written to the new phy addr address on disk (Figure 514 ), and the write request is marked as completed. 3.3. Deduplication Workflow - Offline Mode 20 3.3 deduplication workflow -offline mode Figure 6: Deduplication Workflow on Offline Mode The beginning of the process is quite similar to the one described above. When the Interceptor receives a storage request to process, the timestamp is collected, and the request is redirected to the Deduplication Engine (Figure 6-1). Next, a pending deduplication request to the same logical address is searched for in the DirtyQueue (Figure 62 ). In fact, if there was a request to the same logical address that was not yet processed, it became obsolete due to the current rewrite. Therefore, we can use the same physical address to store the data present in the current storage request. If an old request did not exist, a new physical address is requested from FreeBlocks (Figure 6-3). So that deduplication can be performed later, it is necessary to store some information to make it possible. Therefore, to avoid disk operations and increase system efficiency, a data digest is calculated and stored in the DirtyQueue (Figure 64 ), alongside the original logical address and the previously chosen physical address. 3.4. Deduplication Workflow - Background Processing 21 Following the previous step and before updating the Metadata, it is necessary to check whether the physical address currently associated with the logical offset in Metadata is being shared among multiple logical addresses. As to verify such condition, the Metadata module is consulted (Figure 65 ) with the request ' s logical address as the key returning the associated physical address and the corresponding CoW flag. Suppose the address is being shared (CoW == 1). Then the digest associated with the physical address is returned by Reverse Index (Figure 66 ), and its number of references is decremented in the Index (Figure 67 ). If the number equals zero, the digest is removed from the Index (Figure 68 ), and the pair (physical address, digest) deleted from Reverse Index (Figure 69 ). To end the current phase, the physical address is returned to FreeBlocks (Figure 6-10 ). Finally, an update to Metadata (Figure 611 ) makes the request ' s logical address point to the physical address chosen in step 2or 3. As deduplication has yet to be performed, the CoW flag is set to zero. The physical address is returned to the Interceptor, which calculates the current timestamp and sends it alongside the initially calculated one to the Deduplication Controller. At last, the data is written to the physical address returned to the Interceptor (Figure 6-12 ). 3.4 deduplication workflow -background processing Figure 7: Background Process Workflow As offline deduplication only stores the necessary information for later processing, not finding nor removing duplicates in the I/O critical path, a background task is required to perform the process. 3.5. Deduplication Controller 22 Therefore, this process, which is only activated periodically, for example, 1minute after the last time it went to sleep, has the primary goal to process the dirty blocks, i.e., the entries in the DirtyQueue. Each dirty block comprises a data digest and a logical address, both present in the original storage request and the physical address (new phy addr) where it was stored on the disk by the foreground I/O logic. The following algorithm is followed for every entry in the DirtyQueue. First, a dirty block is retrieved from the DirtyQueue (Figure 71 ). Next, a test and increment operation is performed on the Index (Figure 72 ) using the digest present in the dirty block as the key. This operation allows for determining if the digest is already in the Index, indicating whether the data is duplicated. If the previous operation replies that the digest is not present in the Index, and since the data is already stored on the disk, it is only necessary to insert the digest and the physical address where the original data was previously stored (new phy addr) in the Index (Figure 73 ). The reverse pair is inserted into the Reverse Index (Figure 74 ). The final step is to update the Metadata (Figure 75 ) pointing the original logical address to the physical address. The CoW flag is also set, indicating that multiple logical addresses could be using that same physical one from now on. Otherwise, i.e., if the digest is already present in the Index, the number of references associated with it is incremented, and the corresponding physical address is returned (phy addr). Next, it is necessary to point the logical address present in the dirty block to the physical address returned by the Index in Metadata (Figure 76 ). As to finish this step, the physical address present in the dirty block (new phy addr) must be returned to FreeBlocks (Figure 76 ) since both phy addr and new phy addr store the same data on disk. This step is required to optimize the used space, eliminating copies of duplicate data on disk, which is the primary goal after all. Finally, the DirtyQueue entry is expunged (Figure 7-7). Being a background job, it competes for resources with the primary process. Such competition may cause concurrency issues as both jobs may access the same structures for processing. In order to mitigate that problem, concurrency control mechanisms for all auxiliary structures were also implemented. 3.5 deduplication controller In a vast set of systems, deduplication is performed in a static manner, i.e., only one mode is implemented. However, HIODS primary goal is to update the operation mode dynamically, inline to offline and vice-versa. The exact moment when the mode should switch is one of the most significant challenges in designing an hybrid deduplication system. In order to achieve such goal, HIODS introduces a new way to switch the operation mode automatically. Namely, it relies on two conditions to switch its operation mode. The first is 3.5. Deduplication Controller 23 the system load, calculated by the Deduplication Controller, and the second is the system performance. Therefore, when the application starts to send a high number of storage requests, the Controller is able to realize that the Engine is under considerable stress and may not be able to achieve its objective. After this realization, the current throughput is acquired and compared with the desired performance. Suppose the former is lower than the latter. In that case, the operation mode is switched to offline and kept that way until the Deduplication Controller decides that the system is no longer under heavy load, in which case, the operation mode is switch back to inline deduplication. As it is possible to observe by the workflow images from the previous chapters (3.2,3.3), inline deduplication does more operations in the I/O critical path than offline deduplication. Such is due to the fact that the latter only finds and removes duplicates later in time and on background. As to find and remove the redundant data that offline deduplication misses, a background job is required. However, when to activate the process does not have a trivial answer. Actually, when activated regularly, an additional amount of resources, which may be necessary to the primary job, will be used by the background process. On the other hand, if the background process is only activate in periods of low I/O load, it will not be able to find and remove duplicates quickly, thus wasting valuable storage space. In HIODS, the DirtyQueue is processed periodically to eliminate as many duplicates as possible, as soon as possible. However, the need to share resources previously mentioned is contemplated. Namely, our solution implements a Feedback Loop Mechanism in order to control the throughput of background deduplication processing. If the target performance objective is not being met, this mechanism calculates a time, in nanoseconds, to delay the processing of the entries in the DirtyQueue. This pause in the background job will allow the foreground process to increase the throughput and achieve the desired performance target. Feedback Loop Controllers, also known as Closed Loop Controllers, are a type of controller that receives input measurements from the same system where they are implemented. In this particular case, it receives the current throughput and calculates the time, in nanoseconds, to delay the background process in order to achieve the target throughput. 4 PROTOTYPE To be able to assess the mechanisms introduced in the previous chapter, a prototype of the system was developed. To achieve that, C was chosen as the programming language and SPDK as the framework where HIODS was integrated. 4.1 spdk Every system ' s performance is always limited by the weakest link, and storage systems are no exception. Until a few years ago, these systems were limited by hardware. However, in the last few years, the hardware business has changed considerably with the appearance of SSDs and, more recently, with NVMe SSDs. All these innovations caused the balance to change sides, and, nowadays, it is the software that introduces overhead to the system. Considering what was previously mentioned and according to tests [ 8 ], the Kernel I/O Stack causes a significant percentage of the software overhead due to context switches, data copy between the kernel and userspace, interrupts, and resources competition. Thus arises SPDK, short for Storage Performance Development Kit, with the primary goal to bridge the gaps previously presented, which means reducing the overhead introduced by software, which ultimately translates into high-performance applications. SPDK achieves its goals with three techniques [8]: • Move all necessary drivers into userspace, which avoids system calls and enables zero-copy access from the applications; • Polling hardware for completions instead of relying on interrupts, which lowers both total latency and latency variance; • Avoiding all locks in the I/O path, instead relying on message passing. Besides being built with performance as the primary focus introducing all the above mechanisms to improve it, SPDK was also designed to be modular and extensible. Thus, this framework introduces a layered structure based on block devices that can be stack on each other. 24 4.2. Implementation Details 25 SPDK presents two types of block device modules. The first is called a block device, and its differentiating characteristic is that it represents physical devices, i.e., devices that can store information. On the other hand, there are virtual block device modules. These receive storage requests, process them in some manner, like deduplication or encryption services, and finally, redirect them to the underlying block device, either physical or virtual. HIODS was developed as a virtual block device module. It receives requests from applications, finds and removes redundant data if inline deduplication, or makes the necessary arrangements for later processing if the offline mode is activated. Finally, if necessary, redirects the request to the NVMe block device for persistent storage. Figure 8: HIODS integration with SPDK So that applications can take advantage of HIODS virtual block device, such is exported as a regular operating system block device by Network Block Device (NBD) [ 42 ], as shown in Figure 8. If this were not the case, the applications would need to be changed in order to integrate with SPDK. 4.2 implementation details With the extra deduplication processing since I/O requests are intercepted until their completion, a decrease in system performance is expected. In order to accurately measure such performance drop, it is necessary to implement the most capable system possible. Thus, the first version of the deduplication system had all its data structures stored in memory. 4.3. Deduplication Controller 26 Therefore, the Index was implemented as a GHashTable from glib [ 43 ] with the data digest as the key. Reverse Index used an array where each position represented a physical address, with its content being the digest of the data there stored. In the same way, Metadata also implemented an array where each position corresponded to a logical address, and its content was the associated physical address and CoW flag. Freeblocks was stored using a circular array where all available physical addresses were stored. This component ' s solution also involved an index for retrieving the associated physical address and a second one for storing a returned address. The final structure, DirtyQueue, once again resorted to an array where each position matches a logical address. Every position stores the corresponding digest and physical address where the data represented by the digest was stored by offline deduplication. However, a system where its data is stored in memory does not allow for its long-term maintenance and scalability. Therefore, HIODS ' second version was developed with the primary goal to promote persistent storage of metadata. Considering the data types store by every component, is it perceptible that all of them associate key-value pairs. For instance, a data digest is associated with the physical address and the number of references in the Index. Therefore, all the previous components could easily be stored in Key-Value Databases. After searching for possible candidates, leveldb [ 44 ] was chosen to store the Index, Reverse Index, and Metadata. Actually, the DirtyQueue remained in memory as it is not a vital component. While the loss of the data stored in the three first mentioned components would lead to the system ' s inconsistency, the loss of DirtyQueue would only lead to some lost deduplication opportunities. Finally, the last component with the need for persistent storage was FreeBlocks. In reality, as it only stores a list of available physical addresses, the first implementation resorted to a file. However, it quickly became apparent that such implementation introduced significant overheads. Therefore, the solution was to store this structure in a dedicated disk partition accessible through SPDK. Nevertheless, if every single request/return of an available physical address required accessing the disk, it could lead to unwanted pressure on this vital component. With that in mind, a configurable caching mechanism, currently set for 16000 blocks, was designed and implemented. 4.3 deduplication controller HIODS ' primary objective is being able to switch between deduplication modes whenever necessary. To achieve such a goal, the Deduplication Controller was developed. As previously mentioned, the switch between inline and offline deduplication is based on two conditions: the current system load and the desired performance goal. So that the former can be calculated, the system uses the entry time of the current request and the 4.3. Deduplication Controller 27 exit timestamp of the previous request. Actually, we assumed that when a system is under heavy workloads, a new request is dealt immediately after the previous one exits the system. Therefore, if the difference between the previous two timestamps is under a certain limit, 3 ms in our implementation, the current request is flagged as “in stress”. Periodically, a background job is responsible for determining if the system is under heavy stress. To label it as such, the ratio between the total number of requests and the ones marked as “in stress” must be at least 90%. Furthermore, the last request must have been caught within a few moments before the evaluation, 1second in our implementation, to eliminate unique bursts as false indicators. For example, let us imagine that only ten requests in a row were intercepted right after an evaluation. As they were made in a row, the first condition is verified. However, it was a solo burst that should not trigger the Controller to detect stress. Therefore, the second condition helps in avoiding such situations. If both conditions are verified, the Controller realizes that the Engine is under stress and may not achieve the desired performance goal. Suppose the first condition is verified. Then, the current system throughput is acquired and compared with the desired performance. Suppose now that the first condition is verified and the target performance is not reached for a consecutive number of measurements in a row, 3in our implementation. In that case, offline deduplication mode is activated, easing the I/O critical path ' s processing, increasing the overall system throughput. For inline deduplication to be switched back, the only requirement is for the Engine not to be under heavy workloads for a certain number of measurements in a row, once again, 3in our implementation. 4.3.1Feedback Loop Controller In order to control the background job ' s throughput, we endowed the deduplication system with a Feedback Loop Controller that delays the processing of dirty blocks. This mechanism controls the number of dirty blocks processed every second, decreasing the interference between foreground and background I/O operations, thus helping the foreground job to reach and maintain the target performance. When it comes to this category, there were several possible choices. One of the most known and used in the industry is the Proportional–Integral–Derivative Controller [ 45 ]. This algorithm was chosen to integrate this system. 4.3. Deduplication Controller 28 integral = 0 previousError = 0 def pi d Co ntr o ll er ( measuredThroughput , dt ) : delay = 0 error = 0 d e r i v a t i v e = 0 kp = 5.0 , ki = 0.15 , kd = 0.25 e r r o r = targetThroughput - measuredThroughput ; i n t e g r a l = i n t e g r a l + er ro r * dt ; d e r i v a t i v e = ( e r r o r - p rev io usE rr or ) / dt ; delay = kp * e rr or + ki * i n t e g r a l + kd * d er iv a ti v e ; previousError = error ; return delay ; Listing 4.1: Feedback Loop Controller One of the characteristics of this type of Controller is the fact that it receives as input a measurement from the system where it will be deployed. Listing 4.1presents the pseudocode for the PID Controller implemented in HIODS. As we can observe from the pseudo-code, this PID algorithm receives as an argument the system performance (measuredThroughput) measured over a period of time (dt in seconds). From the former, it is possible to calculate the error, i.e., the Proportional component, by subtracting the measured to the desired throughput (targetThroughput). Next, the remaining two components, Integral and Derivative, are computed. Afterward, each component is multiplied by its coefficient, kp , ki , and kd . Finally, the time to delay the processing of dirty blocks, in nanoseconds, is obtained by adding the previously multiplied components. 5.3. Micro Experiments 35 When comparing the use of 1and 4processes, we can observe that uniform performance increased from 38 MB/s to 140 MB/s and that the hotspot mode also recorded substantial gains (120 MB/s to around 400 MB/s). However, sequential performance with the highperf distribution suffered a small drop to 301,45 MB/s compared to the 325,96 MB/s that had been achieved with a single process. Once again, the substantial amount of unique data makes caching impossible, requiring accessing the disk for every request. These accesses from four different processes caused interference with each other, which ultimately lead to performance drops. In order to perceive the influence of deduplication in the overall system performance, we must turn our attention to both tables. After comparing its results, a performance decrease is evident. For example, sequential operations dropped from 1475 MB/s to 300/400 MB/s, uniform performance decreased to 38 MB/s from 50 MB/s, and hotspot reads declined from 190 MB/s to 120 MB/s. Because a new layer of processing was added to the workflow, a reduction in throughput was expected. However, the drop is considerably higher in sequential reads when compared to the others. Despite the extra processing costs seen in uniform and hotspot, deduplication also introduces disk fragmentation, most visible in sequential requests. While sequential logical addresses translate to sequential physical addresses in a typical environment, such a statement is not accurate with deduplication since sequential logical addresses can be associated with physical blocks scattered across the disk. Mode nProcesses Distribution Throughput (MB/s) Latency (us) Mean SDeviation Mean SDeviation Sequential 1HighPerf 249,65 0,60 15,67 0,58 Kernels 336,06 0,50 11,33 0,58 4HighPerf 233,94 0,59 66,67 0,49 Kernels 449,28 0,30 35,00 0,00 Uniform 1HighPerf 35,71 0,08 109,00 0,00 Kernels 36,98 0,03 105,00 0,00 4HighPerf 126,00 0,30 123,67 0,49 Kernels 132,97 0,24 117,00 0,00 HotSpot 1HighPerf 132,06 0,59 29,00 0,00 Kernels 137,18 0,35 28,00 0,00 4HighPerf 424,31 2,54 36,42 0,51 Kernels 463,60 14,39 33,33 0,98 Table 7: Read Operations with Persistent Deduplication 5.3. Micro Experiments 36 Considering that the memory implementation is always the most efficient version of a system, it was evident that the switch to persistent storage would bring performance losses. This decrease in performance can be confirmed in Table 7. These results show a sequential performance of around 250/330 MB/s, compared to the 325/390 MB/s with the memory version. Uniform reads also dropped from 38 MB/s to 36 MB/s. Since it focuses its operation on a limited number of addresses, the hotspot mode can, once again, take full advantage of data already cached. As it relies on caching mechanisms, queries to leveldb are minimal in this operation mode, which allows the performance to remain stable between the two versions. Environment CPU (%) Memory (GB) No Deduplication 9,79 4,98 Memory Deduplication 43,69 9,21 Persistent Deduplication 42,54 3,57 Table 8: Resources It is possible to note, from analyzing Table 8, which compares the resources used by the multiple testing environments, an increase in CPU (from 9,79% to 43,69%) and memory usage (from 4,98 GB to 9,21 GB) between the environment without deduplication and HIODS memory version. Actually, the increase was expected as deduplication introduces additional processing. Furthermore, as the metadata structures were stored in memory, such an increase was also foreseen. Finally, the processing power used by the persistent version of HIODS remains unchanged, as the process itself does not change between versions. However, the metadata is now stored in leveldb, which allows for freeing the memory previously used to store the auxiliary data. 5.3. Micro Experiments 37 5.3.1.2Write Operations Mode nProcesses Distribution Throughput (MB/s) Latency (us) Mean SDeviation Mean SDeviation Sequential 1HighPerf 441,78 10,51 7,33 0,58 Kernels 451,66 1,37 7,00 0,00 4HighPerf 435,19 4,00 34,33 0,49 Kernels 439,68 1,91 34,00 0,00 Uniform 1HighPerf 400,76 24,74 8,00 1,00 Kernels 387,36 1,10 8,00 0,00 4HighPerf 389,18 3,53 38,67 0,49 Kernels 392,61 5,82 38,33 0,49 HotSpot 1HighPerf 380,17 11,37 8,67 0,58 Kernels 378,71 6,91 8,67 0,58 4HighPerf 392,64 1,25 38,17 0,39 Kernels 402,07 2,29 37,33 0,49 Table 9: Write Operations without Deduplication Concerning write operations and observing Table 9, it is possible to conclude that the sequential mode delivered the best performance among the three, achieving around 440 MB/s. In fact, such results were expected as sequential operations introduce the lowest overheads. Changing the focus to uniform and hotspot operations, a slight decrease to around 390 MB/s is observed on both. Actually, modern hardware like regular SSDs and NVMe SSDs can reach almost identical performances between sequential and uniform write operations as they do not possess physical components like regular HDDs, where uniform operations are significantly more costly. Moving on to the differences between 1and 4processes, stability in the results is observed. Contrary to what happened in the readings, a single process can take full advantage of the available bandwidth. With the introduction of multiple processes, the disk resources must be shared between them, which can cause interference among the processes, occasionally leading to slightly lower performances. Finally, the content distribution used does not influence the results because deduplication is not implemented on this first setup. 5.3. Micro Experiments 38 Mode nProcesses Distribution Throughput (MB/s) Latency (us) Mean SDeviation Mean SDeviation Sequential 1HighPerf 293,89 1,88 12,00 0,00 Kernels 296,41 1,22 12,00 0,00 4HighPerf 286,01 2,20 53,00 0,00 Kernels 294,55 0,63 51,33 0,49 Uniform 1HighPerf 271,13 0,70 13,00 0,00 Kernels 276,79 0,74 12,00 0,00 4HighPerf 282,83 3,07 53,83 0,39 Kernels 284,39 0,91 53,17 0,39 HotSpot 1HighPerf 461,10 2,71 7,00 0,00 Kernels 465,89 2,79 7,00 0,00 4HighPerf 443,10 4,23 33,42 0,51 Kernels 446,22 0,91 33,00 0,00 Table 10: Write Operations with Inline Memory Deduplication Following the base measurements, a memory deduplication layer was introduced. With this version, the overhead introduced by deduplication will be easily recognized. Firstly, the inline mode was tested, and the results are shown in Table 10. Focusing on these last results, a general performance drop compared to the environment without deduplication is quickly perceived. For instance, sequential write performance decreased from 440 MB/s to 290 MB/s, and uniform mode performance dropped to 270/280 MB/s from the 390 MB/s previously obtained. The drop in performance is a direct consequence of an additional processing layer. A second observation is a reduced difference between sequential and uniform operations, which was around 50 MB/s without deduplication, and now stands at 15 MB/s. Actually, when started from scratch, the deduplication system transforms all other requests into sequential ones as sequential addresses are provided by FreeBlocks to the Deduplication Engine. The previous fact, combined with operating system optimizations and lower disk usage, as it is not necessary to store all data, allow hotspot mode to gain 20% in performance, delivering around 450 MB/s versus the original 390 MB/s. Directing our attention to the last table alone, slightly higher results are observed when using the kernels content distribution, when compared to the highperf one. For example, sequential operations using one process and the highperf content distribution delivered 293,89 MB/s, while the same configuration using the kernels content distribution reached 296,41 MB/s. In fact, the higher the number of duplicates, the better the engine will perform 5.3. Micro Experiments 39 since fewer interactions with the components and fewer communications with the disk are performed. With 75% of redundant content against only 20%, kernels does not produce such heavy disk usage, which, combined with fewer interactions with the components, results in higher performance. Finally, we can still observe that the competition for resources among the four processes leads to small decreases compared to a single process. Mode nProcesses Distribution Throughput (MB/s) Latency (us) Mean SDeviation Mean SDeviation Sequential 1HighPerf 307,33 0,17 11,00 0,00 Kernels 307,82 0,12 11,00 0,00 4HighPerf 306,63 0,25 49,17 0,39 Kernels 307,04 0,61 49,08 0,29 Uniform 1HighPerf 295,88 0,05 12,00 0,00 Kernels 297,07 0,33 11,00 0,00 4HighPerf 293,98 0,44 51,33 0,49 Kernels 295,58 0,04 51,00 0,00 HotSpot 1HighPerf 481,43 0,51 6,00 0,00 Kernels 490,32 1,43 6,00 0,00 4HighPerf 467,40 11,64 31,75 0,75 Kernels 459,60 20,52 32,17 1,40 Table 11: Write Operations with Offline Memory Deduplication without Background Processing Inline deduplication introduces extra overhead since it finds and removes duplicate data in the I/O critical path. As an alternative, offline deduplication was developed. This new mode does not find or remove duplicate data in the I/O critical path, relying on a background job that competes for resources with the main task. To observe the real impact that the background process has on performance, tests targeting offline deduplication without and with it were conducted. Table 11 presents the results of the former. Since the targeted environment does not find or remove duplicates, either in the critical path or later in time, a boost in performance was expected and is confirmed by the results. For instance, sequential operations that achieved 290 MB/s with inline deduplication, reached 307 MB/s. Uniform and hotspot performance also improved from 275 MB/s and 450 MB/s to 295 MB/s and 475 MB/s, respectively. 5.3. Micro Experiments 40 Mode nProcesses Distribution Throughput (MB/s) Latency (us) Mean SDeviation Mean SDeviation Sequential 1HighPerf 294,69 0,28 12,00 0,00 Kernels 294,76 0,42 12,00 0,00 4HighPerf 293,46 0,62 51,83 0,39 Kernels 294,41 1,33 51,58 0,51 Uniform 1HighPerf 276,10 0,28 12,00 0,00 Kernels 277,08 0,44 12,00 0,00 4HighPerf 273,11 0,44 55,25 0,45 Kernels 274,99 0,58 55,00 0,00 HotSpot 1HighPerf 455,65 2,62 7,00 0,00 Kernels 458,28 3,34 7,00 0,00 4HighPerf 434,81 7,31 34,25 0,62 Kernels 467,51 3,60 31,67 0,49 Table 12: Write Operations with Offline Memory Deduplication with Background Processing Despite exhibiting the best possible performance, the targeted HIODS setup in Table 11 does not find or remove duplicates because offline deduplication requires a background job to do so. Therefore, the background task was activated, and the results are presented in Table 12. As expected, since the secondary job competes for resources with the primary process, a performance drop is noticeable. In fact, the sequential mode that delivered 307 MB/s without the background job could only achieve 294 MB/s with the current system configuration. The same drop was experienced in the remaining modes, which saw their performance drop to 275 MB/s and 450 MB/s from the 295 MB/s and 475 MB/s previously obtained by uniform and hotspot experiments. 5.3. Micro Experiments 41 Mode nProcesses Distribution Throughput (MB/s) Latency (us) Mean SDeviation Mean SDeviation Sequential 1HighPerf 77,02 0,82 49,33 0,58 Kernels 95,39 0,33 39,00 0,00 4HighPerf 77,69 0,15 198,33 0,58 Kernels 96,05 0,11 160,67 0,58 Uniform 1HighPerf 61,25 0,22 62,00 0,00 Kernels 81,71 0,17 46,00 0,00 4HighPerf 60,83 0,04 253,33 1,15 Kernels 81,11 0,21 190,00 0,00 HotSpot 1HighPerf 102,05 22,39 32,00 0,00 Kernels 153,71 2,85 23,33 0,58 4HighPerf 133,15 0,31 113,33 1,53 Kernels 153,62 0,53 99,33 0,58 Table 13: Write Operations with Inline Persistent Deduplication The previous round of tests targeted the memory version of the system. However, a system should not rely on memory to store its data. Therefore, Table 13 reveals the results from the tests performed with inline persistent deduplication. When comparing the memory version (Table 10) with the persistent version (Table 13), it is possible to realize the negative impact that a key-value store like leveldb has on performance. In the former, sequential and uniform performance hovered around 250 to 300 MB/s, and hotspot operations reached 450 MB/s. With these last results, the first two modes dropped to between 60 and 100 MB/s, and hotspot experiments delivered higher results between 100 and 150 MB/s, but still far from the original performance. Furthermore, the performance disparity between highperf and kernels content distributions, which was around 5MB/s in memory experiments, is now close to 20 MB/s. Besides the reduced disk accesses when using the latter, the former has substantially more unique data that must be stored on the Index and Reverse Index, which leads to more leveldb interactions, thus significantly increasing the overhead with the highperf distribution. 5.3. Micro Experiments 42 Mode nProcesses Distribution Throughput (MB/s) Latency (us) Mean SDeviation Mean SDeviation Sequential 1HighPerf 143,13 0,30 26,00 0,00 Kernels 143,53 0,30 26,00 0,00 4HighPerf 143,62 0,18 106,67 0,58 Kernels 143,02 0,28 107,00 0,00 Uniform 1HighPerf 139,81 0,10 26,00 0,00 Kernels 139,99 0,38 26,00 0,00 4HighPerf 139,88 0,21 109,33 0,58 Kernels 140,44 0,14 109,00 0,00 HotSpot 1HighPerf 261,00 0,29 13,00 0,00 Kernels 263,13 1,22 13,00 0,00 4HighPerf 263,40 1,10 57,00 0,00 Kernels 262,46 5,32 57,33 1,53 Table 14: Write Operations with Offline Persistent Deduplication without Background Processing As to observe the real overhead introduced by inline mode, since the system does not live in memory anymore, tests targeting persistent offline deduplication without background processing were executed once again. The results can be seen in Table 14. As expected, a performance boost that reached two times the inline performance is witnessed. For example, sequential operations that achieved around 80 MB/s now reach 143 MB/s. Furthermore, uniform performance also increased from about 71 MB/s to 140 MB/s, and the 100 to 150 MB/s hotspot operations now reach 262 MB/s. Such gains are directly related to the fact that offline mode does not find or remove duplicates in the I/O critical path. However, while the gains were almost negligible when in memory, here, the performance increase reached 50%. These considerable gains relate to the difference in operations between inline and offline, which were not best seen in memory due to its high-speed nature. However, when on leveldb, every operation involving it causes additional overhead, resulting in a much lower performance with inline deduplication. Regarding the results involving the two different distributions, it is clear that the previously seen disparity no longer exists. The gap disappearance relates to the fact that all blocks are written to disk with offline deduplication. Furthermore, as the current target does not find or remove duplicates, the Index and Reverse Index are only consulted for update operations resulting in almost negligible overheads. The existence of updates in uniform mode is also the reason for its slightly lower results when compared to sequential operations. 5.3. Micro Experiments 43 Mode nProcesses Distribution Throughput (MB/s) Latency (us) Mean SDeviation Mean SDeviation Sequential 1HighPerf 60,98 0,61 62,33 0,58 Kernels 81,07 0,38 46,33 0,58 4HighPerf 67,94 2,29 227,67 7,77 Kernels 83,46 0,75 185,33 1,53 Uniform 1HighPerf 47,56 0,23 80,33 0,58 Kernels 71,38 1,02 53,00 1,00 4HighPerf 44,41 0,37 346,67 2,08 Kernels 71,24 0,52 215,33 2,52 HotSpot 1HighPerf 122,25 1,42 30,33 0,58 Kernels 136,87 0,74 27,00 0,00 4HighPerf 114,27 1,02 134,33 1,15 Kernels 129,43 2,26 117,00 2,00 Table 15: Write Operations with Offline Persistent Deduplication with Background Processing One of the most significant downsides of offline deduplication is the need for extra resources. In addition to storage space, since all chunks are stored in the disk, offline deduplication also requires a background job to find and remove duplicates, which competes for resources alongside the foreground job. Table 15 presents the results of offline persistent deduplication with simultaneous background processing. As already seen in the memory version, although more lightly, a 50% drop in performance from the previous results is discerned. For example, sequential performance dropped from 143 MB/s to around 70 MB/s, uniform operations decreased from 140 MB/s to an average of 58 MB/s, and hotspot experiments dropped to 125 MB/s from 263 MB/s. In reality, the competition for resources is so intense that even inline deduplication with all its overhead outperforms it. For example, sequential mode, which reported 75 to 100 MB/s with inline deduplication, only achieves 60 to 80 MB/s with the current setup. A second difference with the previous results is the return of the contrast between distributions that did not exist without background processing. In reality, highperf introduces more unique data into the system, which must be stored on Index and Reverse Index, significantly increasing leveldb accesses in the background job. As such operations are quite costly, the processing power is redirected to the secondary task decreasing the overall system capability. 5.3. Micro Experiments 44 5.3.1.3Feedback Loop Controller Unlike inline deduplication, where redundant data is found and eliminated directly in the I/O critical path, offline mode requires a secondary process to achieve the same goal. However, as the secondary job also requires resources to find and eliminate duplicate data, the total system capacity must be shared between the two. This split of resources may cause a decrease in the primary process performance, which we witnessed in the previous experiments (Table 15). As to reduce the background process activity, which releases resources to the primary job, increasing its overall performance, HIODS implements a Feedback Loop Controller mechanism capable of regulating the secondary job throughput, thus helping to reach and maintain the performance goal. Mode nProcesses Distribution Throughput (MB/s) Latency (us) Mean SDeviation Mean SDeviation Sequential 1HighPerf 117,98 0,62 31,67 0,58 Kernels 119,89 1,65 30,67 0,58 4HighPerf 118,29 0,41 129,67 0,58 Kernels 120,34 0,04 127,00 0,00 Uniform 1HighPerf 123,03 0,25 30,00 0,00 Kernels 123,41 0,26 30,00 0,00 4HighPerf 123,66 0,47 124,00 1,00 Kernels 124,17 0,26 123,67 0,58 HotSpot 1HighPerf 241,22 2,21 14,33 0,58 Kernels 248,61 1,53 14,00 0,00 4HighPerf 247,50 0,61 60,33 0,58 Kernels 250,84 0,13 60,00 0,00 Table 16: Write Operations with Offline Persistent Deduplication with Feedback Loop Controller Analyzing the results presented in Table 16, we can conclude that this FLC mechanism, capable of limiting the background job throughput, is vital in helping HIODS reach and maintain the desired performance. In fact, the sequential and uniform results without the FLC achieved between 60 to 80 MB/s but, with the current strategy, measurements between 118 and 125 MB/s were reached. Despite the good results, the tests show that the FLC is not being aggressive enough because it did not reach the goal set to 35000 operations per second (136,72 MB/s) with the following parameters: kp=5.0 , ki=0.001 , and kd=0.25 . However, fixing the lack 6 CONCLUSION This dissertation presents HIODS, a hybrid inline and offline deduplication system capable of dynamically switching between inline and offline modes to achieve and maintain the desired performance goals of distinct applications. When analyzing the state of the art it is possible to conclude that some systems already leverage both deduplication modes. However, these systems present new algorithms and mechanisms whose main objective is only to mitigate the overhead introduced by inline deduplication. For example, DIODE and D3classify the input file into three types based on its extension degree of deduplication. Such classification is then used to determine the best deduplication mode for the file. Therefore, in a general fashion, these systems identify the best candidates to inline deduplication, leaving the remaining ones, which may cause extra performance interference, to be dealt in background. The deduplication system designed in this dissertation aims differently. While the previous systems decide the best operation mode according to each request ' s data to efficiently perform inline deduplication, HIODS bases its decision on the performance goals of applications using the storage system to choose the best deduplication mode. In order to achieve the proposed goal, the system relies on a performance objective that must be achieved and maintained to keep inline deduplication operating. In the cases where the overhead introduced by the inline mode does not allow achieving the proposed objective, the offline mode is chosen. Furthermore, HIODS also introduces a second mechanism based on Feedback Loop Controllers that limits the background deduplication job to reduce the interference with critical I/O operations and, again, achieve the desired application performance. Following the design of the system, a prototype was implemented using SPDK. This prototype implements both inline and offline deduplication, the switching mechanism, and the Feedback Loop Controller (FLC) capable of rate limiting offline deduplication. To summarize these components, inline deduplication processes the storage request in the I/O critical path introducing additional overhead but only storing unique copies. On the other hand, the offline mode only performs the required procedures for later processing, thus reducing to the minimum the overhead in the I/O critical path but storing all data, unique or duplicate. Periodically, the switching mechanism analyses the current and desired 51 6.1. Future Work 52 performances and decides if the operation mode should change or not. Finally, suppose the offline mode is active, and the performance goal is still not being reached. In that case, the FLC delays the background deduplication processing, reducing the competition for resources between deduplication and I/O operations and, therefore, increasing storage I/O performance. In order to evaluate the mechanisms introduced in HIODS, a series of experiments were designed and executed. The results show that HIODS successfully changed its operation mode based on the system workload and performance objective. Furthermore, it was also possible to conclude that the FLC mechanism plays a vital role in helping HIODS reach and maintain the desired performance. In conclusion, this dissertation introduces a system capable of dynamically changing its deduplication mode to reach and maintain the performance requirements of applications. 6.1 future work Since deduplication introduces additional performance costs, finding and removing duplicates directly in the I/O critical path or preparing the data for later processing, the optimization of both operation modes allows for lower overheads and higher performance. Implementing mechanisms capable of taking advantage of data locality, or more complex indexes with lower access times are a few examples of possible optimizations. A second improvement in the system would be developing an alternative to persistently store the deduplication metadata. As observable in the micro experiments, the transition from memory to a persistent implementation with leveldb brought significant performance overhead. A possible solution would be to store this metadata directly on a disk partition while using SPDK to do it. Also, despite the promising results shown by the Feedback Loop Controller mechanism, the system may benefit from research regarding its parameters, kp , ki , and kd . Finally, the switch from offline to inline deduplication causes a burst of background deduplication operations. This burst can interfere with the foreground I/O operations, so a new mechanism capable of limiting such processing may also be an asset to HIODS. BIBLIOGRAPHY [1] Abhishek Mukherjee, Alvin Afuang, Bill Rojas, Hugh Ujhazy, and Theresa Rago. Iot growth demands rethink of long-term storage strategies, says idc. Technical report, International Data Corporation, July 2020. [2] David Reinsel, John Gantz, and John Rydning. Data age 2025: The evolution of data to life-critical. Technical report, International Data Corporation, November 2018. [3] 451 Research. 69% of enterprises will have multi-cloud/hybrid it environments by 2019, but greater choice brings excessive complexity. Technical report, 451 Research, New York (NY) and Las Vegas (LV), November 2017. [4] Aayushi Vernika Das, Delisha Clair Sequeira, Gulshan Damini Patel, and V R Srividhya. A survey on deduplication techniques in cloud storage with cryptographic techniques. In 2017 International Conference on Pervasive Computing and Networking. International Journal of Engineering Research & Technology (IJERT), 2017. [5] Youngjoo Shin, Dongyoung Koo, and Junbeom Hur. A survey of secure data deduplication schemes for cloud storage systems. ACM Computing Surveys,49(4):1–38, February 2017. [6] Dirk Meister, Jurgen Kaiser, Andre Brinkmann, Toni Cortes, Michael Kuhn, and Julian Kunkel. A study on data deduplication in HPC storage systems. In 2012 International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, November 2012. [7] Jo ˜ ao Paulo and Jos ´ e Pereira. A survey and classification of storage deduplication systems. ACM Comput. Sur. 47,1, Article 11, page 30 pages, may 2014. [8] Ziye Yang, James R. Harris, Benjamin Walker, Daniel Verkamp, Changpeng Liu, Cunyin Chang, Gang Cao, Jonathan Stern, Vishal Verma, and Luse E. Paul. SPDK: A development kit to build high performance storage applications. In 2017 IEEE International Conference on Cloud Computing Technology and Science (CloudCom). IEEE, December 2017. [9] William J Bolosky, Scott Corbin, David Goebel, and John R Douceur. Single instance storage in windows 2000. In Proceedings of the 4th USENIX Windows Systems Symposium, pages 13–24. Seattle, WA, 2000. 53 bibliography 54 [10] Calicrates Policroniades and Ian Pratt. Alternatives for detecting redundancy in storage systems data. In USENIX Annual Technical Conference, General Track, pages 73–86,2004. [11] Sean Quinlan and Sean Dorward. Venti: A new approach to archival storage. In FAST, volume 2, pages 89–101,2002. [12] Bo Hong, Demyn Plantenberg, Darrell DE Long, and Miriam Sivan-Zimet. Duplicate data elimination in a san file system. In MSST, pages 301–314,2004. [13] Michal Kaczmarczyk, Marcin Barczynski, Wojciech Kilian, and Cezary Dubnicki. Reducing impact of data fragmentation caused by in-line deduplication. In Proceedings of the 5th Annual International Systems and Storage Conference, pages 1–12,2012. [14] Kave Eshghi and Hsiu Khuern Tang. A framework for analyzing and improving content-based chunking algorithms. Hewlett-Packard Labs Technical Report TR,30(2005), 2005. [15] Athicha Muthitacharoen, Benjie Chen, and David Mazieres. A low-bandwidth network file system. In Proceedings of the eighteenth ACM symposium on Operating systems principles, pages 174–187,2001. [16] Sean C Rhea, Russ Cox, and Alex Pesterev. Fast, inexpensive content-addressed storage in foundation. In USENIX Annual Technical Conference, pages 143–156,2008. [17] Benjamin Zhu, Kai Li, and R Hugo Patterson. Avoiding the disk bottleneck in the data domain deduplication file system. In Fast, volume 8, pages 1–14,2008. [18] Cristian Ungureanu, Benjamin Atkin, Akshat Aranya, Salil Gokhale, Stephen Rago, Grzegorz Calkowski, Cezary Dubnicki, and Aniruddha Bohra. Hydrafs: A highthroughput file system for the hydrastor content-addressable storage system. In FAST, volume 10, pages 225–239,2010. [19] Kiran Srinivasan, Timothy Bisson, Garth R Goodson, and Kaladhar Voruganti. iDedup: latency-aware, inline data deduplication for primary storage. In Fast, volume 12, pages 1–14,2012. [20] Mark Lillibridge, Kave Eshghi, Deepavali Bhagwat, Vinay Deolalikar, Greg Trezis, and Peter Camble. Sparse indexing: Large scale, inline deduplication using sampling and locality. In Fast, volume 9, pages 111–123,2009. [21] Deepavali Bhagwat, Kave Eshghi, Darrell DE Long, and Mark Lillibridge. Extreme binning: Scalable, parallel deduplication for chunk-based file backup. In 2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems, pages 1–9. IEEE, 2009. bibliography 55 [22] Fanglu Guo and Petros Efstathopoulos. Building a high-performance deduplication system. In USENIX annual technical conference,2011. [23] Feng Chen, Tian Luo, and Xiaodong Zhang. Caftl: A content-aware flash translation layer enhancing the lifespan of flash memory based solid state drives. In FAST, volume 11, pages 77–90,2011. [24] Aayush Gupta, Raghav Pisolkar, Bhuvan Urgaonkar, and Anand Sivasubramaniam. Leveraging value locality in optimizing nand flash-based ssds. In FAST, pages 91–103, 2011. [25] Jonghwa Kim, Choonghyun Lee, Sangyup Lee, Ikjoon Son, Jongmoo Choi, Sungroh Yoon, Hu-ung Lee, Sooyong Kang, Youjip Won, and Jaehyuk Cha. Deduplication in ssds: Model and quantitative analysis. In 012 IEEE 28th Symposium on Mass Storage Systems and Technologies (MSST), pages 1–12. IEEE, 2012. [26] Cezary Dubnicki, Leszek Gryz, Lukasz Heldt, Michal Kaczmarczyk, Wojciech Kilian, Przemyslaw Strzelczak, Jerzy Szczepkowski, Cristian Ungureanu, and Michal Welnicki. Hydrastor: A scalable secondary storage. In FAST, volume 9, pages 197–210,2009. [27] Tian-Ming Yang, Dan Feng, Zhong-ying Niu, and Ya-ping Wan. Scalable high performance de-duplication backup via hash join. Journal of Zhejiang University SCIENCE C, 11(5):315–327,2010. [28] Austin T Clements, Irfan Ahmad, Murali Vilayannur, Jinyuan Li, et al. Decentralized deduplication in san cluster file systems. In USENIX annual technical conference, pages 101–114,2009. [29] Lior Aronovich, Ron Asher, Eitan Bachmat, Haim Bitner, Michael Hirsch, and Shmuel T Klein. The design of a similarity based deduplication system. In Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference, pages 1–14,2009. [30] Randal C Burns and Darrell DE Long. Efficient distributed backup with delta compression. In Proceedings of the fifth workshop on I/O in parallel and distributed systems, pages 27–36,1997. [31] Lawrence You and Christos T Karamanolis. Evaluation of efficient archival storage techniques. In MSST, pages 227–232,2004. [32] Lawrence L You, Kristal T Pollack, and Darrell DE Long. Deep store: An archival storage system architecture. In 21st International Conference on Data Engineering (ICDE’05), pages 804–815. IEEE, 2005. bibliography 56 [33] John R Douceur, Atul Adya, William J Bolosky, P Simon, and Marvin Theimer. Reclaiming space from duplicate files in a serverless distributed file system. In Proceedings 22nd international conference on distributed computing systems, pages 617–624. IEEE, 2002. [34] Yan Tang, Jianwei Yin, Shuiguang Deng, and Ying Li. DIODE: Dynamic Inline-Offline DEduplication providing efficient space-saving and read/write performance for primary storage systems. In 2016 IEEE 24th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS). IEEE, September 2016. [35] Bo Mao, Hong Jiang, Suzhen Wu, and Lei Tian. POD: Performance oriented i/o deduplication for primary storage systems in the cloud. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium. IEEE, May 2014. [36] Jianwei Yin, Yan Tang, Shuiguang Deng, Ying Li, and Albert Y. Zomaya. D3: A dynamic dual-phase deduplication framework for distributed primary storage. IEEE Transactions on Computers,67(2):193–207, February 2018. [37] Huijun Wu, Chen Wang, Yinjin Fu, Sherif Sakr, Liming Zhu, and Kai Lu. HPDedup: A hybrid prioritized data deduplication mechanism for primary storage in the cloud, 2017. [38] Amdewar Godavari, Chapram Sudhakar, and T. Ramesh. Hybrid Deduplication System—a block-level similarity-based approach. IEEE Systems Journal, pages 1–11,2020. [39] Jay Lofstead, Milo Polte, Garth Gibson, Scott Klasky, Karsten Schwan, Ron Oldfield, Matthew Wolf, and Qing Liu. Six degrees of scientific data: reading patterns for extreme scale science io. In Proceedings of the 20th international symposium on High performance distributed computing, pages 49–60,2011. [40] Ahmed El-Shimi, Ran Kalach, Ankit Kumar, Adi Ottean, Jin Li, and Sudipta Sengupta. Primary data deduplication—large scale study and system design. In Presented as part of the 2012 USENIX Annual Technical Conference (USENIX ATC 12), pages 285–296,2012. [41] Sonam Mandal, Geoff Kuenning, Dongju Ok, Varun Shastry, Philip Shilane, Sun Zhen, Vasily Tarasov, and Erez Zadok. Using hints to improve inline block-layer deduplication. In 14th USENIX Conference on File and Storage Technologies (FAST 16), pages 315–322, 2016. [42] Network block device. https://nbd.sourceforge.io/. Accessed: 18-12-2020. [43] Glib reference manual. https://developer.gnome.org/glib/. Accessed: 18-12-2020. [44] Google. google/leveldb. https://github.com/google/leveldb. Accessed: 18-12-2020. bibliography 57 [45] Vineet Kumar, BC Nakra, and AP Mittal. A review on classical and fuzzy pid controllers. International Journal of Intelligent Control and Systems,16(3):170–181,2011. [46] JTPaulo. jtpaulo/dedisbench. https://github.com/jtpaulo/dedisbench . Accessed: 18-122020. [47] dstat. https://linux.die.net/man/1/dstat. Accessed: 18-12-2020.