Restoring a database using fuzzy snapshot techniques

[0001] The present invention relates to database snapshots. More particularly, the present invention relates to database snapshots of a main memory database without using hindering locks on the database.

[0002] Main memory database systems maintain a simple but potentially large, in-memory data structure that holds the data of the database. This type of database is typically between about 1 Gigabyte and about 4 Gigabytes in size, and cannot be larger than the memory of the particular computer because the database is in-memory. The memory utilized is standard RAM in standard servers.

[0003] in order to be able to recover such a database after a crash, the database maintenance system needs to ensure that all the information contained in memory is also on disk as a backup. Accordingly, the database maintenance system logs updates to the database. In other words, every time a change happens to the database, the database maintenance system logs the change into the log. When the database is restarted, the database maintenance replays the log. As can be imagined, after a relatively short time, the log can grow to be extremely long. Every time the database is rebooted, the database start time is longer than the previous reboot as the log grows.

[0004] To address this problem, the database maintenance software periodically takes snapshots of the database in order to reduce the recovery time when the database needs to be restarted. For example, after every 10,000 transactions or so, the database maintenance takes a snapshot of the database. After each snapshot, the database maintenance software starts a new log. Otherwise, without the snapshots, the database log would grow without bounds and the startup time would be proportional to the size of the database log. Using this snapshot method, when the database maintenance system needs to do a recovery, the system returns to the last snapshot and applies the log entries. The database maintenance system may thereby quickly recover a database. Continuing with the example above, at most, the database maintenance system has to restore a snapshot and replay 10,000 transactions.

[0005] Unfortunately, in order to take a snapshot, the database maintenance system must lock the database, write the entire database onto disk and unlock the database in order to start updating the database again. Meanwhile, real world implementations of databases are relatively large. Accordingly, as the database grows, it takes longer and longer to snapshot. So, the time to take a snapshot is much higher than the minimum request latency of updates to the database. For example, a database over about one Gigabyte requires a time for a lock that is too long for practical implementations of the database. For this reason, the database maintenance system cannot lock the database to take a snapshot of the database.

[0006] To address these problems, a proposed solution is to use some form of copy-on-write or partial locks. Copy-on-write is an optimization strategy used in computer programming. The fundamental idea is that if multiple callers ask for resources which are initially indistinguishable, you can give them pointers to the same resource. This fiction can be maintained until a caller tries to modify its “copy” of the resource, at which point a true private copy is created to prevent the changes becoming visible to everyone else. All of this happens transparently to the callers. The primary advantage is that if a caller never makes any modifications, no private copy need ever be created. A database maintenance system uses the copy-on-write concept hi maintenance of instant snapshots on database servers like Microsoft® SQL Server® 2005. As discussed above, instant snapshots preserve a static view of a database by storing a pre-modification copy of data when underlying data is updated.

[0007] Unfortunately, copy-on-write complicates certain implementations of database maintenance software. Also, partial locks still introduce unwanted latencies.

[0008] What is needed is an improved method having features for addressing the problems mentioned above and new features not yet discussed. Broadly speaking, the present invention fills these needs by providing a method and system of taking a database snapshot using a fuzzy snapshot. It should be appreciated that the present invention can be implemented in numerous ways, including as a method, a process, an apparatus, a system or a device. Inventive embodiments of the present invention are summarized below.

[0009] In one embodiment, a method of taking a snapshot, of a database is provided. The method comprises starting and maintaining a transaction log of the database, starting and maintaining a fuzzy snapshot of the database without applying any hindering locks to the database, and restoring the database by applying the transaction log to the fuzzy snapshot.

[0010] In another embodiment, a database snapshot device comprises a transaction log device configured to start and maintain a transaction log of the database, and a fuzzy snapshot device configured to start and maintain a fuzzy snapshot of the database without applying any hindering locks to the database, wherein the database snapshot device is configured to restore the database by applying the transaction log to the fuzzy snapshot.

