Claims:
1. An apparatus to recover from crash using a non-volatile random-access memory (NVRAM), the apparatus comprises: a processor coupled to the NVRAM, the processor, configured to:
detect an occurrence of the crash in the NVRAM;
generate at least a hint associated with the occurrence detected, the at least a hint comprises an identification of at least a database, a logical address of at least a memory block in the at least a database, and a status of at least an operation of the at least a database during the crash occurred, wherein:
the at least a memory block in the at least a data portion is accessed during the crash occurred,
the at least a memory block is allocated for the at least an operation of the at least a database during the crash occurred, and
the at least a database is stored in the NVRAM or stored in a remote host in communication with the NVRAM;
update at least a recovery thread with the at least an operation in progress at the time of the generation of the hint according to the status of the at least an operation;
backtrack the at least an operation into the at least a database according to the identification of the at least a database; and
recover the data from at least a memory block according to the logical address of the at least a memory block in the at least a database.

2. The apparatus as claimed in claim 1 is further configured to: detect at least an operation in progress at the time of the crash is completed, wherein:
if the at least an operation is not completed, undo the at least an operation of the at least a memory block using the logical address of the at least a memory block in the database, and recover the at least an operation; or
if the at least an operation is completed, read undo on the at least a database.

3. The apparatus as claimed in claim 1, wherein the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion:
the header portion is configured to store a complete meta-data for the NVRAM and at least a state for an internal memory organization of the NVRAM;
the undo information portion comprises a memory area or a file storage to store the undo information of NVRAM operations, preferably an ALLOC operation and/or a FREE operation;
the undo record portion comprises a memory area to store the undo record from the database operation, preferably an insert operation and/or update operation and/or a delete operation;
the data directory portion is configured to store a list of memory block descriptors associated with the data portion; and
the data portion comprises a memory area configured to allocate atleast one block in dynamic sizes and/or present the data to an user on a request.

4. A method to recover from crash using a non-volatile random-access memory (NVRAM), the method comprising:
detecting an occurrence of the crash in the NVRAM;
generating at least a hint associated with the occurrence detected, the at least a hint comprises an identification of at least a database, a logical address of at least a memory block in the at least a database, and a status of at least an operation of the at least a database during the crash occurred;
the at least a memory block in the at least a data portion is accessed during the crash occurred,
the at least a memory block is allocated for the at least an operation of the at least a database during the crash occurred, and
the at least a database is stored in the NVRAM or stored in a remote host in communication with the NVRAM;

updating at least a recovery thread with the at least an operation in progress at the time of the generation of the hint according to the status of the at least an operation;
backtracking the at least an operation into the at least a database according to the identification of the at least a database; and
recovering the data from at least a memory block according to the logical address of the at least a memory block in the at least a database.

5. The method as claimed in claims 4, wherein the method further comprises detecting at least an operation in progress at the time of the crash is completed, wherein:
if the at least an operation is not completed, undo the at least an operation of the at least a memory block using the logical address of the at least a memory block in the database, and recover the at least an operation; or
if the at least an operation is completed, read undo on the at least a database.

6. The method as claimed in claim 4, wherein the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion:
the header portion is configured to store a complete meta-data for the NVRAM and at least a state for an internal memory organization of the NVRAM;
the undo information portion comprises a memory area or a file storage to store the undo information of NVRAM operations, preferably an ALLOC operation and/or a FREE operation;
the undo record portion comprises a memory area to store the undo record from the database operation, preferably an insert operation and/or update operation and/or a delete operation;
the data directory portion is configured to store a list of memory block descriptors associated with the data portion; and

the data portion comprises a memory area configured to allocate at least one memory block in dynamic sizes and/or present the data to an user on a request.

7. An apparatus to recover from change using a non-volatile random-access memory (NVRAM) comprising: a processor, coupled to the NVRAM, for executing a plurality of modules present in the NVRAM, the processor on execution of the modules, configured to:
detect at least a change in the NVRAM, the change is the writing of data to the NVRAM and/or reading of data from the NVRAM;
generate at least a hint associated with the change detected, the at least a hint comprises an identification of at least a database, a logical address of at least a memory block in the at least a database, and a status of at least an operation of the at least a database during the change occurred, wherein:
the at least a memory block in the at least a data is accessed during the change occurred,
the at least a memory block is allocated for the at least an operation of the at least a database during the change occurred, and
the at least a database is stored in the NVRAM or stored in a remote host in communication with the NVRAM;

update at least a recovery thread with the at least an operation in progress at the time of the generation of the hint according to the status of the at least an operation;
backtrack the at least an operation into the at least a database according to the identification of the at least a database;
recover the data from at least a memory block according to the logical address of the at least a memory block in the at least a database.

8. The apparatus as claimed in claim 7 is further configured to store the at least one hint in the NVRAM, wherein the at least one hint is written first and thereafter an allocation of and/or a de-allocation of the at least a memory block is performed.

9. The apparatus as claimed in claim 7 is further configured to re-use the hint generated stored in the NVRAM for at least a subsequent write operation.

