Description

FLASH MEMORY STORING SYSTEM FOR DATABASE SYSTEM AND METHOD THEREFOR

Technical Field

[1] The invention relates to a method and system for using flash memory as a storing system in database system. More specifically, the invention relates to a flash memory storing system for providing an interface between the database system and the flash memory so as to use the flash memory as a storing device in the database system. Background Art

[2] Flash memory is a semiconductor device using fowler-nordheim tunneling or hot electron injection, which is insensitive to a shock and a non- volatile memory device that keeps the stored information without power supply.

[3] There are two types of flash memory; NOR type and NAND type. Since the flash memory of the NOR type has the cells for storing data in a parallel structure, the integration is not high, but the random access is possible. That is, since there exist data lines and address lines in parallel such that a byte programming is possible, it is widely used for storing codes. On the contrary, the flash memory of the NAND type has a high integration since the flash memory of the NAND type has the cells in a serial structure, but it should select a corresponding block before reading operation and its reading speed is relatively slow because the operation resistance is large. Therefore, the flash memory of the NANT type is usually used for storing data.

[4] If such a flash memory wants to write or program a new data at a location where an old data is stored already, it must erase the old data before writing the new data. This erasing operation cannot be performed on the location storing the old data only, but it can erases in the unit of a sector, block, or page, which is determined by hardware. The erasing unit is determined by the manufacturer of memory. In general, the writing operation of the flash memory is to change the bits of the corresponding region to "0", and the erasing operation is to change all the bits in the unit region to " 1".

[5] From a point of view of data processing, a file is a set of related records, and a file system is about how to name the files and where to save the files logically for storing and searching. The file is located in a directory or a subdirectory of a hierarchy structure, and the rules for naming file including the limit to file name length and the limit to file name character types are applied. Further the rules include how to set the path to the file through the directory structure. Also, the file system for the flash memory manages the file, and has the functions to write to and read the file from the flash memory.

[6] The portable communication devices such as PDA, mobile communication devices using a flash memory as storing device use a file system utilizing a data structure as an interface between a host system and the flash memory. However, as the amount of information to handle gets larger and more complicated, the file system suffers from problems such as a deterioration of a data structure standard, lack of flexibility of program and data, drop of program productivity, etc. As the portable communication devices mentioned in the above keep advancing to have more functions, the data gets complicated and diversified such that it may cause problems of the above to keep using the same file system in such an environment.

[7] If a database system is introduced to such portable communication devices, it will solve the problems of the file system. However, there are a couple of considerations in introducing the database system. The file system and the database systems have a common goal to manage data in terms of files even before speculating their utility. A device using a flash memory as a storing device used a file system that considered the hardware characteristics of flash memory for a file management and reading/writing data, but if the database system is introduced for file management, then the two systems, the flash file system and the database system, operate together for a single goal of a file management so as to waste a resource in a limited embedded resources. Disclosure of Invention

Technical Problem

[8] Therefore, the invention introduces a database system to the portable communication devices, but the database system is responsible for a file management function and the flash memory storing system having a flash interface designed considering the characteristics of the flash memory and the database system instead of the file system is responsible for a data input/output function.

[9] Therefore, an objective of the invention is to solve the above problems of the prior art by providing a flash memory storing system for database system, which has functions of input/output without a file management and of garbage collection for recycling of a flash memory space used by a write operation and guarantees a durability and atomicity of the database system against transaction errors or system errors.

[10] Another objective of the invention is to provide a flash memory storing system for database system, in which an interface between the database system and the flash memory is designed in a hierarchical structure, such that a change of the database system or a change of the flash memory can be applied with a change of a necessary part in the hierarchical structure, not an entire redesigning of the flash memory storing system.

[11] Still another objective of the invention is to provide a flash memory storing method using the flash memory storing system for database system. Technical Solution

[12] According to an embodiment of the present invention, a system for interfacing between a database system and a flash memory is provided, wherein the flash memory comprises a plurality of sectors which are divided in buckets of a same page and size of the database system and mapped logically, wherein each of the buckets comprises a bucket header having an identification information of each bucket and a bucket body for recording data, wherein the bucket header is a status_flag indicating a operating status of the bucket and a page_number registering a page number of data recorded in the bucket, and wherein the system comprises: a logical memory interface for processing a series of procedures for flash memory input/output on receiving commands to write, read, and delete and commands of start, end, and rollback of transaction from the database system, wherein the logical memory interface provides a bucket_use_table with columns of the number of the flash memory buckets and rows of the number of buckets in each sector for indicating status of the buckets, a bucket_page_table mapped the bucket numbers to the page_number, and a transaction_action_list for managing transaction procedures of the database system; and a physical memory interface for input/outputting the processing data of the logical memory interface to and from the flash memory by converting the logical address of the buckets which was processed in and outputted from the logical memory interface.

[13] According to the above embodiment, the logical memory interface comprises a sector_status_table indicating whether there is a writable bucket in each sector.

[14] According to the above embodiment, the bucket_use_table, the bucket_page_table, the sector_status_table, and the trans action_action_list are provided by referring the status_flag and the page_number during the system initialization and loaded to a system memory.

[15] According to another aspect of the invention for the above objectives, a method for interfacing between a database system and a flash memory is provided, wherein the flash memory divides a plurality of sectors in buckets having a same page and size of the database system and maps logically, wherein each of the buckets comprises a bucket header having an identification information of each bucket and a bucket body for recording data, wherein the bucket header registers a status_flag indicating a operating status of the bucket and a page_number registering a page number of data recorded in the bucket, and wherein if receiving commands to write, read, and delete and commands of start, end, and rollback of transaction from the database system then the flash memory storing method processes the commands by referring the

bucket_use_table, the bucket_page_table, and the transaction_action_list and processes a series of procedures for flash memory input/output, wherein the logical memory interface provides a bucket_use_table with columns of the number of the flash memory buckets and rows of the number of buckets in each sector for indicating status of the buckets, a bucket_page_table mapped the bucket numbers to the page_number, and a transaction_action_list for managing transaction procedures of the database system, and wherein the bucket_use_table, the bucket_page_table, the sector_status_table, and the transaction_action_list are provided by referring the status_flag and the page_number and loaded to a system memory during a system initialization.

