Storage controller, storage device, data processing method, and computer program product
According to an embodiment, a storage controller comprises a circuitry configured to implement an address generator, a reader, and a duplication detector. The address generator is configured to generate a scan address indicating each storage area of a storage that stores therein externally written data, according to a particular scan pattern for defining an order of an address of data to be read. The reader is configured to read data from the storage area of the storage indicated by the scan address. The duplication detector is configured to detect whether the data read by the reader is a duplicate of any one of a past predetermined number of pieces of data.
1. A storage controller comprising:
a circuitry configured to implement:
an address generator configured to generate a scan address, which is one of discontinuous addresses indicating storage areas of a first storage that store therein externally written data, according to a particular scan pattern for defining an order of an address of data to be read;
a reader configured to read data from a storage area of the storage areas of the first storage indicated by a scan address of the scan addresses;
a duplication detector configured to detect whether the data read by the reader is a duplicate of any one of pieces of data in the first storage by detecting whether a hash value of the data read by the reader is a duplicate of any one of hash values of a past predetermined number of pieces of data, wherein
the reader reads the data in a unit of a predetermined size from the storage area of the first storage indicated by the scan address;
the duplication detector includes:
a hash generator configured to generate the hash value from the data having the predetermined size read by the reader,
an acquirer configured to acquire location information corresponding to information indicating part of the hash value generated by the hash generator from second information in which information indicating part of the hash value and location information indicating a location in first information including the hash values of the predetermined number of pieces of data are associated with each other, the first information being stored in a second storage, and
a searcher configured to conduct a linear search from the location in the first information indicated by the location information acquired by the acquirer for a hash value identical to the hash value generated by the hash generator, to detect whether there is a duplicate of the data having the predetermined size read by the reader;
after the duplication detection by the duplication detector, the address generator updates the scan address according to the particular scan pattern to indicate another storage area of the first storage that is a new target of the duplication detection, the updated scan address being one of the discontinuous addresses,
the storage controller further comprises a pattern updater configured to perform an update to a different scan pattern from the particular scan pattern after the duplication detector performs duplication detection for data in every storage area of the first storage, the duplication detection been performed using the particular scan pattern, and
the storage controller further comprises an adder configured to add, when the duplication detector detects that the data read by the reader is not in duplicate, the hash value to the first information.
2. The storage controller according to claim 1 , wherein the first storage is a NAND-type flash memory.
3. The storage controller according to claim 1 , wherein the duplication detector detects whether the hash value of the data read by the reader is a duplicate of any one of the hash value of the predetermined number of pieces of data having a number smaller than the number of all pieces of data stored in the first storage.
4. The storage controller according to claim 1 , wherein
the first storage stores therein the externally written data and an error correcting code of the data, and
the duplication detector uses the error correcting code of the data having the predetermined size as the hash value.
5. The storage controller according to claim 1 , further comprising a duplication remover configured to, when the duplication detector detects that the data read by the reader is in duplicate, invalidate any one of the data read by the reader and duplicate data of the data so as to remove duplication.
6. The storage controller according to claim 1 , further comprising a notifier configured to, when the duplication detector detects that the data read by the reader is in duplicate, notify a controller that accesses the first storage of information indicating which data is in duplicate.
7. The storage controller according to claim 1 , further comprising:
an error detector configured to calculate an error rate of the data read by the reader, and detect that the data has an error when the error rate is equal to or greater than a predetermined value; and
a rewriter configured to rewrite the data in which the error detector detects an error into a different storage area from a storage area in which the data is stored in the first storage.
8. A storage device comprising:
the first storage; and
the storage controller according to claim 1 .
9. A storage controller comprising:
a circuitry configured to implement:
an address generator configured to generate a scan address, which is one of discontinuous addresses indicating storage areas of a storage that store therein externally written data, according to a particular scan pattern for defining an order of address of data to be read;
a reader configured to read data from the storage area of the storage indicated by the scan address;
a duplication detector configured to detect whether the data read by the reader is a duplicate of any one of a past predetermined number of pieces of data; wherein
after the duplication detection by the duplication detector, the address generator updates the scan address according to the particular scan pattern to indicate another storage area of the storage that is a new target of the duplication detection, the updated scan address being one of the discontinuous addresses; and
a pattern updater configured to perform an update to a different scan pattern from the particular scan pattern after the duplication detector performs duplication detection for data in every storage area of the storage, the duplication detection been performed using the particular scan pattern, wherein
the address generator generates a scan address according to the different scan pattern,
the reader reads the data in a unit of a predetermined size from the storage area of the storage indicated by the scan address; and
the duplication detector includes:
a hash generator configured to generate a hash value from the data having the predetermined size read by the reader,
an acquirer configured to acquire location information corresponding to information indicating part of the hash value generated by the hash generator from second information in which information indicating part of the hash value and location information indicating a location in first information including the predetermined number of pieces of data are associated with each other, and
a searcher configured to conduct a linear search from the location in the first information indicated by the location information acquired by the acquirer for a hash value identical to the hash value generated by the hash generator, to detect whether there is a duplicate of the data having the predetermined size read by the reader.
10. The storage controller according to claim 9 , wherein the duplication detector detects whether the data read by the reader is a duplicate of any one of the predetermined number of pieces of data having a number smaller than the number of all pieces of data stored in the storage.
11. The storage controller according to claim 9 , wherein
the storage stores therein the externally written data and an error correcting code of the data, and
the duplication detector uses the error correcting code of the data having the predetermined size as the hash value.
12. The storage controller according to claim 9 , further comprising a duplication remover configured to, when the duplication detector detects that the data read by the reader is in duplicate, invalidate any one of the data read by the reader and duplicate data of the data to remove duplication.
13. The storage controller according to claim 9 , further comprising a notifier configured to, when the duplication detector detects that the data read by the reader is in duplicate, notify a controller that accesses the storage of information indicating which data is in duplicate.