[0011] In still another embodiment, a computer readable medium carrying one or more instructions for taking a snapshot of a database is provided, wherein the one or more instructions, when executed by one or more processors, cause the one or more processors to perform the steps of starting and maintaining a transaction log of the database, starting and maintain a fuzzy snapshot of the database without applying any hindering locks to the database, and restoring the database by applying the transaction log to the fuzzy snapshot.

[0012] The invention encompasses other embodiments configured as set forth above and with other features and alternatives.

[0019] An invention for taking a database snapshot using a fuzzy snapshot is disclosed. Numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be understood, however, to one skilled in the art, that the present invention may be practiced with other specific details.

[0020] FIG. 2 is a high-level view of a database snapshot system 200, in accordance with an embodiment of the present invention. The database snapshot system 200 includes a server 204 coupled to a network 202, which may include the Internet, a local area network (LAN), wide area network (WAN) or other type of network. The server 204 includes a database 206 and a database snapshot device 208. The database snapshot device 208 includes a transaction log device 210 and a fuzzy snapshot device 212. Generally, a device is software, hardware or a combination thereof. FIG. 2 shows the database snapshot device 208 inside the server 204. However, the database snapshot device 208 does not have to be located inside the server 204. There are alternative locations for the database snapshot device 208. For example, the database snapshot device 208 may be located on another networked computer in the database snapshot system 200.

[0021] Rather than locking the database and taking a static snapshot of the database 206, the database snapshot device 208 starts a snapshot that serializes (or processes) the database 206 while the database 206 is being updated. Since the database snapshot device 208 does not lock the database 206, the end result is a fuzzy snapshot that consists of the database 206 at the start of the snapshot with some subset of the updates that occurred to the database 206 while the snapshot was in process. Thus, the database snapshot device 208 addresses lack of control over memory management by exploiting a tree data model of the fuzzy snapshot and the idempotent nature of the updates to the database 206.

[0022] The database snapshot device 208 maintains a transaction log in a conventional manner. Also, the database snapshot device 208 initiates a snapshot in a conventional manner. For example, after about 10,000 transactions, the database snapshot device 208 starts a snapshot. However, the database snapshot device 208 does not apply any hindering locks to the database 206. A hindering lock is a lock that slows down the database, such as a global lock or a regional lock on a substantial part of the database.

[0023] Accordingly, the database snapshot device 208 has started a thread that is taking a snapshot of the database 206. However, as the database snapshot device 208 is taking the snapshot, transactions are coming into the database 206. The database 206 is dynamic and is constantly changing during the snapshot. The only thing in the database 206 that the database snapshot device 208 actually locks is each individual entry into the database 206 as the database snapshot device 208 processes that entry. The database snapshot device 208 goes through the database 206 and continuously writes new database entries. Writing out an entry is extremely fast because the size of an entry is on the order of kilobytes. Thus, the database snapshot device 208 does not need to take out any hindering locks.

[0024] The database snapshot device 208 may then start writing the database 206 to disk for future restoring. If the database snapshot device 208 goes to writing particular data out that has been deleted, then the database snapshot device 208 skips that particular data and continues the writing process. When this snapshot process is finished, the disk contains the fuzzy snapshot, which is an extremely fuzzy state of the database 206.

[0025] At this point, on the disk is the database 206 with which the database snapshot device 208 started at the start of the snapshot plus some random set of transactions that came in between the start and the end of the snapshot applied. The disk contains what looks like, to the untrained eye, a random mess. A number of the entries are valid. However, some of the entries are invalid. For example, the database snapshot device 208 may have written to disk some entries that were changed before the snapshot is finished. Also, there may be other entries that were not at a particular place when the database snapshot device 208 started writing the snapshot. However, by the time the database snapshot device 208 started that particular place in the dataset, the server 204 created these other entries. So, the database snapshot device serializes these new entries. The resulting fuzzy snapshot is a seemingly random mix of data, including data that was in the database 206 at the beginning of the snapshot and data changes made during the snapshot.