10. The apparatus as claimed in claim 7, wherein the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion, and wherein:
the header portion is configured to store a complete meta-data for the NVRAM and at least a state for an internal memory organization of the NVRAM;
the undo information portion comprises a memory area or a file storage to store the undo information of NVRAM operations, preferably an ALLOC operation and/or a FREE operation;
the undo record portion comprises a memory area to store the undo record from the database operation, preferably an insert operation and/or update operation and/or a delete operation;
the data directory portion is configured to store a list of memory block descriptors associated with the data portion;
the data portion comprises a memory area configured to allocate at least one memory block in dynamic sizes and/or present the data to an user on a request.

11. A method to recover from change using a non-volatile random-access memory (NVRAM), the method comprising:
detecting at least a change in the NVRAM, the change is the writing of data to the NVRAM and/or reading of data from the NVRAM;
generating at least a hint associated with the change detected, the at least a hint comprises an identification of at least a database, a logical address of at least a memory block in the at least a database, and a status of at least an operation of the at least a database during the change occurred, wherein:
the at least a memory block in the at least a data is accessed during the change occurred,
the at least a memory block is allocated for the at least an operation of the at least a database during the change occurred, and
the at least a database is stored in the NVRAM or stored in a remote host in communication with the NVRAM;

updating at least a recovery thread with the at least an operation in progress at the time of the generation of the hint according to the status of the at least an operation;
backtracking the at least an operation into the at least a database according to the identification of the at least a database;
recovering the data from at least a memory block according to the logical address of the at least a memory block in the at least a database.

12. The method as claimed in claim 11 further comprises: storing the at least one hint in the NVRAM, wherein the at least one hint is written first and thereafter an allocation of and/or a de-allocation of the at least a memory block is performed.

13. The method as claimed in claim 11 further comprises: re-using the hint generated stored in the NVRAM for at least a subsequent write operation.

14. The method as claimed in claim 11, wherein the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion:
the header portion is configured to store a complete meta-data for the NVRAM and at least a state for an internal memory organization of the NVRAM;
the undo information portion comprises a memory area or a file storage to store the undo information of NVRAM operations, preferably an ALLOC operation and/or a FREE operation;
the undo record portion comprises a memory area to store the undo record from the database operation, preferably an insert operation and/or update operation and/or a delete operation;
the data directory portion is configured to store a list of memory block descriptors associated with the data portion;
the data portion comprises a memory area configured to allocate at least one memory block in dynamic sizes and/or present the data to an user on a request.
, Description:
TECHNICAL FIELD

The present subject matter described herein, in general, relates to memory devices and database technologies, and more particularly, to apparatus and method for recovery in nonvolatile memory based databases.

BACKGROUND

Nonvolatile (sometimes written as “non-volatile”) random access memory (“nvram,” or “NVRAM”) is typically a form of static RAM whose content is saved when a computer is turned off or loses its external power source. As is known to those skilled in the art, NVRAM may be implemented in various ways, including by providing static RAM with backup battery power, or by saving its contents and restoring them from an Electrically Erasable Programmable Read Only Memory (“EEPROM”). The NVRAM technologies are an emerging area in storage technologies. The main advantages that the NVRAM may offer are persistence same as disk, read/write latency is same to dynamic random-access memory (DRAM), write latencies are much lesser than disk but not comparable to DRAM, and byte addressable with finer control on the data stored.

In view of the above understanding, the NVRAM becomes an ideal for applications having requirement for an immediate recovery of database and higher durability for all transactions. If NVRAM is used to store the database, the database management system can recover the data store from the last consistent state upon reboot in faster rate as compared to the log based recovery in traditional database storage on secondary storage media. This approach presents a very attractive durability option for an in-memory database. In contrast to the transaction logging approach involving disk I/O related overhead, or to the replication approach with its communication overhead, an NVRAM database incurs no disk or network overhead during operation.

In spite of the above fact, the NVRAM used for database (DB) has been mainly for recovery or temporary storage of logs, or for durability purpose as a replacement for hard disk. Still the recovery performance for the NVRAM is a major concern. In the case of the NVRAM based database each write to the database is analogous to a checkpoint in traditional database systems. Failures during checkpoints is treated in many special ways like using double-checkpoint and redo logs, or using fuzzy checkpoint and redo logs. However, recovery mechanisms in the NVRAM based databases need not use redo logs. So in the NVRAM based databases error tracking of a record write and ensuring sanity during recovery is a major concern. A naive approach focuses on writing a kind of hash code (like CRC32) to the record before the record is written, or writing magic code at the start and end of records and the like. Further, in the naive approach the recovery needs to walk through all pages to ensure sanity. This causes the recovery to be too slow.

SUMMARY

This summary is provided to introduce concepts related to apparatuses and methods for recovery in nonvolatile memory based databases, and the same are further described below in the detailed description. This summary is not intended to identify essential features of the claimed subject matter nor is it intended for use in determining or limiting the scope of the claimed subject matter.

