Method and system for storage

A method and system for storage is provided that in one embodiment includes a store process that continually appends data to the end of a data file and without deleting the data file. Additions, changes and deletions to data are managed by adding new data to the file and changing appropriate pointers in the data file to reflect the new data. Various application programming interfaces are also provided so that the store process can operate transparently to higher level applications. Various plug-ins are also provided so that the store process can utilize different types, configurations and numbers of storage devices.

FIELD

This specification relates generally to computer hardware and software architecture, and more particularly relates to a method and system for storage.

BACKGROUND

Relational databases were originally developed at a time when the speed of central processing units (“CPU”) were relatively slow, the amount of random access memory was relatively small, the size of hard disks was relatively small, but the speed at which hard disks was accessed was relatively fast. Interestingly, hardware advancements have now lead to a different paradigm, where CPUs are relatively fast, the amount of random access memory is relatively high, the size of hard disks is relatively large, but the speed at which hard disks are accessed is relatively slow. This new paradigm means that where large amounts of data are written in relatively small blocks across a large hard disk, the speed at which that data can be accessed is somewhat limited.

SUMMARY

A method and system for storage is provided that in one embodiment includes a store process that continually appends data to the end of a data file and without deleting the data file. Changes to data structures are managed by adding new data to the file and changing appropriate pointers in the data file to reflect the new data. Various application programming interfaces are also provided so that the store process can operate transparently to higher level applications. Various plug-ins are also provided so that the store process can utilize different types, configurations and numbers of storage devices.

An aspect of the specification provides a method for storing comprising:receiving a write command including an object to be written;seeking to an end of a file;defining a write location at or adjacent to said end of file;writing said object at said write location;defining an object identifier associated with said write location;redefining said end of file after said write location;wherein said method is invoked for:additions of objects to said file;deletions of objects from said file; andchanges of objects to said file.

Another aspect of the specification provides a skip-list data structure readable by a processing unit. The processing unit is configured to perform operations on contents of the data structure. The skip list data structure comprises a root object, a first child object and a plurality of additional child objects. The root object includes a pointer from said root object to said first child object. The root object also includes a pointer from the root object to every other one of the additional child objects. The every other one of said additional child objects including a pointer to one of each of said additional child objects to which said root object does not point.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Referring now toFIG. 1, a system for storage is indicated generally at50. System50can be based on a now-known or future-conceived computing environment. To provide an example,FIG. 1shows a block diagram representing exemplary components of system50. System50thus includes a processor54(which can also be referred to as a central processing unit) which interconnects input devices, if present, (e.g. a mouse58and keyboard62) and output devices, if present, (e.g. a display66). Processor54can be implemented, of course, as a plurality of processors or one or more multi-core processors. Processor54is also connected to a persistent storage device70. Persistent storage device70can be implemented using, for example, a hard disc drive, a redundant array of inexpensive discs (“RAID”), or the like, and/or can include other programmable read only memory (“PROM”) technology, a removable “smart card” and/or can comprised combinations of the foregoing.

System50also optionally includes a network interface74that connects processor54to a network (not shown), which in turn can connect to one or more additional persistent storage devices (not shown) that are similar in function to persistent storage device70.

System50also includes volatile storage78, which can be implemented as random access memory (“RAM”), which can be used to temporarily store applications and data as they are being used by processor54. System50also includes read only memory (“ROM”)82which contains a basic operating system containing rudimentary programming instructions, commonly known as a Basic Input/Output System (“BIOS”) that are executable by processor54when system50is initially powered so that a higher level operating system and applications can be loaded and executed on processor54. Collectively, one can view processor54, volatile storage device and ROM82as a microcomputer. It should now be apparent that system50can be based on the structure and functionality of a commercial server such as a Sun Fire X4450 Server from Sun Microsystems Inc., of Palo Alto, USA, but it is to be stressed that this is a purely exemplary server, as server50(and other elements of system50aand its variants) could also be based on any type of computing device including from other manufacturers.

