Systems and methods for global consistency in distributed shared-data databases

1 . A method comprising:

receiving, by a receiving node, the receiving node being one of a plurality of nodes of a distributed database storing a plurality of data items, a query to read a value of a specific data item of the plurality of data items;

requesting, by the receiving node, from each of the plurality of nodes other than the receiving node, a latest timestamp for a respective latest transaction conducted by each respective node of the plurality of nodes other than the receiving node;

receiving, by the receiving node from said each of the plurality of nodes other than the receiving node, the respective latest timestamp for the respective latest transaction;

managing, by the receiving node, a cache of the receiving node, the cache comprising a set of values corresponding to a set of data items of the plurality of data items, by, for each of the plurality of nodes other than the receiving node, processing log records of transactions conducted by that node up to the respective latest timestamp, and based on the log records, invalidating or updating corresponding values in the cache;

reading, by the receiving node, the value of the specific data item;

determining, by the receiving node, that there are no requests sent by the receiving node to one or more nodes of the plurality of nodes for a latest timestamp in progress;

adding, by the receiving node, the query to a queue for current timestamp request, the queue for current timestamp request being a queue for one or more queries currently being serviced for collection of latest timestamps

removing, by the receiving node, the query from the queue for current timestamp request after receiving, by the receiving node from each of the plurality of nodes other than the receiving node, the respective latest timestamp for the respective latest transaction; and

determining, by the receiving node, whether there are one or more queries in a queue for next timestamp request, the queue for next timestamp request being a queue for one or more queries waiting to be transferred to the queue for current timestamp request.

2 . The method of claim 1 , wherein the distributed database is one of: a shared-data database, a shared-nothing database, a multi-writer database, and a single-writer-multiple-readers database.

3 . The method of claim 1 , wherein the query is a read after write (RAW) query.

4 . The method of claim 1 , wherein the latest timestamp is a clock counter of a clock corresponding to said each of the plurality of nodes other than the receiving node.

5 . The method of claim 3 , wherein the clock corresponding to said each of the plurality of nodes other than the receiving node is one of a vector clock or a vector-scalar clock, and the respective latest timestamp is a vector timestamp comprising an array of values, each value corresponding to a different node of the plurality of nodes of the distributed database, and wherein managing, by the receiving node, the cache of the plurality of data items comprises:

for each vector timestamp received from said each of the plurality of nodes other than the receiving node, processing, by the receiving node, the cache of the plurality of data items based on a maximum value of the array of values corresponding to said each of the plurality of nodes other than the receiving node.

6 . The method of claim 1 , wherein reading, by the receiving node, the value of the specific data item comprises:

obtaining, by the receiving node, the value of the specific data item from one of: the cache of the plurality of data items or a data storage of the distributed database; and

sending, by the receiving node, a reply comprising the obtained value of the specific data item.

7 . The method of claim 1 , wherein the respective latest transaction is a last committed transaction.

8 . An apparatus, comprising:

one or more processors; and

a memory storing instructions which, when executed by the one or more processors, configure the apparatus to perform the method of claim 1 .

9 . The apparatus of claim 8 , wherein the distributed database is one of: a shared-data database, a shared-nothing database, a multi-writer database, and a single-writer-multiple-readers database.

10 . The apparatus of claim 8 , wherein the query is a read after write (RAW) query.

11 . The apparatus of claim 8 , wherein the latest timestamp is a clock counter of a clock corresponding to said each of the plurality of nodes other than the receiving node.

12 . The apparatus of claim 8 , wherein the clock corresponding to said each of the plurality of nodes other than the receiving node is one of a vector clock or a vector-scalar clock, and the respective latest timestamp is a vector timestamp comprising an array of values, each value corresponding to a different node of the plurality of nodes of the distributed database, and wherein managing, by the receiving node, the cache of the plurality of data items comprises:

for each vector timestamp received from said each of the plurality of nodes other than the receiving node, processing, by the receiving node, the cache of the plurality of data items based on a maximum value of the array of values corresponding to said each of the plurality of nodes other than the receiving node.

13 . The apparatus of claim 8 , wherein reading, by the receiving node, the value of the specific data item comprises:

obtaining, by the receiving node, the value of the specific data item from one of: the cache of the plurality of data items or a data storage of the distributed database; and

sending, by the receiving node, a reply comprising the obtained value of the specific data item.

14 . The apparatus of claim 8 , wherein the respective latest transaction is a last committed transaction.

15 . A method of managing queries, the method comprising:

receiving, by a receiving node of a plurality of nodes of a distributed database storing a plurality of data items, a first query for reading a value of a data item of the plurality of data items;

determining, by the receiving node, whether one or more requests sent by the receiving node to one or more nodes of the plurality of nodes are still in progress, each of the one or more requests requesting for a latest timestamp corresponding to a latest transaction at a corresponding node of the one or more nodes;