Advantageous Effects

[16] A flash memory storing system for database system according to the invention makes the input/output fast and precise, without a complicated calculation as in a flash memory file system, by dividing the flash memory into a same structure (size) as the page, an input/output unit for the database system, which is called bucket, and accepting a transaction function of the database system with a memory characteristics of the flash memory considered through managing the buckets corresponding to the page in the database system. Furthermore, the method and system according to the invention are simple in structure and fast in handling data compared to a prior art which is using two systems for a single objective of a file management in portable communication devices using database system.

[17] Furthermore, by providing a database recovery region in addition to a database storing region as in a prior art using a conventional file system, a recovering page does not have to be recorded every time during the transaction in the invention. A complete recovery is possible by managing the status_flag of the bucket_header without allocating a space only for recovery, and the cost for writing the recovery region can be reduced.

Brief Description of the Drawings

[18] Fig. 1 is a block diagram illustrating a structure of a flash memory storing system according to the invention,

[19] Fig. 2 is a diagram illustrating a structure of section of the flash memory according to the invention,

[20] Fig. 3 is a detailed diagram illustrating a sector in Fig. 2 divided into a bucket, a logical unit,

[21] Fig. 4 is a diagram illustrating a structure of a bucket-header of a bucket in Fig. 3,

[22] Fig. 5 is a diagram illustrating a bucket_use_table which mapped the flash memory into a logical table according to the invention,

[23] Fig. 6 is a flowchart illustrating the status change of the bucket according to the

invention,

[24] Fig. 7 is a diagram illustrating a sector_status_table indicating a sector's status according to the invention,

[25] Fig. 8 is a diagram illustrating a structure of a bucket_page_table which mapped a bucket number to a page number according to the invention,

[26] Fig. 9 is a diagram illustrating a structure of a status_flag of the bucket-header in

Fi.g 4,

[27] Fig. 10 is a diagram illustrating an example of a transaction_action_list,

[28] Fig. 11 is a flowchart illustrating a process to form a node of the transaction_action_list according to the invention,

[29] Fig. 12 is a flowchart illustrating a first stage process of a transaction commit according to the invention,

[30] Fig. 13 is a flowchart illustrating a second stage process of a transaction commit according to the invention,

[31] Fig. 14 is a flowchart illustrating a transaction rollback process according to the invention,

[32] Fig. 15 is a flowchart illustrating a transaction checkpoint rollback process according to the invention,

[33] Fig. 16 is a flowchart illustrating a garbage collection process according to the invention,

[34] Fig. 17 is a diagram illustrating procedures of the garbage collection in order of occurrence according to the invention, and

[35] Fig. 18 is a flowchart illustrating a restart recovery process according to the invention. Best Mode for Carrying Out the Invention

[36] Embodiments of the invention are explained in detail in reference to the drawings.

[37] Fig. 1 is a block diagram illustrating a structure of a flash memory storing system according to the invention, Fig. 2 is a diagram illustrating a structure of section of the flash memory according to the invention, Fig. 3 is a detailed diagram illustrating a sector in Fig. 2 divided into a bucket, a logical unit, Fig. 4 is a diagram illustrating a structure of a bucket-header of a bucket in Fig. 3, Fig. 5 is a diagram illustrating a bucket_use_table which mapped the flash memory into a logical table according to the invention, Fig. 6 is a flowchart illustrating the status change of the bucket according to the invention, Fig. 7 is a diagram illustrating a sector_status_table indicating a sector's status according to the invention, Fig. 8 is a diagram illustrating a structure of a bucket_page_table which mapped a bucket number to a page number according to the invention, and Fig. 9 is a diagram illustrating a structure of a status_flag of the bucket-

header in Fi.g 4.

[38] As shown in Fig. 1, a flash memory storing system (1) of the invention comprises a memory interface (10) for interfacing a database system (20) and a flash memory (30). The memory interface (10) comprises a hierarchical structure comprising a logical memory interface (12) and a physical memory interface (14). The logical memory interface (12) receives and performs commands to write, read, and delete and commands of start, end, and rollback of transaction from the database system (20), and processes a series of procedures for input/outputting according to the characteristics of the flash memory (30) and the database system (20). On the other hand, the physical memory interface (14) converts a bucket processed with a logical address in the logical memory interface (12) to a physical address of the flash memory, and input/outputs directly with the flash memory (30). Most of the operation is performed by the logical memory interface (12) in the invention, and the physical memory interface (14) interfaces directly with the flash memory (30) according to the results processed by the logical memory interface (12). Therefore, the structure and operation of the logical memory interface (12) are explained in detail below. Also, the flash memory (30) of the NOR type and the NAND type can be used, but the explanation is for an example using the NOR type.

