Identifying data items

• US 9,792,340 B2
• Filed: 02/28/2014
• Issued: 10/17/2017
• Est. Priority Date: 08/31/2011
• Status: Active Grant

• Current Assignee: Metaswitch Networks Limited (Microsoft Corporation)
• Original Assignee: Metaswitch Networks Limited (Microsoft Corporation)
• Inventors: Wansbrough, Keith, Dundas, Alistair
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US14/194,447
• Publication Number:
  US 20140181030A1
• Time in Patent Office: 1,327 Days
• Field of Search: 707639
• CPC Class Codes: G06F 16/1734 Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

Each of a plurality of data items has an associated update time. Identifying updated data items comprises identifying those data items that have an update time later than a last synchronization time. The data items are updated such that each data item is associated with one of a plurality of update tokens. Each update token is associated with updates performed up to a respective bound period from a time at which the update token is superseded by a successive update token. The update tokens are allocated successively in a monotonic sequence. Data indicating a last synchronization time is received. An update token is identified that is associated with one or more updates performed relative to a point in time related to the last synchronization time by the bound period. Data items having an update time after the last synchronization time are identified on the basis of the identified update token.

Claims

1. A method for identifying updated data items in a plurality of data items stored at a data item storage system, the method comprising:

receiving, at the data item storage system, data indicating a last synchronization time,

wherein each data item in the plurality of data items has an associated update time,

wherein identifying updated data items comprises identifying those data items in the plurality of data items that have an update time later than the last synchronization time,

wherein the data items are updated such that each data item is associated with one of a plurality of update tokens, each update token being associated with updates performed up to an end of a respective bound period that commences at a time at which the update token is superseded by a successive update token,

wherein information relating to each data item is stored using at least one of a plurality of files in a network file system, each file having a file name, file content and a last modified time that corresponds to the update time of said data item, wherein information relating to the update token of each data item is stored in the file name of at least one of the plurality of files storing the information relating to that data item, and

wherein the update tokens are allocated successively in a monotonic sequence;

identifying, at the data item storage system, an update token that is associated with one or more updates performed relative to a point in time related to the last synchronization time by the bound period; and

identifying, at the data item storage system, data items having an update time after said last synchronization time based on said identified update token.

2. The method according to claim 1, wherein the identified update token is associated with one or more updates performed relative to said point in time in that at least one of said one or more updates is performed before said point in time.

3. The method according to claim 1, wherein the identified update token is associated with one or more updates performed relative to said point in time in that at least one of said one or more updates are performed after said point in time.

4. The method according to claim 1, wherein identifying said update token comprises:

identifying a first update token that is associated with at least one update to one side of said point in time; and

identifying a second update token, adjacent to said first update token in said monotonic sequence, that is associated with at least one update to the other side of said point in time.

5. The method according to claim 1, further comprising:

identifying an update token associated with at least one update performed after a point in time following said last synchronization time by said bound period; and

identifying, on the basis of this update token, that all data items having update tokens greater than or equal to this update token have an update time after said last synchronization time.

6. The method according to claim 1, further comprising:

identifying an update token associated with at least one update performed before a point in time preceding said last synchronization time by said bound period; and

identifying, on the basis of this update token, that all data items having update tokens less than or equal to this update token have an update time before said last synchronization time.

7. The method according to claim 1, further comprising:

retrieving the data items identified as having an update time after said last synchronization time; and

transmitting information relating to the retrieved data items.

8. The method according to claim 1, wherein a given data item is stored in at least one of the file name and the file contents of the file that stores information relating to the data item.

9. The method according to claim 1, further comprising,

for a given request:

receiving from a client device said last synchronization time in a request for update information in relation to the plurality of data items; and

responding to said request for update information by transmitting to said client device information relating to the data items identified as having an update time after said last synchronization time,

wherein requests for update information in relation to the plurality of data items are received from a plurality of client devices.

10. The method according to claim 9, wherein responding to said request for update information additionally comprises transmitting a new last synchronization time to the client device, wherein said new last synchronization time is determined at least partly on the basis of the update time of at least one of the data items identified as having an update time after said last synchronization time.

11. The method according to claim 1, further comprising:

receiving at a first time an update token associated with current updates;

receiving update information relating to a data item; and

if the time elapsed since said first time is less than said bound period, associating said data item with the received update token and storing the update to the data item, wherein said update to the data item is stored such that the time when said update is stored is recorded as the data item'"'"'s update time.

12. The method according to claim 11, wherein the update token associated with current updates is at least partially determined on the basis of a next new data item identifier.

13. The method according to claim 11, wherein the update token associated with current updates is at least partially determined on the basis of a server time.

14. The method according to claim 1, wherein identifying an update token that is associated with one or more updates performed relative to said point in time comprises, for each update token:

testing the update time of at most one data item having said update token.

15. The method according to claim 1, wherein identifying an update token that is associated with one or more updates performed relative to said point in time comprises:

receiving said plurality of data items sorted on the basis of their respective update tokens.

16. The method according to claim 15, wherein identifying an update token that is associated with one or more updates performed relative to said point in time further comprises:

performing a binary search on at least some of said sorted data items on the basis of at least one of their respective update tokens and their respective update times.

17. The method according to claim 15, wherein identifying an update token that is associated with one or more updates performed relative to said point in time further comprises:

testing a non-contiguous subset of the sorted data items in order to identify at least one of a first sorted data item and a second data item, wherein the first sorted data item has an update time to one side of said point in time and said second sorted data item has an update time to the other side of said point in time.

18. The method according to claim 17, wherein testing a non-contiguous subset comprises testing the update times of the sorted data items in said subset, and wherein said first sorted data item has the latest update time of the data items in said subset that is before said point in time, and said second sorted data item has the earliest update time of the data items in said subset that is after said point in time.

