DETAILED ACTION
This office action is in response to the above identified application filed on January 24, 2025. The application contains claims 1-20.
Claims 1-20 are pending
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Information Disclosure Statement
The information disclosure statement (IDS) was submitted on 04/15/2026. The submission is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Claim Objections
Claims 1, 4, 5, 11, 12, 15, 18, and 19 are objected to because of the following informalities:
Claim 1, line 1: “garbage collect” should read “garbage collection”.
Claim 4, lines 1-2: “by selecting the last N bytes in the first letter of the first word” should read “by selecting the last N bytes in the first letter of the first word of the suffixed fingerprint” for clarity
Claim 5, line 9: “the CIDs” should read “the CIDs of the multiple suffixed fingerprints” for clarity.
Claim 11, line 2: “by selecting the last N bytes in the first letter of the first word” should read “by selecting the last N bytes in the first letter of the first word of the suffixed fingerprint” for clarity
Claim 12, line 9: “the CIDs” should read “the CIDs of the multiple suffixed fingerprints” for clarity.
Claim 15, line 12: “garbage collect” should read “garbage collection”.
Claim 18, lines 1-2: “by selecting the last N bytes in the first letter of the first word” should read “by selecting the last N bytes in the first letter of the first word of the suffixed fingerprint” for clarity
Claim 19, line 9: “the CIDs” should read “the CIDs of the multiple suffixed fingerprints” for clarity.
Appropriate correction is required.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless -
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-3, 7-10, and 14-17 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Wallace (US 20190171563 A1).
With respect to claim 1,
Wallace teaches
a method for identifying dead segments for garbage collect (Abstract), the method comprising:
selecting a suffixed fingerprint from a bucket (Fig. 4; [0061]: use a fingerprint index (FP index 414), or a memory resident cache of the fingerprint index, to determine a set of fingerprint and container identifier (CID) pairs 418 that references the newest container that includes a copy of each storage segment referenced by the fingerprint. The determining includes “selecting” a FP index from FP index 414. Fig. 3; [0057]: the fingerprint index 302 stores fingerprint data in the form of fingerprint and container identifier pairs (e.g., <FP,CID>) which associate a fingerprint with a container identifier storing the storage segment associated with the fingerprint. The fingerprint associated with a container identifier reads on “suffixed fingerprint” and FP index 414 corresponds to “a bucket” under BRI);
making a first determination that the suffixed fingerprint is live using a live filter (Fig. 4; [0061]: determine a set of fingerprint and container identifier (CID) pairs 418 that references the newest container that includes a copy of each storage segment referenced by the fingerprint in the live fingerprint Bloom filters 408 and identifies the live instance of a data segment that is in use in the directory/file tree 412);
based on the first determining, making a second determination that a container identification number (CID) associated with the suffixed fingerprint is higher than a cached fingerprint in a live instance filter (Fig. 4; [0061]-[0062]: determine a set of fingerprint and container identifier (CID) pairs 418 that references the newest container that includes a copy of each storage segment referenced by the fingerprint in the live fingerprint Bloom filters 408, wherein determining the newest container teaches “higher than …”);
based on the second determining, replacing the cached fingerprint in the live instance filter with the suffixed fingerprint (Fig. 4; [0062]: insert the set of <FP, CID> pairs into a set of live-instance Bloom filters 410 that can be queried during the copy-forward process); and
marking everything not in the live instance filter as available for garbage collection (Fig. 4; [0062]: once all the live data segments in a container have been copied forward to a new container, the container is deleted and the space reclaimed, i.e., available for garbage collection).
With respect to claim 2,
Wallace further teaches
the method of claim 1, wherein the suffixed fingerprint comprises a fingerprint and a container identifier (CID) (Fig. 3; [0057]: the fingerprint index 302 stores fingerprint data in the form of fingerprint and container identifier pairs (e.g., <FP,CID>) which associate a fingerprint with a container identifier storing the storage segment associated with the fingerprint).
With respect to claim 3,
Wallace further teaches
the method of claim 1, wherein the bucket containing the suffixed fingerprint is part of a plurality of buckets (Fig. 6; [0073]: each Bloom filter in the set of Bloom filters may be associated with a separate virtual or physical computational node, where each node processes fingerprints within an assigned range and each Bloom filter stores fingerprints within the assigned range, wherein fingerprints within an assigned range indicates “a plurality of buckets”).
With respect to claim 7,
Wallace further teaches
the method of claim 1, wherein the live filter is a bloom filter (Fig. 4; [0061]: live fingerprint Bloom filters 408).
With respect to claim 8,
Wallace teaches
a non-transitory computer readable medium comprising computer readable program code, which when executed by a computer processor (Fig. 22: 2201 processor(s)) enables the computer processor to perform a method for managing data in a storage system (Abstract), the method comprising:
selecting a suffixed fingerprint from a bucket (Fig. 4; [0061]: use a fingerprint index (FP index 414), or a memory resident cache of the fingerprint index, to determine a set of fingerprint and container identifier (CID) pairs 418 that references the newest container that includes a copy of each storage segment referenced by the fingerprint. The determining includes “selecting” a FP index from FP index 414. Fig. 3; [0057]: the fingerprint index 302 stores fingerprint data in the form of fingerprint and container identifier pairs (e.g., <FP,CID>) which associate a fingerprint with a container identifier storing the storage segment associated with the fingerprint. The fingerprint associated with a container identifier reads on “suffixed fingerprint” and FP index 414 corresponds to “a bucket” under BRI);
making a first determination that the suffixed fingerprint is live using a live filter (Fig. 4; [0061]: determine a set of fingerprint and container identifier (CID) pairs 418 that references the newest container that includes a copy of each storage segment referenced by the fingerprint in the live fingerprint Bloom filters 408 and identifies the live instance of a data segment that is in use in the directory/file tree 412);
based on the first determining, making a second determination that a container identification number (CID) associated with the suffixed fingerprint is higher than a cached fingerprint in a live instance filter (Fig. 4; [0061]-[0062]: determine a set of fingerprint and container identifier (CID) pairs 418 that references the newest container that includes a copy of each storage segment referenced by the fingerprint in the live fingerprint Bloom filters 408, wherein determining the newest container teaches “higher than …”);
based on the second determining, replacing the cached fingerprint in the live instance filter with the suffixed fingerprint (Fig. 4; [0062]: insert the set of <FP, CID> pairs into a set of live-instance Bloom filters 410 that can be queried during the copy-forward process); and
marking everything not in the live instance filter as available for garbage collection (Fig. 4; [0062]: once all the live data segments in a container have been copied forward to a new container, the container is deleted and the space reclaimed, i.e., available for garbage collection).
With respect to claim 9,
Wallace further teaches
the non-transitory computer readable medium of claim 8, wherein the suffixed fingerprint comprises a fingerprint and a CID (Fig. 3; [0057]: the fingerprint index 302 stores fingerprint data in the form of fingerprint and container identifier pairs (e.g., <FP,CID>) which associate a fingerprint with a container identifier storing the storage segment associated with the fingerprint).
With respect to claim 10,
Wallace further teaches
the non-transitory computer readable medium of claim 8, wherein the bucket containing the suffixed fingerprint is part of a plurality of buckets (Fig. 6; [0073]: each Bloom filter in the set of Bloom filters may be associated with a separate virtual or physical computational node, where each node processes fingerprints within an assigned range and each Bloom filter stores fingerprints within the assigned range, wherein fingerprints within an assigned range indicates “a plurality of buckets”).
With respect to claim 14,
Wallace further teaches
the non-transitory computer readable medium of claim 8, wherein the live filter is a bloom filter (Fig. 4; [0061]: live fingerprint Bloom filters 408).
With respect to claim 15,
Wallace teaches
a system for managing data in a storage system (Abstract), the system comprising:
a processor (Fig. 22: processor(s) 2201) comprising circuitry;
memory (Fig. 22: memory 2203) comprising instructions, which when executed by the processor perform a method, the method comprising:
selecting a suffixed fingerprint from a bucket (Fig. 4; [0061]: use a fingerprint index (FP index 414), or a memory resident cache of the fingerprint index, to determine a set of fingerprint and container identifier (CID) pairs 418 that references the newest container that includes a copy of each storage segment referenced by the fingerprint. The determining includes “selecting” a FP index from FP index 414. Fig. 3; [0057]: the fingerprint index 302 stores fingerprint data in the form of fingerprint and container identifier pairs (e.g., <FP,CID>) which associate a fingerprint with a container identifier storing the storage segment associated with the fingerprint. The fingerprint associated with a container identifier reads on “suffixed fingerprint” and FP index 414 corresponds to “a bucket” under BRI);
making a first determination that the suffixed fingerprint is live using a live filter (Fig. 4; [0061]: determine a set of fingerprint and container identifier (CID) pairs 418 that references the newest container that includes a copy of each storage segment referenced by the fingerprint in the live fingerprint Bloom filters 408 and identifies the live instance of a data segment that is in use in the directory/file tree 412);
based on the first determining, making a second determination that a container identification number (CID) associated with the suffixed fingerprint is higher than a cached fingerprint in a live instance filter (Fig. 4; [0061]-[0062]: determine a set of fingerprint and container identifier (CID) pairs 418 that references the newest container that includes a copy of each storage segment referenced by the fingerprint in the live fingerprint Bloom filters 408, wherein determining the newest container teaches “higher than …”);
based on the second determining, replacing the cached fingerprint in the live instance filter with the suffixed fingerprint (Fig. 4; [0062]: insert the set of <FP, CID> pairs into a set of live-instance Bloom filters 410 that can be queried during the copy-forward process); and
marking everything not in the live instance filter as available for garbage collect (Fig. 4; [0062]: once all the live data segments in a container have been copied forward to a new container, the container is deleted and the space reclaimed, i.e., available for garbage collection).
With respect to claim 16,
Wallace further teaches
the system of claim 15, wherein the suffixed fingerprint comprises a fingerprint and a CID (Fig. 3; [0057]: the fingerprint index 302 stores fingerprint data in the form of fingerprint and container identifier pairs (e.g., <FP,CID>) which associate a fingerprint with a container identifier storing the storage segment associated with the fingerprint).
With respect to claim 17,
Wallace further teaches
the system of claim 15, wherein the bucket containing the suffixed fingerprint is part of a plurality of buckets (Fig. 6; [0073]: each Bloom filter in the set of Bloom filters may be associated with a separate virtual or physical computational node, where each node processes fingerprints within an assigned range and each Bloom filter stores fingerprints within the assigned range, wherein fingerprints within an assigned range indicates “a plurality of buckets”).
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 5, 12, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Wallace (US 20190171563 A1), in view of Mondal (US 9715505 B1).
With respect to claim 5,
As discussed in claim 3, Wallace teaches all the limitations.
Wallace does not teach
the method of claim 3, wherein each of the plurality of buckets contains a subset of suffixed fingerprints from a sorted index, wherein the suffixed fingerprints each comprise a fingerprint and a container identifier (CID),wherein each of the suffixed fingerprints are lexicographically sorted based on the fingerprint and when there are multiple suffixed fingerprints that have the same fingerprint, the multiple suffixed fingerprints are stored in a numerically descending order based on the CIDs.
Mondal teaches
the method of claim 3, wherein each of the plurality of buckets contains a subset of suffixed fingerprints from a sorted index, wherein the suffixed fingerprints each comprise a fingerprint and a container identifier (CID) (Fig. 9A; Col. 11, lines 51-67; Col. 12, lines 1-4: a fingerprint to container ID index may be sorted according to the fingerprint values and the duplicate entries having the same fingerprint may be removed),
wherein each of the suffixed fingerprints are lexicographically sorted based on the fingerprint and when there are multiple suffixed fingerprints that have the same fingerprint, the multiple suffixed fingerprints are stored in a numerically descending order based on the CIDs (Fig. 9M; Col. 14, lines 51-67; Col. 15, lines 1-7: When multiple entries of the same fingerprint are detected, the {fingerprint, CID} pairs are recorded in a list. The list is then sorted based on the container ID so that those fingerprints are now available in the LSR record order).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wallace to incorporate the teachings of Mondal to contain a subset of suffixed fingerprints from a sorted index in each of the plurality of buckets, wherein the suffixed fingerprints each comprise a fingerprint and a container identifier (CID),wherein each of the suffixed fingerprints are lexicographically sorted based on the fingerprint and when there are multiple suffixed fingerprints that have the same fingerprint, the multiple suffixed fingerprints are stored in a numerically descending order based on the CIDs. Doing so would identify duplicated entries with the same fingerprints based on the sorted entries as taught by Mondal (Fig. 9M; Col. 14, lines 51-67; Col. 15, lines 1-7).
With respect to claim 12,
As discussed in claim 10, Wallace teaches all the limitations.
Wallace does not teach
the non-transitory computer readable medium of claim 10, wherein each of the plurality of buckets contains a subset of suffixed fingerprints from a sorted index, wherein the suffixed fingerprints each comprise a fingerprint and a container identifier (CID),wherein each of the suffixed fingerprints are lexicographically sorted based on the fingerprint and when there are multiple suffixed fingerprints that have the same fingerprint, the multiple suffixed fingerprints are stored in a numerically descending order based on the CIDs.
Mondal teaches
the non-transitory computer readable medium of claim 10, wherein each of the plurality of buckets contains a subset of suffixed fingerprints from a sorted index, wherein the suffixed fingerprints each comprise a fingerprint and a container identifier (CID) (Fig. 9A; Col. 11, lines 51-67; Col. 12, lines 1-4: a fingerprint to container ID index may be sorted according to the fingerprint values and the duplicate entries having the same fingerprint may be removed),
wherein each of the suffixed fingerprints are lexicographically sorted based on the fingerprint and when there are multiple suffixed fingerprints that have the same fingerprint, the multiple suffixed fingerprints are stored in a numerically descending order based on the CIDs (Fig. 9M; Col. 14, lines 51-67; Col. 15, lines 1-7: When multiple entries of the same fingerprint are detected, the {fingerprint, CID} pairs are recorded in a list. The list is then sorted based on the container ID so that those fingerprints are now available in the LSR record order).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wallace to incorporate the teachings of Mondal to contain a subset of suffixed fingerprints from a sorted index in each of the plurality of buckets, wherein the suffixed fingerprints each comprise a fingerprint and a container identifier (CID),wherein each of the suffixed fingerprints are lexicographically sorted based on the fingerprint and when there are multiple suffixed fingerprints that have the same fingerprint, the multiple suffixed fingerprints are stored in a numerically descending order based on the CIDs. Doing so would identify duplicated entries with the same fingerprints based on the sorted entries as taught by Mondal (Fig. 9M; Col. 14, lines 51-67; Col. 15, lines 1-7).
With respect to claim 19,
As discussed in claim 17, Wallace teaches all the limitations.
Wallace does not teach
the system of claim 17, wherein each of the plurality of buckets contains a subset of suffixed fingerprints from a sorted index, wherein the suffixed fingerprints each comprise a fingerprint and a container identifier (CID),wherein each of the suffixed fingerprints are lexicographically sorted based on the fingerprint and when there are multiple suffixed fingerprints that have the same fingerprint, the multiple suffixed fingerprints are stored in a numerically descending order based on the CIDs.
Mondal teaches
the system of claim 17, wherein each of the plurality of buckets contains a subset of suffixed fingerprints from a sorted index, wherein the suffixed fingerprints each comprise a fingerprint and a container identifier (CID) (Fig. 9A; Col. 11, lines 51-67; Col. 12, lines 1-4: a fingerprint to container ID index may be sorted according to the fingerprint values and the duplicate entries having the same fingerprint may be removed),
wherein each of the suffixed fingerprints are lexicographically sorted based on the fingerprint and when there are multiple suffixed fingerprints that have the same fingerprint, the multiple suffixed fingerprints are stored in a numerically descending order based on the CIDs (Fig. 9M; Col. 14, lines 51-67; Col. 15, lines 1-7: When multiple entries of the same fingerprint are detected, the {fingerprint, CID} pairs are recorded in a list. The list is then sorted based on the container ID so that those fingerprints are now available in the LSR record order).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wallace to incorporate the teachings of Mondal to contain a subset of suffixed fingerprints from a sorted index in each of the plurality of buckets, wherein the suffixed fingerprints each comprise a fingerprint and a container identifier (CID),wherein each of the suffixed fingerprints are lexicographically sorted based on the fingerprint and when there are multiple suffixed fingerprints that have the same fingerprint, the multiple suffixed fingerprints are stored in a numerically descending order based on the CIDs. Doing so would identify duplicated entries with the same fingerprints based on the sorted entries as taught by Mondal (Fig. 9M; Col. 14, lines 51-67; Col. 15, lines 1-7).
Claims 6, 13, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Wallace (US 20190171563 A1), in view of JAIN et al. (US 20230221864 A1).
With respect to claim 6,
As discussed in claim 1, Wallace teaches all the limitations.
Wallace does not teach
the method of claim 1, wherein the live filter is a quotient filter.
JAIN teaches
the method of claim 1, wherein the live filter is a quotient filter ([0120]: a counting quotient filter (CQF)).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wallace to incorporate the teachings of JAIN to use a quotient filter as the live filter. Doing so would take advantage of the quotient filter's capability of resizing dynamically and avoid eviction and recovery operations as taught by Wallace ([0120]).
With respect to claim 13,
As discussed in claim 8, Wallace teaches all the limitations.
Wallace does not teach
the non-transitory computer readable medium of claim 8, wherein the live filter is a quotient filter.
JAIN teaches
the non-transitory computer readable medium of claim 8, wherein the live filter is a quotient filter ([0120]: a counting quotient filter (CQF)).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wallace to incorporate the teachings of JAIN to use a quotient filter as the live filter. Doing so would take advantage of the quotient filter's capability of resizing dynamically and avoid eviction and recovery operations as taught by Wallace ([0120]).
With respect to claim 20,
As discussed in claim 15, Wallace teaches all the limitations.
Wallace does not teach
the system of claim 15, wherein the live filter is a quotient filter.
JAIN teaches
the system of claim 15, wherein the live filter is a quotient filter ([0120]: a counting quotient filter (CQF)).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wallace to incorporate the teachings of JAIN to use a quotient filter as the live filter. Doing so would take advantage of the quotient filter's capability of resizing dynamically and avoid eviction and recovery operations as taught by Wallace ([0120]).
Allowable Subject Matter
Claims 4, 11, and 18 are objected to as being dependent upon a rejected claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims and overcoming all the objections and rejections set forth in this office action above.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to XIAOQIN HU whose telephone number is (571)272-1792. The examiner can normally be reached on Monday-Friday 7:00am-3:30pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Charles Rones can be reached on (571) 272-4085. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/XIAOQIN HU/Examiner, Art Unit 2168
/CHARLES RONES/Supervisory Patent Examiner, Art Unit 2168
Prosecution Insights