DETAILED ACTION
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 .
Priority
Acknowledgment is made of applicant's claim for foreign priority based on a Chinese Patent Application filed on 12/06/2023. It is noted, however, that an attempt by the office to electronically retrieve, under the priority document exchange program, the foreign application 202311662286.5 to which priority is claimed has failed on 05/06/2025, which is required by 37 CFR 1.55 as a certified copy of the CN202311662286.5 application.
Claim Objections
3. Claims 5 and 18 are objected to because of the following informalities:
Claim 5 is objected because there is a spelling error at line 4 of the claim which is "token". Possible correction "taken".
Claim 18 is objected because there is a typo at line 1 of the claim which is "An electronic device,:". Possible correction “An electronic device:”.
Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
4. Claim 2-5 and 19 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor, or for pre-AIA the applicant regards as the invention.
Claim 2 recites the limitation "the second key data" in line 4. There is insufficient antecedent basis for this limitation in the claim.
Claim 4 recites the limitation "the first value data" in line 13. There is insufficient antecedent basis for this limitation in the claim.
Claim 5 recites the limitation "the highest hierarchical level" in line 4. There is insufficient antecedent basis for this limitation in the claim.
Claim 19 recites the limitation "the second key data" in line 2. There is insufficient antecedent basis for this limitation in the claim.
The remaining claims are rejected for fully incorporating the deficiencies of the base claim(s) from which they depend.
Claim Rejections - 35 USC § 102
5. 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)(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.
6. Claims 1-20 are rejected under 35 U.S.C. 102(a)(2) as being anticipated by Lakshman et al. (US 2024/0028596 A1) hereinafter Lakshman.
As to claim 1, Lakshman discloses a data collection method, comprising:
determining, in response to a garbage collection request, respective first index entries from a first data table to be processed, wherein first key-value pair data and the first index entries are stored in the first data table, the first key-value pair data is derived from a key-value separated log-structured merge tree, and first key data and storage location information in the first data table of the first key-value pair data corresponding to the first key data are stored in the first index entries (Fig. 11, Para. 5, the system stores a set of documents in log-structured object store comprising sequence numbers and document values. The log-structured object store, i.e., a first data table, stores documents of the set of documents in a sorted order and comprises an index, i.e., first index entries, for accessing a document given a sequence number. The system stores a log structured merge tree that maps keys to sequence numbers for accessing documents of the set of documents. The system receives a query statement for querying a database that is managed by the data management system. The query statement specifies a key. The system searches the key in a cache memory. If the key is not found in the cache memory, the system searches for the key in the log-structured merge tree. The system obtains a document sequence number by matching the key from the log-structured merge tree. The system obtains a document value from a log-structured object store that maintains documents sequence numbers and document values. The write amplification in the LSM tree is minimized by separating the storage of the sequence number from document values. Para. 59, “When a document is updated multiple times, the system generates different versions with unique sequence numbers. The log can contain multiple versions of the same key. When a new version is appended, the older versions of the same document are considered stale. The system garbage collects stale versions to reclaim space.”. Thus, the first key-value pair data is derived from a key-value separated log-structured merge tree, and first key data and storage location information in the first data table of the first key-value pair data corresponding to the first key data are stored in the first index entries.);
selecting valid target key data from the first key data stored in the respective first index entries according to current respective second data tables in the log-structured merge tree (Para. 74, “The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files.”. Para. 73, the system stores a set of documents in the log-structured object store and further stores 1110 a log structured merge-tree T1, i.e., second data tables in the log structured merge tree, mapping keys to sequence numbers for accessing documents of the set of documents. The log-structured object store comprises a plurality of log segments. Para. 50, “Since a value pointer is a physical offset derived based on a segment's position within the blocks of the segment, when valid values are rewritten to a new segment, the original value pointers become invalid. For valid values, the system updates the corresponding value pointer offsets in the byKey Index. While cleaning a value store segment, the system determines whether each value is valid or not by performing a lookup into the byKey index. This involves an I/O (input/output) operation per value.”. Para. 77, “The system selects a log segment with the highest fragmentation based on the estimates and rewrites the log segment file by compacting it. The system performs the rewrite process by performing sort merge between the sorted deleted sequence number list and the documents in the log segment. The system identifies matching documents with the stale document list sequence numbers and discards them during the log segment rewrite.”. Thus, selecting valid target key data from the first key data stored in the respective first index entries according to current respective second data tables in the log-structured merge tree.);
reading target value data corresponding to the respective target key data in the first data table according to storage location information in the first index entries where the respective target key data are located (Fig. 3B, 4, Para. 42, The LSM Tree index 330 is an index for the documents stored on a log structured object store, i.e., the first data table, is organized as an LSM Tree. The LSM Tree index stores document key, document sequence number, i.e., storage location information, and size metadata as key-value pairs. For document read operations, the LSM Tree is initially looked up to obtain the document sequence number which is used to read the document value from the log-structured object storage. The LSM tree index maintains bloom filters to optimize the lookup I/O. Thus, reading target value data corresponding to the respective target key data in the first data table according to storage location information in the first index entries where the respective target key data are located.); and
constructing a new first data table according to the target key data and the target value data, and collecting the first data table to be processed, wherein target key-value pair data consisting of the target key data and the target value data, as well as new first index entries, are stored in the new first data table, the target key data and storage location information in the new first data table of the target key-value pair data corresponding to the target key data are comprised in the new first index entries (Para. 50, “The system uses LSM Tree for implementing the byKey index. If the document value is placed along with the key in the byKey index, when LSM Tree runs compaction operations to maintain the tree balance for read and space amplification, a value gets rewritten many times (Up to 40 times for a 4 level tree). To overcome unnecessary write amplification, the storage engine places values in a separate log structured storage and uses sequence number based logical addressing. Instead of actual values, a value pointer is stored in the byKey index in the place of value along with the key. The system maintains a separate storage system tuned for storing large values. When the value storage internal segments (unit of storage) become fragmented, the system cleans the segments by rewriting the values to a new segment. Since a value pointer is a physical offset derived based on a segment's position within the blocks of the segment, when valid values are rewritten to a new segment, the original value pointers become invalid. For valid values, the system updates the corresponding value pointer offsets in the byKey Index. While cleaning a value store segment, the system determines whether each value is valid or not by performing a lookup into the byKey index.”. Para. 74, “The LSM Tree key index in the system follows an LSM Tree level based compaction process to reclaim space. When each level of the LSM Tree disk usage goes above the threshold, few ssTable files from the level are picked and moved to the next level by merging with the overlapping files in the next level. The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files.”. Para. 78, The key index LSM tree maintains the latest state of the database with key and sequence number pairs. When the system performs an LSM Tree compaction, multiple ssTables are merged into new ssTables, i.e., constructing a new first data table, and older versions or deleted key-value pairs are discarded. Thus, constructing a new first data table according to the target key data and the target value data, and collecting the first data table to be processed, wherein target key-value pair data consisting of the target key data and the target value data, as well as new first index entries, are stored in the new first data table, the target key data and storage location information in the new first data table of the target key-value pair data corresponding to the target key data are comprised in the new first index entries.).
As to claim 2, the claim is rejected for the same reasons as claim 1 above. In addition, Lakshman discloses wherein selecting the valid target key data from the first key data stored in the respective first index entries according to the current respective second data tables in the log-structured merge tree, comprises: selecting first key data identical to any one of the second key data, as the valid target key data, from the first key data stored in the respective first index entries according to respective second key data stored in the current respective second data tables in the log-structured merge tree (Para. 5, “the system stores a set of documents in log-structured object store comprising sequence numbers and document values. The log-structured object store stores documents of the set of documents in a sorted order and comprises an index for accessing a document given a sequence number. The system stores a log structured merge tree that maps keys to sequence numbers for accessing documents of the set of documents. The system receives a query statement for querying a database that is managed by the data management system. The query statement specifies a key. The system searches the key in a cache memory. If the key is not found in the cache memory, the system searches for the key in the log-structured merge tree. The system obtains a document sequence number by matching the key from the log-structured merge tree. The system obtains a document value from a log-structured object store that maintains documents sequence numbers and document values.”. Para. 77, “The system selects a log segment with the highest fragmentation based on the estimates and rewrites the log segment file by compacting it. The system performs the rewrite process by performing sort merge between the sorted deleted sequence number list and the documents in the log segment. The system identifies matching documents with the stale document list sequence numbers and discards them during the log segment rewrite.”. Thus, selecting first key data identical to any one of the second key data, as the valid target key data, from the first key data stored in the respective first index entries according to respective second key data stored in the current respective second data tables in the log-structured merge tree.).
As to claim 3, the claim is rejected for the same reasons as claim 2 above. In addition, Lakshman discloses wherein selecting the first key data identical to any one of the second key data as the valid target key data from the first key data stored in the respective first index entries according to the respective second key data stored in current respective current second data tables in the log-structured merge tree, comprises: traversing, with respect to any one of the first key data, the respective second data tables sequentially in accordance with a hierarchy to which the respective second data table belongs in the log-structured merge tree to search a second data table associated with the first key data (Para. 32, “When a record needs to be added or removed to the copy-on-write B+Tree, the system locates the leaf page where the record key belongs by traversing the tree from root page, navigating through the intermediate nodes. The system makes a copy of the page in-memory and makes the modification in the page to add or remove the record. The new version of the page is appended to the database file.”.); and determining that the first key data is the valid target key data in response to that the second data table associated with the first key data is searched and the second key data in the second data table which is identical to the first key data has the same version as the first key data (Para. 5, “the system stores a set of documents in log-structured object store comprising sequence numbers and document values. The log-structured object store stores documents of the set of documents in a sorted order and comprises an index for accessing a document given a sequence number. The system stores a log structured merge tree that maps keys to sequence numbers for accessing documents of the set of documents. The system receives a query statement for querying a database that is managed by the data management system. The query statement specifies a key. The system searches the key in a cache memory. If the key is not found in the cache memory, the system searches for the key in the log-structured merge tree. The system obtains a document sequence number by matching the key from the log-structured merge tree. The system obtains a document value from a log-structured object store that maintains documents sequence numbers and document values.”. Para. 77, “The system selects a log segment with the highest fragmentation based on the estimates and rewrites the log segment file by compacting it. The system performs the rewrite process by performing sort merge between the sorted deleted sequence number list and the documents in the log segment. The system identifies matching documents with the stale document list sequence numbers and discards them during the log segment rewrite.”. Thus, determining that the first key data is the valid target key data in response to that the second data table associated with the first key data is searched and the second key data in the second data table which is identical to the first key data has the same version as the first key data.).
As to claim 4, the claim is rejected for the same reasons as claim 2 above. In addition, Lakshman discloses wherein selecting the first key data identical to any one of the second key data as the valid target key data, from the first key data stored in the respective first index entries according to the respective second key data stored in current respective second data tables in the log-structured merge tree, comprises: traversing, with respect to any one of the first key data, the respective second data tables sequentially in accordance with a hierarchy to which the respective second data table belongs in the log-structured merge tree to determine a second data table associated with the first key data (Para. 32, “When a record needs to be added or removed to the copy-on-write B+Tree, the system locates the leaf page where the record key belongs by traversing the tree from root page, navigating through the intermediate nodes. The system makes a copy of the page in-memory and makes the modification in the page to add or remove the record. The new version of the page is appended to the database file.”.); and reading a first target index data block from the second data table associated with the first key data, wherein the first target index data block comprises multiple second index entries, the second index entries are first type of index entries and/or second type of index entries, the first type of index entries are indexes associated with the second key data and table indexes of the first data table in which the first value data corresponding to the second key data is located, the second type of index entries are index entries associated with third key data and storage location information of key-value pair data corresponding to the third key data in the second data table, the key-value pair data corresponding to the third key data has a data volume less than a preset data volume, and the key-value pair data corresponding to the second key data has a data volume greater than or equal to the preset data volume; determining, in response to the multiple second index entries with the first type of index entries, whether second key data matching the first key data exists according to the second key data in the first type of index entries; and taking the first key data as the target key data in response to determining that second key data matching the first key data exists (Para. 5, “the system stores a set of documents in log-structured object store comprising sequence numbers and document values. The log-structured object store stores documents of the set of documents in a sorted order and comprises an index for accessing a document given a sequence number. The system stores a log structured merge tree that maps keys to sequence numbers for accessing documents of the set of documents. The system receives a query statement for querying a database that is managed by the data management system. The query statement specifies a key. The system searches the key in a cache memory. If the key is not found in the cache memory, the system searches for the key in the log-structured merge tree. The system obtains a document sequence number by matching the key from the log-structured merge tree. The system obtains a document value from a log-structured object store that maintains documents sequence numbers and document values. The system returns the document value to the requestor. The write amplification in the LSM tree is minimized by separating the storage of the sequence number from document values.”. Para. 77, “The system selects a log segment with the highest fragmentation based on the estimates and rewrites the log segment file by compacting it. The system performs the rewrite process by performing sort merge between the sorted deleted sequence number list and the documents in the log segment. The system identifies matching documents with the stale document list sequence numbers and discards them during the log segment rewrite.”. Thus, taking the first key data as the target key data in response to determining that second key data matching the first key data exists.).
As to claim 5, the claim is rejected for the same reasons as claim 3 above. In addition, Lakshman discloses wherein the second data table associated with the first key data contains second key data identical to the first key data, and in response to that there exists multiple second data tables containing the second key data identical to the first key data, a second data table with the highest hierarchical level in the multiple second data tables is token as the second data table associated with the first key data (Para. 83, “FIG. 12 illustrates storing information describing hot or cold writes according to an embodiment. The old sequence numbers belong to the old writes and higher sequence numbers correspond to the recent writes. The log follows a time series order. If few documents are modified periodically, they get rewritten often and most likely the tail end of the log accumulates garbage more often. The cleaner can pick the log segments from the tail side and rewrite them by removing obsolete values and replacing the log segment. The colder segments from the head side of the log are never rewritten unnecessarily until a certain percentage of the objects in the log segment becomes garbage.”. Thus, the second data table associated with the first key data contains second key data identical to the first key data, and in response to that there exists multiple second data tables containing the second key data identical to the first key data, a second data table with the highest hierarchical level in the multiple second data tables is token as the second data table associated with the first key data.).
As to claim 6, the claim is rejected for the same reasons as claim 1 above. In addition, Lakshman discloses wherein before selecting the first key data identical to any one of the second key data as the valid target key data from the first key data stored in the respective first index entries according to the respective second key data stored in current respective second data tables in the log-structured merge tree, the method comprises: determining, with respect to any one of the first key data, whether matched key data matching the first key data exists from buffered key data with a hot data feature that is contained in a set of key data buffered in a memory, wherein the hot data feature is used for indicating that the buffered key data is key data repeatedly written multiple times; determining whether the matched key data and the first key data are the same version in response to that there exists the matched key data matched with the first key data; and determining that the first key data is invalid key data in response to that the matched key data and the first key data are not the same version; or taking the first key data directly as the target key data in response to that the matched key data and the first key data are the same version (Para. 5, “The system searches the key in a cache memory. If the key is not found in the cache memory, the system searches for the key in the log-structured merge tree. The system obtains a document sequence number by matching the key from the log-structured merge tree. The system obtains a document value from a log-structured object store that maintains documents sequence numbers and document values.”. Para. 77, “The system selects a log segment with the highest fragmentation based on the estimates and rewrites the log segment file by compacting it. The system performs the rewrite process by performing sort merge between the sorted deleted sequence number list and the documents in the log segment. The system identifies matching documents with the stale document list sequence numbers and discards them during the log segment rewrite.”. Para. 84, “The head side of the log behaves similar to separate cold log in special value store. The disclosed systems and methods simplify the number of moving parts in the system by unifying large value storage to sequence tree. The disclosed systems and methods save the lookup I/O per item required for value relocation (for valid items). The disclosed systems and methods eliminate duplicate key storage in value store (reduces space amplification). The disclosed systems and methods save the additional CPU required for value store writes, relocations, overhead of maintaining hot-cold classification and cleaning operation. The write amplification savings due to separate value store are also applicable in unified seq tree. For seq tree iterations, earlier lookup into keyindex and a read from value store were required for fetching a separated item. With sequence log, an additional one I/O can be saved.”. Thus, the matched key data and the first key data are the same version in response to that there exists the matched key data matched with the first key data.).
As to claim 7, the claim is rejected for the same reasons as claim 6 above. In addition, Lakshman discloses wherein selecting the first key data identical to any one of the second key data as the valid target key data, from the first key data stored in the respective first index entries according to the respective second key data stored in current respective second data tables in the log-structured merge tree, comprises: selecting the target key data from the first key data without the matched key data according to the respective second key data stored in the respective second data tables (Para. 77, “The system selects a log segment with the highest fragmentation based on the estimates and rewrites the log segment file by compacting it. The system performs the rewrite process by performing sort merge between the sorted deleted sequence number list and the documents in the log segment. The system identifies matching documents with the stale document list sequence numbers and discards them during the log segment rewrite.”. Thus, selecting the target key data from the first key data without the matched key data according to the respective second key data stored in the respective second data tables.).
As to claim 8, the claim is rejected for the same reasons as claim 7 above. In addition, Lakshman discloses wherein constructing the new first data table according to the target key data and the target value data, comprises: determining the target key data with the matched key data as hot key data with the hot data feature, and/or, determining the target key data without the matched key data as cold key data with a cold data feature, wherein the cold data feature is used for indicating that the cold key data is key data written once; and constructing the new first data table with the hot data feature according to the respective hot key data and target value data corresponding to the hot key data, and/or, constructing the new first data table with the cold data feature according to the respective cold key data and target value data corresponding to the cold key data (Para. Para. 78, The key index LSM tree maintains the latest state of the database with key and sequence number pairs. When the system performs an LSM Tree compaction, multiple ssTables are merged into new ssTables, i.e., constructing a new first data table, and older versions or deleted key-value pairs are discarded. Para. 84, “The head side of the log behaves similar to separate cold log in special value store. The disclosed systems and methods simplify the number of moving parts in the system by unifying large value storage to sequence tree. The disclosed systems and methods save the lookup I/O per item required for value relocation (for valid items). The disclosed systems and methods eliminate duplicate key storage in value store (reduces space amplification). The disclosed systems and methods save the additional CPU required for value store writes, relocations, overhead of maintaining hot-cold classification and cleaning operation. The write amplification savings due to separate value store are also applicable in unified seq tree. For seq tree iterations, earlier lookup into keyindex and a read from value store were required for fetching a separated item. With sequence log, an additional one I/O can be saved.”.).
As to claim 9, the claim is rejected for the same reasons as claim 1 above. In addition, Lakshman discloses wherein determining, in response to the garbage collection request, the respective first index entries from the first data table to be processed, comprises: determining, in response to the garbage collection request, multiple first data tables; selecting a first data table with a hot data feature from the multiple first data tables; and taking the filtered first data table with the hot data feature as the first data table to be processed, and determining the respective first index entries from the first data table to be processed (Para. 74, The LSM Tree key index in the system follows an LSM Tree level based compaction process to reclaim space. When each level of the LSM Tree disk usage goes above the threshold, few ssTable files from the level are picked and moved to the next level by merging with the overlapping files in the next level. The stale records or deleted records are filtered out while writing out the new set of ssTable files, i.e., taking the filtered first data table with the hot data feature, and space is reclaimed by deleting the prior ssTable files. For key index LSM Tree, the system may use a size multiplier (e.g., 10) for the level sizes. Para. 84, “The head side of the log behaves similar to separate cold log in special value store. The disclosed systems and methods simplify the number of moving parts in the system by unifying large value storage to sequence tree. The disclosed systems and methods save the lookup I/O per item required for value relocation (for valid items). The disclosed systems and methods eliminate duplicate key storage in value store (reduces space amplification). The disclosed systems and methods save the additional CPU required for value store writes, relocations, overhead of maintaining hot-cold classification and cleaning operation. The write amplification savings due to separate value store are also applicable in unified seq tree. For seq tree iterations, earlier lookup into keyindex and a read from value store were required for fetching a separated item. With sequence log, an additional one I/O can be saved.”.).
As to claim 10, the claim is rejected for the same reasons as claim 9 above. In addition, Lakshman discloses wherein the method further comprises: after taking the filtered first data table with the hot data feature as the first data table to be processed and performing the data collection method, determining the remaining first data tables with the cold data feature as the first data table to be processed, and performing the data collection method (Para. 83, “FIG. 12 illustrates storing information describing hot or cold writes according to an embodiment. The old sequence numbers belong to the old writes and higher sequence numbers correspond to the recent writes. The log follows a time series order. If few documents are modified periodically, they get rewritten often and most likely the tail end of the log accumulates garbage more often. The cleaner can pick the log segments from the tail side and rewrite them by removing obsolete values and replacing the log segment. The colder segments from the head side of the log are never rewritten unnecessarily until a certain percentage of the objects in the log segment becomes garbage.”. Thus, determining the remaining first data tables with the cold data feature as the first data table to be processed, and performing the data collection method.).
As to claim 11, the claim is rejected for the same reasons as claim 9 above. In addition, Lakshman discloses wherein determining the respective first index entries from the first data table to be processed, comprises: determining whether the respective first index entries associated with the first data table to be processed are pre-buffered in the memory (Para. 41, “The write-ahead log (WAL) 320 is an append-only log where the incoming key-value pair writes are initially written to provide durability. Writes are initially buffered in the write-cache and also written to the write-ahead log. The write API returns only after issuing an fsync (file sync operation) on the write-ahead log file.”. Para. 81, “The system uses a shared write head log to ensure durability for the write operations by logging the modification operation in the WAL while writes are buffered in the in-memory write cache.”.); and determining the respective first index entries from the first data table to be processed in response to that the respective first index entries associated with the first data table to be processed are not pre-buffered in the memory; and buffering the respective first index entries in the memory (Para. 40, “The write-cache 310 is an in-memory component used to buffer key-value pairs and provide large sequential writes to the persistent storage. The write-cache is also used during lookup for key-value pairs.”. Para. 60, “Similar to the in-memory component used by an LSM tree, the log-structured object store uses a write buffer to issue large writes to the tail log segment.”.).
As to claim 12, the claim is rejected for the same reasons as claim 1 above. In addition, Lakshman discloses wherein the method further comprises: receiving a data write operation instruction to determine key-value pair data to be stored; selecting, in response to the data volume of the determined key-value pair data to be stored reaching a data volume threshold, third key-value pair data with a data volume greater than or equal to a preset data volume and fourth key-value pair data with a data volume less than the preset data volume from multiple key-value pair data to be stored (Para. 74, “The LSM Tree key index in the system follows an LSM Tree level based compaction process to reclaim space. When each level of the LSM Tree disk usage goes above the threshold, few ssTable files from the level are picked and moved to the next level by merging with the overlapping files in the next level. The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files. For key index LSM Tree, the system may use a size multiplier (e.g., 10) for the level sizes.”. Para. 48, “The system tracks the number of mutation records in the cache memory. If the number of records stored in the cache memory exceed a threshold, the system stores the content of the cache memory in a persistent storage. This operation is performed by (1) converting key-value pairs into key index for a log-structured merge tree (LSM tree) and (2) appending documents to a tail log-segment of a log-structured object store. The system clears the cache memory and returns an indication to the client device that the mutation operation has successfully performed to the database.”. Para. 57, “The log comprises log segments with predefined sizes. The storage engine maintains a tail log file. As writes occur, document mutations are appended to the tail log. Once the tail log file reaches the size threshold, a current log file is made immutable, and a new tail log file is initialized. A tail log file may also be referred to herein as a log segment.”.);
constructing a new first data table according to the third key-value pair data; and constructing a new second data table according to the fourth key-value pair data, and table indexes of the first data table in which key data in the third key-value pair data and value data in the third key-value pair data are located (Para. 78, The key index LSM tree maintains the latest state of the database with key and sequence number pairs. When the system performs an LSM Tree compaction, multiple ssTables are merged into new ssTables, i.e., constructing a new first data table, and older versions or deleted key-value pairs are discarded.).
As to claim 13, the claim is rejected for the same reasons as claim 12 above. In addition, Lakshman discloses wherein constructing the new first data table according to the third key-value pair data, comprises: obtaining a set of key data buffered in the memory, wherein the set of key data includes at least one piece of buffered key data with a hot data feature, the hot data feature is used for indicating that the buffered key data is key data repeatedly written multiple times; selecting fifth key-value pair data with matched buffered key data from the third key-value pair data (Para. 84, “The head side of the log behaves similar to separate cold log in special value store. The disclosed systems and methods simplify the number of moving parts in the system by unifying large value storage to sequence tree. The disclosed systems and methods save the lookup I/O per item required for value relocation (for valid items). The disclosed systems and methods eliminate duplicate key storage in value store (reduces space amplification). The disclosed systems and methods save the additional CPU required for value store writes, relocations, overhead of maintaining hot-cold classification and cleaning operation. The write amplification savings due to separate value store are also applicable in unified seq tree. For seq tree iterations, earlier lookup into keyindex and a read from value store were required for fetching a separated item. With sequence log, an additional one I/O can be saved.”.); and
constructing a new first data table with the hot data feature according to the fifth key-value pair data; and constructing a new first data table with a cold data feature according to key-value pair data in the third key-value pair data other than the fifth key-value pair data (Para. 78, The key index LSM tree maintains the latest state of the database with key and sequence number pairs. When the system performs an LSM Tree compaction, multiple ssTables are merged into new ssTables, i.e., constructing a new first data table, and older versions or deleted key-value pairs are discarded.).
As to claim 14, the claim is rejected for the same reasons as claim 13 above. In addition, Lakshman discloses wherein after constructing the new second data table, the method further comprises: performing, in response to a data table compaction operation instruction, a data compaction operation on at least part of the constructed second data tables of the log-structured merge tree to obtain a merged second data table, wherein table indexes in second index entries corresponding to the second key data in the merged second data table are determined according to a first data table in which value data corresponding to the second key data is located at the time it is last written; and updating the set of key data using the second key data in the merged second data table (Para. 74, “The LSM Tree key index in the system follows an LSM Tree level based compaction process to reclaim space. When each level of the LSM Tree disk usage goes above the threshold, few ssTable files from the level are picked and moved to the next level by merging with the overlapping files in the next level. The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files. For key index LSM Tree, the system may use a size multiplier (e.g., 10) for the level sizes.”. Para. 77, “The system selects a log segment with the highest fragmentation based on the estimates and rewrites the log segment file by compacting it. The system performs the rewrite process by performing sort merge between the sorted deleted sequence number list and the documents in the log segment. The system identifies matching documents with the stale document list sequence numbers and discards them during the log segment rewrite.”. Para. 78, “The key index LSM tree maintains the latest state of the database with key and sequence number pairs. When the system performs an LSM Tree compaction, multiple ssTables are merged into new ssTables and older versions or deleted key-value pairs are discarded.”.).
As to claim 15, the claim is rejected for the same reasons as claim 1 above. In addition, Lakshman discloses wherein the method further comprises: determining a total size of storage space currently used by the log-structured merge tree and all the first data tables; and adjusting a receiving frequency of a data write operation according to the total size of storage space and a preset space threshold (Para. 36, “As more data is written, the database file grows in size. To reclaim the space occupied by the stale pages, the system performs defragmentation or compaction. The B+ Tree metadata maintains the size of the current live B+tree in the file. Once the stale data size grows above a fragmentation threshold compared to the database file size, the system performs compaction.”. Para. 74, “The LSM Tree key index in the system follows an LSM Tree level based compaction process to reclaim space. When each level of the LSM Tree disk usage goes above the threshold, few ssTable files from the level are picked and moved to the next level by merging with the overlapping files in the next level. The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files. For key index LSM Tree, the system may use a size multiplier (e.g., 10) for the level sizes.”.).
As to claim 16, the claim is rejected for the same reasons as claim 15 above. In addition, Lakshman discloses wherein adjusting the receiving frequency of the data write operation according to the total size of storage space and the preset space threshold, comprises: determining a receiving frequency decrease value for the data write operation in response to the total size of storage space reaches a first preset space threshold, and controlling the receiving frequency of the data write operation according to the receiving frequency decrease value; or stopping receiving the data write operation instruction in response to the total size of storage space reaching a second preset space threshold, wherein the second preset space threshold is greater than the first preset space threshold (Para. 36, “As more data is written, the database file grows in size. To reclaim the space occupied by the stale pages, the system performs defragmentation or compaction. The B+ Tree metadata maintains the size of the current live B+tree in the file. Once the stale data size grows above a fragmentation threshold compared to the database file size, the system performs compaction.”. Para. 74, “The LSM Tree key index in the system follows an LSM Tree level based compaction process to reclaim space. When each level of the LSM Tree disk usage goes above the threshold, few ssTable files from the level are picked and moved to the next level by merging with the overlapping files in the next level. The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files. For key index LSM Tree, the system may use a size multiplier (e.g., 10) for the level sizes.”.).
As to claim 17, the claim is rejected for the same reasons as claim 16 above. In addition, Lakshman discloses wherein the method further comprises: determining a first thread number of a garbage collection thread in response to the total size of storage space does not reach the first preset space threshold, wherein the garbage collection thread is used for performing a garbage collection operation for at least one first data table; or determining a second thread number of a garbage collection thread in response to the total size of storage space reaches the first preset space threshold, wherein the second thread number is greater than the first thread number; or determining a third thread number of a garbage collection thread in response to the total size of storage space reaches the first preset space threshold, wherein the third thread number is greater than the second thread number (Para. 37, “The system performs a compaction operation using a background thread. The system obtains the current B+tree root offset and opens a B+tree iterator. The system opens a new database file and performs a B+ Tree bulk load operation to the new file to rebuild the B+tree. While the compaction is running, the writes may be still ongoing with the old database file. The compactor operates on a point-in-time version of the B+tree. After finishing the B+ Tree bulk load, the system runs a catchup phase to replay over the new additions/deletions that happened to the B+Tree from the point-in-time version used by the compactor up to the latest B+ Tree in the database file. On completion of the catchup phase, the old database file is removed, and writers and readers switch to the new database file. The space is reclaimed.”. Thus, the garbage collection thread is used for performing a garbage collection operation for at least one first data table.).
As to claim 18, Lakshman discloses, an electronic device: at least a processor, and a non-transitory memory with instructions thereon, wherein the instructions upon execution by the processor (Fig. 13, Para. 87), cause the processor to: determine, in response to a garbage collection request, respective first index entries from a first data table to be processed, wherein first key-value pair data and the first index entries are stored in the first data table, the first key-value pair data is derived from a key-value separated log-structured merge tree, and first key data and storage location information in the first data table of the first key-value pair data corresponding to the first key data are stored in the first index entries (Fig. 11, Para. 5, the system stores a set of documents in log-structured object store comprising sequence numbers and document values. The log-structured object store, i.e., a first data table, stores documents of the set of documents in a sorted order and comprises an index, i.e., first index entries, for accessing a document given a sequence number. The system stores a log structured merge tree that maps keys to sequence numbers for accessing documents of the set of documents. The system receives a query statement for querying a database that is managed by the data management system. The query statement specifies a key. The system searches the key in a cache memory. If the key is not found in the cache memory, the system searches for the key in the log-structured merge tree. The system obtains a document sequence number by matching the key from the log-structured merge tree. The system obtains a document value from a log-structured object store that maintains documents sequence numbers and document values. The write amplification in the LSM tree is minimized by separating the storage of the sequence number from document values. Para. 59, “When a document is updated multiple times, the system generates different versions with unique sequence numbers. The log can contain multiple versions of the same key. When a new version is appended, the older versions of the same document are considered stale. The system garbage collects stale versions to reclaim space.”. Thus, the first key-value pair data is derived from a key-value separated log-structured merge tree, and first key data and storage location information in the first data table of the first key-value pair data corresponding to the first key data are stored in the first index entries.);
filter out valid target key data from the first key data stored in the respective first index entries according to current respective second data tables in the log-structured merge tree (Para. 74, “The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files.”. Para. 73, the system stores a set of documents in the log-structured object store and further stores 1110 a log structured merge-tree T1, i.e., second data tables in the log structured merge tree, mapping keys to sequence numbers for accessing documents of the set of documents. The log-structured object store comprises a plurality of log segments. Para. 50, “Since a value pointer is a physical offset derived based on a segment's position within the blocks of the segment, when valid values are rewritten to a new segment, the original value pointers become invalid. For valid values, the system updates the corresponding value pointer offsets in the byKey Index. While cleaning a value store segment, the system determines whether each value is valid or not by performing a lookup into the byKey index. This involves an I/O (input/output) operation per value.”. Para. 77, “The system selects a log segment with the highest fragmentation based on the estimates and rewrites the log segment file by compacting it. The system performs the rewrite process by performing sort merge between the sorted deleted sequence number list and the documents in the log segment. The system identifies matching documents with the stale document list sequence numbers and discards them during the log segment rewrite.”. Thus, filter out valid target key data from the first key data stored in the respective first index entries according to current respective second data tables in the log-structured merge tree.);
read target value data corresponding to the respective target key data in the first data table according to storage location information in the first index entries where the respective target key data are located (Fig. 3B, 4, Para. 42, The LSM Tree index 330 is an index for the documents stored on a log structured object store, i.e., the first data table, is organized as an LSM Tree. The LSM Tree index stores document key, document sequence number, i.e., storage location information, and size metadata as key-value pairs. For document read operations, the LSM Tree is initially looked up to obtain the document sequence number which is used to read the document value from the log-structured object storage. The LSM tree index maintains bloom filters to optimize the lookup I/O. Thus, reading target value data corresponding to the respective target key data in the first data table according to storage location information in the first index entries where the respective target key data are located.); and
construct a new first data table according to the target key data and the target value data, and collecting the first data table to be processed, wherein target key-value pair data consisting of the target key data and the target value data, as well as new first index entries, are stored in the new first data table, the target key data and storage location information in the new first data table of the target key-value pair data corresponding to the target key data are comprised in the new first index entries (Para. 50, “The system uses LSM Tree for implementing the byKey index. If the document value is placed along with the key in the byKey index, when LSM Tree runs compaction operations to maintain the tree balance for read and space amplification, a value gets rewritten many times (Up to 40 times for a 4 level tree). To overcome unnecessary write amplification, the storage engine places values in a separate log structured storage and uses sequence number based logical addressing. Instead of actual values, a value pointer is stored in the byKey index in the place of value along with the key. The system maintains a separate storage system tuned for storing large values. When the value storage internal segments (unit of storage) become fragmented, the system cleans the segments by rewriting the values to a new segment. Since a value pointer is a physical offset derived based on a segment's position within the blocks of the segment, when valid values are rewritten to a new segment, the original value pointers become invalid. For valid values, the system updates the corresponding value pointer offsets in the byKey Index. While cleaning a value store segment, the system determines whether each value is valid or not by performing a lookup into the byKey index.”. Para. 74, “The LSM Tree key index in the system follows an LSM Tree level based compaction process to reclaim space. When each level of the LSM Tree disk usage goes above the threshold, few ssTable files from the level are picked and moved to the next level by merging with the overlapping files in the next level. The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files.”. Para. 78, The key index LSM tree maintains the latest state of the database with key and sequence number pairs. When the system performs an LSM Tree compaction, multiple ssTables are merged into new ssTables, i.e., constructing a new first data table, and older versions or deleted key-value pairs are discarded. Thus, construct a new first data table according to the target key data and the target value data, and collecting the first data table to be processed, wherein target key-value pair data consisting of the target key data and the target value data, as well as new first index entries, are stored in the new first data table, the target key data and storage location information in the new first data table of the target key-value pair data corresponding to the target key data are comprised in the new first index entries.).
As to claim 19, the claim is rejected for the same reasons as claim 18 above. In addition, Lakshman discloses wherein the processor is caused to: filter out first key data identical to any one of the second key data, as the valid target key data, from the first key data stored in the respective first index entries according to respective second key data stored in the current respective second data tables in the log-structured merge tree (Para. 42, “the LSM Tree is initially looked up to obtain the document sequence number which is used to read the document value from the log-structured object storage.”. Para. 74, “The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files.”. Para. 50, “The system maintains a separate storage system tuned for storing large values. When the value storage internal segments (unit of storage) become fragmented, the system cleans the segments by rewriting the values to a new segment. Since a value pointer is a physical offset derived based on a segment's position within the blocks of the segment, when valid values are rewritten to a new segment, the original value pointers become invalid. For valid values, the system updates the corresponding value pointer offsets in the byKey Index. While cleaning a value store segment, the system determines whether each value is valid or not by performing a lookup into the byKey index. This involves an I/O (input/output) operation per value.”. Thus, the processor is caused to: filter out first key data identical to any one of the second key data, as the valid target key data, from the first key data stored in the respective first index entries according to respective second key data stored in the current respective second data tables in the log-structured merge tree.).
As to claim 20, Lakshman discloses a non-transitory computer-readable storage medium storing instructions that cause at least a processor to (Fig. 13, Para. 87): determine, in response to a garbage collection request, respective first index entries from a first data table to be processed, wherein first key-value pair data and the first index entries are stored in the first data table, the first key-value pair data is derived from a key-value separated log-structured merge tree, and first key data and storage location information in the first data table of the first key-value pair data corresponding to the first key data are stored in the first index entries (Fig. 11, Para. 5, the system stores a set of documents in log-structured object store comprising sequence numbers and document values. The log-structured object store, i.e., a first data table, stores documents of the set of documents in a sorted order and comprises an index, i.e., first index entries, for accessing a document given a sequence number. The system stores a log structured merge tree that maps keys to sequence numbers for accessing documents of the set of documents. The system receives a query statement for querying a database that is managed by the data management system. The query statement specifies a key. The system searches the key in a cache memory. If the key is not found in the cache memory, the system searches for the key in the log-structured merge tree. The system obtains a document sequence number by matching the key from the log-structured merge tree. The system obtains a document value from a log-structured object store that maintains documents sequence numbers and document values. The write amplification in the LSM tree is minimized by separating the storage of the sequence number from document values. Para. 59, “When a document is updated multiple times, the system generates different versions with unique sequence numbers. The log can contain multiple versions of the same key. When a new version is appended, the older versions of the same document are considered stale. The system garbage collects stale versions to reclaim space.”. Thus, the first key-value pair data is derived from a key-value separated log-structured merge tree, and first key data and storage location information in the first data table of the first key-value pair data corresponding to the first key data are stored in the first index entries.);
filter out valid target key data from the first key data stored in the respective first index entries according to current respective second data tables in the log-structured merge tree (Para. 74, “The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files.”. Para. 73, the system stores a set of documents in the log-structured object store and further stores 1110 a log structured merge-tree T1, i.e., second data tables in the log structured merge tree, mapping keys to sequence numbers for accessing documents of the set of documents. The log-structured object store comprises a plurality of log segments. Para. 50, “Since a value pointer is a physical offset derived based on a segment's position within the blocks of the segment, when valid values are rewritten to a new segment, the original value pointers become invalid. For valid values, the system updates the corresponding value pointer offsets in the byKey Index. While cleaning a value store segment, the system determines whether each value is valid or not by performing a lookup into the byKey index. This involves an I/O (input/output) operation per value.”. Para. 77, “The system selects a log segment with the highest fragmentation based on the estimates and rewrites the log segment file by compacting it. The system performs the rewrite process by performing sort merge between the sorted deleted sequence number list and the documents in the log segment. The system identifies matching documents with the stale document list sequence numbers and discards them during the log segment rewrite.”. Thus, filter out valid target key data from the first key data stored in the respective first index entries according to current respective second data tables in the log-structured merge tree.);
read target value data corresponding to the respective target key data in the first data table according to storage location information in the first index entries where the respective target key data are located (Fig. 3B, 4, Para. 42, The LSM Tree index 330 is an index for the documents stored on a log structured object store, i.e., the first data table, is organized as an LSM Tree. The LSM Tree index stores document key, document sequence number, i.e., storage location information, and size metadata as key-value pairs. For document read operations, the LSM Tree is initially looked up to obtain the document sequence number which is used to read the document value from the log-structured object storage. The LSM tree index maintains bloom filters to optimize the lookup I/O. Thus, reading target value data corresponding to the respective target key data in the first data table according to storage location information in the first index entries where the respective target key data are located.); and
construct a new first data table according to the target key data and the target value data, and collecting the first data table to be processed, wherein target key-value pair data consisting of the target key data and the target value data, as well as new first index entries, are stored in the new first data table, the target key data and storage location information in the new first data table of the target key-value pair data corresponding to the target key data are comprised in the new first index entries (Para. 50, “The system uses LSM Tree for implementing the byKey index. If the document value is placed along with the key in the byKey index, when LSM Tree runs compaction operations to maintain the tree balance for read and space amplification, a value gets rewritten many times (Up to 40 times for a 4 level tree). To overcome unnecessary write amplification, the storage engine places values in a separate log structured storage and uses sequence number based logical addressing. Instead of actual values, a value pointer is stored in the byKey index in the place of value along with the key. The system maintains a separate storage system tuned for storing large values. When the value storage internal segments (unit of storage) become fragmented, the system cleans the segments by rewriting the values to a new segment. Since a value pointer is a physical offset derived based on a segment's position within the blocks of the segment, when valid values are rewritten to a new segment, the original value pointers become invalid. For valid values, the system updates the corresponding value pointer offsets in the byKey Index. While cleaning a value store segment, the system determines whether each value is valid or not by performing a lookup into the byKey index.”. Para. 74, “The LSM Tree key index in the system follows an LSM Tree level based compaction process to reclaim space. When each level of the LSM Tree disk usage goes above the threshold, few ssTable files from the level are picked and moved to the next level by merging with the overlapping files in the next level. The stale records or deleted records are filtered out while writing out the new set of ssTable files and space is reclaimed by deleting the prior ssTable files.”. Para. 78, The key index LSM tree maintains the latest state of the database with key and sequence number pairs. When the system performs an LSM Tree compaction, multiple ssTables are merged into new ssTables, i.e., constructing a new first data table, and older versions or deleted key-value pairs are discarded. Thus, construct a new first data table according to the target key data and the target value data, and collecting the first data table to be processed, wherein target key-value pair data consisting of the target key data and the target value data, as well as new first index entries, are stored in the new first data table, the target key data and storage location information in the new first data table of the target key-value pair data corresponding to the target key data are comprised in the new first index entries.).
Conclusion
7. The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Boles et al. (US 2019/0065621 A1) teaches a KVS tree database.
XUE et al. (US 2022/0335028 A1) teaches a data access method, a data access control device, and a data access system.
LEE et al. (US 2024/0370363 A1) teaches a key-value based data storage device that efficiently processes a range query command by performing a prefetch operation and an operation method thereof.
8. Any inquiry concerning this communication or earlier communications from the examiner should be directed to MOHAMMAD SOLAIMAN BHUYAN whose telephone number is (571)272-7843. The examiner can normally be reached on Monday - Friday 9:00am-5:00pm EST.
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, Robert Beausoliel can be reached on 571-272-3645. 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.
/MOHAMMAD S BHUYAN/Examiner, Art Unit 2167
/ROBERT W BEAUSOLIEL JR/Supervisory Patent Examiner, Art Unit 2167