[39] A database system (20) using the flash memory (30) as a storing system interfaces by dividing a single large database file structure into small file units (for example, 4KB), which is called a page. The first four bytes of the page are processed as a dummy value. The flash memory (30) is divided into sectors (32), a physical unit, as shown in Fig. 2, and a plurality of sectors (32) forms a flash memory (30). For example, if the size of the flash memory (30) is 1MB and the size of a sector (32) is 64KB, then the flash memory (30) comprises 16 sectors (32). For an efficient management of the flash memory (30) in the invention, each sector (32) is logically divided into fixed buckets (34) (4KB each) of a same size as a page of the database system as shown in Fig. 3. And, each bucket (34) comprises a bucket_header (4 bytes) (36) indicating an identification information of bucket (34) and a bucket_body (4KB-4 bytes) (38) for writing data. Since the size of a sector (32) is 64KB, there exist 16 buckets (34) in a bucket (32). Each bucket (32) means a space in the flash memory (30) for storing the contents of each page of the database system (20), and one page is mapped into a bucket (34). The bucket_header (12) corresponding to meaningless first four bytes of page of the database system (20) comprises meaningful values including a status_flag (36') and a page_number (36") by the logical memory interface (12) as shown in Fig. 4. The status_flag (36') indicates the status of a bucket (34) changing with transaction, and the page_number (36") indicates which page's contents the bucket (34) stores.

[40] The logical memory interface (12) comprises a bucket_use_table (TbI) for managing the usage status of the buckets (34) as shown in Fig. 5. The table (TbI) comprises rows of the number of the sectors (32) and columns of the number of buckets (34) in each sector (32). The value of entry <m,n> of the bucket_use_table (TbI) indicates the usage status of the bucket n of the sector m. The value for the bucket entry is one of 'initialized' , 'allocated', 'deallocated', etc. shown in Fig. 6. For example, as shown in Fig. 6, the bucket entry value is 'initialized' (StI) when a sector (32) including a bucket (34) is deleted by a sector erase operation of the garbage collector, 'allocated' (St2) when the bucket (34) is allocated to a specific page of the database system (20), and 'deallocated' (St3) when the bucket (34) is deallocated from a specific page. In Fig. 6, the values other than 'initialized' (StI), 'allocated' (St2), and 'deallocated' (St3) indicate values for transient status during a transaction, and the state changes of the bucket (34) according to the transaction will be explained in detail in reference to Fig. 6 later. Especially, the bucket_use_table (TbI) is initialized by reading the status_flag (36') and the page_number (36") of the bucket-header (36) of all the buckets (34) of the flash memory (30) at system booting, and is deleted from the system memory at system termination. The system memory comprises a random access memory (RAM).

[41] Each sectors (32) of the flash memory (30) is allocated from the first bucket to the last bucket in order. Since the present usage status of a specific bucket (34) of a specific sector (32) is identified rapidly and easily using the bucket_use_table (TbI), it is efficient to locate a memory space for recording the changed contents of a new page or an old page of the database system (20).

[42] The logical memory interface (12) stores the bucket_number of the lastly allocated bucket (34) at a variable (for example, the last_bucket_number (LBN)) in the RAM. Therefore, in order to allocate a new bucket (34), a location with a bucket entry value of the bucket_use_table (TbI) having 'initialized' is looked for from the bucket_number of the variable LBN in order. If there does not exist a location having the bucket entry value 'initialized' to the last entry, then the search begins again from the first bucket entry. If all the bucket entries are not 'initialized', then it means 'database full', that is there is no more blank space to record to the flash memory (30).

[43] When the number of sectors (32) is H and the number of buckets (34) in a sector

(32) is W, the relationship between the bucket_number B (0 < B < HxW) and these numbers is given as equations below.

[44] (1) When the bucket_number B is given, a sector index s (0-15) and a bucket index o (0-15) are given as follows.

[45] s = BAV;

[46] o = B % W;

[47] (2) When the sector index s and the bucket index o are given, the bucket number B of the bucket is obtained by the followings.

[48] B = sxW + o;

[49] The logical memory interface (12) provides a sector_status_table (Tb2) for indicating the status of the sector (32) as shown in Fig. 7. The sector_status_table (Tb2) is created in the system memory (RAM) during the system initialization, and deleted on the system termination. In the sector_status_table (Tb2), it is in a status of 'available' if there exist more than one 'initialized' buckets in one sector, and it is in a status of 'full' if there is no 'initialized' bucket. Changing of the sector_status_table (Tb2) takes place in the following cases.

[50] (1) If the last bucket in the sector is allocated, the status of the sector is changed to a

'full' status.

[51] (2) If the sector is deleted by the garbage collector, the status of the sector is changed from 'full' to 'available'.

[52] The sector_status_table (Tb2) affects the operation of the garbage collector, explained later, by determining the number of existing 'initialized' sectors.

[53] When updating a specific page, the flash memory (30) must get a new bucket, record the corrected page in the bucket, and delete the old bucket right away or later since the flash memory (30) cannot inplace-update the corresponding bucket (34) of the page. Therefore, in order to correct an already written page P (its contents is A and its bucket is B) to a page with a new content A', it must record the corrected page (the content is A') in an 'initialized' bucket B', and process the bucket B as a 'deallocated', which is made 'initialized' at the time or later by a deleting operation of sector.

[54] Since referring a page in the database system (20) and the logical memory interface

(12) is performed with the page_number of the page, when a page is changed, it is going to be too much a burden to change all the other bucket (34) having the page_number of the page. Therefore, in order to perform referring one bucket (34) in one page precisely without referring the buckets (34) one by one, the present invention provides a bucket_page_table (Tb3) which maps the bucket number to the page number as shown in Fig. 8. The bucket_page_table (Tb3) comprises entries of the total number H of sectors x the total number W of buckets in a sector, and as mentioned in the above each of the entries comprises a bucket_number (B = sxW + o) given in terms of the sector index (s) and the bucket index (o). The bucket_page_table (Tb3) is managed only in the system memory (RAM), and is provided using the status_flag (36') and the page_number (36") of the bucket-header (36) of each sector (32) in a 1MB flash memory (30) on the system booting. That is, only when the status_flag (36') of the bucket-header (36) is 'allocated' the entry of the bucket_page_table (Tb3) corresponding to the page_number (36") is set to the bucket_number (B) of the bucket

(34). Therefore, when a specific bucket (34) is allocated to a specific page_number (36") the value of the entry corresponding to the page_number (36") is set to the bucket_number (B), when the bucket (34) corresponding to the deleted specific page in the database is deleted the corresponding entry value is set to -1, and on the system termination the bucket_page_table (Tb3) is deleted from the system memory (RAM).

[55] The bucket-header (36) comprises a status_flag (36') indicating the status of a bucket (34) and a page_number (36") indicating the page corresponding to the bucket (34) as described in the above. The status_flag (36') of the bucket (34) is used for a restart recovery or a normal rebooting of the system. The status_flag (36') comprises a meaningful bit field having 16 bits as shown in Fig. 9, and each field looks as follows. That is, the bit field from 15th to 6th is meaningless, which is for later expansion. The 5' bit field means that the data becomes meaningful by a part of the commit process of a transaction. The 4th bit field means that the bucket (34) becomes a target of change or deletion. The 3 ^r bit field means that the data becomes a target of deallocation by a p art of the commit process of a transaction. The 2° bit field means that the bucket as the deallocated bucket (34) can become a target of the garbage collection. The 1 ^st bit field means that the 'initialized' bucket (34) can be allocated as a target of transaction. The 0 bit field means that it is the bucket (34) on which the transaction is done.

[56] These status_flags (36') of the bucket (34) change according to a proceeding of the transaction as shown in Fig. 6, and the meaning of each status in Fig. 6 is as follows.

[57] 1) 5bit~0bit of the initial status (StI) has a value '111111', and a new bucket can be allocated since no data has been recorded.

[58] 2) 5bit~0bit of the in_allocation_transaction (St4) has a value '111101', and it means that after a specific bucket having a initialized status (StI) is allocated the bucket neither committed nor rollbacked. The bucket may have a content of the page. This is because the bucket content can be changed after the status_flag (36') of a bucket (34) in allocation. An allocation of a new bucket (34) is performed in the folio wings cases. A first case is when allocated a new page. A second case is when the terminating transaction changes the content of the written bucket. A third case is when the present transaction changes the content of the written page.

[59] 3) 5bit~0bit of the allocation_transaction_committed (St5) has a value '011101', and it means that the bucket in the in_allocation_trans action (St4) status includes a useful data as a commit process of the transaction.

[60] 4) 5bit~0bit of the allocation_committed (St2) has a value '011100', and it means that the bucket in the allocation_transaction_committed (St5) becomes a data file once terminating the transaction since the bucket became a complete bucket (34) as a final process of the commit process of the transaction.

[61] 5) 5bit~0bit of the deallocation_transaction_ended (St6) has a value '001100', and it

