System and method for fault tolerant queries
View Patent ↗Fault tolerant querying of data distributed across multiple nodes is accomplished by each node determining and reporting its own health status and indexing status to the other nodes in the cluster via a gossip protocol. A coordinator node then prioritizes replica nodes based on the received status of the other nodes and sends query requests to those nodes based on the prioritization. Should a node fail to provide an response to a query request, further query requests are sent to a next highest priority replica node containing the relevant data. This results in improved query performance by avoiding busy nodes and further provides a fault tolerant approach to data queries.
1. A fault tolerant query method, in a cluster of nodes, the method comprising:
determining, by each node in the cluster, its own health status wherein the health status is an indication of how likely the node is to provide correct data;
determining, by each node in the cluster, its own indexing status by determining whether the node is currently undergoing a reindexing of its dataset partitions or if a most recent reindexing operation had failed;
communicating, from each node in the cluster to each other node in the cluster, the determined health status and the determined indexing status;
receiving a client query at a first node in the cluster;
determining, by the first node in the cluster, which nodes in the cluster contain data partitions relevant to the received client query;
prioritizing, by the first node in the cluster, the determined nodes using the received indexing status of the determined nodes and then the received health status of the determined nodes;
sending query requests from the first node in the cluster to one or more of the determined nodes having a higher priority than one or more other of the determined nodes having a lower priority;
receiving by the first node query responses from the one or more of the determined nodes having a higher priority;
sorting by the first node the received query responses into a query result; and,
sending the query result from the first node to the client.
2. The method of claim 1 further comprising before the step of sorting by the first node the received query responses into a query result:
determining by the first node that one or more query response is not being received from the one or more of the determined nodes having a higher priority;
sending one or more additional query request from the first node in the cluster to one or more of the determined nodes having a next higher priority than one or more other of the determined nodes having a higher priority; and,
receiving by the first node one or more query responses from the one or more of the determined nodes having a next higher priority.
3. The method of claim 1 wherein determining, by each node in the cluster, its own health status is according to the function:
node health=node uptime/(1+dropped updates)
and where node uptime is calculated according to the function:
round (100×(uptime×smoothing constant)/(1+uptime×smoothing constant))/100.
4. The method of claim 1 wherein communicating the determined health status and the determined indexing status is performed using a gossip protocol.
5. The method of claim 1 wherein prioritizing the determined nodes based on the received health status and indexing status of the determined nodes further comprises prioritizing the determined nodes based on whether the determined nodes are active and the proximity of each of the determined nodes to the first node in the cluster.
6. A fault tolerant query system comprising:
a cluster of nodes, each node in the cluster configured to:
determine its health status wherein the health status is an indication of how likely the node is to provide correct data;
determine its indexing status by determining whether the node is currently undergoing a reindexing of its dataset partitions or if a most recent reindexing operation had failed; and
communicate its determined health status and determined indexing status to each other node in the cluster;
at least one node in the cluster configured to:
receive a client query,
determine which nodes in the cluster contain data partitions relevant to the received client query;
prioritize the determined nodes using the received indexing status of the determined nodes and then the received health status of the determined nodes;
send query requests to one or more of the determined nodes having a higher priority than one or more other of the determined nodes having a lower priority;
receive query responses from the one or more of the determined nodes having a higher priority;
sort the received query responses into a query result; and,
send the query result to the client.
7. The system of claim 6 wherein the at least one node in the cluster is further configured to:
determine that one or more query response is not being received from the one or more determined nodes having a higher priority;
send one or more additional query request to one or more of the determined nodes having a next higher priority than one or more other of the determined nodes having a higher priority; and,
receive one or more query response from the one or more of the determined nodes having a next higher priority,
before being configured to sort the received query responses into the query result.
8. The system of claim 6 wherein each node in the cluster configured to determine its health status is according to the function:
node health=node uptime/(1+dropped updates)
and where node uptime is calculated according to the function:
round (100×(uptime×smoothing constant)/(1+uptime×smoothing constant))/100.
9. The system of claim 6 wherein each node configured to communicate its determined health status and determined indexing status uses a gossip protocol.
10. The system of claim 6 wherein the at least one node configured to prioritize the determined nodes based on the communicated health status and indexing status of the determined nodes is configured to prioritize the determined nodes based on whether the determined nodes are active and the proximity of each of the determined nodes to the at least one node in the cluster.
11. A non-transitory computer readable storage medium having embodied thereon a program, the program being executable by a processor to perform a fault tolerant query method, in a cluster of nodes, the method comprising the steps of:
determining, by each node in the cluster, its own health status wherein the health status is an indication of how likely the node is to provide correct data;
determining, by each node in the cluster, its own indexing status by determining whether the node is currently undergoing a reindexing of its dataset partitions or if a most recent reindexing operation had failed;
communicating, from each node in the cluster to each other node in the cluster, the determined health status and the determined indexing status;
receiving a client query at a first node in the cluster;
determining, by the first node in the cluster, which nodes in the cluster contain data partitions relevant to the received client query;
prioritizing, by the first node in the cluster, the determined nodes using the received indexing status of the determined nodes and then the received health status of the determined nodes;
sending query requests from the first node in the cluster to one or more of the determined nodes having a higher priority than one or more other of the determined nodes having a lower priority;
receiving by the first node query responses from the one or more of the determined nodes having a higher priority;
sorting by the first node the received query responses into a query result; and,
sending the query result from the first node to the client.
12. The non-transitory computer readable storage medium of claim 11 , wherein the method further comprises the steps of, before the step of sorting by the first node the received query responses into a query result:
determining by the first node that one or more query response is not being received from the one or more of the determined nodes having a higher priority;
sending one or more additional query request from the first node in the cluster to one or more of the determined nodes having a next higher priority than one or more other of the determined nodes having a higher priority; and,
receiving by the first node one or more query responses from the one or more of the determined nodes having a next higher priority.
13. The non-transitory computer readable storage medium of claim 11 wherein determining, by each node in the cluster, its own health status is according to the function:
node health=node uptime/(1+dropped updates)
and where node uptime is calculated according to the function:
round (100×(uptime×smoothing constant)/(1+uptime×smoothing constant))/100.
14. The non-transitory computer readable storage medium of claim 11 wherein communicating the determined health status and the determined indexing status is performed using a gossip protocol.
15. The non-transitory computer readable storage medium of claim 11 wherein prioritizing the determined nodes based on the received health status and indexing status of the determined nodes further comprises prioritizing the determined nodes based on whether the determined nodes are active and the proximity of each of the determined nodes to the first node in the cluster.