Hash-based replication using short hash handle and identity bit

Patent metadata

Field	Value
Publication number	US-9396243-B1
Application number	US-201414317449-A
Country	US
Kind code	B1
Filing date	Jun 27, 2014
Priority date	Jun 27, 2014
Publication date	Jul 19, 2016
Grant date	Jul 19, 2016

Abstract

In one aspect, a method includes sending a first short hash handle and a first identity bit associated with the first short hash handle to a replication site, determining if a second hash handle is identical to the first short hash handle, determining if a second identity bit associated with the second short hash handle at the replication is set if the second short hash handle is identical to the first short hash handle and using the second hash handle to identify the data if the second identity bit being is set. The first short hash handle is an identifier of data stored on a disk.

First claim

What is claimed is:

1. A method comprising:
sending a first short hash handle and a first identity bit associated with the first short hash handle to a replication site, wherein a short hash handle is generated using a full hash having n bits and the short hash handle is a lowest n−1 bits of the full hash, the full hash is hash of data on a disk;
determining if a second short hash handle at the replication site is identical to the first short hash handle;
determining if a second identity bit associated with the second short hash handle at the replication site is set in response to the second short hash handle being identical to the first short hash handle;
using the second hash handle to identify data on the disk in response to the second identity bit being set;
in response to the second short hash handle not being identical to the first short hash handle and the first identity bit not being set:
reading a first full hash from a production site;
sending the first full hash to the replication site;
determining if a second full hash is identical to the first full hash;
writing a third short hash handle in response to the second full hash being identical to the first full hash;
determining if the second full hash is pointed to by the same short hash handle as the first short hash handle in response to the second full hash being identical to the first full hash; and
setting a third identity bit in response to the second full hash being pointed to by the same short hash handle as the first short hash handle.

2. The method of claim 1 , further comprising setting the first identity bit if the first short hash handle exists at the replication site.

3. The method of claim 1 , further comprising reading the data from the disk and sending the data to the replication site if the first short hash handle does not exist at the replication site.

4. An apparatus comprising:
electronic hardware circuitry configured to:
send a first short hash handle and a first identity bit associated with the first short hash handle to a replication site, wherein a short hash handle is generated using a full hash having n bits and the short hash handle is a lowest n−1 bits of the full hash, the full hash is hash of data on a disk;
determine if a second short hash handle at the replication site is identical to the first short hash handle;
determine if a second identity bit associated with the second short hash handle at the replication site is set in response to the second short hash handle being identical to the first short hash handle; and
use the second hash handle to identify data on the disk in response to the second identity bit being set;
in response to the second short hash handle not being identical to the first short hash handle and the first identity bit not being set:
read a first full hash from a production site;
send the first full hash to the replication site;
determine if a second full hash is identical to the first full hash;
write a third short hash handle in response to the second full hash being identical to the first full hash;
determine if the second full hash is pointed to by the same short hash handle as the first short hash handle in response to the second full hash being identical to the first full hash; and
set a third identity bit in response to the second full hash being pointed to by the same short hash handle as the first short hash handle.

5. The apparatus of claim 4 wherein the circuitry comprises at least one of a processor, a memory, a programmable logic device or a logic gate.

6. The apparatus of claim 4 , further comprising circuitry configured to set the first identity bit if the first short hash handle exists at the replication site.

7. The apparatus of claim 4 , further comprising circuitry configured to read the data from the disk and sending the data to the replication site if the first short hash handle does not exist at the replication site.

8. An article comprising:
a non-transitory computer-readable medium that stores computer-executable instructions, the instructions causing a machine to:
send a first short hash handle and a first identity bit associated with the first short hash handle to a replication site, wherein a short hash handle is generated using a full hash having n bits and the short hash handle is a lowest n−1 bits of the full hash, the full hash is hash of data on a disk;
determine if a second short hash handle at the replication site is identical to the first short hash handle;
determine if a second identity bit associated with the second short hash handle at the replication site is set in response to the second short hash handle being identical to the first short hash handle; and
use the second hash handle to identify data on the disk in response to the second identity bit being set
in response to the second short hash handle not being identical to the first short hash handle and the first identity bit not being set:
read a first full hash from a production site;
send the first full hash to the replication site;
determine if a second full hash is identical to the first full hash;
write a third short hash handle in response to the second full hash being identical to the first full hash;
determine if the second full hash is pointed to by the same short hash handle as the first short hash handle in response to the second full hash being identical to the first full hash; and
set a third identity bit in response to the second full hash being pointed to by the same short hash handle as the first short hash handle.

9. The article of claim 8 , further comprising instructions causing the machine to set the first identity bit if the first short hash handle exists at the replication site.

10. The article of claim 8 , further comprising instructions causing the machine to read the data from the disk and sending the data to the replication site if the first short hash handle does not exist at the replication site.

Assignees

• Emc Corp

Inventors

• Halevi Ido
• Meiri David

Classifications

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F3/065 Primary

  Replication mechanisms · CPC title

• G06F3/0608 Primary

  Saving storage space on storage systems · CPC title

• G06F16/137

  Hash-based (content-based indexing of textual data G06F16/31) · CPC title

• G06F16/2365

  Ensuring data consistency and integrity · CPC title