The microcomputer implemented on system50is thus configured to store and execute the requisite BIOS, operating system and applications to provide the desired functionality of system50. In particular, system50is configured so that a plurality of processes is executable on processor54. InFIG. 1, processor54is represented as configured to execute the following processes: store100, read150, commit200and root250each of which can be invoked by commands entered via keyboard62and/or via other processes (not shown) executing on processor54. Also inFIG. 1, persistent storage70is shown as maintaining a file300that can be operated upon by store100, read150, commit200and root250as will be discussed in greater detail below. File300inFIG. 1is shown as being “empty”, only including an end-of-file marker EOF, which is located at Location zero L0within file300.

Referring now toFIG. 2, a flow-chart depicting an exemplary method of implementing store100is indicated generally100. Exemplary performance of store100is represented inFIGS. 3 and 4as an object O1is shown as being taken from volatile storage78and stored within file300using store100. At block105, a write command is received. Such a write command can be received by store100using any known means, including a direct command inputted via keyboard62, or via another process (not shown) executing on processor54. At block110, the object to be written is received. The object received at block110is associated with the write command received at step105. At block115, the end of file is sought. As part of block115, store100accesses file300and seeks end-of-file marker EOF in file300in order to determine the Location of end-of-file marker EOF. Taking the result from block115, at block120store110defines the write Location in file300for object O1, which in the present example is Location L0. At block125, the object is written at the Location defined at block120. Block125is represented inFIG. 4as object O1is shown now located at Location L0within file300. At block130an object identifier is defined that is associated with object O1as it is now stored in Location L0. The object identifier can be any index or pointer that now reflects Location L0. At block135, the end-of-file marker EOF is redefined to the Location after the Location in which the object has been written at step125. In the present example, as shown inFIG. 4, end-of-file marker EOF is now shown as stored in Location L1.

It should now be understood the repeated performances of store100will continue to append objects to file300. For example, assume that store100is executed again for a second object O2immediately after the preceding exemplary performance of store100for object O1. As a result of such performance, file300would appear as represented inFIG. 5, with object O1in Location L0, object O2in Location L1, and end-of-file marker EOF at Location L2. To continue with this example, the object identifier for O2is Location L1. According to this example, Table I below shows another representation of the contents of file300that corresponds toFIG. 5.

Thus, Table I corresponds to the file300as shown inFIG. 5, with the one exception that Table I additionally includes a column titled “Active” which is not actually reflective of file contents but instead represents whether the particular object in the respective Location of Table I is currently in use or not. The purpose of the “Active” column will become clearer from further reading below.

The teachings herein are applicable to the storage of many types of file structures. One exemplary type of file structure is a tree structure. Building on the example of file300inFIG. 5and Table II,FIG. 6shows object O2and object O1represented as part of a very basic tree structure T-1with a root and single child node, wherein object O2is the root and object O1is the child node. Accordingly, pointers are also needed identify the relationships in the tree structure. Thus, a root marker RM is additionally needed with a pointer to the Location of object O2. Table II builds upon Table I and includes such pointers.

Referring now toFIG. 7, a flow-chart depicting an exemplary method of implementing commit200(previously mentioned in relation toFIG. 1) is indicated generally200. Commit200can be used to add root marker RM.FIG. 8shows system50wherein file300reflects the contents of Table II including the invocation of commit200in order to include root marker RM and appropriate pointers in file300. At block205, the commit command is received. Such a commit command can be received by commit100using any known means, including a direct command inputted via keyboard62, or via another process (not shown) executing on processor54. At block110, the object ID to be written is received. The object ID received at block110is associated with the commit command received at step105, and typically embedded therein. In the present example, the commit command includes the parameter O2to identify object O2. At block215, the root marker is appended. As part of block215, commit200accesses file300and seeks end-of-file marker EOF in file300in order to determine the location of end-of-file marker EOF, and then defines the write location for the root marker RM and moves end-of-file marker EOF to location L3. Additionally, root marker RM is stored to include pointer P1which points to object O2in location L1, and object O2is stored to include pointer P2which points to object O1in location L0. Those skilled in the art will now recognize that file300now stores object O1and object O2in a manner that corresponds to tree structure T-1shown inFIG. 6.

It should now be understood that store100and commit200can be performed any number of times and file300will grow in size, particularly in light of the fact that no delete command is utilized. For example, assume that tree structure T-1is to be replaced by tree structure T-2shown inFIG. 9. Tree structure T-2includes a root containing object O4and a child node containing object O3. When store100is performed twice to store object O3and object O4, and when commit200is performed once to identify object O4as the root, file300will have the appearance as shown inFIG. 10. Table III shows a corresponding representation of file300inFIG. 10.