A main objective of the present invention is to solve the technical problem as recited above by providing an apparatus and a method for recovery in nonvolatile memory based databases.

Another objective of the present invention is to provide an apparatus and a method for fast corruption detection in NVRAM based databases.

Another objective of the present invention is to provide an apparatus and a method handle recovery in NVRAM based databases.

Another objective of the present invention is to provide an apparatus and a method to track errors by identifying an error segments during recovery.

Another objective of the present invention is to provide an apparatus and a method to recover associated database from a detected page corruptions to maintain database consistency.

Yet another objective of the present invention is to provide an apparatus and a method to reduce the crash recovery time for NVRAM based databases, and increases their availability.

Yet another objective of the present invention is to provide an apparatus and a method to track back the NVRAM memory manager changes to the database operation which caused the crash.

Yet another objective of the present invention is to provide an apparatus and a method to track the pages which were under change during the database shutdown process.

Still another objective of the present invention is to provide an apparatus and a method to use the tracked page list to check the sanity of the corresponding pages.

Accordingly, in one implementation, when a memory format of NVRAM is being changed due to allocation of a new block or de-allocation of any existing block, a hint is generated and stored in the NVRAM. The hint enables a recovery thread to know a type of operation that was in progress when the memory format was changed. The thread backtracks to at least one database, therein to at least one block allocation and the associated details. The backtracked data from the block is either allocated or freed or recovered based on the change detected.

In one implementation, only one hint for the whole NVRAM is generated, as only one user operation at a time is allowed to change the NVRAM memory manager.

In one implementation, the hint is written first, only after which the actual allocation/de-allocation is done. The placeholder for hint is reused for subsequent write operations, as the space in NVRAM is costly.

In one implementation, an apparatus to recover from crash using a non-volatile random-access memory (NVRAM) is disclosed. The apparatus comprises a processor coupled to the NVRAM, the processor, configured to: detect an occurrence of the crash in the NVRAM; generate at least a hint associated with the occurrence detected, the at least a hint comprises an identification of at least a database, a logical address of at least a memory block in the at least a database, and a status of at least an operation of the at least a database during the crash occurred, wherein: the at least a memory block in the at least a data portion is accessed during the crash occurred, the at least a memory block is allocated for the at least an operation of the at least a database during the crash occurred, and the at least a database is stored in the NVRAM or stored in a remote host in communication with the NVRAM; update at least a recovery thread with the at least an operation in progress at the time of the generation of the hint according to the status of the at least an operation; backtrack the at least an operation into the at least a database according to the identification of the at least a database; and recover the data from at least a memory block according to the logical address of the at least a memory block in the at least a database.

In one implementation, an apparatus to recover from change using a non-volatile random-access memory (NVRAM) comprises a processor, coupled to the NVRAM, for executing a plurality of modules present in the NVRAM. The processor on execution of the modules, configured to: detect at least a change in the NVRAM, the change is the writing of data to the NVRAM and/or reading of data from the NVRAM; generate at least a hint associated with the change detected, the at least a hint comprises an identification of at least a database, a logical address of at least a memory block in the at least a database, and a status of at least an operation of the at least a database during the change occurred, wherein: the at least a memory block in the at least a data is accessed during the change occurred, the at least a memory block is allocated for the at least an operation of the at least a database during the change occurred, and the at least a database is stored in the NVRAM or stored in a remote host in communication with the NVRAM; update at least a recovery thread with the at least an operation in progress at the time of the generation of the hint according to the status of the at least an operation; backtrack the at least an operation into the at least a database according to the identification of the at least a database; recover the data from at least a memory block according to the logical address of the at least a memory block in the at least a database.

In one implementation, a method to recover from crash using a non-volatile random-access memory (NVRAM) is disclosed. The method comprises detecting an occurrence of the crash in the NVRAM; generating at least a hint associated with the occurrence detected, the at least a hint comprises an identification of at least a database, a logical address of at least a memory block in the at least a database, and a status of at least an operation of the at least a database during the crash occurred; the at least a memory block in the at least a data portion is accessed during the crash occurred, the at least a memory block is allocated for the at least an operation of the at least a database during the crash occurred, and the at least a database is stored in the NVRAM or stored in a remote host in communication with the NVRAM; updating at least a recovery thread with the at least an operation in progress at the time of the generation of the hint according to the status of the at least an operation; backtracking the at least an operation into the at least a database according to the identification of the at least a database; and recovering the data from at least a memory block according to the logical address of the at least a memory block in the at least a database.

In one implementation, A method to recover from change using a non-volatile random-access memory (NVRAM), the method comprises detecting at least a change in the NVRAM, the change is the writing of data to the NVRAM and/or reading of data from the NVRAM; generating at least a hint associated with the change detected, the at least a hint comprises an identification of at least a database, a logical address of at least a memory block in the at least a database, and a status of at least an operation of the at least a database during the change occurred, wherein: the at least a memory block in the at least a data is accessed during the change occurred, the at least a memory block is allocated for the at least an operation of the at least a database during the change occurred, and the at least a database is stored in the NVRAM or stored in a remote host in communication with the NVRAM; updating at least a recovery thread with the at least an operation in progress at the time of the generation of the hint according to the status of the at least an operation; backtracking the at least an operation into the at least a database according to the identification of the at least a database; recovering the data from at least a memory block according to the logical address of the at least a memory block in the at least a database.

