Shulou(Shulou.com)06/03 Report--

Second, the principle of dm dedup

The code of dmdedup on github:

Https://github.com/dmdedup/dmdedup4.13

Design document

Http://www.fsl.cs.stonybrook.edu/docs/ols-dmdedup/dmdedup-ols14.pdf

Author:

Dm-dedup was developed in the File system and Storage Lab (FSL) at Stony Brook University Computer Science Department, in collaboration with Harvey Mudd College and Dell-EMC.

Key people involved in the project were Vasily Tarasov, Geoff Kuenning, Sonam Mandal, Karthikeyani Palanisami, Philip Shilane, Sagar Trehan, and Erez Zadok.

We also acknowledge the help of several students involved in the deduplication project: Teo Asinari, Deepak Jain, Mandar Joshi, Atul Karmarkar, Gary Lent, Amar Mudrankit, Meg O'Keefe, Nidhi Panpalia, Vinothkumar Raja, Ujwala Tulshigiri and Nabil Zaman.

The above is the existing information, you can also directly under the source code and look at the original design documents.

I'm going to start directly, starting with its design:

The design idea of dmdedup is actually very simple, and you can see three main logic from the diagram:

1 、 hash index

2 、 LBN Mapping

3 、 space manager

1.hash index, first of all, dm dmdedup supports many hash algorithms, so we need to understand the collision probability generated by hash index.

To put it simply, the approximate probability of the algorithm generating hash collisions is as follows:

For n hash 128s, the probability of hash collisions is

P = (1, 2, 3, 3). + (nmai 1)) × r = (1pm 2) × n × (nmai 1) × r

If hash 128 is substituted by md5,r=1/2e128, the probability of repetition is:

P = (1max 2) × n × (n Mel 1) x (1/2e128).

The probability of data errors generated by the hard disk is 10 ^-18 ~ 10 ^ 15. If p n = (1par 3) x 10 ^ 20 is about 10 ^ 10, if each data block is 4k on average, it can represent about 37TB. In the original paper, it is said that there is 100TB. I am here for a rough calculation, that is, the total amount of data in a re-deleted set can be established.

If we are familiar with the principle of its hash index, we can establish it, as long as the data range is less than that described in the paper: 100TB.

You can use hash index to describe the relationship between hash to pbn.

LBN mapping logical block number mapping, if hash index describes all existing PBN (physical blocks), then LBN mapping describes all meaningful PBN,LBN mapping which should be familiar to everyone. He describes the mapping of logical blocks to physical blocks, which is widely used in Thin provisioning, another module of dm.

3.space manager space manager, well, if hash index and LBN mapping are not enough for you to understand the principle of dedup, then after space manager, it seems to be a little clearer.

The three combinations we just talked about here combine them into a set of logical mappings.

This logical process is roughly divided into three steps:

1. Chunk DATA, which is the most commonly used method in block-level mapping: chunking. It is widely used in raid and snapshots. In order to record the changed data clearly, the sliced data can be directly represented by its lba, so that the changed data has its unique domain.

Chunk way to split each request at the chunk boundary (for example: {lba:3k,size:4k}-> {lba:3k,size=1k} + {lba:4k,size=3k})

2. For the request after chunk data, we need to calculate the HASH of the data and find out whether the HASH already exists.

If it exists, it means that we already have this data, if not, we need to apply for a chunk-sized block from spare manager to place the request and calculate and save its hash value.

The role of hash index is mainly used to describe whether a hash-PBN already exists (that is, the data content is the same).

3. Next is the case of LBN, where there are four situations:

The first step is to introduce the need for another LBN MAP,LBN-PBN correspondence, which can be understood as the mapping table of virtual devices with re-deletion function.

① no hash & & no lbn, this means that no hash-PBN is found and no LBN-PBN is found, that is, the data content of this request is unseen, and the location in which it is to be placed is new and has not been accessed before. Usually this produces new files and new content. The next step is to generate and record all the new hash index and LBN you need.

② no hash & & lba, which means that hash-PBN does not exist, but LBN-PBN exists, indicating that some LBN data has been changed to new content, because our hash window is of fixed length (4k or 8k), so this situation is more common. As long as the data modified by the application layer is less than 4k, such as our documentation and code work. When this happens, the program needs to replace the former LBN-oldPBN with a new LBN-newPBN, and the refcount-1 of hash index represents that we have one less mapping on this existing hash-PBN, then this hash-PBN is likely to become an orphan, without LBN and its map, but the program is in no hurry to release it, hoping it can be used by the situation ③.

③ hash & & no lba, in this case, shows that what you want most, in this case, you only need to add a mapping of LBN-PBN and quote + 1 of PBN, that is, you can save a BLOCK space. This is the place that best reflects the value of the re-deletion program, saving the actual space.

④ hash & & lba, this situation means that the data content of request exists, and the LBA to be accessed also exists, but this does not mean that the data must not have changed, because the existence of hash-PBN is only the same as the content of a physical block and request, but it does not mean that there was memory in the LBA, so it is also necessary to judge whether it is the same content in the former LBA. Then you need to compare the PBN-number of LBN-PBN? = hash-PBN), put PBN-old refcount-1 and PBN-new refcount+1 if different, and update the LBN-PBN. This is usually the case when batch files are synchronized / overwritten under a system, in which case the references of copy An and copy B remain unchanged, and the logical mapping relationship changes.

[this article is only posted by 51cto blogger "underlying Storage Technology" https://blog.51cto.com/12580077, official account release: storage Valley], if you need to reprint, please contact me, thank you.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.