means that when the present transaction change the content of a page in a bucket, created by a terminated transaction, having the status of allocation_commited (St2) the status of the bucket (34) is changed to a status of a deallocation_transaction_ended (St6). In the case of changing the content (for example, BB) of a page (for example, Pi) in a bucket (for example, Bm) in the status of allocation_commited (St2), the procedure changes the status of the bucket Bm to the status of deallocation_transaction_ended (St6), is allocated with a new bucket (for example, Bw), sets the status of the bucket Bw to in_allocation_transaction (St4), and records the content BB' of the changed page Pi to a bucket_body (38) of the bucket Bw.

[62] 6) 5bit~0bit of the deallocation_transaction_commited (St7) has a value '000100', and it is a status in which a bucket of the status of in_deallocation_trans action (St8) or deallocation_transaction_ended (St6) will be deallocated as a part of the process commit of the transaction.

[63] 7) 5bit~0bit of the deallocation_commited (St3) has a value '000000', and it means that a bucket in the status of deallocation_transaction_commited (St7) can be deallocated in a last stage of the transaction commit to participate a sector erase process.

[64] 8) 5bit~0bit of the in_deallocation_transaction (St8) has a value '101101', and it means that a bucket (34) of in_allocation_trans action (St4) allocated by a present transaction to store the content of a page changes the status of the present bucket from the in_allocation_trans action (St4) to in_deallocation_trans action (St8) when the content of the page is changed by the transaction and to be stored in the new bucket. Then, the content of the changed page is allocated with a bucket having the initial status (StI), changes the status to the in_allocation_trans action (St4), and records the content of the page to the bucket_body (38).

[65] The logical memory interface (12) manages the information related to the transaction for the transaction commit and rollback and the check point commit and rollback by providing a linked list in the order of occurrence. This is called a transaction_action_list, and Fig. 10 shows an example of the transaction_action_list, in which it is shown that the list is provided by being linked to a plurality of nodes (Ndl~Nd6). Each of the nodes of the transaction_action_list comprises <action_type, page_number, before_bucket_number, after_bucket_number> as shown in Fig. 10. An operation code for executing the above looks as follows.

[66]

[67] typedef struct tagTransactionNode

[68] {

[69] UNIT8 ActionType;

[70] UNIT 16 PageNr;

[71 ] UNIT 16 BeforeBNo; /* before bucket number */

[72] UNIT 16 AfterBNo; I* after bucket number */ [73] Struc tagTransactionNode *next;

[74] } TransactionNode; _[75]

[76] 'Actionjype' generated in and requested by a database system (20) comprises

TR_BEGIN' indicating a beginning of the transaction, 'TR-COMMIT' indicating a commit of the transaction, TR_ROLLBACK' indicating a rollback of the transaction, TR_CPBEGIN' & TR_CPCOMMIT' indicating a status's beginning (Implicit_Savepoint_Start, CheckPoint_Begin) and commit at the beginning and the ending for a durability of a status as in the start and end of the transaction, and TR_CPROLLBACK' indicating a rollback. The actionjype further comprises TR_WRITE' indicating writing a new page determined in the logical memory interface (12), TR_DELETE' indicating a deletion of a page, and TR_UPDATE' indicating changing of a page through writing on the page. There is an operation of page reading, but it is not included in the transaction_anction_list, in which when a reading request comes in, it reads in from the flash memory (30) to the database system (20) by searching the location of the bucket (34) having the page data with the requested page_number using the bucket_page_table (Tb3). Furthermore, a following method is provided for a fast response to the reading request. The method provides in the system memory (RAM) a buffer of a predetermined size and a table for finding where in the buffer the content of which page is recorded and recording the content of the page once reading-requested to the buffer, and later when a same reading-request comes in, the method reads the page content in the buffer using the table without reading the flash memory (30) directly. If the page in the buffer is changed in the flash memory (30), then the page content is erased from the buffer, because the content stored in the buffer gets different from the content written in the flash memory (30). Thereby as many page contents as the number of the deleted pages in the buffer can be recorded in the buffer for the next reading request. However, since it needs a buffer having a size of page size times n, the method has a disadvantage of requiring relatively large RAM space.

[77] The 'page_number' in the transaction_action_list indicates the page number of a page related to write, change, and delete. 'Before_bucket_number' indicates the bucket number of a bucket having data (including image data) before change of the page related to the deletion. 'After_bucket_number' indicates the bucket number of a bucket having data of a page related to change or a new data.

[78] Therefore, in performing a transaction such as an addition of a new status, a transaction commit, and a transaction rollback, in order to check a bucket status and which bucket (34) participates in the transaction, the present invention verifies and

