Assigning nodes to shards based on a flow graph model

1. A method comprising:

determining, by a processor, a target throughput for a query directed to a plurality of shards based on a total number of the plurality of shards, wherein the target throughput is a target amount of query data being processed in a predetermined time unit;

generating, by the processor, a flow graph model to be used to process the query, the flow graph model including a source vertex connected to shard vertices that represent the plurality of shards, the shard vertices connected to node vertices that represent a plurality of nodes that serve the plurality of shards, and the node vertices connected to a sink vertex via node-to-sink edges; and

assigning the plurality of nodes to the plurality of shards based on the flow graph model, wherein the assigning comprises:

performing a first iteration to determine a first set of assignments of the plurality of nodes to the plurality of shards based on the flow graph model, including assigning each of the node-to-sink edges of the flow graph model with a flow capacity such that an aggregate outflow of the first iteration from all of the node vertices to the sink vertex is less than the target throughput; and

performing a second iteration to determine a second set of assignments of the plurality of nodes to the plurality of shards based on the first set of assignments, including increasing the flow capacity assigned to each of the node-to-sink edges such that an aggregate outflow of the second iteration is closer to the target throughput than the aggregate outflow of the first iteration is to the target throughput.

2. The method of claim 1 , wherein the target throughput is proportional to the total number of the plurality of shards.

3. The method of claim 1 , wherein the flow capacity assigned to each of the node-to-sink edges in the first iteration is equal to an integer quotient of the total number of the plurality of shards divided by a total number of the plurality of nodes.

4. The method of claim 1 , wherein performing the first iteration comprises pseudo randomly or randomly determining an order in which the first set of assignments are determined.

5. The method of claim 1 , wherein performing the first iteration comprises omitting a node of the plurality of nodes from the first set of assignments such that the omitted node is not assigned to any shard of the plurality of shards.

6. The method of claim 1 , wherein performing the first iteration comprises prioritizing a sub-plurality of the plurality of nodes to favor at least a first node of the plurality of nodes to serve the query relative to a second node of the plurality of nodes.

7. The method of claim 1 , wherein performing the first iteration comprises prioritizing a sub-plurality of the plurality of nodes to favor at least a first set of nodes of the plurality of nodes to serve the query.

8. The method of claim 7 , wherein the first set of nodes comprises servers disposed on a physical rack shared in common among the nodes of the first set of nodes.

9. An article comprising a non-transitory computer readable storage medium storing instructions that when executed by at least one processor cause the at least one processor to:

generate a flow graph model to be used to process a query, the flow graph model including a source vertex connected to shard vertices that represent a plurality of shards for the query, the shard vertices connected to node vertices that represent a plurality of nodes that serve the plurality of shards, and the node vertices connected to a sink vertex via node-to-sink edges; and

model assignments of the plurality of nodes to the plurality of shards associated with a database operation based on the flow graph model and a target throughput for the plurality of nodes, wherein the target throughput is a target amount of query data being processed in a predetermined time unit, and wherein the instructions cause the at least processor to:

perform a first iteration to determine a first set of assignments of the plurality of nodes to the plurality of shards based on the flow graph model, including assigning each of the node-to-sink edges of the flow graph model with a flow capacity such that an aggregate outflow of the first iteration from the node vertices to the sink vertex is less than the target throughput, and

perform a second iteration to determine a second set of assignments of the plurality of nodes to the plurality of shards based on the first set of assignments, including increasing the flow capacity assigned to each of the node-to-sink edges such that an aggregate outflow of the second iteration is closer to the target throughput than the aggregate outflow of the first iteration is to the target throughput.

10. The article of claim 9 , wherein the non-transitory computer readable storage medium stores instructions that when executed by the at least one processor cause the at least one processor to model the target throughput as being proportional to a total number of the plurality of shards.

11. The article of claim 9 , wherein the flow capacity assigned to each of the node-to-sink edges in the first iteration is equal to an integer quotient of a total number of the plurality of shards divided by a total number of the plurality of nodes.

12. The article of claim 9 , wherein the non-transitory computer readable storage medium stores instructions that when executed by the at least one processor cause the at least one processor to prioritize the plurality of nodes to favor a first set of nodes that are installed in a same physical rack to serve the query.

13. The article of claim 9 , wherein the non-transitory computer readable storage medium stores instructions that when executed by the at least one processor cause the at least one processor to assign priorities to the plurality of nodes and determine the first set of assignments based on the priorities.

14. The article of claim 13 , wherein the non-transitory computer readable storage medium stores instructions that when executed by the at least one processor cause the at least one processor to prioritize the plurality of nodes based on bandwidths associated with node-to-node communications.

15. An apparatus comprising:

a storage to store a plurality of shards;

a processor; and

a memory to store instructions that, when executed by the processor, cause the processor to:

generate a flow graph model to be used to process a query, the flow graph model including a source vertex connected to shard vertices that represent the plurality of shards, the shard vertices connected to node vertices that represent a plurality of nodes that serve the plurality of shards, and the node vertices connected to a sink vertex via node-to-sink edges;

perform a first iteration to determine a first set of assignments of the plurality of nodes to the plurality of shards, including assigning each of the node-to-sink edges of the flow graph model with a flow capacity such that an aggregate outflow of the first iteration from the node vertices to the sink vertex is less than a target throughput, wherein the target throughput is a target amount of query data being processed in a predetermined time unit; and

perform a second iteration to determine a second set of assignments of the plurality of nodes to the plurality of shards based on the first set of assignments, including increasing the flow capacity assigned to each of the node-to-sink edges such that an aggregate outflow of the second iteration is closer to the target throughput than the aggregate outflow of the first iteration is to the target throughput.

16. The apparatus of claim 15 , wherein the instructions, when executed by the processor, cause the processor to progressively increase the flow capacity assigned to each of the node-to-sink edges over additional iterations.

17. The apparatus of claim 16 , wherein the flow capacity assigned to each of the node-to-sink edges is equal to an integer quotient of a total number of the plurality of shards divided by a total number of the plurality of nodes.

18. The apparatus of claim 15 , wherein edges between the source vertex and the shard vertices in the flow graph model have a same flow capacity.

19. The apparatus of claim 15 , wherein the instructions, when executed by the processor, cause the processor to maintain output flows from the plurality of nodes to be the same.

20. The apparatus of claim 15 , wherein the instructions, when executed by the processor, cause the processor to prioritize the plurality of nodes based on a node-to-node communication bandwidth.