[0026] An important part here is using the fuzzy snapshot during recovery of the database. The database snapshot device 208 has the fuzzy snapshot in memory. The fuzzy snapshot may not look like any database 206 that was ever present at any particular time because the fuzzy snapshot contains the mix of old and new data. The database snapshot device 208 takes the set of transactions (or transaction log) that the database snapshot device 208 received since the beginning of the snapshot and applies that set of transactions to the fuzzy snapshot in memory.

[0027] When the database snapshot device 208 applies these transactions, the database snapshot device 208 skips any errors. For example, the database snapshot device 208 may come across a transaction in the log that indicates “set the row ABC to the value 123”; the database snapshot device 208 goes to do the set and finds there is no row ABC; thus, the set fails. In other words, this example presents an error. In such an example, the database snapshot device 208 ignores the error. The database snapshot device ignores any errors.

[0028] Interestingly, once the database snapshot device 208 applies the full set of transactions in the transaction log to the fuzzy snapshot, the end result is a valid database. The resulting database is the database that was in memory at the time of the last transaction in the transaction log.

[0029] This process works because the operations in the log have an idempotent property. In fact, order for process to work properly, the transactions applied to the database and put into the log must be idempotent. In other words, the database snapshot device 208 can apply a particular transaction more than once, and the result of the applied transaction will be the same. For example, if the command “set the row ABC to the value 123” is applied twice, the result will be the same; in other words. Row ABC will contain 123, even though the database snapshot device 208 applied the transaction twice. In another example, if the database snapshot device deletes particular data, that particular data is gone; if the database snapshot device 208 deletes that particular data again, there will be an error, but that particular data will still be gone. In yet another example, if the database snapshot device creates particular data, the particular data is now there; if the database snapshot device 208 creates that particular data again, there will be an error, but the particular data will be there from the first create command.

[0030] The examples discussed above illustrate the basic commands (set, delete and create) that the database snapshot device 208 applies to the fuzzy snapshot using the transaction, log. Because the transactions are idempotent, the database snapshot device 208 can apply the transactions to the fuzzy snapshot multiple times and still end up with the same result. The database snapshot device 208 will simply replace any transaction in the fuzzy snapshot that occurred after the start of the snapshot. Note that the database snapshot device 208 may apply a given transaction multiple times because the database snapshot device 208 simply applies transactions according to the transaction log. Accordingly, no transactions are missed. It is just that because of the fuzzy nature of the fuzzy snapshot, the database snapshot device 208 may end up applying any particular transaction more than once. However, that is acceptable because the transactions are idempotent.

[0031] Here are more examples of how the fuzzy snapshot of the database works. The database snapshot device 208 starts a fuzzy snapshot. Then, a create command comes in. If the entry created is processed accordingly by the snapshot thread, the result is a fuzzy snapshot without that create command. However, the transaction log has the create command. When the database snapshot device 208 restores the database and applies that create command according to the transaction log, the database will have the correct form with respect to that create command.

[0032] Potentially what can happen is that the database snapshot device 208 starts a snapshot Then, a create command happens. Then, a set command happens. Then, a delete command happens. If the snapshot thread happens to process that part of the database before any of these commands happen, it will be like the snapshot was done synchronously. In other words, upon restoring the database into memory* no entry would be there in the fuzzy snapshot. However, the transaction log contains the create, set and delete commands, and everything restores synchronously. Upon applying the transaction log to the fuzzy snapshot, the create, set and delete commands occur synchronously as planned.

[0033] Alternatively, the database snapshot device 208 happens to process that part of the database after the create command happens but before the set and delete commands. Upon restoring the database into memory, the create entry from the create command will already have affected that part of the fuzzy snapshot. Also, the transaction log contains the create, set and delete commands. Upon applying the transaction log to the fuzzy snapshot, the create command from the transaction, log will create an error, and that is fine. The database snapshot device 208 will simply skip that create command because the entry created is already there in the restored database. Then, the database snapshot device 208 applies the set command. The set command will work because the entry is there. Then, the database snapshot device applies the delete command. The delete command will work because the entry is there and modified by the set command.