Of note is that file300continues to grow, but object O1, object O2and the root marker RM in location L2are no longer active. However, it is to be reemphasized that the “Active” status column is not expressly maintained by file300, but is the effective result of utilizing store and commit as previously described. Indeed, the “active” status need not even be relevant depending on the intended use of file300, since tree structure T-1in the form of object O1, object O2and the root marker RM in location L2is still available on an archive basis.

Referring now toFIG. 11, a flow-chart depicting an exemplary method of implementing root250(previously mentioned in relation toFIG. 1) is indicated generally250. Root250can be used to locate the root of a given tree structure stored within file300.FIG. 12shows system50representing exemplary performance of the method inFIG. 11. At block205, the root command is received. Such a root command can be received by root250using any known means, including a direct command inputted via keyboard62, or via another process (not shown) executing on processor54. At block260, a seek to end of file is performed. At block265a backwards scan through file300is performed until the root marker RM is found. In the case of Table III, the backwards scan reaches the root marker RM in location L4, and thus it can be seen where there is more than one root marker RM in a given file, only the root marker RM nearest the end of file marker EOF will be found at block265. Accordingly, the remaining root markers RM in a given file are effectively rendered inactive, without the need to expressly identify them as such. At block270, the root is located. Block270is performed by examining the pointer associated with the root marker RM found at block265. In this example, the pointer references location L4, where object O4is stored. At block275, the root found at block270is returned—and thus in this case object O4is returned to root250for further processing.

Referring now toFIG. 13, a flow-chart depicting an exemplary method of implementing read150(previously mentioned in relation toFIG. 1) is indicated generally150. Read150can be used to read the contents of a given object within file300.FIG. 13shows system50representing exemplary performance of the method inFIG. 14. At block155, the read command is received. Such a root command can be received by read150using any known means, including a direct command inputted via keyboard62, or via another process (not shown) executing on processor54. Additionally at block155, an object identifier OID associated with the read command is received. In a basic form, the object identifier can be one of the locations L0-L5within file300inFIG. 14. (In more complex scenarios, the object identifier itself can be a variable (e.g. “X”) that itself points to the location L0-L5, so that if the object is changed by writing it again at a subsequent location within file300using store200, then the location associated with the variable is updated at the time it is written.) In a present example object identifier OID is the location L4. At block165, the location of file300associated with the location associated with object identifier OID is accessed—which in this example is location L4. At block170, the contents of the location accessed at block165are returned—which in this example is object O4as stored in location L4.

Referring now toFIG. 15, another implementation of system50is shown. InFIG. 15, system50additionally includes a plurality of higher-level application program interfaces (API)300. APIs300, in a present embodiment, include a file system interface302, a B-tree (B-tree) interface304, a skip list interface308, a store and forward interface316, and a geographic interface320. APIs300in turn can be accessed by a data access object (DAO)320, a structured query language (SQL)324. All of the foregoing can be accessed by an application328. It should now be apparent that store100is in and of itself an application program interface which can be utilized, directly or indirectly, by APIs300, DAO320, SQL324or application328. Such utilization of store100can be substantially transparent, such that the exact means by which store100actually interacts with file300is completely unknown and substantially irrelevant to the operation of APIs300, DAO320, SQL324or application328. It should also be understood that system50as shown inFIG. 15can be varied to include none of, or one or more of, APIs300, DAO320, SQL324or application328.

InFIG. 15, system50additionally includes a plurality of lower-level plug-ins400. Plug-ins400, in a present embodiment, include caching plug-in402, a clustering plug-in404, a partitioning plug-in408, a sequencing plug-in412, a monitoring plug-in416and a remoting plug-in420. It should also be understood that system50as shown inFIG. 15can be varied to include none of, or one or more of plug-ins400. Each plug-in400can be used to influence and/or enhance how store100interacts with file300. It should now also be apparent that regardless of which plug-ins400are used, such plug-ins are also transparent to APIs300, DAO320, SQL324or application328.

File system interface302can be based on any suitable file manager, such as the well-known file manager interface found within a Windows™ operating system from Microsoft Corporation, Redmond, Wash., USA.