receiving, by the receiving node, a set of replies from a set of nodes of the plurality of nodes, each reply corresponding to a node of the set of nodes and being based on a request from the receiving node for a latest timestamp corresponding to a latest transaction by the corresponding node, said each reply further indicating the latest timestamp;

managing, by the receiving node, a cache of the receiving node, the cache comprising a set of values of a set of data items of the plurality of data items, by, for each of the plurality of nodes other than the receiving node, processing log records of transactions conducted by that node up to the respective latest timestamp, and based on the log records, invalidating or updating corresponding values in the cache;

wherein determining, by the receiving node, whether one or more requests sent by the receiving node to one or more nodes of the plurality of nodes are still in progress comprises determining, by the receiving node, that one or more requests sent by the receiving node to the one or more nodes of the plurality of nodes for a latest timestamp are still in progress, the one or more requests corresponding to one or more queries in a queue for current timestamp request, the queue for current timestamp request being a queue for one or more queries currently being serviced for collection of latest timestamp, the one or more queries in the queue for current timestamp request received by the receiving node before the first query, and wherein the received set of replies corresponds to the one or more queries in the queue for current timestamp request, the method further comprising:

adding, by the receiving node, the first query to a queue for next timestamp request, the queue for next timestamp request being a queue for one or more queries waiting to be transferred to the queue for current timestamp request.

16 . The method of claim 15 , wherein the set of replies from the set of nodes of the plurality of nodes correspond to the one or more requests sent by the receiving node to the one or more nodes of the plurality of nodes that are still in progress, the method further comprising:

removing, by the receiving node, the one or more queries from the queue for current timestamp request;

executing, by the receiving node, the one or more queries removed from the queue for current timestamp request;

determining, by the receiving node, that there are one or more queries in the queue for next timestamp request including the first query; and

moving, by the receiving node, the one or more queries in the queue for next timestamp request from the queue for next timestamp request to the queue for current timestamp request.

17 . An apparatus, comprising:

one or more processors; and

a memory storing instructions which, when executed by the one or more processors, configure the apparatus to perform the method of claim 15 .

18 . The apparatus of claim 17 , wherein the set of replies from the set of nodes of the plurality of nodes correspond to the one or more requests sent by the receiving node to the one or more nodes of the plurality of nodes that are still in progress, wherein the instructions which, when executed by the one or more processors, further configure the apparatus for:

removing, by the receiving node, the one or more queries from the queue for current timestamp request;

executing, by the receiving node, the one or more queries removed from the queue for current timestamp request;

determining, by the receiving node, that there are one or more queries in the queue for next timestamp request including the first query; and

moving, by the receiving node, the one or more queries in the queue for next timestamp request from the queue for next timestamp request to the queue for current timestamp request.

19 . A method of managing queries, the method comprising:

receiving, by a receiving node of a plurality of nodes of a distributed database storing a plurality of data items, a first query for reading a value of a data item of the plurality of data items:

determining, by the receiving node, whether one or more requests sent by the receiving node to one or more nodes of the plurality of nodes are still in progress, each of the one or more requests requesting for a latest timestamp corresponding to a latest transaction at a corresponding node of the one or more nodes;

receiving, by the receiving node, a set of replies from a set of nodes of the plurality of nodes, each reply corresponding to a node of the set of nodes and being based on a request from the receiving node for a latest timestamp corresponding to a latest transaction by the corresponding node, said each reply further indicating the latest timestamp;

managing, by the receiving node, a cache of the receiving node, the cache comprising a set of values of a set of data items of the plurality of data items, by, for each of the plurality of nodes other than the receiving node, processing log records of transactions conducted by that node up to the respective latest timestamp, and based on the log records, invalidating or updating corresponding values in the cache;

wherein determining, by the receiving node, whether one or more requests sent by the receiving node to one or more nodes of the plurality of nodes are still in progress comprises determining, by the receiving node, that there are no requests sent by the receiving node to the one or more nodes of the plurality of nodes for the latest timestamp in progress, the method further comprising:

adding, by the receiving node, the first query to a queue for current timestamp request, the queue for current timestamp request being a queue for one or more queries that are currently being serviced for collection of latest timestamps:

requesting, by the receiving node, from each of the plurality of nodes other than the receiving node, a latest timestamp for a respective latest transaction conducted by said each node;

removing, by the receiving node, the first query from the queue for current timestamp request;

executing, by the receiving node, the first query; and

determining, by the receiving node, whether there are one or more queries in a queue for next timestamp request, the queue for next timestamp request being a queue for one or more queries waiting to be transferred to the queue for current timestamp request.

20 . An apparatus, comprising:

one or more processors; and

a memory storing instructions which, when executed by the one or more processors, configure the apparatus to perform the method of claim 19 .