[0034] Alternatively, the database snapshot device 208 happens to process that part of the database after the create and set commands happen but before the delete command happens. Upon restoring the database into memory, the create entry from the create and set commands will already have affected that part of the fuzzy snapshot. Also, the transaction log contains the create, set and delete commands. Upon applying the transaction log to the fuzzy snapshot, the create and set commands from the transaction log will create errors, and that is fine. The database snapshot device 208 will simply skip those create and set commands because the modified entry is already there in the restored database. Then, the database snapshot device applies the delete command. The delete command will work because the entry is there and modified by the set command.

[0035] Alternatively, the database snapshot device 208 happens to process that part of the database after the create, set and delete commands happen. Upon restoring the database into memory, nothing is there with respect to that part of the database because the delete command took the entry away. Accordingly, the create, set and delete commands will have already affected that part of the fuzzy snapshot. Also, the transaction log contains the create, set and delete commands. Upon applying the transaction log to the fuzzy snapshot, the database recovery device 208 will apply the create, set and delete commands because no entry is there to return an error. In this example, after the database recover device 208 applies the delete command, the end result will correctly be no entry.

[0036] FIG. 1 is a schematic diagram 100 of a database snapshot device, in accordance with an embodiment of the present invention. The schematic diagram shows the relationship between the transactions log 102 and the fuzzy database 104. In short, the database at the nth transaction is equal to the database at the ith transaction plus all the transactions from i+1 to n applied to the database at the ith transaction.

[0037] S_i is the database at any transaction t_i, which is the ith transaction and is the start of the snapshot. L_i is the transaction log started at transaction t_i. S_i+1 is the database at transaction t_i+1, which is the i+1th transaction and indicates i+1 transactions (or updates) occurred. L_i+1 is the transaction log started at transaction t_i+j. S_n is the database at transaction t_n, which is the nth transaction and indicates n transactions (or updates) occurred. L_n is the transaction log that contains the transactions from transaction t_i to transaction t_n. We define S′_n to be the snapshot that began with S_i and ended before S_n. L′_n contains the transactions of L_n that are captured during S′_n.

[0038] Whenever the method for taking fuzzy snapshot is restarted, the database snapshot device has S′_n and the transaction log L_n. However, the database snapshot device needs to get S_n to make sure the database snapshot, device starts where the database snapshot device left off.

[0039] If the database snapshot device defines L′_n to be the transactions captured in S′_n during the snapshot, then S′_n=S_n+L′_n, where+indicates the transactions in L′_n are applied to S_n. L′_n is a subset of L_n because L_n has all the transactions applied since S_i. Observe that S′_n+L_n=S_n+L′_n+L_n. Due to the idempotent nature of the transactions, L′_n+L_n=L_n. Thus, S_n=S′_n+L_n.

[0040] To recover the database, the database snapshot device takes the fuzzy snapshot S′_n and applies the update log L_n to S′_n. Whenever the database snapshot device applies L_n, the database snapshot device ignores any errors that would result from applying the transaction more than one time.

[0041] FIG. 3 is flowchart of a method 300 of taking a snapshot and restoring a database, in accordance with an embodiment of the present invention. The method starts in step 302 where the database snapshot device restores the database by applying the most current transaction log to the most current fuzzy snapshot. This step is skipped if this happens to be the first time this method 300 is applied to the database.

[0042] An important purpose of the transaction log and fuzzy snapshot is to get the transactions to non-volatile storage. Accordingly, the method 300 continues to step 304 where the database snapshot device starts and maintains a transaction log of the database. This starting and maintaining involves writing the transaction log to the transaction log device. Shortly thereafter or simultaneously, in step 306, the database snapshot device periodically takes fuzzy snapshots of the database. Taking a fuzzy snapshot involves writing a fuzzy snapshot to the fuzzy snapshot device. In other words, the fuzzy snapshot begins serializing (or processing) the database without applying any hindering locks to the database. Then, in step 308, the database snapshot device receives and applies transactions to the database. Because of the idempotent nature of the transactions, the database snapshot device may apply the same transaction multiple times to the fuzzy snapshot and still end with the same restored database.

[0043] The steps of the method 300 continue as appropriate. The database stays in the ready state of this method 300 until the database is shutdown. The method 300 is then at an end.

