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 .
Response to Amendment
In view of Applicant's amendments, the objection to the claims is withdrawn except those addressed below.
In view of Applicant's amendments, the rejection under 35 USC § 112(b) is withdrawn.
Claim Objections
Claims 5 and 17-20 are objected to because of the following informalities:
Claim 5, line 2, before “M new nodes”, insert --the-- and line 3, after “of”, “a” should be --the--.
Claim 17, line 15, before “new nodes”, insert --the--.
Claims 18-20 depend on the objected claim and inherit the same issue.
Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of the first paragraph of pre-AIA 35 U.S.C. 112:
The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor of carrying out his invention.
Claims 3-8 and 14-20 rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. The claim(s) contains subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention.
Claim 3 recites the generating the virtual nodes comprises determining a number of virtual nodes to generate for each of the new nodes based on at least one of a capacity of the new nodes, a desired load balance factor, or virtual node-to-physical node ratio.
The specification recites (see paragraphs [0030] and [0032]):
Specifically, the cumulative balance selection is used for assigning virtual nodes. The list of new nodes M to be added is provided as input in block 402. A number of virtual nodes U is generated in block 404. For example, if M=5 and 100 virtual nodes are assigned per node, then U=500. In block 406, each node will then be assigned virtual nodes from the virtual node list in a round robin structure.
This scheme may be a constraint that for the possible balancing. The capacity of each node 510, including different capacities may be utilized for determining which nodes need balanced and how they are to be balanced.
The specification recites generating a number of virtual nodes and the capacity of each node may be utilized for determining which nodes need balanced and how they are to be balanced. However, the specification does not disclose determining a number of virtual nodes to generate for each of the new nodes based on at least one of a capacity of the new nodes, a desired load balance factor, or virtual node-to-physical node ratio. Thus, the specification does not support “determining a number of virtual nodes to generate for each of the new nodes based on at least one of a capacity of the new nodes, a desired load balance factor, or virtual node-to-physical node ratio” of claim 3.
Claim 4 recites the allocating the virtual nodes to the token range on the consistent hash ring comprises assigning each virtual node a token position within the token range based on a hash function applied to an identifier of the virtual node.
The specification recites (see paragraph [0014]):
A consistent hash function may determine for each key on which N nodes the key is stored. A hash value may be called a token. Each node may be assigned a value on the hash ring, and a token range is the region on the ring from the current token to the predecessor token. The keys whose hash values fall in the range are assigned to that node which owns the right end of the token range as shown in FIG. 1.
The specification recites generating a consistent hash function may determine which nodes store the key and assigning each node to a value on the hash ring. However, the specification does not disclose assigning each virtual node a token position within the token range based on a hash function applied to an identifier of the virtual node. Thus, the specification does not support “the allocating the virtual nodes to the token range on the consistent hash ring comprises assigning each virtual node a token position within the token range based on a hash function applied to an identifier of the virtual node” of claim 4.
Claim 7 recites wherein the generating the virtual nodes or the assigning each of the virtual nodes considers a determination of configurations associated with the new nodes.
The specification recites (see paragraphs [0030] and [0032]):
Specifically, the cumulative balance selection is used for assigning virtual nodes. The list of new nodes M to be added is provided as input in block 402. A number of virtual nodes U is generated in block 404. For example, if M=5 and 100 virtual nodes are assigned per node, then U=500. In block 406, each node will then be assigned virtual nodes from the virtual node list in a round robin structure.
FIG. 5 illustrates example configurations 502 that may be considered for the balancing. Specifically, the algorithm or system considers one or more of these configurations 502 to determine which nodes are balanced and how they are balanced.
The specification recites generating a number of virtual nodes, assigning virtual nodes to nodes in a round robin structure, and considering configurations for balancing. However, the specification does not disclose generating the virtual nodes or assigning the virtual nodes considering configurations associated with the new nodes. Thus, the specification does not support “wherein the generating the virtual nodes or the assigning each of the virtual nodes considers a determination of configurations associated with the new nodes” of claim 7.
Claim 14 recites the generating the virtual nodes comprises determining a number of virtual nodes to generate for each of the identified nodes based on at least one of a capacity of the identified nodes, a desired load balance factor, or virtual node-to-physical node ratio.
The specification recites (see paragraphs [0030] and [0032]):
Specifically, the cumulative balance selection is used for assigning virtual nodes. The list of new nodes M to be added is provided as input in block 402. A number of virtual nodes U is generated in block 404. For example, if M=5 and 100 virtual nodes are assigned per node, then U=500. In block 406, each node will then be assigned virtual nodes from the virtual node list in a round robin structure.
This scheme may be a constraint that for the possible balancing. The capacity of each node 510, including different capacities may be utilized for determining which nodes need balanced and how they are to be balanced.
The specification recites generating a number of virtual nodes and the capacity of each node may be utilized for determining which nodes need balanced and how they are to be balanced. However, the specification does not disclose determining a number of virtual nodes to generate for each of the identified nodes based on at least one of a capacity of the new nodes, a desired load balance factor, or virtual node-to-physical node ratio. Thus, the specification does not support “the generating the virtual nodes comprises determining a number of virtual nodes to generate for each of the identified nodes based on at least one of a capacity of the identified nodes, a desired load balance factor, or virtual node-to-physical node ratio” of claim 14.
Claim 15 recites wherein the generating the virtual nodes or the assigning each of the virtual nodes considers a determination of configurations associated with the identified nodes.
The specification recites (see paragraphs [0030] and [0032]):
Specifically, the cumulative balance selection is used for assigning virtual nodes. The list of new nodes M to be added is provided as input in block 402. A number of virtual nodes U is generated in block 404. For example, if M=5 and 100 virtual nodes are assigned per node, then U=500. In block 406, each node will then be assigned virtual nodes from the virtual node list in a round robin structure.
FIG. 5 illustrates example configurations 502 that may be considered for the balancing. Specifically, the algorithm or system considers one or more of these configurations 502 to determine which nodes are balanced and how they are balanced.
The specification recites generating a number of virtual nodes, assigning virtual nodes to nodes in a round robin structure, and considering configurations for balancing. However, the specification does not disclose generating the virtual nodes or assigning the virtual nodes considering configurations associated with the identified nodes. Thus, the specification does not support “wherein the generating the virtual nodes or the assigning each of the virtual nodes considers a determination of configurations associated with the identified nodes” of claim 15.
Claim 17 recites determine configurations associated with the new nodes.
The specification recites (see paragraphs [0030] and [0032]):
Specifically, the cumulative balance selection is used for assigning virtual nodes. The list of new nodes M to be added is provided as input in block 402. A number of virtual nodes U is generated in block 404. For example, if M=5 and 100 virtual nodes are assigned per node, then U=500. In block 406, each node will then be assigned virtual nodes from the virtual node list in a round robin structure.
FIG. 5 illustrates example configurations 502 that may be considered for the balancing. Specifically, the algorithm or system considers one or more of these configurations 502 to determine which nodes are balanced and how they are balanced.
The specification recites generating a number of virtual nodes, assigning virtual nodes to nodes in a round robin structure, and considering configurations for balancing. However, the specification does not disclose generating the virtual nodes or assigning the virtual nodes considering configurations associated with the new nodes. Thus, the specification does not support “determine configurations associated with the new nodes” of claim 17.
Claim 17 recites generate a plurality of virtual nodes corresponding to the new nodes based on the determined configurations;
The specification recites (see paragraphs [0030] and [0032]):
Specifically, the cumulative balance selection is used for assigning virtual nodes. The list of new nodes M to be added is provided as input in block 402. A number of virtual nodes U is generated in block 404. For example, if M=5 and 100 virtual nodes are assigned per node, then U=500. In block 406, each node will then be assigned virtual nodes from the virtual node list in a round robin structure.
FIG. 5 illustrates example configurations 502 that may be considered for the balancing. Specifically, the algorithm or system considers one or more of these configurations 502 to determine which nodes are balanced and how they are balanced.
The specification recites generating a number of virtual nodes, assigning virtual nodes to nodes in a round robin structure, and considering configurations for balancing. However, the specification does not disclose generate a plurality of virtual nodes corresponding to the new nodes based on the determined configurations Thus, the specification does not support “generate a plurality of virtual nodes corresponding to the new nodes based on the determined configurations”.
Claim 19 recites execute a simulation to determine a node distribution for the new nodes based on the measured imbalance.
The specification recites (see paragraph [0005]):
There may be an algorithm or system that can measure an imbalance at individual nodes. The imbalance may be due to traffic distribution or other usage at the nodes. The goal may be to minimize any imbalance. In particular, the determination for the balancing may be part of a simulation for balancing. The simulation can be used for determining proper node distribution (e.g. number of nodes, capacity of nodes, etc.) which can be used to plan and predict future expansion. There may be a threshold value used such that any node that exceeds the threshold requires balancing. As described, there may be configurations that are considered for each node for the determination of balancing.
The specification recites measuring an imbalance at individual nodes, determination for balancing being a part of a simulation, a simulation can be used for determining proper node distribution, and configurations that are considered for each node for the determination of balancing However, the specification does not disclose determining a node distribution for the new nodes based on the measure imbalance. Thus, the specification does not support “execute a simulation to determine a node distribution for the new nodes based on the measured imbalance” of claim 19.
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.
Claims 3 and 14 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 applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
They recite “a desired load balance factor”. However, the term “desired” is subjective and the specification does not disclose how to decide “desired”. Thus, metes and bounds of claims are indefinite.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1 and 2 are rejected under 35 U.S.C. 103 as being unpatentable over Jawahar et al. (U.S. Patent Application Publication No. US 20200319909 A1, hereinafter “Jawahar”) in view of Araujo et al. (U.S. Patent Application Publication No. US 20190149410 A1, hereinafter “Araujo”) and Nevsv et al. (“cassandra - Difference between a node and vnode - Stack Overflow”, hereinafter “Nevsv”).
With regard to claim 1, Jawahar discloses:
A method for hash token selection (“a system and method for a distributed key-value store”, para [0004]) comprising:
identifying new (“The cluster manager 220 includes programmed instructions to add one or more of the container instances 206 to a cluster and/or remove one or more of the container instances 206 from a cluster.”, para [0050], “The cluster manager 220 may include instructions to restart the existing container instances 206 and to deploy the new container instances 206.”, para [0050]);
generating virtual nodes to correspond with the new (“For example, if there are three container instances and four vnodes created, the first vnode is assigned to the first container instance, the second vnode is assigned to the second container instance, the third vnode is assigned to the third container instance, and the fourth vnode is assigned to the first container instance.”, para [0066]); and
assigning each of the virtual nodes to the new (“The cluster manager distributes the node number of virtual nodes equally across the container number of container instances (306). In some embodiments, distributing the node number of vnodes across the container number of container instance may include round robin assigning.”, para [0066]), wherein each virtual node is sequentially assigned to a corresponding one of the new (“The cluster manager distributes the node number of virtual nodes equally across the container number of container instances (306). In some embodiments, distributing the node number of vnodes across the container number of container instance may include round robin assigning. For example, if there are three container instances and four vnodes created, the first vnode is assigned to the first container instance, the second vnode is assigned to the second container instance, the third vnode is assigned to the third container instance, and the fourth vnode is assigned to the first container instance.”, para [0066]); and
Jawahar does not disclose:
nodes
allocating the virtual nodes to a token range of a consistent hash ring;
Araujo discloses container instances are nodes ("The computing devices may further host virtual environments allowing multiple computing nodes (e.g., virtual machine instances, container instances) to be hosted on a single physical computing device.", para [0002]).
Both the systems of Jawahar and Araujo deal with container instances. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar in view of Araujo to understand container instances are nodes.
Nevsv discloses:
allocating the virtual nodes to a token range of a consistent hash ring (“vnodes architecture (also used in riak for example) makes virtualization of the "node" layer, splitting the ring into high number of token ranges (vnodes) and each physical node (cassandra service) has number of vnodes running on it.”, middle of page 1).
Both the systems of Jawahar and Nevsv deal with virtual nodes. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Nevsv to “making data distribution much more flexible.” (Sharma, middle of page 1).
With regard to claim 2, Jawahar as modified discloses the method of claim 1.
Jawahar further discloses:
wherein the virtual nodes correspond with the new (“The cluster manager distributes the node number of virtual nodes equally across the container number of container instances (306). In some embodiments, distributing the node number of vnodes across the container number of container instance may include round robin assigning. For example, if there are three container instances and four vnodes created, the first vnode is assigned to the first container instance, the second vnode is assigned to the second container instance, the third vnode is assigned to the third container instance, and the fourth vnode is assigned to the first container instance.”, para [0066]).
However, Jawahar does not explicitly teach nodes. Araujo discloses container instances are nodes ("The computing devices may further host virtual environments allowing multiple computing nodes (e.g., virtual machine instances, container instances) to be hosted on a single physical computing device.", para [0002]).
Both the systems of Jawahar and Araujo deal with container instances. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Araujo to understand container instances are nodes.
Claims 3 and 7-8 are rejected under 35 U.S.C. 103 as being unpatentable over Jawahar in view of Araujo, and Nevsv as applied to claims 1 and 2 above, and further view of Williams (“Virtual nodes in Cassandra 1.2”).
With regard to claim 3, Jawahar as modified discloses the method of claim 2.
Jawahar as modified does not disclose however, Williams discloses:
wherein the generating the virtual nodes comprises determining a number of virtual nodes to generate for each of the new nodes based on at least one of a capacity of the new nodes, (“If you started your older machines with 64 vnodes per node and the new machines are twice as powerful, simply give them 128 vnodes each and the cluster remains balanced even during transition.”, page 4, first full paragraph).
Both the systems of Jawahar and Williams deal with virtual nodes. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Williams to improve system reliability.
With regard to claim 7, Jawahar as modified discloses the method of claim 1.
Jawahar as modified does not disclose however, Williams discloses:
wherein the generating the virtual nodes or the assigning each of the virtual nodes considers a determination of configurations associated with the new nodes (“If you started your older machines with 64 vnodes per node and the new machines are twice as powerful, simply give them 128 vnodes each and the cluster remains balanced even during transition.”, page 4, first full paragraph).
Both the systems of Jawahar and Williams deal with virtual nodes. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Williams to improve system reliability.
With regard to claim 8, Jawahar as modified discloses the method of claim 7.
Jawahar as modified does not disclose however, Williams discloses:
wherein the configurations comprise at least one of (“If you started your older machines with 64 vnodes per node and the new machines are twice as powerful, simply give them 128 vnodes each and the cluster remains balanced even during transition.”, page 4, first full paragraph).
Both the systems of Jawahar and Williams deal with virtual nodes. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Williams to improve system reliability.
Claims 9 and 13 are rejected under 35 U.S.C. 103 as being unpatentable over Jawahar et al. (U.S. Patent Application Publication No. US 20200319909 A1, hereinafter “Jawahar”) in view of Araujo et al. (U.S. Patent Application Publication No. US 20190149410 A1, hereinafter “Araujo”).
With regard to claim 9, Jawahar discloses:
A method for cumulative balance selection (“a system and method for a distributed key-value store”, para [0004]) comprising:
identifying (“The cluster manager 220 includes programmed instructions to add one or more of the container instances 206 to a cluster and/or remove one or more of the container instances 206 from a cluster.”, para [0050], “The cluster manager 220 may include instructionws to restart the existing container instances 206 and to deploy the new container instances 206.”, para [0050]);
generating virtual nodes to correspond with the identified (“For example, if there are three container instances and four vnodes created, the first vnode is assigned to the first container instance, the second vnode is assigned to the second container instance, the third vnode is assigned to the third container instance, and the fourth vnode is assigned to the first container instance.”, para [0066]); and
assigning each of the virtual nodes to the identified nodes (“The cluster manager distributes the node number of virtual nodes equally across the container number of container instances (306). In some embodiments, distributing the node number of vnodes across the container number of container instance may include round robin assigning. For example, if there are three container instances and four vnodes created, the first vnode is assigned to the first container instance, the second vnode is assigned to the second container instance, the third vnode is assigned to the third container instance, and the fourth vnode is assigned to the first container instance.”, para [0066]).
However, Jawahar does not explicitly teach nodes. Araujo discloses container instances are nodes ("The computing devices may further host virtual environments allowing multiple computing nodes (e.g., virtual machine instances, container instances) to be hosted on a single physical computing device.", para [0002]).
Both the systems of Jawahar and Araujo deal with container instances. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar in view of Araujo to understand container instances are nodes.
With regard to claim 13, Jawahar as modified discloses the method of claim 9.
Jawahar further discloses:
wherein the virtual nodes correspond with the identified (“the first vnode is assigned to the first container instance”, para [0066], “The cluster manager 220 may include instructions to restart the existing container instances 206 and to deploy the new container instances 206.”, para [0050]).
However, Jawahar does not explicitly teach nodes. Araujo discloses container instances are nodes ("The computing devices may further host virtual environments allowing multiple computing nodes (e.g., virtual machine instances, container instances) to be hosted on a single physical computing device.", para [0002]).
Both the systems of Jawahar and Araujo deal with container instances. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar in view of Araujo to understand container instances are nodes.
Claim 10 is rejected under 35 U.S.C. 103 as being unpatentable over Jawahar in view of Araujo as applied to claim 10 above, and further view of Nevsv et al. (“cassandra - Difference between a node and vnode - Stack Overflow”, hereinafter “Nevsv”).
With regard to claim 10, Jawahar as modified discloses the method of claim 9.
Jawahar as modified does not disclose however, Nevsv discloses:
wherein the round robin structure allocates the virtual nodes to a token range of a consistent hash ring (“vnodes architecture (also used in riak for example) makes virtualization of the "node" layer, splitting the ring into high number of token ranges (vnodes) and each physical node (cassandra service) has number of vnodes running on it.”, middle of page 1).
Both the systems of Jawahar and Nevsv deal with virtual nodes. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Nevsv to “making data distribution much more flexible.” (Sharma, middle of page 1).
Claims 11-12 are rejected under 35 U.S.C. 103 as being unpatentable over Jawahar in view of Araujo and Nevsv as applied to claim 10 above, and further view of Weisberg et al. (U.S. Patent Application Publication No. US 20150186187 A1, hereinafter “Weisberg”).
With regard to claim 11, Jawahar as modified discloses the method of claim 10.
Jawahar as modified does not disclose however, Weisberg discloses:
wherein when adding M new nodes (“FIG. 3 is a simplified illustration showing the addition of a new node 3 with logical partitions P5 and P6 to a database cluster.”, para [0023], fig 3), a distance between two of the virtual nodes for one of M identified nodes is at least M-1 virtual nodes of a consistent hash ring (“FIG. 4 illustrates addition of logical partitions P5 and P6 to the hash ring of FIG. 2.”, para [0024], fig 4, Fig. 4 shows three logical partitions between P5 and P6).
PNG
media_image1.png
352
376
media_image1.png
Greyscale
Both the systems of Jawahar and Weisberg deal with consistent hashing. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Weisberg to improve the distribution of the load.
With regard to claim 12, Jawahar as modified discloses the method of claim 11.
Jawahar further discloses:
wherein the round robin structure comprises assigning a first identified node a 0th index virtual node, and assigning a second identified node a 1st index virtual node (“In some embodiments, distributing the node number of vnodes across the container number of container instance may include round robin assigning. For example, if there are three container instances and four vnodes created, the first vnode is assigned to the first container instance, the second vnode is assigned to the second container instance, the third vnode is assigned to the third container instance, and the fourth vnode is assigned to the first container instance.”, para [0066]).
Claim 14 is rejected under 35 U.S.C. 103 as being unpatentable over Jawahar in view of Araujo as applied to claim 9 above, and further view of Williams (“Virtual nodes in Cassandra 1.2”).
With regard to claim 14, Jawahar as modified discloses the method of claim 9.
Jawahar as modified does not disclose however, Williams discloses:
wherein the generating the virtual nodes comprises determining a number of virtual nodes to generate for each of the identified nodes based on at least one of a capacity of the identified nodes, (“If you started your older machines with 64 vnodes per node and the new machines are twice as powerful, simply give them 128 vnodes each and the cluster remains balanced even during transition.”, page 4, first full paragraph).
Both the systems of Jawahar and Williams deal with virtual nodes. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Williams to improve system reliability.
Claim 17 is rejected under 35 U.S.C. 103 as being unpatentable over Jawahar et al. (U.S. Patent Application Publication No. US 20200319909 A1, hereinafter “Jawahar”) in view of Araujo et al. (U.S. Patent Application Publication No. US 20190149410 A1, hereinafter “Araujo”), Weisberg et al. (U.S. Patent Application Publication No. US 20150186187 A1, hereinafter “Weisberg”), Williams (“Virtual nodes in Cassandra 1.2”), and Nevsv et al. (“cassandra - Difference between a node and vnode - Stack Overflow”, hereinafter “Nevsv”).
With regard to claim 17, Jawahar discloses:
A distributed storage system for balanced virtual node allocation comprising:
a processor configured to execute instructions stored in memory to (“The instructions may be stored on one or more computer readable and/or executable storage media including non-transitory storage media such as non-transitory storage media in the storage pool 140 with respect to FIG. 1.”, para [0036]):
identify new (“The cluster manager 220 includes programmed instructions to add one or more of the container instances 206 to a cluster and/or remove one or more of the container instances 206 from a cluster.”, para [0050], “The cluster manager 220 may include instructions to restart the existing container instances 206 and to deploy the new container instances 206.”, para [0050]);
assign each of the plurality of virtual nodes to the new (“The cluster manager distributes the node number of virtual nodes equally across the container number of container instances (306). In some embodiments, distributing the node number of vnodes across the container number of container instance may include round robin assigning. For example, if there are three container instances and four vnodes created, the first vnode is assigned to the first container instance, the second vnode is assigned to the second container instance, the third vnode is assigned to the third container instance, and the fourth vnode is assigned to the first container instance.”, para [0066])
Jawahar does not disclose:
nodes
such that a distance between any two virtual nodes assigned to a same one of the new nodes is at least M-1 virtual nodes, where M is the number of new nodes; and
determine configurations associated with the new nodes, wherein the configurations comprise at least one of: a number of the new nodes, a source data center of the new nodes, a protection scheme, a node capacity of at least one of the new nodes, or a hash table assignment;
generate a plurality of virtual nodes corresponding to the new nodes based on the determined configurations;
allocate the assigned virtual nodes to a token range of a consistent hash ring to balance at least one of request traffic or storage amounts across the distributed cluster.
Araujo discloses container instances are nodes ("The computing devices may further host virtual environments allowing multiple computing nodes (e.g., virtual machine instances, container instances) to be hosted on a single physical computing device.", para [0002]).
Both the systems of Jawahar and Araujo deal with container instances. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar in view of Araujo to understand container instances are nodes.
Weisberg discloses:
such that a distance between any two virtual nodes assigned to a same one of the new nodes is at least M-1 virtual nodes, where M is the number of new nodes(“FIG. 3 is a simplified illustration showing the addition of a new node 3 with logical partitions P5 and P6 to a database cluster.”, para [0023], fig 3, “FIG. 4 illustrates addition of logical partitions P5 and P6 to the hash ring of FIG. 2.”, para [0024], fig 4, Fig. 4 shows three logical partitions between P5 and P6); and
PNG
media_image1.png
352
376
media_image1.png
Greyscale
Both the systems of Jawahar and Weisberg deal with consistent hashing. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Weisberg to improve the distribution of the load.
Williams discloses:
determine configurations associated with the new nodes, wherein the configurations comprise at least one of: (“If you started your older machines with 64 vnodes per node and the new machines are twice as powerful, simply give them 128 vnodes each and the cluster remains balanced even during transition.”, page 4, first full paragraph);
generate a plurality of virtual nodes corresponding to the new nodes based on the determined configurations (“If you started your older machines with 64 vnodes per node and the new machines are twice as powerful, simply give them 128 vnodes each and the cluster remains balanced even during transition.”, page 4, first full paragraph);
Both the systems of Jawahar and Williams deal with virtual nodes. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Williams to improve system reliability.
Nevsv discloses:
allocating the virtual nodes to a token range of a consistent hash ring (“vnodes architecture (also used in riak for example) makes virtualization of the "node" layer, splitting the ring into high number of token ranges (vnodes) and each physical node (cassandra service) has number of vnodes running on it.”, middle of page 1) to balance at least one of request traffic or storage amounts across the distributed cluster (“This limitation recites an intended use/result carrying no patentable weight.).
Both the systems of Jawahar and Nevsv deal with virtual nodes. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Nevsv to “making data distribution much more flexible.” (Sharma, middle of page 1).
Claim 18 and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Jawahar in view of Araujo, Weisberg, Williams, and Nevsv as applied to claim 17 above, and further in view of Snider et al. (U.S. Patent Application Publication No. US 20160316003 A1, hereinafter “Snider”).
With regard to claim 18, Jawahar as modified discloses the distributed storage system of claim 17.
Jawahar as modified does not disclose however, Snider discloses:
wherein the processor is further configured to measure an imbalance at individual ones of the existing nodes prior to identifying the new nodes (“For example, application placement component 210 may at least attempt to generate a placement plan based on detecting imbalance of one or more resources in the cloud computing environment as exceeding a threshold value. The imbalance may be with respect to one or more nodes (e.g., based on detection of one or more hot nodes with respect to one or more resources) or the system overall.”, para [0065], “Each candidate placement plan generated by application placement component 210 can comprise a set of movements of job instances with respect to nodes of the cloud computing platform that are operable to achieve a corresponding target placement of job instances on the nodes. In some implantations, a movement provides a new location (i.e., node) to a job instance.”, para [0068], “For instance, various functions may be carried out by a processor executing instructions stored in memory.”, para [0023]).
Both the systems of Jawahar and Snider deal with computing clusters. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Snider to “improve balance of the resource metrics across the nodes of a cloud computing platform” (Snider, para [0005]).
With regard to claim 19 Jawahar as modified discloses the distributed storage system of claim 18.
Jawahar as modified does not disclose however, Snider discloses:
wherein the processor is configured to execute a simulation to determine a node distribution for the new nodes based on the measured imbalance (“In particular, method 500 shows an implementation for selecting a preferred placement plan that employs a simulated annealing algorithm.”, para [0013], “For example, application placement component 210 may at least attempt to generate a placement plan based on detecting imbalance of one or more resources in the cloud computing environment as exceeding a threshold value. The imbalance may be with respect to one or more nodes (e.g., based on detection of one or more hot nodes with respect to one or more resources) or the system overall.”, para [0065], “Each candidate placement plan generated by application placement component 210 can comprise a set of movements of job instances with respect to nodes of the cloud computing platform that are operable to achieve a corresponding target placement of job instances on the nodes. In some implantations, a movement provides a new location (i.e., node) to a job instance.”, para [0068], “For instance, various functions may be carried out by a processor executing instructions stored in memory.”, para [0023]).
Both the systems of Jawahar and Snider deal with computing clusters. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of Snider to “improve balance of the resource metrics across the nodes of a cloud computing platform” (Snider, para [0005]).
Claim 20 is are rejected under 35 U.S.C. 103 as being unpatentable over Jawahar in view of Araujo, Weisberg, Williams, and Nevsv as applied to claim 17 above, and further in view of DataStax (“The cassandra.yaml configuration file | apache cassandra 3.0”).
With regard to claim 20 Jawahar as modified discloses the distributed storage system of claim 17.
Jawahar as modified does not disclose however, DataStax discloses:
wherein the source data center comprises a location constraint (“allocate_tokens_for_local_replication_factor When adding a vnode to an existing cluster or setting up nodes in a new datacenter, set to the target replication factor (RF) of keyspaces in the datacenter.”, bottom of page 9-top of page 10), and wherein the processor is configured to apply the location constraint as an additional constraint on virtual node placement within token ranges belonging to the source data center (“allocate_tokens_for_local_replication_factor When adding a vnode to an existing cluster or setting up nodes in a new datacenter, set to the target replication factor (RF) of keyspaces in the datacenter. Triggers algorithmic allocation for the RF and num_tokens for this node. The allocation algorithm attempts to choose tokens in a way that optimizes replicated load over the nodes in the datacenter for the specified RF.”, bottom of page 9-top of page 10).
Both the systems of Jawahar and DataStax deal with vnodes. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine Jawahar as modified in view of DataStax to improve load distribution.
Response to Arguments
Applicant argued:
“For example, the cited portions of Jawahar and Araujo do not disclose or suggest "a round robin structure wherein each virtual node is sequentially assigned to a corresponding one of the identified nodes," as recited in independent claims 1 and 9.” (Remarks, pg. 7, second paragraph), “Jawahar does not disclose or suggest assigning virtual nodes only to the new nodes being added. Thus, Jawahar does not disclose sequentially assigning each virtual node to a corresponding new node being added in a round robin structure (not to all nodes). Accordingly, Jawahar does not disclose or suggest “a round robin structure, wherein each virtual node is sequentially assigned to a corresponding one of the identified nodes." (Remarks, pg. 8, first paragraph), and “The Examiner cites Araujo solely for the proposition that "container instances are nodes." This is merely a definitional teaching that does not cure the deficiencies in Jawahar. Thus, Araujo does not disclose assigning virtual nodes. Therefore, Araujo does not disclose or suggest a round robin structure where each virtual node is sequentially assigned to a corresponding one of the identified nodes," as recited in claims 1 and 9.” (Remarks, pg. 8, second paragraph)
The Applicant asserts that the claim term, “a round robin structure, wherein each virtual node is sequentially assigned to a corresponding one of the new nodes” is limited to “assigning virtual nodes only to the new nodes being added”. The claim recites, "a round robin structure, wherein each virtual node is sequentially assigned to a corresponding one of the new nodes". One of ordinary skill in the art would reasonably interpret this claim limitation to mean assigning vnodes to new nodes which is taught by Jawahar and Araujo as addressed in the above rejection. Should the Applicant wish the claim to conform to the Applicant's interpretation, the Applicant is advised to amend the claim to explicitly limit the claim to the Applicant's interpretation.
Applicant also argued:
“Further, Jawahar does not explicitly teach a token range allocation process. While Jawahar mentions that "each virtual node owns a corresponding key range of the key-value store" (See Jawahar, para. [0050]), this describes ownership of key ranges by virtual nodes, not the process of generating new virtual nodes after the token ranges were already previously assigned, and then allocating a newly generated virtual node to a token range as part of a hash token selection method. Thus, Jawahar does not disclose or teach allocating the virtual nodes to a token range, as recited in independent claim 1.” (Remarks, pg. 8, first paragraph) and “Further, Araujo does not explicitly teach a token range allocation process. Thus, Araujo does not disclose or teach allocating the virtual nodes to a token range, as recited in independent claim 1.” (Remarks, pg. 8, second paragraph)
The arguments with respect to claim 1 have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument.
Applicant also argued:
“Neither Jawahar nor Araujo disclose or teach a specific virtual node distance or spacing requirement. Thus, claims 5 and 11 are allowable.” (Remarks, pg. 9, second paragraph)
The prior art rejection for claim 5 is withdrawn due to being dependent upon a base claim without a prior art rejection. Claim 11 is rejected under 35 U.S.C. 103 as being unpatentable over Jawahar in view of Araujo and Nevsv as applied to claim 10, and further view of Weisber. As set forth in the previous Office Action (01/29/26, pg. 10), Examiner introduced Weisber to teach “a distance between two of the virtual nodes for one of M identified nodes is at least M-1 virtual nodes of a consistent hash ring”.
Applicant also argued:
“Jawahar and Araujo do not disclose or suggest using a specific assignment pattern where a first new node receives the 0th index virtual node, a second node receives the 1st index virtual node, continuing sequentially such that node M receives the (M-1)th index virtual node, then first new node receives the Mth index virtual node, and the pattern repeats. Thus, claims 6 and 12 are allowable.” (Remarks,
Examiner respectfully disagrees. Claims 6 and 12 recite, "wherein the round robin structure comprises assigning a first new node a 0th index virtual node, and assigning a second new node a 1st index virtual node". One of ordinary skill in the art would reasonably interpret this claim limitation to mean a one-to-one correspondence between virtual nodes and new nodes which is taught by Jawahar and Araujo as addressed in the above rejection. The prior art rejection for claim 6 is withdrawn due to being dependent upon a base claim without a prior art rejection.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Grasso (“The Impacts of Changing the Number of VNodes in Apache Cassandra”) discloses “To solve the shortcomings of a single token assignment, Cassandra version 1.2 was enhanced to allow a node to be assigned multiple tokens. That is a node could be responsible for multiple token ranges. This Cassandra feature is known as “virtual node” or vnodes for short. The vnodes feature was introduced via CASSANDRA-4119.” (page 5, first paragraph).
Singh (“Mechanics of Consistent Hashing”) discloses “Here, the hash range is divided into multiple smaller ranges. Instead of assigning a single token to a node, each physical node is assigned several of these smaller ranges. Each of these subranges is considered as vNode. With vNodes, instead of a node being responsible for just one token, it is responsible for many subranges (or tokens).” (page 4, last paragraph).
Singh (“System design: Consistent hashing - dev community.”) discloses “As VNodes help spread the load more evenly across the physical nodes on the cluster by diving the hash ranges into smaller subranges, this speeds up the re-balancing process after adding or removing nodes. This also helps us reduce the probability of hotspots.” (last paragraph of page 4-first paragraph page 5).
Takada (“GitHub - mixu/vnodehash: Consistent hashing using virtual nodes.”) discloses “The number of vnodes a server is responsible for can represent its capacity, so more capable nodes can be assigned more vnodes.” (middle of page 2).
Chowdhury (U.S. Patent Application Publication No. US 20190028201 A1) discloses “These constraints ensure that each VNode is mapped to exactly one IP node according to the location constraints.” (para [0068]).
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SELENA SABAH NAHRA whose telephone number is (571)272-6115. The examiner can normally be reached Monday-Thursday 7:00 AM -5:30 PM.
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, Hyung Sough can be reached at (571) 272-6799. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/S.S.N./Examiner, Art Unit 2192
/S. Sough/SPE, Art Unit 2192
Prosecution Insights