corrects the information in the bucket_use_table (TbI) without reading the status_flag (36') of the bucket (34) and changes the status_flag (36'). Thereby, it gets rid of time and cost for reading the status_flag (36') of the bucket (34) in the flash memory (30).

[79] Fig. 11 is a flowchart illustrating a process to form a node of the transaction_action_list according to the invention, and how the node accesses the flash memory is explained referring to Fig. 11.

[80] a) Start a transaction if there is a start command from a database system (20). Here, the logical memory interface (12) does not perform any operation.

[81] b) The logical memory interface (12) forms a new node and records the requested

'page_number' to this node (SlOO) if there is a request to write or delete to the logical memory interface (12) from the database system (20).

[82] c) The operations for page change or addition coming from the database interface regardless of SQL sentence processed in the database system (20) are write and delete. Therefore, on determining whether the operation is a write or delete (S 102), the following steps are performed for write.

[83] Determine if it is a write operation or an update operation by reading an entry value of the bucket_page_table (Tb3) corresponding to the page_number of the operation command (S 104). For example, in writing the page_number Pi and the data Pd of the page, if the entry value of Pi in the bucket_page_table (Tb3) is -1, then it means that there is no effective bucket with the same page_number in the flash memory (30), and therefore it is a write of a new page, and the actionjype becomes TR_WRITE (S 106). Otherwise, if the entry value is not -1 in step S 104, then it is a page update, and the actionjype in the page update becomes TR_UPDATE (S 108).

[84] On the other hand, if a delete command, not a write command, is requested from the database system (20) in step S 102, it determines to be a page delete, and the action_type becomes TR_DELETE (SI lO).

[85] d) The update and delete operations register the bucket_number of the bucket (34) storing the page, the entry value corresponding to the requested page_number of the bucket_page_table (Tb3), to the 'before_bucket_number' of the node (S 112), read the status_flag (36') of the bucket from the bucket_use_table (TbI), and determine (Sl 14) if the allocation is complete (S80). Here, if complete, the values of the status_flag (36') and the bucket_use_table (TbI) of the bucket is updated to the deallocation_transaction_ended (St6) (Sl 16), and otherwise if it is in the in_allocation_transaction (St4), the values of the status_flag (36') and the bucket_use_table (TbI) of the bucket (34) is updated to the in_deallocation_trans action (St8) (Sl 18). Here, updating the values of the status_flag (36') as well as the bucket_use_table (TbI) is for recovering the database in case that it cannot operate normally due to a sudden power failure and others.

[86] e) Determining whether the actionjype is TR_DELETE after steps Sl 16 and Sl 18