[0044] FIG. 4 is a flowchart of a method 400 of taking a snapshot of a database, in accordance with an embodiment of the present invention. The method 400 starts in step 402 where the database snapshot device receives a transaction. Next, in step 404, the database snapshot device logs the transaction into a transaction log. In other words, the database snapshot device writes the transaction log, including the transaction, to the transaction log device. Then, in step 406, the database snapshot device applies the transaction to the database.

[0045] The method 400 then continues to decision operation 408 where the database snapshot device determines if the number of transactions in the transaction log has reached a threshold number of transactions. This threshold number could be 10,000 transactions for example. If the number of transactions in the log has not reached the threshold number, the method 400 moves to decision operation 410. In decision operation 410, if the database is still in the ready state, the method 400 returns to step 402 where the database, snapshot device receives another transaction and the method 400 continues. Decision operation 410 actually applies to the database constantly but is placed where it is in the method 400 for simplicity.

[0046] If the number of transactions has reached the threshold number, the method 400 proceeds to step 412 where database snapshot device starts a fuzzy snapshot. Next or simultaneously, in step 414, the database snapshot device starts a new transaction log. Without waiting for the fuzzy snapshot to complete, the method 400 moves to decision operation 410 where it is determined if the database is still in the ready state. If so, the method 400 returns to step 402 where the database snapshot device receives another transaction and the method 400 continues. However, if it is determined in decision operation 410 that the database is not in the ready state, the method 400 is at an end.

[0047] FIG. 5 is a flowchart of a method 500 of restoring a database, in accordance with an embodiment of the present invention. The method 500 starts in step 502 where the database snapshot device restores the last complete snapshot of the database. Next, in step 504, the database snapshot device applies all transaction in order in the transaction togs that occurred after the last snapshot was started. The database snapshot device ignores all errors. The method 500 is then at an end.

Computer Readable Medium Implementation

[0048] Portions of the present invention may be conveniently implemented using a conventional general purpose or a specialized digital computer or microprocessor programmed according to the teachings of the present disclosure, as will be apparent to those skilled in the computer art.

[0049] Appropriate software coding can readily be prepared by skilled programmers based on the teachings of the present disclosure, as will be apparent to those skilled in the software art. The invention may also be implemented by the preparation of application specific integrated circuits or by interconnecting an appropriate network of conventional component circuits, as will be readily apparent to those skilled in the art.

[0050] The present invention includes a computer program product which is a storage medium (media) having instructions stored thereon/in which can be used to control, or cause, a computer to perform any of the processes of the present invention. The storage medium can include, but is not limited to, any type of disk including floppy disks, mini disks (MD's), optical disks, DVD, CD-ROMS, micro-drive, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, DRAMs, VRAMs, flash memory devices (including flash cards), magnetic or optical cards, nanosystems (including molecular memory ICs), RAID devices, remote data storage/archive/warehousing, or any type of media or device suitable for storing instructions and/or data.

[0051] Stored on any one of the computer readable medium (media), the present invention includes software for controlling both the hardware of the general purpose/specialized computer or microprocessor, and for enabling the computer or microprocessor to interact with a human user or other mechanism utilizing the results of the present invention. Such software may include, but is not limited to, device drivers, operating systems, and user applications. Ultimately, such computer readable media further includes software for performing the present invention, as described above.

[0052] Included in the programming (software) of the general/specialized computer or microprocessor are software modules for implementing the teachings of the present invention, including but not limited to starting and maintaining a transaction log of the database, starting and maintaining a fuzzy snapshot of the database without applying any hindering locks to the database, and restoring the database by applying the transaction log to the fuzzy snapshot, according to processes of the present invention.

Advantages

[0053] This invention allows the database snapshot device to maintain system performance while the fuzzy snapshot is in process because the database snapshot device does not take any hindering locks during the snapshot. The database snapshot device achieves this functionality with a very simple implementation because the database snapshot device does not have to add new data structures to the database. Nor does the database snapshot device have to add new metadata to the transaction log or fuzzy snapshot.

[0054] In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.