In contrast to the prior-art techniques, the present invention by apparatus and methods, enables to manage pages in the NVRAM, record NVRAM data organization format and data page operation and building hints to be used in an event of recovery, invoke UNDO for database data and metadata for associated data recovery and consistency of database, and provides a recovery mechanisms where only UNDO needs to be replayed (either from the meta data segment or from the data segment).

In contrast to the prior-art techniques, when a crash occurs, a HINT recorded will point to check what operation happened before crash and the associated location of the operation. The present invention uses this information/hint to directly jump to those addresses/memory blocks and correct them using the UNDO information. This saves us a big search of whole of the NVRAM memory layout to isolate the problem area. Hence, hint according to the present invention stores the location and type of operation carried out since last operation (which automatically is a “Last known good state” of the database) as stored on NVRAM.

After crash, on restart of the system, a recovery method checks for HINT (if saved) and jumps directly to the location where the last operation was carried, and re-apply the original state as stored in the HINT registers, thereby restoring the possibly corrupted block of NVRAM to the original “Last known good state”. Additionally, the database specific operation level information is also stored in the HINT, which directly points for the recovery mechanism to initiate the rollback recovery in that database bringing back sanity of the database and transaction which was last operating.

Further, if any operation occurs on the NVRAM memory at any given time, this is utilized by recording what modifications are carried out to the NVRAM at that instant (viz. HINT) by the present invention.

In naive approach a recovery requires to scan whole or most part of the NVRAM to check for possible corruption in the linkages in the directory structure, memory blocks etc. which make the cost of this recovery in order of O(n) wherein, n tends to be blocks involved in the NVRAM FS. However, the present invention preserves the knowledge of operation along with the location when operation (i.e. HINT) is happening, across system crash and uses this information to directly access the location/address in NVRAM and fix it; Since, only 1 NVRAM modification operations (FREE/ALLOC) is allowed as per this approach, so at any instant only one directly entry or block entry can be corrupted during crash. Hence, recovery operation reaches in 1 step to the corruption location and fix it thereby, making the cost of recovery in order of O(1).

When the present invention is implemented in any of existing corruption checking concepts, the recovery is in O(1) space, as opposed to the original O(n) space (n à data size, page size) as available in any of the existing techniques.

The various options and preferred embodiments referred to above in relation to the first implementation are also applicable in relation to the other implementations.

BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS

The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to refer like features and components.

Figure 1 illustrates a flowchart showing the overall summary of the invention, in accordance with an embodiment of the present subject matter.

Figure 2 illustrates a NVRAM memory layout, in accordance with an embodiment of the present subject matter.

Figure 3 illustrates a flowchart for the NVRAM operation like ALLOC, in accordance with an embodiment of the present subject matter.

Figure 4 illustrates a flowchart for recovery from crash in NVRAM, in accordance with an embodiment of the present subject matter.

Figure 5 illustrates an apparatus implementing the present invention, in accordance with an embodiment of the present subject matter.

It is to be understood that the attached drawings are for purposes of illustrating the concepts of the invention and may not be to scale.

DETAILED DESCRIPTION OF THE PRESENT INVENTION

The following clearly describes the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Apparently, the described embodiments are merely a part rather than all of the embodiments of the present invention. All other embodiments obtained by a person of ordinary skill in the art based on the embodiments of the present invention without creative efforts shall fall within the protection scope of the present invention.

The invention can be implemented in numerous ways, as a process, an apparatus, a system, a composition of matter, a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication links. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. In general, the order of the steps of disclosed processes may be altered within the scope of the invention.

A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured.

Apparatus and methods for recovery in nonvolatile memory based databases are disclosed.

While aspects are described for apparatus and methods for recovery in nonvolatile memory based databases, the present invention may be implemented in any number of different computing systems, environments, and/or configurations, the embodiments are described in the context of the following exemplary systems, apparatus, and methods.

In one implementation, when a memory format of NVRAM is being changed due to allocation of a new block or de-allocation of any existing block, a hint is generated and stored in the NVRAM. The hint enables a recovery thread to know a type of operation that was in progress when the memory format was changed. The thread backtracks to at least one database, therein to at least one block allocation and the associated details. The backtracked data from the block is either allocated or freed or recovered based on the change detected.

In one implementation, only one hint for the whole NVRAM is generated, as only one user operation at a time is allowed to change the NVRAM memory manager.

In one implementation, the hint is written first, only after which the actual allocation/de-allocation is done. The placeholder for hint is reused for subsequent write operations, as the space in NVRAM is costly.

Referring now to figure 1, a flowchart showing the overall summary of the invention is illustrated, in accordance with an embodiment of the present subject matter. In one implementation, as shown in figure 1:

At step 1: a database may be created at the NVRAM using any of the convention or new mechanism. The NVRAM used in the present invention is segmented into various sections and each section is designated for specific purpose. As shown in figure 2, in one embodiment, the NVRAM may be divided into:
i. a header section: The header section stores a complete meta-data for the complete NVRAM memory block and states for internal memory organization.
ii. a UNDO (meta) section: The Undo (meta) section is a memory area / a file storage reserved for storage undo information of NVRAM operations like ALLOC/FREE. In one implementation, UNDO(meta) can be inside the NVRAM unit or maintained externally, using the UNDO maintained externally can ensure recovery of the NVRAM which is crashed.
iii. a data directory section: The data directory section stores a list of memory block descriptors.
iv. a data section: The data section is a memory area where blocks are allocated in dynamic sizes and presented to user on request.
v. a UNDO (data): The undo data section is a memory area reserved for storage of undo records from database operations (like Insert/Update/Delete).

In one implementation, a general configuration is below for easier visualization; however, it may be understood by the person skilled in the art that, the configuration is not limited or restricted to the configuration provided below. The exemplary configuration is as provided below:

i. UNDO segment is generally about 20% of the NVRAM, and/or the UNDO segment is allowed to be used in case data segment is full.
ii. UNDO (META) is relatively very insignificant, and/or the UNDO (META) generally is about 512KB.
iii. Database headers segment is little over 1024KB in size
iv. Remaining size is used by DATA segment and data directory, wherein data directory (each entry about 512 bytes) grows from top to bottom. And DATA blocks allocated with size as per request form the database storage subsystem, allocated from bottom to top.

At step 2, a particular operation like a write or retrieve data from the NVRAM is received. It may be understood that the NVRAM may store data from and/or retrieve data to at least one host to which the NVRAM is connected.

At step 3, on receipt of the particular operation, an UNDO for data and metadata is generated as per the convention al techniques available and is stored in the NVRAM.

At step 4, on receipt of the particular operation, the present invention is configured to generate at least a hint for at least one NVRAM manager indicating at least a change occurrence or is to be occurring in the NVRAM. The hint generated may be stored in the NVRAM itself. In one embodiment, the hint comprises at least information associated with the occurrence detected. The information may be at least a database identification of the database during the access of which the crash occur a logical address of a block in the database or a status of a database operation or any combination thereof.

At step 5, the database operation is performed in the NVRAM.

At step 6, the NVRAM is configured to release all the UNDO’s generated at step 3.

At step 7, a result of the operation performed by the NVRAM is returned to the user.

It may be understood by the person skilled in that art that, the system may crash at any point of time during the steps 1-7 above. Hence a new mechanism as shown in dotted box in figure 1 is disclosed in the present invention, according to which on occurrence of the crash, updates at least a recovery thread with at least an operation in progress at the time of the generation of the hint. The operation is backtracked into at least a database stored using the hint in the NVRAM or stored remotely. Based on the backtracked information, the present invention recovers the data from at least a block allocated for the operation backtracked from the database. The present invention rollbacks the records based on backtracking and the results are displayed to the user accordingly after performing the operation.

Figure 2 illustrates a NVRAM memory layout, in accordance with an embodiment of the present subject matter. In one implementation, figure 2 illustrates a nonvolatile memory medium logically partitioned into memory blocks according to aspects of the present invention. As compared to the prior-art techniques, the NVRAM is used in the application to database and record database specific events to the hint. The present invention uses the database operation level information also recorded in the hint to process the recovery of database alongside file system recovery.

Figure 3 illustrates a flowchart for the NVRAM operation like ALLOC, in accordance with an embodiment of the present subject matter. In one implementation, during NVRAM operation like ALLOC, following steps may be carried out:
i. an unused block is identified from the NVRAM memory segments;
ii. a hint is generated containing the block address identified, the entries in a free list, previous entry in a used block list, a database operation to be performed, and a database identified among other database;
iii. the hint generated may be written to the NVRAM;
iv. the identified block is added to the used block list, and then
v. the start address of the data block is returned to top level the database operation to perform i.e., to allocate the data block to store data in the NVRAM database.

In one implementation, all the above steps are performed in exclusive lock, i.e., only one operation can change the block structures.

In one implementation, according to the present invention, before executing steps i-v above, the UNDO (Meta) record portion of the NVRAM is updated with a state of the free memory, an operating data-block Directory, a next-previous nodes in free list of data block directory or data-block free list.

In one implementation, all the data blocks are linked with each other, and all data directory blocks are linked with each other. For each type (data block, and data directory) a used list per database and a unified free list is maintain. Whenever, any NVRAM operation for allocation is done, a free list entry if available is used or new one allocated and added to used list. The reverse of the same is achieved during FREE/Release operation.

UNDO (meta) field records the operation that causes modification on NVRAM, and then records the location of the blocks along with their current state values. Once recorded, the operation is performed. On successful completion of operation UNDO(meta) entry for this operation is reset/deleted. In case before success a crash occurs, this UNDO(meta) is used for recovery of the NVRAM.