B-tree interface304, discussed further below, can be an interface that automatically manages the storage (including deletion and appending) of objects maintained in a B-tree structure on behalf of a higher level application. (While the present example is a B-tree, in other embodiments similar tree structures are contemplated such as B+-Tree, B*-Tree, binary tree, trie, and the like.)

Skip list interface308, can be an interface that automatically manages the storage (including deletion and appending) of objects maintained in a linked list structure on behalf of a higher level application.

Likewise, store and forward interface316is also an interface that automatically manages storage of objects maintained in the structures bearing similar name to the respective interface. Store-and-forward interface316can be used to implement clustering, since with clustering changes to the local store are communicated to remote stores so that remote stores can make the corresponding changes local to their copies as well. In this example, remoting plug-in460would be used in conjunction with store and forward interface316. In the event the remote server being accessed by remoting plug-in460is temporarily inaccessible, then data would be stored somewhere until such time as the missing resource becomes accessible again, all of which would be managed by store-and-forward interface316. All updates for the remote node would be stored in a store-and-forward structure until they could ultimately be delivered.

Geographic interface320manages the storage of objects that represent geographic locations, as might be implemented using a quad-tree. It should now be apparent that interfaces300in general manage the storage structure as that structure is utilized by higher level applications, and such interfaces300access store100accordingly. Interfaces300can issue interact with store100via block105and block110as per the method shown inFIG. 2. Though not shown inFIG. 15, interfaces300can likewise interact with read150, commit200and root250.

DAO320, SQL324and application328represent higher level applications or interfaces which directly or indirectly utilize store100.

Caching plug-in402can work transparently with and on behalf of store100such that storage of certain objects according to store100are temporarily stored in volatile storage78(or a separate volatile storage device not shown) according to a given criteria. When the criteria is satisfied those objects are actually flushed to persistent storage device70in the manner described above.

Clustering plug-in404can work transparently with and on behalf of store100such that file300is spread across a plurality of persistent storage devices (not shown inFIG. 15).

Partitioning plug-in408is similar in concept to clustering plug-in404and can also work transparently with and on behalf of store100such that portions of file300are stored across a multiple number of persistent storage devices70. By way of further explanation, clustering plug-in stores404all data to all persistent storage devices, whereas partitioning plug-in408typically only stores a subset of data across each persistent storage device. Also, with clustering, updates can originate from multiple locations whereas with partitioning updates typically occur from one location unless there is further partitioning.

Sequencing plug-in412, can be implemented as a variant of clustering plug-in404, utilizes a plurality of persistent storage devices (not shown) in sequence, such that when one persistent storage device is full the file is continued on the next persistent storage device. Sequencing plug-in412, can also be implemented so that data inserted during the same time period (e.g. during one day or week) are all stored in the same file. This implementation can make time-based retention policies simple (ie. deleting data after 90 days for example) as one just drop whole files of when the data in them expires.

Monitoring plug-in416can be used to assess the utilization of persistent storage device70(or multiples thereof) so that operations from store100can be moderated to accommodate any restrictions associated with a given persistent storage devices.

Remoting plug-in420can be used where a remotely connected persistent storage device (not shown) is connected to network interface74, in order to permit store100to utilize such remotely connected persistent storage devices.

It is to be reemphasized that the components relative to interfaces300and plug-ins400as introduced inFIG. 15can be “mixed and matched” according to any desired combination.FIG. 16shows one such simplified example, wherein B-tree interface304is shown alone in conjunction with store100as being accessed by application328.FIG. 17shows a B-tree T-3stored in volatile storage78which is to be written to file300.FIG. 17shows an example of B-tree T-3in greater detail that is be stored by application328using B-tree interface304and store100. When completely stored, file300will appear as shown inFIG. 18. B-tree interface304issues the instructions to store100(and to commit200) as appropriate so that file300has the structure of storage locations, pointers, root marker and contents that are reflective of B-tree T-3, as shown inFIG. 18, all in a manner transparent to application328. B-tree T-3can now likewise be accessed by application150via tree interface304using read150and root250.

