Local and global quality of service shaper on ingress in a distributed system
A distributed computing system, such as may be used to implement an electronic trading system, controls inbound message flow rates. Limiting a per-client or per-connection inbound message rate also helps ensure fair provisioning of computing resources, so that a single client's excessive use of resources cannot overwhelm the system to such an extent that it prevents other clients from interacting with the distributed system. It is also desirable to have system-wide control of the overall inbound message rate across all client connections. Such system-wide control ensures that the distributed system as a whole can maintain the required levels of service, including offering a predictable level of access for all clients.
1 . A method of operating a distributed data processing system to control inbound flow of messages from a plurality of gateway nodes to a plurality of compute nodes and to a system-level node, the method comprising:
at the plurality of gateway nodes:
receiving the messages over one or more client connections;
controlling a sustained flow rate and/or a burst flow rate of the messages on a per-client or per-connection basis; and
forwarding the messages to the system-level node;
at the system-level node:
receiving the messages from the plurality of gateway nodes;
controlling a system-wide message flow rate, wherein controlling the system-wide message flow rate further comprises controlling a sustained flow rate and/or a burst flow rate on a per-gateway-node-basis for each of the plurality of gateway nodes; and
forwarding the messages to the compute nodes;
at one or more of the plurality of compute nodes:
receiving the messages from the system-level node;
operating on the messages;
generating a response message; and
returning the response message to a selected one of the gateway nodes; and
at the selected gateway node:
returning the response message over at least one of the one or more client connections.
2 . The method of claim 1 wherein
the messages are application layer messages, in which multiple application layer messages are contained in a packet encoded according to a lower layer protocol; and
wherein at least one of the steps of controlling the sustained flow rate and/or burst flow rate further comprises providing feedback to a layer of the lower layer protocol.
3 . The method of claim 2 wherein the lower layer protocol is a transport layer protocol, and the feedback is provided by controlling a transport layer window size.
4 . The method of claim 1 wherein the system is an electronic trading system and wherein operating on the messages is further to perform an electronic trading function.
5 . The method of claim 1 wherein at least one of the steps of controlling sustained flow rate and/or burst flow rate further comprises:
queuing the messages with a plurality of queues;
feeding the messages from the queues to a plurality of token buckets; and
selecting messages from token buckets.
6 . The method of claim 5 wherein the queues are FIFOs.
7 . The method of claim 5 wherein the selecting is on a round-robin basis.
8 . The method of claim 1 wherein the sustained flow rate and/or burst flow rate is further controlled on the per-client or per-connection basis in response to a client request.
9 . The method of claim 1 wherein the system-wide message flow rate is further controlled by the system-level node providing feedback to one or more of the gateway nodes.
10 . The method of claim 9 where the step of providing feedback by the system-level node further comprises at least one of:
lowering a TCP window size on a per-connection basis for all connections from the system-level node to the one or more of the gateway nodes, or
lowering the sustained flow rate and/or a burst flow rate by adjusting at least one parameter of a per-connection token bucket for all connections from the system-level node to the one or more of the gateway nodes, or
sending a feedback message to the one or more of the gateway nodes.
11 . The method of claim 1 wherein the system-wide message flow rate is further controlled by pausing one or more of the gateway nodes.
12 . The method of claim 11 wherein the step of pausing one or more of the gateway nodes further comprises at least one of:
setting a TCP window size to zero for a least one client connection on the one or more of the gateway nodes,
not adding new messages to at least one per-connection FIFO queue for the one or more of the gateway nodes,
not servicing messages from at least one per-connection FIFO queue for the one or more of the gateway nodes, or
setting at least one of the sustained flow rate and/or burst flow rate for at least one connection on the one or more gateway nodes to zero.
13 . The method of claim 1 wherein controlling the sustained flow rate and/or burst flow rate on per-client or per-connection basis further comprises:
controlling a flow from one of the gateway nodes to a selected client and/or connection.
14 . The method of claim 1 where the step of controlling the sustained flow rate and/or burst flow rate further comprises at least one of:
lowering a TCP window size on a per-client or per-connection basis; or
lowering the sustained flow rate and/or burst flow rate by adjusting at least one parameter of a per-client or per-connection token bucket.
15 . The method of claim 1 wherein the sustained flow rate and/or burst flow rate on a per-client or per-connection basis is further controlled on the per-client or per-connection basis by pausing at least one client or connection.
16 . The method of claim 15 wherein the step of pausing at least one client or connection further comprises at least one of:
setting a TCP window size to zero on a per-client or per-connection basis,
not adding new messages to a per-client or a per-connection FIFO for at least one of the gateway nodes,
not servicing messages from a per-client or a per-connection FIFO queue, or
setting at least one of the sustained flow rate or burst flow rate for at least one client or connection to zero.
17 . The method of claim 1 additionally comprising:
receiving the messages at the system-level node from the gateway nodes via a full mesh set of point to point direct connections.
18 . The method of claim 1 additionally comprising:
at the system-level node:
receiving the messages from the compute nodes; and
slowing a rate at which the messages are received from the gateway nodes, when the messages from the compute nodes are received at greater than a predetermined rate.
19 . The method of claim 1 additionally comprising:
at each of the compute nodes:
slowing a rate at which the messages are received from the gateway nodes, when the messages received from or to be sent from the compute nodes to the gateway nodes exceed a rate greater than a predetermined rate.
20 . The method of claim 1 wherein controlling the system-wide message flow rate further comprises:
computing a gateway budget based on the sustained rate and/or a gateway burst rate for each of the plurality of gateway nodes; and
while said gateway budget is exceeded for a corresponding one of the gateway nodes, transmitting gateway feedback messages that instruct the corresponding one of the gateway nodes to adjust at least one parameter of said per-connection limits, whereby the per-connection limits are enforced subject to the gateway budget of the corresponding one of the gateway nodes as determined by the system-level node.
21 . The method of claim 1 wherein controlling the system-wide message flow rate further comprises:
at one or more of the plurality of gateway nodes;
while congestion in the system-wide message flow rate is detected,
adjusting the sustained flow rate and/or burst flow rate on the per-gateway node basis for those corresponding gateway nodes.
22 . A messaging system comprising:
a plurality of gateway nodes configured to:
receive messages over one or more client connections;
control a sustained flow rate and/or a burst flow rate of the messages on a per-client or per-connection basis; and
forward the messages to a system-level node;
the system-level node configured to:
receive the messages from the plurality of gateway nodes;
control a system-wide message flow rate for the system, and further to control a sustained flow rate and/or a burst flow rate on a per-gateway-node-basis for each of the plurality of gateway node; and
forward the messages to one or more compute nodes; and
one or more of the compute nodes configured to:
receive the messages from the system-level node;
operate on the messages;
generate a response message; and
return the response message to a selected one of the gateway nodes; and
the selected one of the gateway nodes further configured to:
return the response message over at least one of the one or more client connections.
23 . The method of claim 1 further comprising:
wherein controlling the system-wide message flow rate further comprises sending flow control messages from the system level node to the plurality of gateway nodes.