In one implementation, a reference of the database engaged which performing the operation is traced using the hint (as multiple database schema can exist in same memory area), which makes this NVRAM allocator logic DB aware.

It may be noted by the person skilled in the art that, for de-allocation, the exact opposite steps as explained above in figure 3 are performed. The details and/or repetition of the same are not explained to avoid complexity and diversion from the essential feature of the present invention.

Figure 4 illustrates a flowchart for recovery from crash in NVRAM, in accordance with an embodiment of the present subject matter. The method may be described in the general context of computer executable instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, functions, etc., that perform particular functions or implement particular abstract data types. The method may also be practiced in a distributed computing environment where functions are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, computer executable instructions may be located in both local and remote computer storage media, including memory storage devices.

The order in which the method is described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the method or alternate methods. Additionally, individual blocks may be deleted from the method without departing from the protection scope of the subject matter described herein. Furthermore, the method can be implemented in any suitable hardware, software, firmware, or combination thereof. However, for ease of explanation, in the embodiments described below, the method may be considered to be implemented in the below described apparatus 500.

In one implementation, a method to recover from crash using a non-volatile random-access memory (NVRAM) is disclosed. The method comprises:
• detecting an occurrence of the crash by the non-volatile random-access memory (NVRAM), the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion;
• generating at least a hint associated with the occurrence detected;
• updating at least a recovery thread with at least an operation in progress at the time of the generation of the hint;
• backtracking the operation into at least a database; and
• recovering the data from at least a block allocated for the operation backtracked from the database.

In one implementation, the hint comprises at least information associated with the occurrence detected, and the information is at least a database identification of the database during the access of which the crash occurred, a logical address of a block in the database or a status of a database operation or any combination thereof.

In one implementation, the method detects at least an operation in progress at the time of the crash is completed. If the operation is not completed, undo the block operation using the logical address of the block in the database, and recover the operation. If the operation is completed, read undo on the database.

In one implementation, the NVRAM is characterized in that the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion. The header portion is configured to store a complete meta-data for the NVRAM and at least a state for an internal memory organization of the NVRAM. The undo information portion comprises memory area or file storage to store the undo information of NVRAM operations, preferably an ALLOC operation and/or a FREE operation. The undo record portion comprises a memory area to store the undo record from the database operation, preferably an insert operation and/or update operation and/or a delete operation. The data directory portion is configured to store a list of memory block descriptors associated with the data portion. The data portion comprises a memory area configured to allocate at least one block in dynamic sizes and/or present the data to a user on a request.

In one implementation, a method is disclosed. The method comprises:
• detecting at least a change in a non-volatile random-access memory (NVRAM), the change is the writing of data to and/or reading of data from the NVRAM ;
• generating at least a hint associated with the change detected;
• updating at least a recovery thread with at least an operation in progress at the time of the generation of the hint;
• backtracking the operation into at least a database;
• recovering the data from at least a block allocated for the operation backtracked from the database.

In one implementation, the hint generated is stored in the NVRAM, wherein the hint generated is written first and thereafter an allocation of and/or a de-allocation of a block is performed.

In one implementation, the hint generated is re-used in the NVRAM for at least a subsequent write operation.

In one implementation, a method for performing an operation, preferably an allocation or free operation, using a non-volatile random-access memory (NVRAM) is disclosed. The method comprises:
• receiving the operation by non-volatile random-access memory (NVRAM), the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion;
• identifying at least one block having a free space and/or allocated for the operation based on the data portion;
• generating at least one hint containing at least an information associated with the block identified;
• storing the hint generated in the data directory portion; and thereby
• performing the operation in non-volatile random-access memory (NVRAM).

In one implementation, the information associated with the block identified comprises at least a logical address of the block identified or a previous/next entry in a free list or a previous entry in a used block list or a database operation or database identification or any combination thereof.

In one implementation, the block identified is stored in the used block list.

In one implementation, at least a start address of the block identified is provided to at least a top level database operation.

In one implementation, at least one database is tracing backed based on at least the operation received.

In one implementation, as shown in figure 4, when NVRAM is recovering from a crash occurred, a hint stored in the NVRAM is read. If the hint is complete a database, a block, a type of operation performed/performing, status of operation complete/incomplete, is determined. If the block operation is completed or if the hint is not complete, the present invention read undo of each database and proceed for recovery.

In one implementation, if the block operation is not completed, the present invention undoes the block operation and proceeds to recover the operation that wanted to change the memory layout or change in the NVRAM.

