As a technique for achieving effective utilization of the storage capacity of a storage (storage device), a technique called, e.g., data redundancy elimination or redundancy exclusion that does not store redundant data in the storage is known. In an apparatus for data redundancy elimination, a Bloom filter or a multi-layer Bloom filter is generally used to determine whether pieces of data are redundant.
A multi-layer Bloom filter has a data structure with multiple layers of Bloom filters. The multi-layer Bloom filter has a function of searching for a storage region (address range) where data is stored. Although use of a multi-layer Bloom filter allows high-speed data redundancy elimination, the size of a multi-layer Bloom filter used for data management increases with an increase in storage size. For this reason, when a multi-layer Bloom filter is used, an apparatus is equipped with a relatively large capacity memory.
For further information, refer to Japanese Patent Laid-Open Publication No. 2011-186954, Japanese Patent Laid-Open Publication No. 2012-094220, International Publication No. WO 2010/100733, and T. Johnson and Dennis Shasha, “2Q: A Low Overhead High Performance Buffer Replacement Algorithm,” Very Large Database Systems Conference 1994, September, 1994.