(S 120), if it is a delete, the request command to the logical memory interface (12) is completed. On the other hand, if the actionjype is not a delete, but a update or a write of step S 106 in step S 120, then it is allocated with an 'initialized' bucket (34), updates the entry of the bucket_use_table (TbI) and the status_flag (36') to the in_allocation_transaction, records the bucket_number of the bucket (34) to the node of transaction_action_list, and records the page data to the bucket_body (38) (S 122).

[87] Now referring to Figs. 6, 10, and 11, the procedures of creating a node and updating the status of each bucket as the transaction proceeds will be explained below. Seeing a result with a transaction_action_list generated as in Fig. 10, since data for page number Pa, Pb were generated in other terminated transaction, the values of the status_flag (36') and the bucket_use_table (TbI) are the 'allocated' (St2), and the page data of page number Pc, Pd are generated and updated by the present transaction.

[88] The transaction_action_list node NdI is generated after the start of the transaction, an action on the page number Pc from the database system (20) is requested to the logical memory interface (12), and accordingly the page number is recorded in the page_number of a newly generated node (SlOO). Since the actionjype is a write, step S 102 proceeds to step S 104, and the 'actionjype' of the node is TR_WRITE because the entry value for the page number of the bucket_pagejable (Tb3) in step S 104 is -1 (S 106). As a result, the transaction allocates a new bucket (34) by the bucket_usejable (TbI), records the bucket_number 2 to 'after J3ucket_number', and updates the bucket_usejable (TbI) and the status Jlag (36'), and records. And then, the transaction records the page data to the bucket (34) (S 122).

[89] A node Nd2 is generated in a same way as that that for the node NdI, appended behind the first node NdI, and recorded in the allocated bucket (34).

[90] A node Nd3 is an update of a page having a page number Pc. The page number Pc is recorded in the 'page_number' by generating a node (SlOO), and since the action (command) is a write and the entry value of the bucket_page Jable (Tb3) is 2 the actionjype is determined TRJJPDATE (S 102, S 104, S 108). Then, since the actionjype is an update, the bucket number 2, the entry value Pb of the bucket_page Jable (Tb3) is recorded in the 'before J3ucket_number' (Sl 12), and since the bucket_use Jable (TbI) of the bucket (34) is the in_allocationjransaction (St4), the values of the status Jlag (36') and the bucket_use Jable (TbI) are updated to the in_deallocationjransaction (St8) and recorded (Sl 18). In order to record the updated page data, a bucket (for example, bucket_numer 4) gets allocated, the bucket_number is recorded in 'after J3ucket_number', and the entry values of the status Jlag (36') and the bucket_use Jable (TbI) are updated to in_allocationjransaction (St4) and recorded. Also, the entry value corresponding to the page number Pb of the

bucket_page_table (TbI) is updated to the newly allocated bucket number 4, the generated node Nd3 is appended behind the node Nd2, and the updated page data is recorded in the bucket 4 (34) (S 122).

[91] A node Nd4 is generated to guarantee the durability of one status when the database system (20) gives a Check Point starting command, and appended behind the node Nd3 with the actionjype of the node set as TR_CPBEGIN. This action does not include an action to a real flash memory, but on receiving a check point rollback command from the database system (20), it just guarantees for the operations performed after the node Nd4 to be recovered to the point before the check point stored in the logical memory interface (12).

[92] A node Nd5 is generated after the check point. The page number Pa of the action is recorded in the 'page_number' (SlOO), the action type is a write, and since the entry value of the bucket_page_table (Tb3) is 0, the 'actionjype' is determined TRJJPDATE (S 102, S 104, S 108). Accordingly, the 'before_bucket_number' is recorded with the bucket number 0 (Sl 12), and since the bucket_use_table (TbI) of the bucket is 'allocated' (St2), the values of the status_flag (36') and the bucket_use_table (TbI) are updated to the deallocation_transaction_ended (St6) (S 116). And, in order to record the updated page data, a bucket (for example, bucket_numer 5) gets allocated, the bucket_number is recorded in 'after_bucket_number', and the entry values of the status_flag (36') and the bucket_use_table (TbI) are updated to in_allocation_transaction (St4) and recorded. Also, the entry value corresponding to the page number Pb of the bucket_page_table (TbI) is updated to the newly allocated bucket number 5, the generated node Nd5 is appended behind the node Nd4, and the updated page data is recorded in the bucket 5 (34) (S 122).

[93] In an operation, a check point commit or rollback command is delivered to the logical memory interface (12) at an arbitrary time point after the node Nd4 when the database system (20) determines. However, the check point commit or the rollback is not reflected on the transaction_action_list. Especially, the check point commit does not incur any operation, and the check point rollback operation returns the state to before the check point, which will be explained in detail later.

[94] A node Nd6 is generated performing a deletion command for a page data of the page number Pb. The page number Pb of the action is recorded in the 'page_number' (SlOO), and since the action type is a delete the 'actionjype' is determined TR_DELETE (S 102, SI lO). Since the entry value of the bucket_pagejable (Tb3) is 1, the 'before J3ucket_number' is recorded with the bucket number 1 (Sl 12), and since the bucket_usejable (TbI) of the bucket is 'allocated' (St2), the values of the status Jlag (36') and the bucket_usejable (TbI) are updated to the deallocation Jransaction_ended (St6) according to Fig. 6 (Sl 14, Sl 16). And, the

generated node Nd6 is appended behind the node Nd5.

[95] The commit and rollback of transaction and the commit and rollback of the check point from the database system (20) during the transaction are processed in order of the following explanation.

[96] Fig. 12 is a flowchart illustrating a first stage process of a transaction commit according to the invention, and Fig. 13 is a flowchart illustrating a second stage process of a transaction commit according to the invention. The commit operation of the transaction will be explained in reference to the two figures.

[97] The transacion commit proceeds with the following two steps. The first step, as shown in Fig. 12, updates the entry values of the status_flag (36') and the bucket_use_table (TbI) of the bucket in the 'before_bucket_number' of TR_UPDATE and TR_DELETE according to the 'actionjype' from the first node to the last node of the transaction_action_list (S200, S202). On the other hand, the entry value of the in the bucket_use_table (TbI) of the bucket number in the 'after_bucket_number' of TR_WRITE and TRJJPDATE according to the 'action_type', if it is the in_allocation_transaction (St4), is updated to the allocation_transaction_committed (St5) (S206, S208), and otherwise updated to the deallocation_transaction_committed (St7) (S210).

[98] In the second step as shown in Fig. 13, classifying from the first node to the last node of the transaction_action_list according to the 'actionjype' the action type TRJJPDATE and TRJOELETE updates the entry values of the status _flag (36') and the bucket_use Jable (TbI) of the bucket in the 'beforej3ucket_number' to the 'deallocated' (St3) (S230, S232). On the other hand, when the 'actionjype' in step S230 is a deallocation commit of step S232 in TRJJPDATE or TR JWRITE, if it is the allocation Jransaction_committed in determining whether the entry value of the bucket_use Jable of the bucket (34) in the 'after J3ucket_number' is the allocationjransaction_committed (St5) (S236), the bucket_usejable (TbI) and the statusjlag is updated to the 'allocated' (St2) (S238), and otherwise updated to the 'deallocated' (St3) (S240).

[99] In an embodiment, if a transaction commit is requested after the last node of the transaction_action Jist of Fig. 10, since the bucket 2 of the node NdI is in the in_deallocationjransaction (St8) by the node Nd3, the process become the deallocation Jransaction_committed (St7) through steps S200 and S202 of Fig. 12 (S200, S202). The bucket 3 of the next node Nd2 becomes the allocationjransaction_committed (St5) through step S200 and S206 in order (S200, S206, S208). The status of the bucket 2 of the next node Nd3 is kept as it was since it is already the deallocationjransaction_commited (St7), and the bucket 4 becomes the allocationjransaction_committed (St5) through steps S206, S208 in Fig. 12. Also, the

bucket 0 of the node Nd5 becomes the deallocation_transaction_committed (St7) through step S202 in Fig. 12, and the bucket 5 becomesthe allocation_transaction_committed (St5) through steps S206, S208 in Fig. 12. The bucket 1 of the node Nd6 becomes the deallocation_transaction_committed (St7) through step S202 in Fig. 12.

[100] As the second step of the transaction commit, the bucket 2 of the first node NdI of the transaction of Fig. 10 becomes 'deallocated' (St3) through steps S230, S236, S240 of Fig. 13, and the bucket 3 of the next node Nd2 becomes 'allocated' (St2) through steps S236, S238 of Fig. 13. Also, the bucket 2 of the next node Nd3 became 'deallocated' (St3) already in the node NdI, and the bucket 4 becomes 'allocated' (St2) through steps S236, S238 of Fig. 13. The bucket 0 of the next node Nd5 becomes 'deallocated' (St3) through step S232 of Fig. 13, and the bucket 5 becomes 'allocated' (St2) through steps S236, S238 of Fig. 13. The bucket 1 of the next node Nd6 becomes 'deallocated' (St3) through step S232 of Fig. 13. Therefore, as a result of the transaction commit of the transaction_action_list in Fig. 10, the bucket status of the bucket 0 is 'deallocated' (St3), the bucket 1 'deallocated' (St3), the bucket 2 'deallocated' (St3), the bucket 3 'allocated' (St2), the bucket 4 'allocated' (St2), and the bucket 5 'allocated' (St2).

[101] Fig. 14 is a flowchart illustrating a transaction rollback process according to the invention, where the transaction rollback is an operation to return the state to before the transaction occurs, which is explained in detail below.

[102] The process comprises: classifying the first node to the last node of the transaction_action_list according to the 'actionjype' (S300); updating the entry values of the status_flag and the bucket_use_table of the bucket in the 'after_bucket_number' to 'deallocated' in case of TR_WRITE and TRJJPDATE (S302); and making a target of the sector erase by making an object for the garbage collection. And, among the buckets located in the before_bucket_number of TR_UPDATE and TR_DELETE, the bucket having the deallocation_transaction_ended are copied to 'initialized' buckets, and the status_flags of the copied buckets are set as 'allocated' (S304, S306, S308). And then, the entry values of the status_flag and the bucket_use_table of the bucket in the 'before_bucket_number' are updated to 'deallocated' (S310). On the contrary, the buckets without the deallocation_transaction_ended are not copied in step S306, but proceeding directly to step S310, the status of the buckets located in the before_bucket_number are updated to 'deallocated'(S310).

[103] In an embodiment, if the transaction_action_list in Fig. 10 receives a transaction rollback command from the database system (20), the bucket 2 of the first node NdI becomes 'deallocated' (S302) as shown in Fig. 14. The bucket 3 of the next node Nd2 becomes 'deallocated' (S302), too. The bucket 4 of the next node Nd3 becomes

'deallocated' (S302), and since the bucket 2 is the 'in_deallocation_transaction' it can be made 'deallocated' which was already updated in the first node NdI. The bucket 5 of the next node Nd5 becomes 'deallocated' (S302), and since the bucket 0 is 'deallocation_transaction_ended', the bucket is copied to a newly allocated 'initialized' bucket, the status of the copied bucket is updated to 'allocated' (S306, S308), and the bucket 0, the original of the copy, is updated to 'deallocated' (S310). The bucket 1 of the next node Nd6, like the bucket 0 in before_bucket_number of the previous node Nd5, is copied to a newly allocated bucket, the status is updated to 'allocated' (S308), and the bucket 1 is updated to 'deallocated' (S310).

[104] On the other hand, since the start (node Nd4) and the end of the check point do not affect the buckets of the transaction_action_list there is no operation.

[105] Fig. 15 is a flowchart illustrating a transaction checkpoint rollback process according to the invention, where the checkpoint rollback returns the state to that before the transactions performed. And, the 'actionjype' between the check point start/ end and rollback according to a command from the database system (20) is TR_UPDATE only. The status_flag of the buckets starting from a node having the actionjype of TR_CPBEGIN in the after_bucket_number in the transaction_action_list is processed to be 'deallocated' (S330). The bucket in the before_bucket_number is copied to a newly allocated bucket (S332); the status of the bucket in the before_bucket_number is determined (S334); if the bucket in the before_bucket_number, the original to copy, is 'deallocation_transaction_ended', the status is updated to 'allocated' (S336); if 'in_ deallocationjxansaction', the status is updated to 'in_allocation_transaction' (S338). Since the bucket updated to 'in_allocation_transaction' was performed in a different status of the present transaction, the process searches the entire transaction_action_list from the first, allocates a bucket of the same bucket number as that in the 'before_bucket_number in step S332, and updates to the bucket number of the bucket which was updated to 'in_allocation_transaction' (S340). Lastly, the bucket located in the before_bucket_number is updated to 'deallocated', and the node is deleted from the transaction_action_list (S342).

[106] For example, in the transaction of Fig. 10, if TR_CPROLLBACK command is issued after the TR_CPBEGIN command of the node Nd4 and after the node Nd5, the bucket 5 becomes 'deallocated' by step S330 of Fig. 15, and since the status of the bucket 0 is the one updated in the present transaction from the result of a different transaction terminated with 'deallocation_transaction_ended', the bucket is copied to a newly allocated bucket (S332). And, the status of the copied bucket is updated to 'allocated' (S334, S336), the bucket in the before_bucket_number is updated to 'deallocated', and the node is deleted from the trans action_action_list (S338, S340,

S342).

[107] Fig. 16 is a flowchart illustrating a garbage collection process according to the invention, and Fig. 17 is a diagram illustrating procedures of the garbage collection in order of occurrence according to the invention. The bucket erase operation will be explained in reference to the figures.

[108] In a database system, a state without any transaction, a state without any input/ output in the flash memory, is called an idle state. In the flash memory, a memory region on which something was written becomes writable only after erase operation, and the erase operation can be performed in the unit of sector. Therefore, the flash memory collects the deallocated buckets during a transaction and initializes the buckets through the erase operation during an idle state, which is called a garbage collection.

[109] If there exist more deallocated buckets than a predetermined amount in a sector, the garbage collection starts in an idle state. More specifically, as shown in Fig. 16, the process includes determining if there exist the 'allocated' buckets in the remaining buckets of the sector (S400), and if exist, reading the buckets and storing the data to a buffer (S402). The process further comprises: checking the lastly allocated bucket number to copy the bucket data stored in the buffer to initialized buckets in the other sector (S404); if the location of the newly allocated bucket for copying the buckets belongs to a sector which is a target for a garbage collection, searching a location where the initialized buckets exist in the following sectors next to the sector (garbage collection target) serially in order (S406, S408); if the location of the newly allocated bucket does not belong to a target sector for a garbage collection, allocating a initialized bucket next to the lastly allocated bucket checked in step S404 (S410); copying the bucket data stored in the buffer in step S402 to the initialized buckets allocated in steps S408 or S410 and updating the corresponding entry values of the status_flag and the bucket_use_table (TbI) of the copied bucket to 'allocated' (S412); determining whether copying of the buckets stored in the buffer is completed (S414) and if not completed, going back to step S404 and keeping to copy by allocating initialized buckets of a sector which is not a target of the garbage collection and which is next to the lastly copied bucket (S404, S410, S412); and if determined by step S414 that there does not exist any more buckets to copy, deleting target sectors of the garbage collection (S416).

[110] To explain more about the erase operation with the procedures in the above referring to Fig. 17, if there exist, for example, twelve deallocated buckets in the sector 0 as shown in Fig. 17(i) and the system proceeds to an idle state, then the sector 0 becomes a target for the garbage collection. In Fig. 17(i), since there exist allocated buckets, for example the buckets having bucket_number 4, 5, 7, 8, in sector 0, the

buckets' data are stored in a buffer (S400, S402). Since the lastly allocated bucket in Fig. 17(i) is the bucket 0 of the sector 1 and thus the location of a newly allocated bucket does not belong to a target sector for a garbage collection, as shown in Fig. 17(ii), the initialized buckets next to the lastly allocated bucket, that is the buckets having bucket_number of 1, 2, 3, 4 of the sector 1, are allocated, the data in the buckets are copied to a buffer (S404, S406, S410, S412), and when copying of all the buckets in the buffer is done, as shown in Fig. 17(iii), the sector 0 is deleted and then the sector 0 having initialized buckets only is generated (S414, S416).

[I l l] Since the buckets are moved around through the erase operations, the changes are reflected by updating the bucket_use_table and the bucket_page_table which manage the usage status of the buckets.

[112] Allocating by finding initialized buckets serially is for using the regions evenly rather than using a single region over and over again since there is a limit to the number of writes in the flash memory. However, sometimes a garbage collection could not be performed since the number of the deallocated buckets is smaller than a predetermined value or the system has not been in an idle state for a long time, and therefore initialized buckets could not be formed even though there exist many deallocated buckets. In the present invention, in order to prevent this problem, if there is only one 'initialized' sector on checking a sector_status_table, a garbage collection is performed for a sector having the most deallocated buckets to obtain 'initialized' sector even though the system is not in an idle state.

[113] Especially, when the information in the RAM such as the bucket_use_table, bucket_page_table, trans action_action_list, etc. is lost due to a power loss or a power failure or an erroneous reset, the system may malfunction because there is no way to know in which operation the database system (20) was from the logical memory interface (12). For this, in the present invention, the system may be recovered by determining the possibility of recovery of each bucket (34) using the status_flag (36') of the bucket-header (36), which is called restart recovery. Fig. 18 is a flowchart illustrating a restart recovery process according to the invention, using which the restart recovery will be explained in detail.

[114] When the system is rebooted or reset, the logical memory interface (12) reads in the status_flag (36') of the bucket-header (36) of the entire flash memory (30), and determines if there are buckets having a status other than 'initialized', 'allocated', and 'deallocated' (S500, S502). If there are such buckets, the logical memory interface (12) classifies the buckets into the follow sets.

[115]

set A (termination_before) = set Al (in_allocation_trans action) U set A2

(in_deallocation_trans action) U set A3 (deallocation_transaction_ended) [116]

set B (termination_after) = set B 1 (allocation_transaction_committed) U set B2 (deallocation_transaction_committed)

[117] The above classification of buckets (34) according to the status_flag (36') as in the above is for determining if the transaction was in the process of termination or not if the transaction was performed right before the failure. The status_flag (36') of the buckets (34) showing that it was in the process of termination is 'deallocation_transaction_committed' or 'allocation_transaction_committed' as shown in Fig. 6. Therefore, as shown in Fig. 18, if the status_flag (36') read in step S502 includes allocated, deallocated, and initialized buckets, then that means that there is no bucket to recover. However, if there exist buckets having status other than allocated, deallocated, and initialized in step S502, then that means that there exist buckets to recover. Then, in order to determine where the buckets to recover reside, it is determined if the status of the bucket to recover belongs to the set A or the set B defined in the above (S504). If the bucket belongs to the set B, then the database system (20) is processing the termination, processing the buckets having 'in_allocation_transaction' and 'allocation_transaction_committed' to 'allocated', and processing the buckets having the other status to 'deallocated' (S506). On the contrary, if there is no bucket belonging to the set B but to the set A, since it is in a state of transaction or not performing the termination, 'in_allocation_transaction' and 'in_deallocation_transaction' are processed to 'deallocated', and since 'deallocation_tranaction_ended' is obtained by updating a result of the other transaction, the bucket is copied to a newly allocated bucket, the status is updated to 'allocated', and the original bucket is updated to 'deallocated' (S508).

[118] For example, if the system was reset by an unexpected error in the middle of a transaction of Fig. 10, for a normal operation of the database system (20) the buckets must be returned to the states before the transaction took place. After the reset, the status of the buckets are bucket number 0 (St6), 2 (St8), 3 (St4), 4 (St4), and 5 (St4). If the recovery according to Fig. 18 is performed, since there is no bucket belonging to the set B (termination_after), the buckets 0 and 1 having

'deallocation_transaction_ended (St6)' among the buckets belonging to the set A (termination_before) are copied to other initialized buckets, the status is updated to 'allocated', and the status of the bucket 0 and 1 is updated to 'deallocated'. And, since the other buckets 2, 3, 4, and 5 were obtained by performing the transaction, the status is updated all to 'deallocated'. Then, the bucket_use_table and the bucket_page_table must be updated accordingly. As a result, the buckets 0 and 1 are updated to 'allocated'

as before the transaction.

[119] On the other hand, the physical memory interface in the invention is in charge of the input/output function with the flash memory (30), converts the buckets processed with a logical address in the logical memory interface (12) to a physical address of the flash memory (30), and interfaces with the flash memory (30) according to the flash memory access control protocol. In the above embodiments, the invention has been explained with the NOR type, but all the explanation can be applied to the NAND type. In the NAND type, however, unlike in the NOR type, a plurality of blocks are collected to form a memory, the block comprises a plurality of pages, and the typical size of the page is 512 bytes, which can be different according to the manufacturers. Therefore, in order to apply the invention to the NAND type, it takes just to map a block to a sector and a page to a bucket. For example, in an embodiment of the invention, since the page and the bucket of the database system is 4KB, if four pages of NAND type memory are mapped to a bucket, then they can be applied in a same way. Since the direct interface between the NOR type and the NAND type flash memory (30) is well known to the public, a detailed description is omitted here. To be more specific, the type of the flash memory access control and the method of commands are suggested by the manufacturers, and the physical memory interface (14) can control the flash memory (30) according to the suggested method. Industrial Applicability

[120] The present invention can be applied to the portable communication devices such as

PDA, mobile communication device, etc. using the flash memory as a storing system, and performs a file management efficiently.

[121] The above embodiments are some embodiments out of many enabled embodiments just for helping the community of the art to understand the invention, but do not limit the scope of the invention. Therefore, the other equivalent embodiments may include various possible changes which are included in the inventive points of the invention.