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 .
Continued Examination Under 37 CFR 1.114
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on 09/15/2025 has been entered.
Response to Amendment
Claims 1, 6, 8, 14, 16, 18, and 20 have been amended. Claims 1-20 are pending in the application.
Response to Arguments
Claim Rejections - 35 USC § 103
Regarding claim 16, Applicant argues that “Wang in combination with Miah fail to disclose at least the following limitations of claim 16 as amended: "determining that a count of snapshot images created between the first snapshot image and the second snapshot image satisfies a count threshold; in response to the determining, generating comparison data for the first snapshot image and the second snapshot image using certain metadata files..." (emphasis added).
In relation to dependent claim 20, Applicant argues that “ the Office concedes that Wang in view of Miah does not clearly disclose "determining to generate the comparison data for the first snapshot image and the second snapshot image based on a distance between the first snapshot image and the second snapshot image on a snapshot creation order satisfying a threshold distance." However, the Office contends this limitation is disclosed by Shilane (US 20190243702 A1). This language from dependent claim 20 is analogous to the above limitations of amended claim 16, with "a count of snapshot images" being a specific example of a "distance between the first snapshot image and the second snapshot image." Thus, the above limitations is not clearly disclosed by either Wang or Miah. Furthermore, despite the Office's contention that the limitations of claim 20 are disclosed by Shilane, Application respectfully submits that the limitations of amended claim 16 are not disclosed by Shilane. The portions of Shilane cited in the Final Office Action describe determining whether to replicate a snapshot based on "if an object name and timestamp exists" in both that snapshot and a different snapshot (see Shilane, para. [0124], "The two snapshots are...compared. If an object name and timestamp exists in both snapshots, it does not need to be replicated."). However, an object name and timestamp are not equivalent to "a count of snapshot images created between the first snapshot image and the second snapshot image," as recited in amended claim 16. The count represents the number of snapshots created between two snapshots being compared (e.g., 50 snapshots), and is independent of both the timestamp at which either of the two snapshots were generated and any object names within those snapshots. Thus, amended claim 16 is not obvious in view of Wang in combination with Miah and/or Shilane. Independent claim 8 has been similarly amended and is therefore likewise not obvious in view of these references.
In relation to dependent claim 18, Applicant argues that” the Office contends that Wang in view of Miah does not clearly disclose, but that Shilane does disclose, "estimating a size of the comparison data based on a number of the certain metadata files." This language from dependent claim 18 is analogous to the above limitations of amended claim 1, with "a predicted computational resource usage" being a specific example of a "size of the comparison data." Thus, the above limitations is not clearly disclosed by either Wang or Miah. Furthermore, despite the Office's contention that the limitations of claim 18 are disclosed by Shilane, Application respectfully submits that the limitations of amended claim 1 are not disclosed by Shilane. Shilane discusses using snapshot deltas, which are comparisons identifying the differences between two snapshots, to determine an amount of computational work to be done (see Shilane, para. [0188], "The controller, upon examining the snapshot delta to determine the amount of data to be copied can then calculate the number of worker nodes to allocate..."). However, amended claim 1 specifies that the predicted computational resource usage is based on "a cumulative number of keys in the certain metadata files," with keys being identifiers for the metadata files. Shilane does not specify which feature of a snapshot delta is used to determine the predicted computational resource usage, nor does Shilane disclose which features are even included in a snapshot delta. Thus, Shilane does not disclose predicting a computational resource usage based specifically on the cumulative number of keys in the certain metadata files, as required by amended claim 1. Amended claim 1 is therefore not obvious in view of Wang in combination with Miah and/or Shilane. “
In response, Examiner relies on a new combination of references.
Allowable Subject Matter
Claims 1-7 are allowed.
The following is a statement of reasons for the indication of allowable subject matter: The prior arts of the record fail to teach neither singly nor in combination “"A computer-implemented method for preventing compaction-based errors related to log-structure-merge-tree-based (LSM-based) snapshot images of a distributed object-based datastore, the computer-implemented method comprising: detecting, by one or more computing nodes associated with the distributed object-based datastore, compaction events performed by an LSM-based metadata datastore that stores metadata files for data objects included in the distributed object-based datastore, wherein each compaction event results in one or more first metadata files stored in the LSM-based metadata datastore being compacted into one or more new metadata files added to the LSM-based metadata datastore, wherein each LSM-based snapshot image of the distributed object-based datastore references a respective subset of the metadata files stored in the LSM-based metadata datastore; maintaining, by the one or more computing nodes, a directed acyclic graph (DAG) data structure that indicates, for each compaction event, a directed relationship from the one or more first metadata files to the one or more new metadata files; receiving, by the one or more computing nodes, a request to compare a first LSM-based snapshot image of the distributed object-based datastore and a second LSM-based snapshot image of the distributed object-based datastore; using, by the one or more computing nodes, the DAG data structure to identify certain metadata files referenced by the second LSM-based snapshot image that lack a respective directed relationship from any metadata file referenced by the first LSM-based snapshot image, wherein to identify the certain metadata files, the DAG data structure is traversed to identify metadata files in the first LSM-based snapshot image that do not lead to the certain metadata files referenced by the second LSM-based snapshot image; determining, by the one or more computing nodes, that a predicted computational resource usage of comparison data based on a cumulative number of keys in the certain metadata files satisfies a usage threshold; in response to the determining, generating, by the one or more computing nodes, the comparison data based on the certain metadata files; and providing, by the one or more computing nodes, the comparison data in response to the request."
Claim Rejections - 35 USC § 103
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 8-12 and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 11,675,745 B2) in view of Miah (US20200089574) in further view of Jain (US 2018/0121453 Al)
Regarding claim 8, Wang discloses: A distributed computing system comprising: a plurality of data nodes implementing an object-based datastore; (Wang, figure 1, item 116, “object store”); column 6, line 3- Local storages 114 housed in, or directly attached to, host machines 105, may provide an aggregate object store 116 for virtual machines (VMs) 120 running on hosts 105.) and one or more manager nodes for the object-based datastore, (Wang, fig. 1, item 134 “metadata storage” ;column 5, line 16- Computer system 100 may include a datacenter 102, a secondary datacenter 104, a network 140, several compute nodes 155, an object storage 165, and a metadata storage 134;)
wherein each manager node is configured to perform operations comprising: detecting compactions performed by a metadata database storing metadata files related to data objects of the object-based datastore, (Wang, column 18, line 20- If process 1000 determines that a readjusting event has occurred, the process may determine, at 1030, whether any shard boundaries need readjustment. For example, process 1000 may check every shard's size to determine whether it has changed by at least the determined threshold; column 17, line 58- FIG. 10 is a flowchart illustrating a method (or process) 1000 for readjusting boundaries of the shards based on the occurrence of an event,... Process 1000 may be performed by a physical or virtual computing device in charge of performing the compaction; column 4, line 55- shard the compaction process of an LSM tree by partitioning the tree into several different shards and having multiple merging entities compact a set of one or more of the shards in parallel; column 3, line 62- each compute node may assign a unique name to the SSTables it stores in the LSM tree, such that during a compaction process of the tree, SSTables that are written by each compute node may be merged together and separate from the SSTables that are written by the other compute nodes.)
wherein each compaction results in an addition to the metadata database of one or more new metadata files that aggregate metadata information recorded on one or more pre-compaction metadata files stored in the metadata database;
(Wang, column 4, line 43- This is because compaction typically involves reading several levels of the LSM tree, merging the SSTables of the different levels, and then writing new and sorted SSTables back into the LSM tree ;column 3, line 1- a merging entity (or compactor) may move the tables stored in a first layer, the size of which has surpassed its threshold, to a second layer below the first layer by merging the tables of the first layer with other tables stored in the second layer, while ensuring that the merged data is ordered or sorted; column 3, line 66-As discussed, the metadata may include a plurality of key-value tables stored as SSTables in the LSM tree data structure…Additionally, each compute node may assign a unique name to the SSTables it stores in the LSM tree, such that during a compaction process of the tree, SSTables that are written by each compute node may be merged together and separate from the SSTables that are written by the other compute nodes;)
receiving a request to compare a second snapshot image against a first snapshot image of the object-based datastore, wherein each of the first snapshot image and the second snapshot image references a corresponding subset of metadata files of the metadata database; (Wang, column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up… in addition to objects and their snapshots, uploader manager 135 may store files (and their snapshots) in object storage 165 or another remote storage for backup purposes and send information associated with the stored files to compute nodes 155 to create, manage, and store metadata associated with the files; column 9, line 25- For example, when a compute node receives, for an object, an object ID "ObjID," a snapshot ID "SnapID," and a number of logical blocks "NumBlocks," the compute node may first generate a new chunk ID and then add a new record to table 142 that maps a three-tuple key <objectID, snapID, LBA> 210 to a two-tuple value <chunkID, NumBlocks> 220; column 3, line 50- a log-structured file system (LFS) data structure may be used to store the object data and an LSM tree data structure may be used to store and manage the metadata.)
in response to the determining, generating comparison data for the first snapshot image and the second snapshot image based on metadata files referenced by the second snapshot image, the particular metadata files compacting the metadata information recorded on corresponding pre- compaction metadata files referenced by the first snapshot image; (Wang, column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up.)
and returning the comparison data in response to the request. (Wang, column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up.)
However Wang does not clearly disclose:
determining that a count of snapshot images created between the first snapshot image and the second snapshot image satisfies a count threshold; in response to the determining, based on identifying particular metadata files referenced by the second snapshot image that lack a respective directed relationship from any metadata file referenced by the first snapshot image, wherein to identify the particular metadata files, a directed acyclic graph (DAG) data structure is traversed to identify metadata files in the first snapshot image that do not lead to the particular metadata files referenced by the second snapshot image,
However Miah discloses:based on identifying particular metadata files referenced by the second snapshot image that lack a respective directed relationship from any metadata file referenced by the first snapshot image, wherein to identify the particular metadata files, a directed acyclic graph (DAG) data structure is traversed to identify metadata files in the first snapshot image that do not lead to the particular metadata files referenced by the second snapshot image,
(Miah, [0066] A directed acyclic graph (DAG) 400 associated with four snapshots ; Fig. 9, step 908 to Determine Candidate Clusters of Snapshots for Given Time; Fig. 4; [0071] Similarly, as between the two snapshots 402C-D of the same underlying block device, file system 410D reflects a change relative to file system 410C, and directory 412D reflects a change relative to directory 412C. As illustrated, the file 414D appears in snapshot 402D but does not appear within 402C, indicating that the file associated with vertex 414D first appeared at the time the snapshot 402D was generated; [0073] the use of DAGs or similar types of models greatly eases the traversal of large numbers of snapshots by allowing for a quick, directed lookup for several different types of information related to the data structures reflected in snapshots at specific points in time, as well as easing comparative lookups and other such data operations;[0026] Such information may be used as an initial stage to deterministically filter a large "cloud" of snapshots into those that are associated with a given multipart block device;)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Wang with the teaching of Miah to use of DAGs or similar types of models that greatly eases the traversal of large numbers of snapshots by allowing for a quick, directed lookup for several different types of information related to the data structures reflected in snapshots at specific points in time, as well as easing comparative lookups and other such data operations, (Miah, [0073]).
However Wang in view of Miah does not clearly disclose:
determining that a count of snapshot images created between the first snapshot image and the second snapshot image satisfies a count threshold;
However Jain discloses:
determining that a count of snapshot images created between the first snapshot image and the second snapshot image satisfies a count threshold; (Jain, [0029] The storage appliance 201 can use a monotonically increasing counter for each new snapshot ; [0044] the snapshot manager updates the local snapshot identifier for assignment to the next received snapshot. For example, the snapshot manager increments a counter. [0158]-[0159], e.g. [0158] The threshold may be a number of snapshots, a size of cached data, etc. As an example, a threshold may be based on both number of snapshots and amount of cache consumed by using a snapshot change rate (i.e., average size of incremental snapshot data). With the snapshot change rate, the snapshot manager can set a threshold number of snapshots that corresponds to an expected cache consumption based on the average change rate. The threshold can also dynamically update by recalculating the snapshot change rate periodically and/or in response to detection of a trending snapshot change rate, either increasing or decreasing trend. If the threshold is not satisfied, then the process ends until a next snapshot is received. If the threshold is satisfied, then control flows to block 1605. [0159] At block 1605, the snapshot manager begins to iterate over the snapshots that precede the received ( or most recent) snapshot back to a baseline snapshot or a preceding synthetic baseline snapshot; [0183] This synthetic baseline snapshot data file changes with each received snapshot. The snapshot manager creates and closes the pre-baseline snapshot data files created from the update of the synthetic baseline snapshot. Accordingly, the snapshot manager transfers invalidated snapshot metadata and snapshot data to the pre-baseline snapshot and incorporates the new/changed data of the snapshot being received.)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Wang in view of Miah with the teaching of Jain to facilitate efficient snapshot manipulation, which may be for snapshot management or snapshot restore and also to facilitate efficient snapshot restore, file restore, and snapshot reclamation, (Jain, abstract).
Regarding claim 9, Wang in view of Miah in view of Jain discloses all of the features with respect to claim 8 as outlined above. Claim 9 further recites: wherein the comparison data is further generated based on: determining that the particular metadata files referenced by the second snapshot image further compact the metadata information recorded on corresponding pre-compaction metadata files referenced by the first snapshot image with a separate metadata file that is not referenced by the first snapshot image or the second snapshot image, and generating the comparison data using the separate metadata file instead of the particular metadata files. (Wang, column 3, line 62- each compute node may assign a unique name to the SSTables it stores in the LSM tree, such that during a compaction process of the tree, SSTables that are written by each compute node may be merged together and separate from the SSTables that are written by the other compute nodes; column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up.)
Regarding claim 10, Wang in view of Miah in view of Jain discloses all of the features with respect to claim 8 as outlined above. Claim 10 further recites: wherein the operations further comprise: storing the comparison data in a snapshot-comparison database, the comparison data being associated with the first snapshot image and the second snapshot image. (Wang , column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up ;)
Regarding claim 11, Wang in view of Miah in view of Jain discloses all of the features with respect to claim 10 as outlined above. Claim 11 further recites: receiving a second request that identifies the first snapshot image and the second snapshot image; in response to the second request, retrieving the comparison data associated with the first snapshot image and the second snapshot image from the snapshot-comparison database; and providing the comparison data in response to the second request. (Wang, column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up. uploader manager may send information associated with the object, such as object ID, snapshot ID, logical block addresses (LBAs) in which the object is stored, etc., to a set of one or more compute nodes 155; column 9, line 3- In case of a failure in datacenter 102 (e.g., when part or all of the data stored in object store 116 is damaged or lost, when datacenter 102 is under a cyber-attack, etc.), a secondary or recovery datacenter, such as secondary datacenter 104, may use the metadata stored in the metadata storage 134 to retrieve the backed up data ( e.g., objects and/or files) stored in object storage 165. After retrieving the backup data (e.g., snapshots of the VMDKs), secondary datacenter 104 may use the data to recreate the objects (e.g., the virtual disks) and run the VMs of datacenter 102; column 3, line 50- a log-structured file system (LFS) data structure may be used to store the object data and an LSM tree data structure may be used to store and manage the metadata;)
Regarding claim 12, Wang in view of Miah in view of Jain discloses all of the features with respect to claim 10 as outlined above. Claim 12 further recites: receiving a second request that identifies a third snapshot image and one of the first snapshot image or the second snapshot image; in response to the second request, retrieving the comparison data associated with the first snapshot image and the second snapshot image; using the comparison data to generate second comparison data for the third snapshot image and the one of the first snapshot image or the second snapshot image; and providing the comparison data in response to the second request. (Wang , column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up ;)
Regarding claim 15, Wang in view of Miah in view of Jain discloses all of the features with respect to claim 8 as outlined above. Claim 15 further recites: wherein the operations further comprise: storing the data structure in an active instance of the metadata database, ( Wang, column 8, line 20- store the generated metadata in an LSM tree data structure (corresponding to “graph-based data structure”) in metadata storage 134; column 4, line 44- This is because compaction typically involves reading several levels of the LSM tree, merging the SSTables of the different levels, and then writing new and sorted SSTables back into the LSM tree.)
the data structure recording directed relationships between the one or more pre-compaction metadata files and the one or more new metadata files of each compaction. ( Wang, column 8, line 20- store the generated metadata in an LSM tree data structure (corresponding to “graph-based data structure”) in metadata storage 134 ;column 2, line 66- In such a case, a process called compaction may be invoked to compact the LSM tree and reclaim space; column 4, line 44- This is because compaction typically involves reading several levels of the LSM tree, merging the SSTables of the different levels, and then writing new and sorted SSTables back into the LSM tree.
However, Wang does not clearly disclose:
the DAG data structure
However Miah discloses:
the DAG data structure
(Miah, [0067] In the illustrated DAG 400, the snapshots 402A-D are associated with root nodes 404A-D for block devices associated with each individual snapshot 402A-D, respectively, as might be generated after ingestion via the techniques described above in connection with FIG. 3. The vertices ( denoted as ovals) indicate data structures ( or versions thereof), while edges (denoted as solid arrows) indicate associations between data structures ( either within the same snapshot or to other snapshots of the same block device).
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Wang with the teaching of Miah to use of DAGs or similar types of models that greatly eases the traversal of large numbers of snapshots by allowing for a quick, directed lookup for several different types of information related to the data structures reflected in snapshots at specific points in time, as well as easing comparative lookups and other such data operations, (Miah, [0073])
Claim 13 is rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 11,675,745 B2) in view of Miah (US20200089574) Jain (US 2018/0121453 Al) in further view of WANG et al. (US 2020/0183905 A1, hereinafter Wang2)
Regarding claim 13, Wang in view of Miah in view of Jain discloses all of the features with respect to claim 8 as outlined above. Wang in view of Miah in view of Jain does not clearly disclose:
wherein the compactions are detected via a synchronous event listener communicatively coupled with the metadata database, the synchronous event listener configured to receive, for a given compaction, an identification of the one or more new metadata files and the one or more pre-compaction metadata files.
However Wang2 discloses:
wherein the compactions are detected via a synchronous event listener communicatively coupled with the metadata database, the synchronous event listener configured to receive, for a given compaction, an identification of the one or more new metadata files and the one or more pre-compaction metadata files. (Wang2 [0070] The event listener is also configured to identify when a shard that has been assigned to a VM for compaction is compacted. In that case, the event listener indicates a "finished shard" event; [0038] A catalogue file is generally created to enable a file system to efficiently find SSTs within a corresponding LSM tree. The catalogue file serves as a superblock of the on-disk representation of a corresponding LSM tree and includes metadata associated with each SST, including the SST's name and key range; [0046] This is because compaction typically involves reading several levels of SSTs, merging the SSTs from the different levels, and then writing new and sorted SSTs back into the LSM tree.)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Wang in view of Miah in view of Jain with the teaching of Wang2 in order to indicate an event when a VM has failed or when a shard's compaction is finished, (Wang2, [0070]).
Claim 14 is rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 11,675,745 B2) in view of Miah (US20200089574) in view of Jain (US 2018/0121453 Al) in further view of Shilane (US 20190243702 A1)
Regarding claim 14, Wang in view of Miah in view of Jain discloses all of the features with respect to claim 8 as outlined above. Wang in view of Miah in view of Jain does not clearly disclose: prior to generating the comparison data, estimating a predicted computational resource usage of the comparison data based on a cumulative number of keys in the particular metadata files; and determining a time to generate the comparison data based on the predicted computational resource usage of the comparison data.
However Shilane discloses:
prior to generating the comparison data, estimating a predicted computational resource usage of the comparison data based on a cumulative number of keys in the particular metadata files; (Shilane [0188] The controller, upon examining the snapshot delta to determine the amount of data to be copied can then calculate the number of worker nodes to allocate based on the specified time constraint and data transfer rate. In other words, the controller assess, examines, estimates, or analyzes the amount of work to be done, reviews the time allowed for replication, and allocates a particular number of worker nodes accordingly; [0124] The controller preserves the previous snapshot (from the last replication event) and calculates a delta of the current snapshot relative to the previous snapshot. Object names in the snapshot include their creation time. The two snapshots are read into memory (possibly in pieces) and compared. If an object name and timestamp exists in both snapshots, it does not need to be replicated.)
and determining a time to generate the comparison data based on the predicted computational resource usage of the comparison data. (Shilane, [0188] The controller, upon examining the snapshot delta to determine the amount of data to be copied can then calculate the number of worker nodes to allocate based on the specified time constraint and data transfer rate. In other words, the controller assess, examines, estimates, or analyzes the amount of work to be done, reviews the time allowed for replication, and allocates a particular number of worker nodes accordingly.)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Wang in view of Miah with the teaching of Shilane in order to strike a balance across efficient use of storage, network bandwidth, and processing time, (Shilane, [0160]).
Claims 16 and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 11,675,745 B2) in view of Jain (US 2018/0121453 Al)
Regarding claim 16, Wang discloses: At least one non-transitory computer-readable medium with instructions stored thereon that, when executed by a processor of a computing device, cause the computing device to perform operations comprising: detecting compactions performed by a metadata database storing metadata files related to data objects of an object-based datastore, (Wang, column 18, line 20- If process 1000 determines that a readjusting event has occurred, the process may determine, at 1030, whether any shard boundaries need readjustment. For example, process 1000 may check every shard's size to determine whether it has changed by at least the determined threshold; column 17, line 58- FIG. 10 is a flowchart illustrating a method (or process) 1000 for readjusting boundaries of the shards based on the occurrence of an event,... Process 1000 may be performed by a physical or virtual computing device in charge of performing the compaction; column 4, line 55- shard the compaction process of an LSM tree by partitioning the tree into several different shards and having multiple merging entities compact a set of one or more of the shards in parallel; column 3, line 62- each compute node may assign a unique name to the SSTables it stores in the LSM tree, such that during a compaction process of the tree, SSTables that are written by each compute node may be merged together and separate from the SSTables that are written by the other compute nodes.)
wherein each compaction results in an addition to the metadata database of one or more new metadata files that aggregate metadata information recorded on a plurality of pre-compaction metadata files stored in the metadata database;
(Wang, column 4, line 43- This is because compaction typically involves reading several levels of the LSM tree, merging the SSTables of the different levels, and then writing new and sorted SSTables back into the LSM tree ;column 3, line 1- a merging entity (or compactor) may move the tables stored in a first layer, the size of which has surpassed its threshold, to a second layer below the first layer by merging the tables of the first layer with other tables stored in the second layer, while ensuring that the merged data is ordered or sorted; column 3, line 66-As discussed, the metadata may include a plurality of key-value tables stored as SSTables in the LSM tree data structure…Additionally, each compute node may assign a unique name to the SSTables it stores in the LSM tree, such that during a compaction process of the tree, SSTables that are written by each compute node may be merged together and separate from the SSTables that are written by the other compute nodes;)
receiving a request to compare a second snapshot image of the object-based datastore against a first snapshot image of the object-based datastore, wherein each of the first snapshot image and the second snapshot image references a respective subset of the metadata files in the metadata database; (Wang, column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up… in addition to objects and their snapshots, uploader manager 135 may store files (and their snapshots) in object storage 165 or another remote storage for backup purposes and send information associated with the stored files to compute nodes 155 to create, manage, and store metadata associated with the files; column 3, line 50- a log-structured file system (LFS) data structure may be used to store the object data and an LSM tree data structure may be used to store and manage the metadata; column 9, line 25- For example, when a compute node receives, for an object, an object ID "ObjID," a snapshot ID "SnapID," and a number of logical blocks "NumBlocks," the compute node may first generate a new chunk ID and then add a new record to table 142 that maps a three-tuple key <objectID, snapID, LBA> 210 to a two-tuple value <chunkID, NumBlocks> 220;)
in response to the determining, generating comparison data for the first snapshot image and the second snapshot image using certain metadata files, the certain metadata files compacting the metadata information recorded on corresponding pre-compaction metadata files referenced by the first snapshot image (Wang, column 3, line 62- each compute node may assign a unique name to the SSTables it stores in the LSM tree, such that during a compaction process of the tree, SSTables that are written by each compute node may be merged together and separate from the SSTables that are written by the other compute nodes; column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up.)
and returning the comparison data in response to the request. (Wang, column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time…uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up.)
However, Wang does not clearly disclose:
determining that a count of snapshot images created between the first snapshot image and the second snapshot image satisfies a count threshold;
determining that a count of snapshot images created between the first snapshot image and the second snapshot image satisfies a count threshold;
However Jain discloses:
determining that a count of snapshot images created between the first snapshot image and the second snapshot image satisfies a count threshold; (Jain, [0029] The storage appliance 201 can use a monotonically increasing counter for each new snapshot ; [0044] the snapshot manager updates the local snapshot identifier for assignment to the next received snapshot. For example, the snapshot manager increments a counter. [0158]-[0159], e.g. [0158] The threshold may be a number of snapshots, a size of cached data, etc. As an example, a threshold may be based on both number of snapshots and amount of cache consumed by using a snapshot change rate (i.e., average size of incremental snapshot data). With the snapshot change rate, the snapshot manager can set a threshold number of snapshots that corresponds to an expected cache consumption based on the average change rate. The threshold can also dynamically update by recalculating the snapshot change rate periodically and/or in response to detection of a trending snapshot change rate, either increasing or decreasing trend. If the threshold is not satisfied, then the process ends until a next snapshot is received. If the threshold is satisfied, then control flows to block 1605. [0159] At block 1605, the snapshot manager begins to iterate over the snapshots that precede the received ( or most recent) snapshot back to a baseline snapshot or a preceding synthetic baseline snapshot; [0183] This synthetic baseline snapshot data file changes with each received snapshot. The snapshot manager creates and closes the pre-baseline snapshot data files created from the update of the synthetic baseline snapshot. Accordingly, the snapshot manager transfers invalidated snapshot metadata and snapshot data to the pre-baseline snapshot and incorporates the new/changed data of the snapshot being received.)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Wang with the teaching of Jain to facilitate efficient snapshot manipulation, which may be for snapshot management or snapshot restore and also to facilitate efficient snapshot restore, file restore, and snapshot reclamation, (Jain, abstract).
Regarding claim 19, Wang in view of Jain discloses all of the features with respect to claim 16 as outlined above. Claim 19 further recites: storing the comparison data in a snapshot-comparison database in association with the first snapshot image and the second snapshot image; and in response to a second request that specifies the first snapshot image and the second snapshot image, retrieving and returning the comparison data. (Wang , column 7, line 50- Uploader manager 135 may receive object data stored in object store 116 and send the data to object storage 165 (e.g., in the cloud) to be stored as backup data for the object. The data may include different snapshots (e.g., backups, delta backups containing only changed data since a previous backup, etc.) of the object taken at different points of time. In some embodiments, uploader manager 135 may send the first snapshot of the object to the data storage 165 and subsequently send only the snapshot differences (may also be referred to as “snapshot diffs”, or “Jiffs”) to the data storage to be backed up ;)
Claim 17 is rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 11,675,745 B2) in view of Jain (US 2018/0121453 Al) in further view of CAMARGOS (US 20220103622 A1)
Regarding claim 17, Wang in view of Jain discloses all of the features with respect to claim 16 as outlined above. Claim 17 further recites:
wherein the operations further comprise: recording a given compaction based on (i) including, in a graph-based data structure, a reference to each of the one or more new metadata files and the plurality of pre-compaction metadata files, (Wang, column 4, line 43- This is because compaction typically involves reading several levels of the LSM tree, merging the SSTables of the different levels, and then writing new and sorted SSTables back into the LSM tree ;column 7, line 65-in addition to objects and their snapshots, uploader manager 135 may store files (and their snapshots) in object storage 165 or another remote storage for backup purposes and send information associated with the stored files to compute nodes 155 to create, manage, and store metadata associated with the files; column 9, line 25- For example, when a compute node receives, for an object, an object ID "ObjID," a snapshot ID "SnapID," and a number of logical blocks "NumBlocks," the compute node may first generate a new chunk ID and then add a new record to table 142 that maps a three-tuple key <objectID, snapID, LBA> 210 to a two-tuple value <chunkID, NumBlocks> 220;)
and (ii) associating, via the graph-based data structure, the one or more new metadata files with the plurality of pre-compaction metadata files, (Wang, column 4, line 43- This is because compaction typically involves reading several levels of the LSM tree, merging the SSTables of the different levels, and then writing new and sorted SSTables back into the LSM tree; column 7, line 65-in addition to objects and their snapshots, uploader manager 135 may store files (and their snapshots) in object storage 165 or another remote storage for backup purposes and send information associated with the stored files to compute nodes 155 to create, manage, and store metadata associated with the files; column 9, line 25- For example, when a compute node receives, for an object, an object ID "ObjID," a snapshot ID "SnapID," and a number of logical blocks "NumBlocks," the compute node may first generate a new chunk ID and then add a new record to table 142 that maps a three-tuple key <objectID, snapID, LBA> 210 to a two-tuple value <chunkID, NumBlocks> 220;)
wherein the metadata database is configured to remove a given metadata file that has zero references. (Wang, column 15, line 14- After the compaction of L0 and Ll is completed, space may be reclaimed in L0 and also in Ll, because all SSTables of L0 are deleted even though new tables 712-718 ( e.g., as well as other tables) are added to L1, but SSTables 702-708 (e.g., as well as other tables) of L1 are deleted (e.g., when no older versions of catalogue file point to these SSTables )
However Wang in view of Jain does not clearly disclose:
a hard- link reference
However, CAMARGOS discloses:
a hard- link reference (CAMARGOS [0087]A modified log-structured merge tree is used to store and compact the metadata SST files; [0147] Hardlinking. SSTs are copied from one RangeletManager to another when view change happens. This is done by hardlinking the existing SST with a name corresponding to the destination range and adding the new SST to the RangeletManager. Because the original data has a history of flushes and compactions, leading for example, to SSTs having sizes in accord with their compaction levels, the system tries to preserve this information by hardlinking them with the same level. For splits, while hardlinking is happening, new data is coming into the new ranges, so flushes are also happening. It is possible that the desired hardlink gets used due to a flush before the hardlink itself happens. For merges, the destination range may already be using the desired hardlink name; [0157] metadata nodes perform garbage collection, which sets up out-of-date metadata for deletion.)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Wang in view of Jain with the teaching of CAMARGOS to preserve the information by hardlinking them with the same level, (CAMARGOS, [0147]).
Claim 18 is rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 11,675,745 B2) in view of Jain (US 2018/0121453 Al) in further view of Shilane (US 20190243702 A1)
Regarding claim 18, Wang in view of Jain discloses all of the features with respect to claim 16 as outlined above. Wang in view of Jain does not clearly disclose: prior to generating the comparison data, estimating a predicted computational resource usage of the comparison data based on a cumulative number of keys in the certain metadata files; and determining to generate the comparison data based on the predicted computational resource usage of the comparison data satisfying a usage threshold.
However Shilane discloses:
prior to generating the comparison data, estimating a predicted computational resource usage of the comparison data based on a cumulative number of keys in the certain metadata files; and determining to generate the comparison data based on the predicted computational resource usage of the comparison data satisfying a usage threshold. (Shilane, [0188] The controller, upon examining the snapshot delta to determine the amount of data to be copied can then calculate the number of worker nodes to allocate based on the specified time constraint and data transfer rate. In other words, the controller assess, examines, estimates, or analyzes the amount of work to be done, reviews the time allowed for replication, and allocates a particular number of worker nodes accordingly; [0124] The controller preserves the previous snapshot (from the last replication event) and calculates a delta of the current snapshot relative to the previous snapshot. Object names in the snapshot include their creation time. The two snapshots are read into memory (possibly in pieces) and compared. If an object name and timestamp exists in both snapshots, it does not need to be replicated.)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Wang in view of Jain with the teaching of Shilane in order to strike a balance across efficient use of storage, network bandwidth, and processing time, (Shilane, [0160]).
Claim 20 is rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 11,675,745 B2) in view of Jain (US 2018/0121453 Al) in further view of in view of Miah (US20200089574)
Regarding claim 20, Wang in view of Jain discloses all of the features with respect to claim 16 as outlined above. Wang in view of Jain does not clearly disclose: identifying the certain metadata files by traversing a directed acyclic graph (DAG) data structure to identify metadata files in the first snapshot image that do not lead to the certain metadata files referenced by the second snapshot image.
However Miah discloses:
identifying the certain metadata files by traversing a directed acyclic graph (DAG) data structure to identify metadata files in the first snapshot image that do not lead to the certain metadata files referenced by the second snapshot image. (Miah, [0066] A directed acyclic graph (DAG) 400 associated with four snapshots ; Fig. 9, step 908 to Determine Candidate Clusters of Snapshots for Given Time; Fig. 4; [0071] Similarly, as between the two snapshots 402C-D of the same underlying block device, file system 410D reflects a change relative to file system 410C, and directory 412D reflects a change relative to directory 412C. As illustrated, the file 414D appears in snapshot 402D but does not appear within 402C, indicating that the file associated with vertex 414D first appeared at the time the snapshot 402D was generated; [0073] the use of DAGs or similar types of models greatly eases the traversal of large numbers of snapshots by allowing for a quick, directed lookup for several different types of information related to the data structures reflected in snapshots at specific points in time, as well as easing comparative lookups and other such data operations;[0026] Such information may be used as an initial stage to deterministically filter a large "cloud" of snapshots into those that are associated with a given multipart block device;)
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teaching of Wang in view of Jain with the teaching of Miah to use of DAGs or similar types of models that greatly eases the traversal of large numbers of snapshots by allowing for a quick, directed lookup for several different types of information related to the data structures reflected in snapshots at specific points in time, as well as easing comparative lookups and other such data operations, (Miah, [0073]).
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Faezeh Forouharnejad whose telephone number is (571)270-7416. The examiner can normally be reached on generally Monday through Friday.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Shah Sanjiv can be reached on (571)272-4098. 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 Patent Center and the Private Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from Patent Center or Private PAIR. Status information for unpublished applications is available through Patent Center and Private PAIR to authorized users only. Should you have questions about access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free)
/F.F. /
Examiner, Art Unit 2166
/KHANH B PHAM/Primary Examiner, Art Unit 2166