Delta query technique

• US 7,693,886 B1
• Filed: 12/15/2006
• Issued: 04/06/2010
• Est. Priority Date: 12/15/2006
• Status: Active Grant

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: NetApp, Inc.
• Inventors: Webman, Erez, Devor, Orly, Novick, Yoram
• Primary Examiner(s): Cottingham; John R
• Assistant Examiner(s): Khakhar; Nirav K
• Application Number:
  US11/640,019
• Time in Patent Office: 1,208 Days
• Field of Search: None
• US Class Current: 707/614
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A delta query technique transmits only latest changes to data of objects from a server to one or more clients in response to a client query (request) to access the object data. A global counter is maintained for all of the objects served by the server. Every time the data of an object changes, a value of the global counter increments (updates) and the updated global counter value is then assumed (“inherited”) by that object. In addition, the global counter is updated when a client issues a request to access one or more objects. If the data of the objects has changed since the last time the client accessed the objects, the server responds with the latest object data and the updated global counter value. Notably, each client maintains a local counter having a value that, upon receipt of the latest object data, is modified to reflect the updated global counter value.

Claims

1. A method for transmitting data, comprising:

maintaining a global counter for a plurality of objects served by a server;

maintaining a local counter at one or more clients;

updating, in response to a first changing of an object by a first client of the one or more clients, a value of the global counter to a first value;

reflecting the first value of the global counter at an inherited counter of the object, wherein the reflected first value is the global counter value at a time when the first changing occurred;

updating, in response to a next changing of the object by a second client of the one or more clients, the value of the global counter to a next value;

reflecting the next value of the global counter at the inherited counter of the object, wherein the reflected next value is the global counter value at a time when the next changing occurred;

comparing a value of the local counter maintained at the first client with the reflected next value at the inherited counter of the object, wherein the value of the local counter maintained at the first client is the global counter value at the time when the first changing occurred; and

transmitting to the first client, in response to the reflected next value at the inherited counter being greater than the value of the local counter maintained at the first client, only a latest change to data of the object since the first client last accessed the object, and in response to the first client receiving the latest change, modifying the value of the local counter maintained at the first client to the reflected next value of the global counter.

2. The method of claim 1 further comprising:

negating transmission of any data of the object from the server to the first client in response to the reflected next value at the inherited counter not being greater than the value of the local counter maintained at the first client.

3. The method of claim 1 wherein transmitting the latest change to data of the object further comprises updating the value of the global counter.

4. The method of claim 1 further comprising:

querying, by the first client, the server, wherein the query comprises the value of the local counter maintained at the first client; and

scanning, by the server, in response to the query, a list and copying one or more nodes to form a query answer until the server reaches a node of the one or more nodes with an inherited counter value not greater than the local counter value maintained at the first client.

5. The method of claim 1 further comprising:

updating the value of the global counter when the first client issues a request to access the object.

6. The method of claim 1 further comprising:

sending an initial query from the first client to the server;

in response, receiving, at the first client, an image of information of the plurality of objects maintained by the server; and

receiving the reflected next value of the global counter at the first client.

7. The method of claim 6 further comprising:

constructing a local copy of the information at the first client using the information of the plurality of objects.

8. A computer system configured to transmit data, comprising:

a processor operatively connected to the computer system;

a plurality of objects stored on a server;

a local counter maintained at a first client, the local counter configured with a value that is provided in response to the first client requesting access to an object of the plurality of objects;

a global counter maintained by the server, the global counter configured with a value that is updated by the server in response to the first client requesting access to the object;

an inherited counter of the object, the inherited counter configured with a value that is reflective of the updated value of the global counter at a time when the first client requested access to the object;

the server configured to compare the value of the local counter maintained at the first client with the value of the inherited counter, wherein the value of the local counter is configured with the global counter value at the time when the first client requested access to the object;

the server further configured to transmit, in response to the value of the inherited counter being greater than the value of the local counter maintained at the first client, a latest object change to the first client, and in response to receipt of the latest object change, the value of the local counter maintained at the first client configured to inherit the value of the global counter updated by the server in response to the first client requesting access to the object.

9. The computer system of claim 8 wherein the server is a software process executing on a storage system, the server further configured to manage and maintain up-to-date information of the objects.

10. The computer system of claim 9 wherein the objects are organized and maintained as a server database.

11. The computer system of claim 8 wherein the first client is a software process executing on a general-purpose computer.

12. The computer system of claim 8 wherein the first client is configured to construct and organize the plurality of objects as a client database.

13. The computer system of claim 8 further comprising a data structure configured to organize the plurality of objects as a collection of nodes.

14. The computer system of claim 13 wherein the data structure is a doubly-linked list.

15. The computer system of claim 13 wherein one or more nodes contain a property identifier (ID), an object ID, a property value and an instance of the inherited counter value.

16. The computer system of claim 13 wherein a nodes initially assumes an arbitrary order in a list and the inherited counters of the collection of nodes are set to a predetermined global counter value.

17. The computer system of claim 16 wherein, upon modifying a property of a particular node, the server is further configured to increase the inherited counter value of the particular node and promote that particular node to a top of the list.

18. The computer system of claim 17 wherein, in response to a query from the first client comprising the value of the local counter, the server is further configured to scan the list from the top and copy one or more nodes to form a query answer until the server reaches a node with an inherited counter value not greater than the local counter value at the first client.

