Data storage system and method

1. A computing system comprising:

a computer processor; and

a non-transitory computable-readable medium storing software instructions executable by the computer processor to cause the computing system to:

receive initial data;

store a data object corresponding to the initial data;

receive a plurality of updates to the initial data;

generate corresponding deltas for each of M sequential updates of the plurality of updates, each delta representing an update to a previous state of the data, wherein M is greater than or equal to one;

generate a first-level combined delta representing N updates of the plurality of updates, wherein N represents the M updates and one or more subsequent updates;

generate a second-level combined delta representing J updates of the plurality of updates, wherein J represents the N updates and one or more subsequent updates;

store the deltas as delta data objects, the first-level combined deltas as first level combined delta objects, and the second-level combined deltas as second level delta data objects;

enable subsequent determination respective states of the data after any specified number of updates by:

retrieving a data object corresponding to the initial data,

determining a minimal set of data objects, wherein the minimal set of data objects comprises:

the second-level combined delta data objects;

first-level combined delta data objects that represent updates after those represented by the second-level combined delta data objects; and

any delta data objects not represented by the first-level and the second-level combined delta data objects;

retrieving the determined minimal set of data objects;

determining updates to the initial data using the retrieved minimal set of data objects; and

reconstituting the data using the data object corresponding to the initial data and the updates.

2. The computing system of claim 1 , wherein J=I×N, where I is a positive integer greater than one.

3. The computing system of claim 2 , wherein the instruction further causes the computing system to generate I−1 first-level combined deltas, each representing a distinct set of N updates of the M updates, and storing the I−1 first-level combined deltas.

4. The computing system of claim 1 , wherein each combined delta represents a continuous portion of an ordered sequence of updates.

5. A method, performed by one or more processors, the method comprising:

receiving initial data;

storing a data object corresponding to the initial data;

receiving a plurality of updates to the initial data;

generating corresponding deltas for each of M sequential updates of the plurality of updates, each delta representing an update to a previous state of the data, wherein M is greater than or equal to one;

for each sequence of N updates of the plurality of M updates, generating a first-level combined delta representing the N updates;

for each sequence of J updates, generating a second-level combined delta representing the J updates of the plurality of updates, where J is larger than N;

storing the deltas as delta data objects, the first-level combined deltas as first level combined delta objects, and the second-level combined deltas as second-level combined delta data objects;

in response to a request for a current state of the data, retrieving the data object corresponding to the initial data, and determining a minimal set of data objects that represent A updates, wherein the minimal set of data objects comprises:

the second-level combined delta data objects;

first-level combined delta data objects that represent updates after those represented by the second-level combined delta data objects; and

any delta data objects not represented by the first-level and the second-level combined delta data objects;

retrieving the determined minimal set of data objects; determining updates to the initial data using the retrieved minimal set of data objects; and

generating updated data using the data object corresponding to the initial data and the determined updates.

6. The method of claim 5 , wherein J=I×N, where I is a positive integer greater than one.

7. The method of claim 6 , the method comprising generating I−1 first-level combined deltas, each representing a distinct set of N updates of the M updates, and storing the I−1 first-level combined deltas.

8. The method of claim 7 , wherein I=N.

9. The method of claim 5 , wherein the initial data, the deltas, the first-level combined deltas and the second-level combined deltas each comprise indexed data, wherein indexed data comprises one or more indexed elements.

10. The method of claim 9 , wherein the storing of the delta data objects, the first-level combined delta data objects and the second-level combined delta data objects is to a token ring database system, wherein the token ring database system allocates each element stored to the token ring database system to a given database server randomly or pseudo-randomly.

11. The method of claim 10 , wherein each of the data object, the delta data objects, the first-level combined delta data objects and the second-level combined delta data objects is divided into a plurality of fragments, wherein each fragment stores several index elements, and each fragment is stored into the token ring database system.

12. The method of claim 11 , further comprising, storing a B+ tree usable for locating each indexed data contained in the respective data object, delta or combined delta data objects, in the token ring database system, wherein the B+ tree indicates the fragment in which an indexed element associated with the indexed data is contained.

13. The method of claim 5 , wherein each combined delta represents a continuous portion of an ordered sequence of updates.

14. The method of claim 13 , the method comprising generating deltas representing each update of a subset of the plurality of updates, wherein the subset of the plurality of updates comprises each update for which the respective update is not the final update of a combined delta.

15. The method of claim 5 , wherein an expectancy of number of elements in the minimal set of data objects is O(log B).

16. The method of claim 5 , wherein the deltas comprise new data.

17. The method of claim 5 , wherein the deltas comprise data changing instructions.

18. The method of claim 5 , wherein generating the first-level combined delta comprises generating the first-level combined data when a threshold number of deltas is reached.

19. A method, performed by one or more processors, the method comprising:

receiving initial data;

storing a data object corresponding to the initial data;

receiving a plurality of updates to the initial data;

for each of M sequential updates of the plurality of updates:

generating deltas representing an update to a previous state of the data, wherein M is greater than or equal to one;

for each sequence of N updates of the plurality of updates, generating a first-level combined delta representing the N updates;

for each sequence of J updates, generating a second-level combined delta representing the J updates of the plurality of updates, where J is larger than N ;

storing the deltas as delta data objects, first-level combined deltas as first level combined delta objects, and second-level combined deltas as second-level combined delta data objects;

in response to a request for a current state of the data after A updates, retrieving the data object corresponding to the initial data and determining a minimal set of delta data objects that represent the A updates by:

determining a highest combined delta level comprising combined delta data objects that represent less than A updates;

selecting combined delta data objects of the highest combined delta level;

selecting combined delta data objects of a second highest combined delta level below which represent updates after those represented by the highest combined delta level;

selecting combined delta data objects, if any, which represent updates after those represented by the second highest combined delta level but before and up to A updates in turn for each lower level of combined deltas until the lowest combined delta level is reached; and

selecting delta data objects before and up to a delta associated with A updates for updates not represented by a delta data object at any level;

retrieving the minimal set of delta data objects;

determining updates to the initial data using the retrieved minimal set of delta data objects; and

generating updated data using the data object corresponding to the initial data and the determined updates.