File300from this point will simply grow in size. For example,FIG. 19shows B-tree T3-A which adds object O11as a child depending from object O8. The top half ofFIG. 20shows B-tree T-3beside its corresponding version of file300, reproducing B-tree T-3fromFIG. 17and file300fromFIG. 18. Assuming that object O11is simply added to B-tree T-3to produce B-tree T-3A by application328, then B-tree interface304will work with store100and commit200such that file300is grown so that it appears as shown in the lower half ofFIG. 20. To further assist in the foregoing, Table IV shows the contents of file300as shown inFIG. 18and in the top half ofFIG. 20, corresponding to the initial storage of B-tree T-3

To further assist in the foregoing, Table V shows the contents of file300after file300is updated from the state shown in Table IV, (and as also shown the bottom half ofFIG. 20), corresponding to the storage of B-tree T-3A in File300by B-tree interface304and store100after application328appended object O11to object O8and instructed that B-tree T-3A be persistently stored.

Using the foregoing, it will now be understood that deletion of nodes can be effected in a similar manner, whereby file300just continues to grow and various locations cease to be active and new locations in file300are written to, even with duplicates of data already present within file300in the event that new pointers are required.

As another example that the components relative to interfaces300and plug-ins400as introduced inFIG. 15can be “mixed and matched” according to any desired combination,FIG. 21shows another simplified example, wherein skip list interface308is shown alone in conjunction with store100as being accessed by application328, for the purpose of storing a skip list SL-1currently being maintained in volatile storage78.FIG. 22shows an exemplary skip list SL-1that can be implemented using the teachings herein. In skip list SL-1the root is object O12which points to objects O13, O14and O16. Object O14points to object O15and object O16points to object17. Thus skip list SL-1differs in structure from a B-tree. Those skilled in the art, however, will now recognize using the previous teachings herein that skip list interface308can be configured to work with store100to create a version of file300that reflects skip list SL-1and, by extension, the various ways that skip list SL-1can be stored within file300. It is further worth noting that inFIG. 23a new skip list SL-1A is provided, which is the same as skip list SL-1except that object O18has been added and that object O16now additionally points to object O18. Assuming that a version of file300already exists that reflects skip list SL-1, then as object O18is added to file300, it is only necessary to write object O18for the first time into a new location in file300, and rewrite object O16into a new location in file300(so that pointers to object O17and object O18can be provided), and to rewrite object O12into a new location in file300(so that the pointer to the new location of object O16can be provided.) Otherwise, objects O13, O14, O15and O17can remain active within file300and need not be rewritten into new locations of file300.

(Those skilled in the art will now recognize that skip-list SL-1is a novel skip list, as in order to be a traditional skip-list, object O13would need to point to object O14; object O15would need to point to object O16; and object O14would need to point to object O16. Thus, skip list SL-1is in fact a novel skip-list. Skip list SL-1is therefore a novel embodiment in and of itself. Skip list SL-1can have many uses, such as journal-based storage.)

As another example that the components relative to interfaces300and plug-ins400as introduced inFIG. 15can be “mixed and matched” according to any desired combination,FIG. 24shows another simplified example, wherein store100is shown with partition plug-in408and sequence plug-in412(which can be implemented collectively as a single plug-in referred to herein as compound storage plug-in), and in turn three different additional instances of store100are provided, namely store100A, store100B and store100C. (Similar additional instances of read150, commit200and root250are also provided but not shown inFIG. 24). Store100A, store100B and store100C are accessible to plug-ins408and412. (Note that the exact placement of each plug-in in relation to each instance of store100may not be exactly as shown inFIG. 24during an actual implementation. For example, an instance of plug-in412could, in practice, not be implemented above store100A, store100B and store100C but instead below each one of store100A, store100B and store100C.) InFIG. 24, system50also includes three persistent storage devices70A,70B and70C, each with its own respective file300A,300B and300C. In this highly simplified example, file300A,300B and300C each only have two locations. Therefore, in order to store four objects O1-O4and identify one of those objects as a root, and to have an end of file marker EOF, partition plug-in408and sequence plug-in412cooperate with store100A, store100B and store100C to store objects O1-O4, the root marker and the end of file marker across storage devices70A,70B and70C. It can be desired to implement system50according toFIG. 24when the sizes of devices70A,70B and/or70C are limited and/or where it is desired to keep a long historical record of changes. A read can be effected to any one of the devices70A,70B,70C. When the devices70A,70B,70C become full a new device70can be added.