19. The method according to claim 1, wherein each of a subset of data items are not associated with an update token, comprising:

associating each data item in said subset with a default update token, said default update token preceding the update tokens in said sequence that are associated with data items not in said subset.

20. A method for identifying data items in a plurality of data items stored at a data item storage system, the method comprising:

receiving, at the data item storage system, data indicating an aspect threshold,

wherein each data item in said plurality of data items has an associated aspect,

wherein identifying data items comprises identifying those data items in said plurality that have an aspect greater or less than an aspect threshold,

wherein said data items are associated with one of a plurality of tokens, each token being associated with a respective bound limit, tokens being allocated successively in a monotonic sequence, and

wherein information relating to each data item is stored using at least one of a plurality of files in a network file system, each file having a file name, file content and an aspect that corresponds to the aspect of said data item, wherein information relating to the token of each data item is stored in the file name of at least one of the plurality of files storing the information relating to that data item;

identifying, at the data item storage system, a token that is associated with one or more data items related to said aspect threshold by the bound limit, and

identifying data items having an aspect greater or less than said aspect threshold based on the identified token.

21. A computer program product comprising a non-transitory computer-readable storage medium having computer readable instructions stored thereon, the computer-readable instructions being executable by a computerized device to cause the computerized device to perform a method for identifying updated data items in a plurality of data items stored at a data item storage system, the method comprising:

receiving, at the data item storage system, data indicating a last synchronization time,

wherein each data item in the plurality of data items has an associated update time,

wherein identifying updated data items comprises identifying those data items in the plurality of data items that have an update time later than the last synchronization time,

wherein the data items are updated such that each data item is associated with one of a plurality of update tokens, each update token being associated with updates performed up to an end of a respective bound period that commences at a time at which the update token is superseded by a successive update token,

wherein information relating to each data item is stored using at least one of a plurality of files in a network file system, each file having a file name, file content and a last modified time that corresponds to the update time of said data item, wherein information relating to the update token of each data item is stored in the file name of at least one of the plurality of files storing the information relating to that data item, and

wherein the update tokens are allocated successively in a monotonic sequence;

identifying, at the data item storage system, an update token that is associated with one or more updates performed relative to a point in time related to the last synchronization time by the bound period; and

identifying, at the data item storage system, data items having an update time after said last synchronization time based on said identified update token.

22. A computer program product comprising a non-transitory computer-readable storage medium having computer readable instructions stored thereon, the computer-readable instructions being executable by a computerized device to cause the computerized device to perform a method for identifying data items in a plurality of data items at a data item storage system, the method comprising:

receiving, at the data item storage system, data indicating an aspect threshold,

wherein each data item in said plurality of data items has an associated aspect,

wherein identifying data items comprises identifying those data items in said plurality that have an aspect greater or less than an aspect threshold,

wherein said data items are associated with one of a plurality of tokens, each token being associated with a respective bound limit, tokens being allocated successively in a monotonic sequence, and

wherein information relating to each data item is stored using at least one of a plurality of files in a network file system, each file having a file name, file content and an aspect that corresponds to the aspect of said data item, wherein information relating to the token of each data item is stored in the file name of at least one of the plurality of files storing the information relating to that data item;

identifying, at the data item storage system, a token that is associated with one or more data items related to said aspect threshold by the bound limit, and

identifying data items having an aspect greater or less than said aspect threshold based on the identified token.

23. An apparatus for identifying updated data items in a plurality of data items at a data item storage system, the apparatus comprising:

a processor; and

a memory including computer program code,

wherein the processor is configured to execute the computer program code in order to cause the apparatus to;

receive, at the data item storage system, data indicating a last synchronization time,

wherein each data item in the plurality of data items has an associated update time,

wherein identifying updated data items comprises identifying those data items in the plurality of data items that have an update time later than the last synchronization time,

wherein the data items are updated such that each data item is associated with one of a plurality of update tokens, each update token being associated with updates performed up to an end of a respective bound period that commences at a time at which the update token is superseded by a successive update token,

wherein information relating to each data item is stored using at least one of a plurality of files in a network file system, each file having a file name, file content and a last modified time that corresponds to the update time of said data item, wherein information relating to the update token of each data item is stored in the file name of at least one of the plurality of files storing the information relating to that data item, and

wherein the update tokens are allocated successively in a monotonic sequence;

identify, at the data item storage system, an update token that is associated with one or more updates performed relative to a point in time related to the last synchronization time by the bound period; and

identify, at the data item storage system, data items having an update time after said last synchronization time based on said identified update token.

24. An apparatus for identifying data items in a plurality of data items at a data item storage system, the apparatus comprising:

a processor; and

a memory including computer program code,

wherein the processor is configured to execute computer program code in order to cause the apparatus to;

receive, at the data item storage system, data indicating an aspect threshold,

wherein each data item in said plurality of data items has an associated aspect,

wherein identifying data items comprises identifying those data items in said plurality that have an aspect greater or less than an aspect threshold,

wherein said data items are associated with one of a plurality of tokens, each token being associated with a respective bound limit, tokens being allocated successively in a monotonic sequence, and

wherein information relating to each data item is stored using at least one of a plurality of files in a network file system, each file having a file name, file content and an aspect that corresponds to the aspect of said data item, wherein information relating to the token of each data item is stored in the file name of at least one of the plurality of files storing the information relating to that data item;

identify, at the data item storage system, a token that is associated with one or more data items related to said aspect threshold by the bound limit, and

identify data items having an aspect greater or less than said aspect threshold based on the identified token.