Figure 5 illustrates an apparatus implementing the present invention, in accordance with an embodiment of the present subject matter. Although the present subject matter is explained considering that the present invention is implemented in using the apparatus 500, it may be understood that the present invention may also be implemented in a variety of computing systems, such as a laptop computer, a desktop computer, a notebook, a workstation, a mainframe computer, a server, a network server, and the like. It will be understood that the database system may be accessed by multiple users, or applications residing on the database system. Examples of the apparatus 500 may include, but are not limited to, a portable computer, a personal digital assistant, a handheld device, sensors, routers, gateways and a workstation. The apparatus 500 are communicatively coupled to each other and/or other devices or a nodes or apparatuses to form a network (not shown). Examples of the apparatus 500 may include, but are not limited to, a portable computer, a personal digital assistant, a handheld device, sensors, routers, gateways and a workstation. The apparatus 500 are communicatively coupled to each other and/or other devices or a nodes or apparatuses to form a network (not shown).

In one implementation, the network (not shown) may be a wireless network, a wired network or a combination thereof. The network can be implemented as one of the different types of networks, such as GSM, CDMA, LTE, UMTS, intranet, local area network (LAN), wide area network (WAN), the internet, and the like. The network may either be a dedicated network or a shared network. The shared network represents an association of the different types of networks that use a variety of protocols, for example, Hypertext Transfer Protocol (HTTP), Transmission Control Protocol/Internet Protocol (TCP/IP), Wireless Application Protocol (WAP), and the like, to communicate with one another. Further the network may include a variety of network devices, including routers, bridges, servers, computing devices, storage devices, and the like.

The apparatus 500 may include a processor 502, an interface 504, and a memory 506. The at least one processor 502 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the at least one processor is configured to fetch and execute computer-readable instructions or modules stored in the memory.

The interface (I/O interface) for example, 504 may include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like. The I/O interface may allow the database system, the first node, the second node, and the third node to interact with a user directly. Further, the I/O interface may enable the federated system 1300 and/or the device 1400 to communicate with other devices or nodes, computing devices, such as web servers and external data servers (not shown). The I/O interface can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, GSM, CDMA, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. The I/O interface may include one or more ports for connecting a number of devices to one another or to another server. The I/O interface may provide interaction between the user and database system, the first node, the second node, and the third node via, a screen provided for the interface.

The memory 506 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. The memory may include plurality of instructions or modules or applications to perform various functionalities. The memory includes routines, programs, objects, components, data structures, etc., which perform particular tasks or implement particular abstract data types.

In one implementation, as shown in figure 5, an apparatus 500 is disclosed. The apparatus comprises a processor 502 configured to control the writing of data to and reading of data from a non-volatile random-access memory (NVRAM) 506, the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion.

In one implementation, the NVRAM is characterized in that the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion. The header portion is configured to store a complete meta-data for the NVRAM and at least a state for an internal memory organization of the NVRAM. The undo information portion comprises memory area or file storage to store the undo information of NVRAM operations, preferably an ALLOC operation and/or a FREE operation. The undo record portion comprises a memory area to store the undo record from the database operation, preferably an insert operation and/or update operation and/or a delete operation. The data directory portion is configured to store a list of memory block descriptors associated with the data portion. The data portion comprises a memory area configured to allocate at least one block in dynamic sizes and/or present the data to a user on a request.

In one implementation, an apparatus 500 to recover from crash using a non-volatile random-access memory (NVRAM) 500 is disclosed. The apparatus 500 comprises a processor 502, coupled to the NVRAM 506, for executing a plurality of modules present in the NVRAM 506, the processor 502 on execution of the modules. The processor 502 is configured to detect 506, 508 an occurrence of the crash by the non-volatile random-access memory (NVRAM), the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion, generate 510 at least a hint associated with the occurrence detected, update at least a recovery thread with at least an operation in progress at the time of the generation of the hint, backtrack the operation into at least a database stored in NVRAM or stored remotely; and recover the data from at least a block allocated for the operation backtracked from the database.

In one implementation, the hint comprises at least information associated with the occurrence detected. The information is at least a database identification of the database during the access of which the crash occurred, or a logical address of a block in the database or a status of a database operation or any combination thereof.

In one implementation, the apparatus 500 detects at least an operation in progress at the time of the crash is completed. If the operation is not completed, undo the block operation using the logical address of the block in the database, and recover the operation. If the operation is completed, the present invention read undo on the database.

In one implementation, the NVRAM is characterized in that the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion. The header portion is configured to store a complete meta-data for the NVRAM and at least a state for an internal memory organization of the NVRAM. The undo information portion comprises memory area or file storage to store the undo information of NVRAM operations, preferably an ALLOC operation and/or a FREE operation. The undo record portion comprises a memory area to store the undo record from the database operation, preferably an insert operation and/or update operation and/or a delete operation. The data directory portion is configured to store a list of memory block descriptors associated with the data portion. The data portion comprises a memory area configured to allocate at least one block in dynamic sizes and/or present the data to a user on a request.

In one implementation, an apparatus 500 is disclosed. The apparatus 500 comprises a processor 502, coupled to a non-volatile random-access memory (NVRAM) 506, for executing a plurality of modules present in the NVRAM, the processor on execution of the modules. The processor 502 is configured to detect at least a change in a non-volatile random-access memory (NVRAM), the change is the writing of data to and/or reading of data from the NVRAM; generate at least a hint associated with the change detected; update at least a recovery thread with at least an operation in progress at the time of the generation of the hint, backtrack the operation into at least a database, recover the data from at least a block allocated for the operation backtracked from the database.