As a further enhancement, it is to be understood that partition plug-in408can be implemented, if desired, in accordance with the teachings of co-pending and commonly-assigned U.S. patent application Ser. No. 11/693,305 filed Mar. 29, 2007, now U.S. Pat. No. 7,680,766, the contents of which are incorporated herein by reference.

As another example that the components relative to interfaces300and plug-ins400as introduced inFIG. 15can be “mixed and matched” according to any desired combination,FIG. 25shows a more complex example including a plurality of separate servers remotely connected to each other, with processor54A representing the processor of the first server; processor54B representing the processor of the second server; and processor54nrepresenting the processor of the “nth” or final server; Processor54A includes store100, cache plug-in402, partition plug-in408and remote plug-in420as previously discussed. Remote plug-in420can communicate with store100on processor54B and store100on processor54n. Processor54B and processor54nthemselves each implement cache plug-in402, partition plug-in408and sequence plug-in412, which make use of two persistent storage devices70local to each processor54B and54n. The configuration inFIG. 25highlights the highly scalable nature of the teachings herein to provide large amounts of storage capacity with transaction speeds that can be described as at least “good” and potentially much better than current commercial database solutions offered by Oracle Corporation, 500 Oracle Parkway, Redwood Shores, Calif. 94065 and others. Furthermore, such storage can be provided relatively inexpensively.

It should now be apparent that many other combinations, subsets and variations of interfaces300and plug-ins400across one or more physical servers are within the scope of the teachings herein. In general, it should now be understood also that combinations, subsets and variations of all of the embodiments herein are contemplated.

Indeed, the present novel system and method for storage can present some advantages in certain implementations. For example, the inventor has done research leading the inventor to believe that a properly configured implementation can provide disk accessing speeds of up to 1.5 million transactions per second. A still further potential advantage from a properly configured implementation where the persistent storage is based on Flash drives can ultimately lead to longer life for such Flash drives, as a properly configured implementation of certain embodiments can lead to substantially equal use of all memory locations in the Flash drive, or at least more equal use of those memory locations than the prior art. Since memory locations in Flash drives “burn out” after a certain number of uses, the useful life of such Flash drives can conceivably be extended. As a still further potential advantage, properly configured implementations of certain embodiments can provide databases where recording of changes to those databases is automatically effected.

In addition, the teachings herein can, in properly configured implementations, support Relational, object oriented, Temporal, Network (Hierarchical), Inverted-Index (search engine), Object-Relational, Geographic and other persistence paradigms which can all be combined into the same database at the same time.

In addition, teachings herein can support, in properly configured implementations, a single top-level first-in-first-out read/write queue that would suffice for an entire system. No internal synchronization would be required for read operations. This is possible because Objects are never updated, only replaced, which can provide good in-memory performance.

In addition, Compact Disk Representation of Objects can be provided using certain properly configured embodiments of the teachings herein. As known to those skilled in the art, relational databases using fixed-size rows can be very wasteful for cases where many rows are unused or usually contain a default value, or when large strings values are used to store only small values on average. The teachings herein can, in properly configured implementations, support storage of non-default values and so that only amount of string data which is actually used is stored. This can lead to significant performance and disk-space efficiency improvements.

In addition, bursty traffic can be more readily accommodated using properly configured embodiments of the teachings. Under short periods of heavy load a journal garbage collector would execute at a lower priority (or not at all), thus allowing for higher peak loads than what could normally be sustained.

In addition, properly configured embodiments of the teachings herein can provide Large Collection Support and obviate the need for a Separate Transaction Journal. This means that transactions can be easily supported without incurring the overhead normally associated with their use.

In addition, properly configured embodiments of the teachings herein can obviate Separate Clustering Channels. This means that larger clusters can be supported more efficiently. A ten fold increase over certain configurations of current clustering performance could be realized.

In addition, properly configured embodiments of the teachings herein can provide scalability because data is never updated, only replaced, there is a reduced (and possibly zero) possibility for corruption. Properly configured embodiments can be equally suitable for databases of all sizes. For small databases it can be as fast as completely in-memory systems. Large databases can be scaled in the same way as completely disk-based systems. This can allow one to code all of databases in the same way without forcing the use a different system depending on your performance or size requirements.