DETAILED ACTION
Notice of Pre-AIA or AIA Status
1. The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Amendment
2. Applicant's response filed 25 June 2025 has been considered and entered. Accordingly, claims 21-40 are pending in this application. Claims 1-20 are cancelled; and claims 21-40 are newly added.
Abstract
3. Applicant is reminded of the proper language and format for an abstract of the disclosure.
The abstract should be in narrative form and generally limited to a single paragraph on a separate sheet within the range of 50 to 150 words in length. The abstract should describe the disclosure sufficiently to assist readers in deciding whether there is a need for consulting the full patent text for details.
The language should be clear and concise and should not repeat information given in the title. It should avoid using phrases which can be implied, such as, “The disclosure concerns,” “The disclosure defined by this invention,” “The disclosure describes,” etc. In addition, the form and legal phraseology often used in patent claims, such as “means” and “said,” should be avoided.
The abstract contains the legal term “embodiment” and that it should be removed. It is suggested to add “aspect” instead of “embodiment”.
Claim Rejections - 35 USC § 102
4. In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale or otherwise available to the public before the effective filing date of the claimed invention.
5. Claims 21-29 and 38-40 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Johnson et al. (cited in IDS) (US 2020/0151268 A1) hereinafter Johnson.
As to claim 21, Johnson discloses a data storage system, comprising: at least one processor; and at least one non-transitory, computer-readable medium containing instructions that, when executed by the at least one processor (Para. 26), cause the data storage system to implement a key-value engine comprising:
a storage structure including leaves and nodes (Fig. 10; 12), a first node including: child data indicating key ranges associated with child nodes of the first node, a first key range associated with a first child node (Fig. 3A, Para. 59, “the buffer tree manager can define a set of compacted packets according to the current set of keys in the pivot of the target node. For example, each compacted packet can correspond to a child of the target node and in particular to the key range associated with that child.”. Para. 36, FIG. 3A shows some details of buffer tree 106, i.e., a storage structure, for storing data elements 14. The buffer tree 106 can include a root node 302 having pivots 312, which point to children nodes 304 of the root node. The root node 302 and children nodes 304 can be referred to as internal nodes. The root node 302 is associated with a corresponding buffer 314 to store data elements 14 received from users 12 of the buffer tree 106. Thus, a first node including: child data indicating key ranges associated with child nodes of the first node, a first key range associated with a first child node.); and
an update buffer including levels of differing capacities, a first level of the levels having a first capacity (Fig. 3A, Para. 107, “the insertion of a packet of data elements in the root node 1202 can result in an avalanche cascade whereby every internal node reaches its maximum buffer capacity and has to flush packets to all its children nodes.”. Para. 37, “Each child node 304, likewise, includes pivots (pointers) 312 that point to its to children nodes, which can be internal nodes 304 or leaf nodes 306. Each child node 304 is also associated with a corresponding buffer 314 for storing data elements 14.”. Thus, an update buffer including levels of differing capacities, a first level of the levels having a first capacity); and
wherein the key-value engine is configured to: obtain a first batch of key-value entries, an amount of the first batch being less than or equal to the first capacity (Para. 38, “With reference to the inset in FIG. 3B, in accordance with some embodiments, the buffer tree 106 can receive and process data elements 14, for insertion into the buffer tree 106, in batches referred to herein as packets 326.”. Para. 50, “The collector can gather batches of data elements and send them to the buffer tree manager as packets of data elements.”. Para. 107, “the insertion of a packet of data elements in the root node 1202 can result in an avalanche cascade whereby every internal node reaches its maximum buffer capacity and has to flush packets to all its children nodes.”. Thus, the key-value engine is configured to: obtain a first batch of key-value entries, an amount of the first batch being less than or equal to the first capacity.);
insert the first batch into the update buffer (Para. 38, “With reference to the inset in FIG. 3B, in accordance with some embodiments, the buffer tree 106 can receive and process data elements 14, for insertion into the buffer tree 106, in batches referred to herein as packets 326.”. Para. 125, “when data elements are added at the root node of a conventional buffer tree, the incoming data elements are sorted with data elements already in the root's buffer, and the updated root buffer is rewritten to disk. Likewise, when data elements are flushed from the root node to its children nodes, the data elements in the children buffer are immediately sorted and rewritten to disk.”.);
determine satisfaction of an update condition for the first child node (Para. 102, a flush operation can be performed when the combined size of uncompacted packets and compacted packets exceeds a threshold value, i.e., determine satisfaction of an update condition, for the target node. In other embodiments, a flush operation can be performed when the number of uncompacted packets and compacted packets exceeds a threshold value for the target node. In still other embodiments, a flush operation can be performed when either the combined size or the total number exceeds its respective threshold value for the target node. Thus, determine satisfaction of an update condition for the first child node.);
extract a second batch of key-value entries from the update buffer (Para. 38, With reference to the inset in FIG. 3B, in accordance with some embodiments, the buffer tree 106 can receive and process data elements 14, for insertion into the buffer tree 106, in batches, i.e., a second batch of key-value entries, referred to herein as packets 326. Para. 50, “users can issue write operations to the collector to store data elements (e.g., key-value pairs) to the buffer tree. The collector can gather batches of data elements and send them to the buffer tree manager as packets of data elements. For example, the collector can simply receive some number N of data elements from the users. When N data elements have been collected, the collector can create a packet of received data elements and send it off to the buffer tree manager. In some embodiments, the collector can sort the data elements in the packet before sending it to the buffer tree manager”.), the second batch including key-value entries within the first key range (Para. 59, “the buffer tree manager can define a set of compacted packets according to the current set of keys in the pivot of the target node. For example, each compacted packet can correspond to a child of the target node and in particular to the key range associated with that child.”. Thus, the second batch including key-value entries within the first key range.); and
provide the second batch to the first child node (Fig. 8; 12, Para. 107, “insertion of the packet in root node 1202 can result in compacted packets in the root node 1202 to be flushed to some of its children nodes 1212, 1214. As the children nodes 1212, 1214 (recursively) process their respective incoming compacted packets, each child node can wind up having to flush compacted packets to some of its children nodes. For example, child node 1212 can flush compacted packets to all its children nodes 1222, 1224. Likewise, child node 1214 can flush compacted packets to all its children nodes 1226, 1228. The process can continue until the leaf nodes are reached.”. Para. 63, the buffer tree manager can perform a flush operation on the target node, which includes pushing one or more of the compacted packets, i.e., the second batch, in the target node to corresponding one's of the target node's children, i.e., provide the second batch to the first child node.).
As to claim 22, the claim is rejected for the same reasons as claim 21 above. In addition, Johnson discloses wherein: inserting the first batch into the update buffer comprises: determining that the first level is empty; and storing the first batch in the first level of the update buffer (Para. 127, “A write to disk does not occur until the data combining operation is performed (e.g., blocks 804-808) in which data elements in the uncompacted portion of the node's buffer are combined and divided into one or more compacted packets in the compacted portion of the node's buffer. Thus, a node can continue receiving and storing packets into its uncompacted portion of the buffer until an event triggers a data combining operation, for example, such as when the size of the uncompacted portion of the buffer reaches a maximum value.”. Para. 62, “At block 810, the buffer tree manager can determine whether to perform a flush (buffer-emptying) operation on the target node. In some embodiments, a flush operation can be performed whenever a data combining operation is performed. In other embodiments, the buffer tree manager can use other suitable criteria to make the determination whether to perform a flush operation on the target node.”.).
As to claim 23, the claim is rejected for the same reasons as claim 21 above. In addition, Johnson discloses wherein: inserting the first batch into the update buffer comprises: determining that the first level includes a third batch of active key-value entries; generating a combined batch using the first batch and third batch of key- value entries; and storing the combined batch in a second level of the update buffer, the second level having a greater capacity than the first level (Para. 127, “A write to disk does not occur until the data combining operation is performed (e.g., blocks 804-808) in which data elements in the uncompacted portion of the node's buffer are combined and divided into one or more compacted packets in the compacted portion of the node's buffer. Thus, a node can continue receiving and storing packets into its uncompacted portion of the buffer until an event triggers a data combining operation, for example, such as when the size of the uncompacted portion of the buffer reaches a maximum value.”. Para. 46, “The compacted portion 424 of the buffer 414 comprises one or more packets referred to as compacted packets 426b. In accordance with the present disclosure, compacted packets 426b can be created during a process referred to as data combining. During data combining, data elements 14 from one or more uncompacted packets 426a in a given node are written into one or more compacted packets 426b of that node. In accordance with some embodiments, the compacted packets 426b can be written to and stored on disk (e.g., block storage subsystem 104, FIG. 1).”.).
As to claim 24, the claim is rejected for the same reasons as claim 23 above. In addition, Johnson discloses wherein: inserting the first batch into the update buffer further comprises: indirectly associating subsets of the combined batch with the child nodes (Para. 37, “Each child node 304, likewise, includes pivots (pointers) 312 that point to its to children nodes, which can be internal nodes 304 or leaf nodes 306. Each child node 304 is also associated with a corresponding buffer 314 for storing data elements 14.”. Thus, inserting the first batch into the update buffer further comprises: indirectly associating subsets of the combined batch with the child nodes.).
As to claim 25, the claim is rejected for the same reasons as claim 21 above. In addition, Johnson discloses wherein: the first node further includes pending update amounts corresponding to the child nodes; and determining satisfaction of the update condition comprises: updating a first pending update amount of the pending update amounts, the first pending update amount corresponding to the first child node; and determining that the updated first pending update amount exceeds an amount threshold (Para. 102, a flush operation can be performed when the combined size of uncompacted packets and compacted packets exceeds a threshold value, i.e., determine satisfaction of an update condition, for the target node. In other embodiments, a flush operation can be performed when the number of uncompacted packets and compacted packets exceeds a threshold value for the target node. In still other embodiments, a flush operation can be performed when either the combined size or the total number exceeds its respective threshold value for the target node. Para. 127, “A write to disk does not occur until the data combining operation is performed (e.g., blocks 804-808) in which data elements in the uncompacted portion of the node's buffer are combined and divided into one or more compacted packets in the compacted portion of the node's buffer. Thus, a node can continue receiving and storing packets into its uncompacted portion of the buffer until an event triggers a data combining operation, for example, such as when the size of the uncompacted portion of the buffer reaches a maximum value.”.).
As to claim 26, the claim is rejected for the same reasons as claim 21 above. In addition, Johnson discloses wherein: the first level includes at least one first filter that indicates active key ranges within the first level; and extracting the second batch of key-value entries from the update buffer includes: identifying a first key-value subset within the first level; including the first key-value subset within the second batch; and updating the at least one first filter to exclude the first key-value subset from the active key ranges (Fig. 4, Para. 59, “Returning to FIG. 8, at block 806, the buffer tree manager can divide the combined data elements, stored in array 904, into one or more compacted packets in the compacted portion of the buffer. In accordance with the present disclosure, the buffer tree manager can define a set of compacted packets according to the current set of keys in the pivot of the target node. For example, each compacted packet can correspond to a child of the target node and in particular to the key range associated with that child. Accordingly, the buffer tree manager can divide the combined data elements among the compacted packets 426b according to their corresponding key ranges.”.).
As to claim 27, the claim is rejected for the same reasons as claim 21 above. In addition, Johnson discloses wherein: the levels form an ordered set of levels of increasing capacities (Para. 122, “FIG. 14 depicts the worst case, where each node in the path can be completely filled with data items that flush to a single child node so that each time a flush occurs, the buffer in the child node increases by nxB, where B is the buffer size and n is the nth flush. Thus, for example, node 1402 would flush B amount of data to node 1412, resulting in a buffer of size 2xB in node 1412. Node 1412 would flush 2xB amount of data to node 1422, resulting in a buffer of size 3xB in node 1422. Node 1422 would flush 3xB amount of data to a single child node, resulting in a buffer of size 4xB in the child node, and so on.”. Para. 125, “when data elements are added at the root node of a conventional buffer tree, the incoming data elements are sorted with data elements already in the root's buffer, and the updated root buffer is rewritten to disk. Likewise, when data elements are flushed from the root node to its children nodes, the data elements in the children buffer are immediately sorted and rewritten to disk.”. Thus, the levels form an ordered set of levels of increasing capacities.).
As to claim 28, the claim is rejected for the same reasons as claim 27 above. In addition, Johnson discloses wherein: a second level in the ordered set of levels follows the first level and has a capacity twice as great as the first level (Para. 122, “FIG. 14 depicts the worst case, where each node in the path can be completely filled with data items that flush to a single child node so that each time a flush occurs, the buffer in the child node increases by nxB, where B is the buffer size and n is the nth flush. Thus, for example, node 1402 would flush B amount of data to node 1412, resulting in a buffer of size 2xB in node 1412. Node 1412 would flush 2xB amount of data to node 1422, resulting in a buffer of size 3xB in node 1422. Node 1422 would flush 3xB amount of data to a single child node, resulting in a buffer of size 4xB in the child node, and so on.”. Thus, a second level in the ordered set of levels follows the first level and has a capacity twice as great as the first level.).
As to claim 29, the claim is rejected for the same reasons as claim 21 above. In addition, Johnson discloses wherein: the key-value engine is further configured to: store contents of each leaf in a data portion corresponding to the leaf (Fig. 4, Para. 43, “data elements 14 are stored among the nodes of the buffer tree in packets (e.g., 326, FIG. 3B). In some embodiments, a data element 14 can comprise a value and a corresponding key, and can be referred to variously as a data pair, a key-value (k-v) pair, a message, and so on. The 'value' part of the data element 14 represents the information of interest to the user 12 (FIG. 1), which is to be stored in the buffer tree 106. The corresponding 'key' component of the data element 14 can be used as an index into the buffer tree 106 to store the value component and later to access the value component. The data elements 14 can be stored in the buffers of the internal nodes of the buffer tree 106 or in the leaf nodes according to their 'key' components.”. Thus, the key-value engine is further configured to: store contents of each leaf in a data portion corresponding to the leaf.); and store contents of each level of the update buffer in data portions corresponding to the level of the update buffer (Fig. 3A, Para. 36, “The buffer tree 106 can include a root node 302 having pivots 312, which point to children nodes 304 of the root node. The root node 302 and children nodes 304 can be referred to as internal nodes. The root node 302 is associated with a corresponding buffer 314 to store data elements 14 received from users 12 of the buffer tree 106.”.).
As to claim 38, Johnson discloses a non-transitory, computer-readable medium containing instructions that, when executed by at least one processor of a data storage system (Para. 26), cause the data storage system to implement a key-value engine comprising:
a storage structure including leaves and nodes (Fig. 10; 12), a first node including: child data indicating key ranges associated with child nodes of the first node, a first key range associated with a first child node (Fig. 3A, Para. 59, “the buffer tree manager can define a set of compacted packets according to the current set of keys in the pivot of the target node. For example, each compacted packet can correspond to a child of the target node and in particular to the key range associated with that child.”. Para. 36, FIG. 3A shows some details of buffer tree 106, i.e., a storage structure, for storing data elements 14. The buffer tree 106 can include a root node 302 having pivots 312, which point to children nodes 304 of the root node. The root node 302 and children nodes 304 can be referred to as internal nodes. The root node 302 is associated with a corresponding buffer 314 to store data elements 14 received from users 12 of the buffer tree 106. Thus, a first node including: child data indicating key ranges associated with child nodes of the first node, a first key range associated with a first child node.); and
an update buffer including levels of differing capacities, a first level of the levels having a first capacity (Fig. 3A, Para. 107, “the insertion of a packet of data elements in the root node 1202 can result in an avalanche cascade whereby every internal node reaches its maximum buffer capacity and has to flush packets to all its children nodes.”. Para. 37, “Each child node 304, likewise, includes pivots (pointers) 312 that point to its to children nodes, which can be internal nodes 304 or leaf nodes 306. Each child node 304 is also associated with a corresponding buffer 314 for storing data elements 14.”. Thus, an update buffer including levels of differing capacities, a first level of the levels having a first capacity); and
wherein the key-value engine is configured to: obtain a first batch of key-value entries, an amount of the first batch being less than or equal to the first capacity (Para. 38, “With reference to the inset in FIG. 3B, in accordance with some embodiments, the buffer tree 106 can receive and process data elements 14, for insertion into the buffer tree 106, in batches referred to herein as packets 326.”. Para. 50, “The collector can gather batches of data elements and send them to the buffer tree manager as packets of data elements.”. Para. 107, “the insertion of a packet of data elements in the root node 1202 can result in an avalanche cascade whereby every internal node reaches its maximum buffer capacity and has to flush packets to all its children nodes.”. Thus, the key-value engine is configured to: obtain a first batch of key-value entries, an amount of the first batch being less than or equal to the first capacity.);
insert the first batch into the update buffer (Para. 38, “With reference to the inset in FIG. 3B, in accordance with some embodiments, the buffer tree 106 can receive and process data elements 14, for insertion into the buffer tree 106, in batches referred to herein as packets 326.”. Para. 125, “when data elements are added at the root node of a conventional buffer tree, the incoming data elements are sorted with data elements already in the root's buffer, and the updated root buffer is rewritten to disk. Likewise, when data elements are flushed from the root node to its children nodes, the data elements in the children buffer are immediately sorted and rewritten to disk.”.);
determine satisfaction of an update condition for the first child node (Para. 102, a flush operation can be performed when the combined size of uncompacted packets and compacted packets exceeds a threshold value, i.e., determine satisfaction of an update condition, for the target node. In other embodiments, a flush operation can be performed when the number of uncompacted packets and compacted packets exceeds a threshold value for the target node. In still other embodiments, a flush operation can be performed when either the combined size or the total number exceeds its respective threshold value for the target node. Thus, determine satisfaction of an update condition for the first child node.);
extract a second batch of key-value entries from the update buffer (Para. 38, With reference to the inset in FIG. 3B, in accordance with some embodiments, the buffer tree 106 can receive and process data elements 14, for insertion into the buffer tree 106, in batches, i.e., a second batch of key-value entries, referred to herein as packets 326. Para. 50, “users can issue write operations to the collector to store data elements (e.g., key-value pairs) to the buffer tree. The collector can gather batches of data elements and send them to the buffer tree manager as packets of data elements. For example, the collector can simply receive some number N of data elements from the users. When N data elements have been collected, the collector can create a packet of received data elements and send it off to the buffer tree manager. In some embodiments, the collector can sort the data elements in the packet before sending it to the buffer tree manager”.), the second batch including key-value entries within the first key range (Para. 59, “the buffer tree manager can define a set of compacted packets according to the current set of keys in the pivot of the target node. For example, each compacted packet can correspond to a child of the target node and in particular to the key range associated with that child.”. Thus, the second batch including key-value entries within the first key range.); and
provide the second batch to the first child node (Fig. 8; 12, Para. 107, “insertion of the packet in root node 1202 can result in compacted packets in the root node 1202 to be flushed to some of its children nodes 1212, 1214. As the children nodes 1212, 1214 (recursively) process their respective incoming compacted packets, each child node can wind up having to flush compacted packets to some of its children nodes. For example, child node 1212 can flush compacted packets to all its children nodes 1222, 1224. Likewise, child node 1214 can flush compacted packets to all its children nodes 1226, 1228. The process can continue until the leaf nodes are reached.”. Para. 63, the buffer tree manager can perform a flush operation on the target node, which includes pushing one or more of the compacted packets, i.e., the second batch, in the target node to corresponding one's of the target node's children, i.e., provide the second batch to the first child node.).
As to claim 39, the claim is rejected for the same reasons as claim 38 above. In addition, Johnson discloses wherein: the first node further includes pending update amounts corresponding to the child nodes; and determining satisfaction of the update condition comprises: updating a first pending update amount of the pending update amounts, the first pending update amount corresponding to the first child node; and determining that the updated first pending update amount exceeds an amount threshold (Para. 102, a flush operation can be performed when the combined size of uncompacted packets and compacted packets exceeds a threshold value, i.e., determine satisfaction of an update condition, for the target node. In other embodiments, a flush operation can be performed when the number of uncompacted packets and compacted packets exceeds a threshold value for the target node. In still other embodiments, a flush operation can be performed when either the combined size or the total number exceeds its respective threshold value for the target node. Para. 127, “A write to disk does not occur until the data combining operation is performed (e.g., blocks 804-808) in which data elements in the uncompacted portion of the node's buffer are combined and divided into one or more compacted packets in the compacted portion of the node's buffer. Thus, a node can continue receiving and storing packets into its uncompacted portion of the buffer until an event triggers a data combining operation, for example, such as when the size of the uncompacted portion of the buffer reaches a maximum value.”.).
As to claim 40, the claim is rejected for the same reasons as claim 38 above. In addition, Johnson discloses wherein: the levels form an ordered set of levels of increasing capacities ((Para. 122, “FIG. 14 depicts the worst case, where each node in the path can be completely filled with data items that flush to a single child node so that each time a flush occurs, the buffer in the child node increases by nxB, where B is the buffer size and n is the nth flush. Thus, for example, node 1402 would flush B amount of data to node 1412, resulting in a buffer of size 2xB in node 1412. Node 1412 would flush 2xB amount of data to node 1422, resulting in a buffer of size 3xB in node 1422. Node 1422 would flush 3xB amount of data to a single child node, resulting in a buffer of size 4xB in the child node, and so on.”. Para. 125, “when data elements are added at the root node of a conventional buffer tree, the incoming data elements are sorted with data elements already in the root's buffer, and the updated root buffer is rewritten to disk. Likewise, when data elements are flushed from the root node to its children nodes, the data elements in the children buffer are immediately sorted and rewritten to disk.”. Thus, the levels form an ordered set of levels of increasing capacities.)).
6. Claims 30 is rejected under 35 U.S.C. 103 as being unpatentable over Johnson as applied above, in view of Bhola et al. (US 2024/0126738 A1) hereinafter Bhola.
As to claim 30, the claim is rejected for the same reasons as claim 21 above. Johnson does not explicitly disclose wherein: the key-value engine further comprises a write-ahead log configured to store key- value entries; and obtaining the first batch of key-value entries comprising deduplicating and sorting a first portion of the write-ahead log.
However, in the same field of endeavor, Bhola discloses wherein: the key-value engine further comprises a write-ahead log configured to store key- value entries (Para. 39, “One or nodes that comprise a cluster may store data (e.g., tables, indexes, etc.) in a map of KV pairs. A node may store a "range", which can be a subset of the KV pairs (or all of the KV pairs depending on the size of the range) stored by the cluster. A range may also be referred to as a "shard" and/or a "micro-partition". A table and its secondary indexes can be mapped to one or more ranges, where each KV pair in a range may represent a single row in the table (which can also be known as the primary index because the table is sorted by the primary key) or a single row in a secondary index.”. Para. 79, data from the memtable is periodically flushed to sstable files (e.g., of the LSM tree) on disk. Another file on disk referred to as write-ahead log (WAL) can be associated with each memtable to ensure durability in case of power loss or other failures. The WAL can be where the newest (e.g., freshest or most recent) updates issued to the storage engine by the replication layer are stored on disk. Thus, the key-value engine further comprises a write-ahead log configured to store key- value entries.); and
obtaining the first batch of key-value entries comprising deduplicating and sorting a first portion of the write-ahead log (Para. 73, “The storage layer may enable the cluster to read and write data to storage device(s) of each node. As described herein, data may be stored as KV pairs on the storage device(s) using a storage engine. The storage layer may provide atomic write batches and snapshots, which can indicate a subset of transactions.”. Para. 127, “Based on all keys within an ingested sstable adopting a same sequence number, multiple range keys must be supported at the same sequence number. In some cases, duplicate internal keys (e.g., keys with equal prefixes, sequence numbers, and kinds) may be prohibited for the storage engine described herein, based on duplicate internal keys being prohibited within the storage engine, fragments with the same boundaries may be merged within snapshot stripes into a single physical KV pair, which may representing multiple logical KV pairs. In some cases, within a physical KV pair, suffix-value pairs may be stored and sorted by suffix in descending order (e.g., newest to oldest or highest to lowest).”. Thus, obtaining the first batch of key-value entries comprising deduplicating and sorting a first portion of the write-ahead log.).
Therefore, it would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the system of Johnson by including the write-ahead log (WAL) file which can be associated with each memtable to ensure durability in case of power loss or other failures as disclosed by Bhola (Para. 79). The WAL can be where the newest (e.g., freshest or most recent) updates issued to the storage engine by the replication layer are stored on disk. One of the ordinary skills in the art would have motivated to make this modification in order to ensure data from the memtable is periodically flushed to sstable files (e.g., of the LSM tree) on disk as suggested by Bhola (Para. 79).
7. Claims 31-37 are rejected under 35 U.S.C. 103 as being unpatentable over Bhola et al. (US 2024/0126738 A1) hereinafter Bhola, in view of Johnson as applied above.
As to claim 31, Bhola discloses a data storage system comprising: at least one processor; and at least one non-transitory, computer-readable medium containing instructions that, when executed by the at least one processor (Fig. 13, Para. 212), cause the data storage system to perform operations comprising:
appending a key-value entry to a write-ahead log (Para. 39, “One or nodes that comprise a cluster may store data (e.g., tables, indexes, etc.) in a map of KV pairs. A node may store a "range", which can be a subset of the KV pairs (or all of the KV pairs depending on the size of the range) stored by the cluster. A range may also be referred to as a "shard" and/or a "micro-partition". A table and its secondary indexes can be mapped to one or more ranges, where each KV pair in a range may represent a single row in the table (which can also be known as the primary index because the table is sorted by the primary key) or a single row in a secondary index.”. Para. 79, data from the memtable is periodically flushed to sstable files (e.g., of the LSM tree) on disk. Another file on disk referred to as write-ahead log (WAL) can be associated with each memtable to ensure durability in case of power loss or other failures. The WAL can be where the newest (e.g., freshest or most recent) updates issued to the storage engine by the replication layer are stored on disk, i.e., appending a key-value entry to a write-ahead log.);
determining that a first portion of the write-ahead log satisfies a batch generation condition, the first portion of the write-ahead log including the appended key-value entry (Fig. 11A-11B, Para. 39, “Based on the range reaching or exceeding a threshold storage size, the range may split into two ranges. For example, based on reaching 512 mebibytes (MiB) in size, the range may split into two ranges. Successive ranges may split into one or more ranges based on reaching or exceeding a threshold storage size”. Para. 172, At step 1104, the node may determine whether the data block is full. Determining whether the data block is full may include determining whether the data block has reached or exceeded a threshold storage capacity, i.e., determining that a first portion of the write-ahead log satisfies a batch generation condition. As an example, a data block may have a maximum capacity of 32 kilobytes (KB). A data block may be configured to have any suitable storage capacity. If the node determines the data block is full, the method 1100 may proceed to step 1106. If the node determines the data block is not full, the method 1100 may proceed to step 1120.);
generating a first batch by deduplicating and sorting the first portion of the write-ahead log (Para. 73, “The storage layer may enable the cluster to read and write data to storage device(s) of each node. As described herein, data may be stored as KV pairs on the storage device(s) using a storage engine. The storage layer may provide atomic write batches and snapshots, which can indicate a subset of transactions.”. Para. 127, “Based on all keys within an ingested sstable adopting a same sequence number, multiple range keys must be supported at the same sequence number. In some cases, duplicate internal keys (e.g., keys with equal prefixes, sequence numbers, and kinds) may be prohibited for the storage engine described herein, based on duplicate internal keys being prohibited within the storage engine, fragments with the same boundaries may be merged within snapshot stripes into a single physical KV pair, which may representing multiple logical KV pairs. In some cases, within a physical KV pair, suffix-value pairs may be stored and sorted by suffix in descending order (e.g., newest to oldest or highest to lowest).”. Thus, generating a first batch by deduplicating and sorting the first portion of the write-ahead log.).
Bhola does not explicitly disclose writing the first batch to a storage structure including nodes and leaves, a first node of the storage structure including first key-range pivots that indicate first child nodes and a first multi-level update buffer.
However, in the same field of endeavor, Johnson discloses writing the first batch to a storage structure including nodes and leaves (Fig. 10; 12), a first node of the storage structure including first key-range pivots that indicate first child nodes and a first multi-level update buffer (Fig. 3A-3B, Para. 59, “the buffer tree manager can define a set of compacted packets according to the current set of keys in the pivot of the target node. For example, each compacted packet can correspond to a child of the target node and in particular to the key range associated with that child.”. Para. 38, “the buffer tree 106 can receive and process data elements 14, for insertion into the buffer tree 106, in batches referred to herein as packets 326.”. Para. 36, FIG. 3A shows some details of buffer tree 106, i.e., a storage structure, for storing data elements 14. The buffer tree 106 can include a root node 302 having pivots 312, which point to children nodes 304 of the root node. The root node 302 and children nodes 304 can be referred to as internal nodes. The root node 302 is associated with a corresponding buffer 314, i.e., update buffer, to store data elements 14 received from users 12 of the buffer tree 106. Thus, a first node of the storage structure including first key-range pivots that indicate first child nodes and a first multi-level update buffer.).
Therefore, it would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the system of Bhola such that the write-ahead log data of Bhola can be stored in the storage structure of Johnson in order to utilize the storage space as disclosed by Johnson (Para. 129). Each child node, likewise, includes pivots (pointers) that point to its children nodes, which can be internal nodes or leaf nodes. Each child node is also associated with a corresponding buffer for storing data elements (Johnson, Para. 37). One of the ordinary skills in the art would have motivated to make this modification in order to provide mass data storage capability as suggested by Johnson (Para. 23).
As to claim 32, the claim is rejected for the same reasons as claim 31 above. In addition, Bhola discloses wherein: the first portion of the write-ahead log follows a first checkpoint; and the operations further comprise: appending a second checkpoint to the write-ahead log following the first portion; and trimming the write-ahead log based on a location of the second checkpoint (Para. 81, A BlockHandle encodes the location of a block (e.g., index block or data block) within the sstable file, which can be represented as a tuple. An example tuple that represents a BlockHandle may be (file-offset, block-length), where "file-offset" may indicate the location of a data or index block within the sstable file and "block-length" indicates the length of the respective data or index block. Above the second-level index blocks, an sstable can include a single top-level index block that includes a key per second-level index-block (e.g., typically the last key in the second-level block). The top-level index block can map keys to BlockHandles (e.g., where the BlockHandle is the respective value for the key). A BlockHandle can function as a "pointer", i.e., checkpoint, that is used to read the associated block (e.g., second-level index block or data block) indicated by the pointer. Para. 79, “data from the memtable is periodically flushed to sstable files (e.g., of the LSM tree) on disk. Another file on disk referred to as write-ahead log (WAL) can be associated with each memtable to ensure durability in case of power loss or other failures. The WAL can be where the newest (e.g., freshest or most recent) updates issued to the storage engine by the replication layer are stored on disk. Each WAL may have a 1 to 1 correspondence with a memtable. Each WAL and memtable can be kept in sync and updates from the WAL and memtable can be written to sstables periodically as part of the storage engine's normal operation.”. Thus, the first portion of the write-ahead log follows a first checkpoint; and the operations further comprise: appending a second checkpoint to the write-ahead log following the first portion; and trimming the write-ahead log based on a location of the second checkpoint.).
As to claim 33, the claim is rejected for the same reasons as claim 31 above. In addition, Bhola discloses wherein: determining that the first portion of the write-ahead log satisfies the batch generation condition comprises determining that a size of the first portion exceeds a size threshold (Para. 39, “Based on the range reaching or exceding a threshold storage size, the range may split into two ranges. For example, based on reaching 512 meb1bytes (MiB) in size, the range may split into two ranges. Successive ranges may split into one or more ranges based on reaching or exceeding a threshold storage size.”. Para. 172, “At step 1104, the node may determine whether the data block is full. Determining whether the data block is full may include determining whether the data block has reached or exceeded a threshold storage capacity. As an example, a data block may have a maximum capacity of 32 kilobytes (KB). A data block may be configured to have any suitable storage capacity.”. Thus, determining that the first portion of the write-ahead log satisfies the batch generation condition comprises determining that a size of the first portion exceeds a size threshold.).
As to claim 34, the claim is rejected for the same reasons as claim 31 above. In addition, Johnson discloses wherein: writing the first batch to the storage structure includes: inserting the first batch into a first level of the first multi-level update buffer; or generating a combined batch using the first batch and active key- values stored in the first level and inserting the combined batch into a second level of the first multi-level update buffer (Para. 127, “A write to disk does not occur until the data combining operation is performed (e.g., blocks 804-808) in which data elements in the uncompacted portion of the node's buffer are combined and divided into one or more compacted packets in the compacted portion of the node's buffer. Thus, a node can continue receiving and storing packets into its uncompacted portion of the buffer until an event triggers a data combining operation, for example, such as when the size of the uncompacted portion of the buffer reaches a maximum value.”. Para. 46, “compacted packets 426b can be created during a process referred to as data combining. During data combining, data elements 14 from one or more uncompacted packets 426a in a given node are written into one or more compacted packets 426b of that node. In accordance with some embodiments, the compacted packets 426b can be written to and stored on disk (e.g., block storage subsystem 104, FIG. 1).”. Thus, writing the first batch to the storage structure includes: inserting the first batch into a first level of the first multi-level update buffer; or generating a combined batch using the first batch and active key- values stored in the first level and inserting the combined batch into a second level of the first multi-level update buffer.).
As to claim 35, the claim is rejected for the same reasons as claim 31 above. In addition, Bhola discloses wherein: the operations further comprise: maintaining a cache structure that stores locations of key-value entries stored in the write-ahead log (Para. 81, A BlockHandle encodes the location of a block (e.g., index block or data block) within the sstable file, which can be represented as a tuple. An example tuple that represents a BlockHandle may be (file-offset, block-length), where "file-offset" may indicate the location of a data or index block within the sstable file and "block-length" indicates the length of the respective data or index block. Above the second-level index blocks, an sstable can include a single top-level index block that includes a key per second-level index-block (e.g., typically the last key in the second-level block). The top-level index block can map keys to BlockHandles (e.g., where the BlockHandle is the respective value for the key). A BlockHandle can function as a "pointer" that is used to read the associated block (e.g., second-level index block or data block) indicated by the pointer. Para. 79, “data from the memtable is periodically flushed to sstable files (e.g., of the LSM tree) on disk. Another file on disk referred to as write-ahead log (WAL) can be associated with each memtable to ensure durability in case of power loss or other failures. The WAL can be where the newest (e.g., freshest or most recent) updates issued to the storage engine by the replication layer are stored on disk. Each WAL may have a 1 to 1 correspondence with a memtable. Each WAL and memtable can be kept in sync and updates from the WAL and memtable can be written to sstables periodically as part of the storage engine's normal operation.”. Thus, the operations further comprise: maintaining a cache structure that stores locations of key-value entries stored in the write-ahead log.).
As to claim 36, the claim is rejected for the same reasons as claim 31 above. In addition, Bhola discloses wherein: the operations further comprise generating, in response to a read request, a snapshot object (Para. 73, “The storage layer may enable the cluster to read and write data to storage device(s) of each node. As described herein, data may be stored as KV pairs on the storage device(s) using a storage engine. The storage layer may provide atomic write batches and snapshots, which can indicate a subset of transactions.”. Thus, the operations further comprise generating, in response to a read request, a snapshot object.).
As to claim 37, the claim is rejected for the same reasons as claim 31 above. In addition, Johnson discloses wherein: contents of each leaf are stored in a data portion corresponding to the leaf (Fig. 4, Para. 43, “data elements 14 are stored among the nodes of the buffer tree in packets (e.g., 326, FIG. 3B). In some embodiments, a data element 14 can comprise a value and a corresponding key, and can be referred to variously as a data pair, a key-value (k-v) pair, a message, and so on. The 'value' part of the data element 14 represents the information of interest to the user 12 (FIG. 1), which is to be stored in the buffer tree 106. The corresponding 'key' component of the data element 14 can be used as an index into the buffer tree 106 to store the value component and later to access the value component. The data elements 14 can be stored in the buffers of the internal nodes of the buffer tree 106 or in the leaf nodes according to their 'key' components.”. Thus, contents of each leaf are stored in a data portion corresponding to the leaf.); and
contents of each level of the first multi-level update buffer are stored in data portions corresponding to the level of the first multi-level update buffer (Fig. 3A, Para. 36, “The buffer tree 106 can include a root node 302 having pivots 312, which point to children nodes 304 of the root node. The root node 302 and children nodes 304 can be referred to as internal nodes. The root node 302 is associated with a corresponding buffer 314 to store data elements 14 received from users 12 of the buffer tree 106.”. Thus, contents of each level of the first multi-level update buffer are stored in data portions corresponding to the level of the first multi-level update buffer.).
Conclusion
8. The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Wu et al. (US 2018/0349095 A1) teaches log-structured merge tree based data storage architecture.
9. 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, Charles Rones can be reached on 571-272-4085. The fax phone number for the organization where this application or proceeding is assigned is 571 -273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/Mohammad S Bhuyan/Examiner, Art Unit 2168
/CHARLES RONES/Supervisory Patent Examiner, Art Unit 2168
Prosecution Insights