In one implementation, the apparatus 500 store the hint generated in the NVRAM, wherein the hint generated is written first and thereafter an allocation of and/or a de-allocation of a block is performed.

In one implementation, an apparatus 500 is disclosed. The apparatus comprises a processor 502, coupled to a non-volatile random-access memory (NVRAM) 506, for executing a plurality of modules present in the NVRAM, the processor on execution of the modules. The processor 506 is configured to receive 508 the operation by non-volatile random-access memory (NVRAM), the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion, identify 510 at least one block having a free space and/or allocated for the operation based on the data portion; generate 512 at least one hint containing at least an information associated with the block identified; store 514 the hint generated in the data directory portion, and thereby perform 516 the operation in non-volatile random-access memory (NVRAM).

In one implementation, the information associated with the block identified comprises at least a logical address of the block identified or a previous/next entry in a free list or a previous entry in a used block list or a database operation or database identification or any combination thereof.

In one implementation, an apparatus 500 is disclosed. The apparatus comprises a processor 502, a memory 506 to store data from and retrieve data to at least one host to which the apparatus is connected, and a controller (not shown). The controller is configured to manage the transfer of the data between the memory and the host. The controller comprises a non-volatile random-access memory (NVRAM), the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion.

In one implementation, the NVRAM is characterized in that the NVRAM is logically divided into memory blocks of predetermined size, wherein each of the memory blocks comprises a header portion, an undo information portion, an undo record portion, a data directory portion, and a data portion. The header portion is configured to store a complete meta-data for the NVRAM and at least a state for an internal memory organization of the NVRAM. The undo information portion comprises memory area or file storage to store the undo information of NVRAM operations, preferably an ALLOC operation and/or a FREE operation. The undo record portion comprises a memory area to store the undo record from the database operation, preferably an insert operation and/or update operation and/or a delete operation. The data directory portion is configured to store a list of memory block descriptors associated with the data portion. The data portion comprises a memory area configured to allocate atleast one block in dynamic sizes and/or present the data to a user on a request.

Apart from what is disclosed above, the present invention has some additional advantages as provided below by:
• providing method to reduce the crash recovery time for NVRAM based databases, and increase its availability;
• providing a method to track back the NVRAM memory manager changes to the database operation which caused the crash;
• providing a method that uses a mechanism to track the pages which were under change during the database shutdown process;
• providing a method that uses the tracked page list to check the sanity of the corresponding pages.

A person skilled in the art may understand that any known or new algorithms by be used for the implementation of the present invention. However, it is to be noted that, the present invention provides a method to be used during back up operation to achieve the above mentioned benefits and technical advancement irrespective of using any known or new algorithms.

A person of ordinary skill in the art may be aware that in combination with the examples described in the embodiments disclosed in this specification, units and algorithm steps may be implemented by electronic hardware, or a combination of computer software and electronic hardware. Whether the functions are performed by hardware or software depends on the particular applications and design constraint conditions of the technical solution. A person skilled in the art may use different methods to implement the described functions for each particular application, but it should not be considered that the implementation goes beyond the scope of the present invention.

It may be clearly understood by a person skilled in the art that for the purpose of convenient and brief description, for a detailed working process of the foregoing system, apparatus, and unit, reference may be made to a corresponding process in the foregoing method embodiments, and details are not described herein again.

In the several embodiments provided in the present application, it should be understood that the disclosed system, apparatus, and method may be implemented in other manners. For example, the described apparatus embodiment is merely exemplary. For example, the unit division is merely logical function division and may be other division in actual implementation. For example, a plurality of units or components may be combined or integrated into another system, or some features may be ignored or not performed. In addition, the displayed or discussed mutual couplings or direct couplings or communication connections may be implemented through some interfaces. The indirect couplings or communication connections between the apparatuses or units may be implemented in electronic, mechanical, or other forms.

When the functions are implemented in a form of a software functional unit and sold or used as an independent product, the functions may be stored in a computer-readable storage medium. Based on such an understanding, the technical solutions of the present invention essentially, or the part contributing to the prior art, or a part of the technical solutions may be implemented in a form of a software product. The computer software product is stored in a storage medium, and includes several instructions for instructing a computer device (which may be a personal computer, a server, or a network device) to perform all or a part of the steps of the methods described in the embodiment of the present invention. The foregoing storage medium includes: any medium that can store program code, such as a USB flash drive, a removable hard disk, a read-only memory (Read-Only Memory, ROM), a random access memory (Random Access Memory, RAM), a magnetic disk, or an optical disc.

Although implementations for apparatus and method for recovery in nonvolatile memory based databases have been described in language specific to structural features and/or methods, it is to be understood that the appended claims are not necessarily limited to the specific features or methods described. Rather, the specific features and methods are disclosed as examples of implementations of the apparatus and methods for recovery in nonvolatile memory based databases.