19. A computer apparatus, comprising:

a processor operatively connected to the computer apparatus;

means for maintaining a global counter for a plurality of objects served by a server;

means for maintaining a local counter at one or more clients

means for updating, in response to a first changing of an object by a first client of the one or more clients, a value of the global counter to a first value;

means for reflecting the first value of the global counter at an inherited counter of the object, wherein the reflected first value is the global counter value at a time when the first changing occurred;

means for updating, in response to a next changing of the object by a second client of the one or more clients, the value of the global counter to a next value;

means for reflecting the next value of the global counter t the inherited counter of the object, wherein the reflected next value is the global counter value at a time when the next changing occurred;

means for comparing a value of the local counter maintained at the first client with the reflected next value at the inherited counter of the object, wherein the value of the local counter maintained at the first client is the global counter value at the lime when the first changing occurred; and

means for transmitting to the first client, in response to the reflected next value at the inherited counter being greater than the value of the local counter maintained at the first client, only a latest change to data of the object since the first client last accessed the object, and in response to the first client receiving the latest change, means for modifying the value of the local counter maintained at the first client to the reflected next value of the global counter.

20. A computer readable medium containing executable program instructions executed by a processor, comprising:

program instructions that maintain a global counter from a plurality of objects served by a server;

program instructions that maintain a local counter at one or more clients;

program instructions that update, in response to a first changing of an object by a first client of the one or more clients, a value of the global counter to a first value;

program instructions that reflect the first value of the global counter at an inherited counter of the object, wherein the reflected first value is the global counter value at a time when the first changing occurred;

program instructions that update, in response to a next changing of the object by a second client of the one or more clients, the value of the global counter to a next value;

program instructions that reflect the next value of the global counter at the inherited counter of the object, wherein the reflected next value is the global counter value at a time when the next changing occurred;

program instructions that compare a value of the local counter maintained at the first client with the reflected next value at the inherited counter of the object, wherein the value of the local counter maintained at the first client is the global counter value at the time when the first changing occurred; and

program instructions that transmit to the first client, in response to the reflected next value at the inherited counter being greater than the value of the local counter maintained at the first client, only a latest change to data of the object since the first client last accessed the object, and in response to the first client receiving the latest change, program instructions that modify the value of the local counter maintained at the first client to the reflected next value of the global counter.

21. A method for transmitting data, comprising:

maintaining a global counter for a plurality of objects;

making, by a client, an access request to a particular object of the plurality of objects;

updating a value of the global counter in response to the access request made to the particular object;

inheriting the updated value at an inherited counter of the particular object, wherein the updated value is the global counter value at a time when the access request was performed;

maintaining a local counter at the client;

comparing a value of the local counter with the value of the inherited counter, wherein the value of the local counter is the global counter value at the time when the access request was performed; and

transmitting, in response to the value of the inherited counter being greater than the value of the local counter, only a newest change to the particular object since the client last accessed the particular object and in response to the client receiving the newest change, modifying the value of the local counter maintained at the client to the updated value of the global counter value.

22. A method for transmitting data, comprising:

maintaining a global counter for a plurality of objects;

updating a value of the global counter in response to one or more changes made to a particular object of the plurality of objects;

inheriting, by the particular object, the updated value of the global counter at an inherited counter of the particular object;

maintaining a local counter at one or more clients of a plurality of clients requesting the particular object;

comparing a value of the local counter with the value of the inherited counter, wherein the local counter value compared is the local counter value of a client requesting the particular object, and wherein the local counter value compared is the updated global counter value at a time when the client requesting the particular object last accessed the particular object;

determining, in response to the comparison, if the value of the inherited counter is greater than the local counter value of the requesting client; and

transmitting to the requesting client, in response to the value of the inherited counter being greater than the local counter value, only a newest change of the one or more changes made to the particular object, and in response to the requesting client receiving the newest change, modifying the value of the local counter maintained at the requesting client to the updated value of the global counter.

23. A method, comprising:

establishing a connection with a server and one or more clients;

receiving by a client of the one or more clients, an image sent from the server of information associated with a plurality of objects, wherein the objects are organized and maintained by a database of the server;

constructing and organizing, in response to the received image, a local copy of the image in a database of the client;

maintaining a global counter value at the server associated with the image;

maintaining a local counter by the client;

sending a client query to the server, wherein the query comprises a local counter value of the local counter and wherein the local counter value is the global counter value at a time when the server receives the query;

receiving by the client, in response to the query, delta information about a newest change made to the database of the server and an updated global counter value, wherein the delta information does not include changes occurring before the newest change, and in response to the client receiving the delta information about the newest change, modifying the value of the local counter of the client to the updated global counter value; and

applying the updated global counter value and the received delta information to the database of the client, wherein the delta information applied to the database of the client creates an updated version of the image sent from the server.

24. The method of claim 23 further comprising:

generating a token in response to the newest change made to the database of the server and sending the token to the client; and

receiving the token from the server.

25. The method of claim 24 wherein generation and receipt of the token by the server and the client, respectively, does not invalidate an earlier token.

26. The method of claim 23 further comprising using an object removal list in conjunction with a variable, where the variable does not appear in the object removal list and reflects the global counter value of an object of the plurality of objects before a removal of the object has taken place.