KR102816588B1 - Method and data structure to evict transaction data on disk intermediately - Google Patents

Abstract

A transaction execution method is disclosed, including an evict step in which an operating system of a host writes some of the write pages among the plurality of write pages belonging to the first transaction to storage if the size of the page cache is smaller than the sizes of the plurality of write pages, and a commit step in which the operating system commits the first transaction.

Description

{Method and data structure to evict transaction data on disk intermediately}

The present invention relates to computing technology, and more particularly, to technology for executing a large-capacity transaction in which the amount of write data included in one transaction is greater than the amount of page cache.

Figure 1 illustrates the configuration of a host provided according to the prior art and one embodiment of the present invention.

The host (10) may be a computing device. The host (10) may include a memory (13), a power supply (16), a storage (17), a processing unit (18), and a communication unit (19). The power supply (16) is configured to supply operating power to the host (10). The storage unit (17) may store a program including commands that cause the processing unit (18) to execute an application (11) and/or an operating system (12). The storage unit (17) may be a non-volatile memory such as an SSD or an HDD. The processing unit (18) may be configured to execute the program to execute the application (11) and/or the operating system (12). The processing unit (18) may be, for example, an AP or a CPU. The memory (13) may be directly controlled by the operating system (12), such as a DRAM. The memory (13) may include a page cache and a shadow page cache. The communication unit (19) may be configured to drive a communication medium that transmits commands from the operating system (12) to storage (20). The communication medium may transmit a baseband communication signal or a modulated communication signal.

An application program running on a host (hereinafter, simply referred to as an 'application') can be the entity that stores data in storage (storage device) (e.g., SSD). However, the application cannot directly control the storage. Therefore, the application can write data to the storage through an operating system that can directly control the storage. The part of the operating system that handles the storage can be referred to as a file system.

If data is not stored in storage in the way the application requires, errors can occur. Transactions can be used to ensure that data is stored in storage in the way the application requires.

A transaction is a set of write data, and must satisfy properties such as atomicity, consistency, isolation between transactions, and durability in the event of a power failure. A set of write data that satisfies these properties can be called a transaction.

In some prior art, the application requires a transaction, but the operating system does not require a transaction. In this case, the application may be configured to implement the transaction in a certain way, which may be inefficient. There is a fast-running cache in the storage. When the application sends a write call for write data to the operating system, and in response, the operating system sends write data to the storage, the write data is usually stored in the cache of the storage. If the application controls the transaction, the cache of the storage may be hardly used. This is because if the write data are cached in the cache of the storage, the transaction order desired by the application may be broken. Therefore, in some prior art, in order to maintain the order of the first and second transactions, the application writes the first transaction to the cache of the storage and then flushes it to the non-volatile area of the storage, and then writes the second transaction to the cache of the storage and then flushes it to the non-volatile area of the storage. Here, flushing the data X may mean storing the data X in the non-volatile memory of the storage.

A transition includes special data called a commit block. The presence of a commit block in storage guarantees that all data of a transaction associated with the commit block in storage have been written without omission. In order to guarantee that a commit block included in a transaction is written after all other remaining blocks, conventional applications use a method in which all other remaining blocks are first written to the cache of storage and flushed, and then the commit block is written to the cache of storage and flushed.

Separate from transactions, applications use a unit called a file when storing write data in storage.

In some conventional techniques, instead of writing a transaction to the original file, a new journal file is created instead. The journal file can be stored in non-volatile memory of the storage. Then, the first transaction is written to the journal file. Only after the first transaction is completely written to the journal file, the first transaction is reflected to the original file. If a power outage occurs, only the transactions that were completely written to the journal file can be recovered.

However, according to the above-described prior art, there is a problem that the following inefficiency exists. That is, when a journal file is created, the writing data must be written once to the journal file and once to the original file in order to process it, so the usage of computing resources increases, and there is also a disadvantage in that many flush calls are made.

There are conventional techniques that solve the above-mentioned problem. The above-mentioned problem is that only the application operates the transaction, and the operating system does not support the transaction. Therefore, in the conventional technique that solves the above-mentioned problem, the operating system supports the transaction function. However, these conventional techniques also have a disadvantage. That is, the write data that the application wants to write is pinned to the memory (page cache) by the operating system. Then, when the application sends a commit call to the operating system, the operating system writes the pinned data to the memory to the storage at once. Even when writing to the storage, the operating system directly uses the transaction form. At this time, since the write data requested by the application must be pinned to the memory, the size of the transaction is limited by the size of the memory.

The present invention aims to provide a technology for solving the problem that the size of a transaction in a file system of an operating system supporting transactions is limited by the size of memory managed by the operating system.

The present invention proposes an intermediate storage device and technique for executing a large-capacity transaction. In the present invention, this may be referred to as stealing. The large-capacity transaction may mean a case where the amount of write data included in one transaction is greater than the amount of page cache.

An application can make various operation calls to the operating system. The Tx start call is a system call that indicates that the application is starting a transaction. The Write call is a system call that indicates that some data will be written to the storage in a file. The Tx end call is a system call that indicates that the transaction will be terminated.

When an application executes a write call after executing a transmission start call, the write data (pages) related to the write call are pinned in the page cache, which is the memory used by the operating system. If the write data cannot all be pinned in the page cache, that is, when the page cache is small, there is a problem in that the transaction is canceled in the prior art. Here, the prior art may mean a technology in which an operating system supporting a transaction executes a transaction.

In the present invention, during a transaction, the operating system first intermediately stores some data (some pages) of the write data stored in the page cache directly managed by the operating system in storage, which is referred to as evict or the evict phase. The blocks of the page cache where the first intermediately stored write data were recorded now become available for use. Then, the operating system pins all remaining write data requested by the application through the transaction in the page cache. Thereafter, when the send end call is called by the application, the operating system executes a command to write all data stored in the page cache to storage.

In the present invention, evict may mean selecting a specific page, writing the content stored in the specific page to storage, and making the selected specific page an empty page so that it can be used for another purpose.

After the above intermediate storage is executed, if the commit of the above transaction is completed, the intermediate storage can be considered as the final storage of the part of the write data. That is, the intermediate storage can be considered as the final storage of the part of the data (some pages) for the storage.

The above-described intermediate storage is possible because the operating system of the present invention uses a log structure file system.

The above log structure file system has a characteristic that when a certain data A recorded in storage is to be modified to A', A' is not written to the first block of the storage where A is recorded, but A' is written to another second block. And A written in the first block is invalidated at an appropriate time. The invalidation can be executed by the operating system using an invalidation command. Here, the 'block' may mean a unit storage where data is stored in the storage. A plurality of blocks can be referred to as one segment. In this way, the log structure file system has a characteristic that even if old data A already recorded in the storage is modified to new data A', the old data A remains in the storage for a predetermined period of time. This point is important to the present invention.

File mapping information, which represents the mapping relationship between some data A recorded in storage and the location of the block where said data A is stored, is stored in a file called an inode. The inode file is stored in storage and can also be temporarily stored in the page cache managed by the operating system.

A block considered valid in a segment may be referred to as a live block. A block declared to have some valid data stored therein by a given mapping information may be referred to as a live block. The process of moving data stored in all live blocks among the blocks included in a certain first segment to another second segment and then making all blocks included in the first segment usable blocks may be referred to as garbage collection. The purpose of garbage collection is to secure an empty segment.

The file system of a conventional operating system that supports transactions is not a log-structured file system. That is, according to the conventional technology, when some old data (=old page) recorded in storage is updated with new data (=new page), the old data immediately disappears from the storage.

In contrast, the present invention, which uses a log structure file system, utilizes the fact that when updating some old data recorded in storage with new data, the old data can be maintained in the storage under certain conditions.

Log-structured file systems support an operation called checkpointing. The checkpointing operation is an operation that flushes file mapping information (inodes) stored in the page cache to storage.

In this regard, file mapping information stored in the non-volatile memory of the storage can be cached in the cache of the storage, and the file mapping information stored in the cache of the storage can be cached again in the memory managed by the operating system of the host, i.e., the page cache. In order for the operating system to modify the file mapping information stored in the storage, the file mapping information stored in the storage can first be cached in the page cache.

According to one aspect of the present invention, during the execution of a transaction, if the page cache becomes saturated, some of the pages stored in the page cache, for example, page A, may be stored in the storage for an intermediate storage. That is, the page A may be evicted. At this time, the old page of page A may be recorded in the first block of the storage, and the new page of page A may be recorded in the second block of the storage. At this time, when the intermediate storage is executed, new file mapping information indicating that the new page is written in the second block may be recorded in the cache of the page cache and the storage. In this case, the old file mapping information indicating that the old page is written in the first block disappears. When a checkpoint operation is called in this state, the new file mapping information is flushed to the storage, and as a result, the old file mapping information existing in the storage disappears. Then, if a system crash (for example, a power outage) occurs before the transaction is committed, the new file mapping information recorded in the storage may be used in the recovery process after the system crash, but the old file mapping information that has already disappeared cannot be used. Therefore, even if recovery is executed, there is a problem that the previous state of the above-mentioned unfinished transaction is not restored. In order to solve this problem, the present invention introduces the following additional configuration.

According to one aspect of the present invention, when the page A is evicted, the new file mapping information regarding the page A can be pinned in the page cache until the transaction is committed. In this way, even if a checkpoint operation is called, the new file mapping information is not flushed, and thus the old file mapping information in the storage can be maintained as is until the transaction is committed.

The call to the checkpoint operation may be performed periodically by the operating system or may be made just before or after a garbage collection call.

For pages where evict has occurred as described above, invalidation of old blocks stored in storage is not performed before the transaction is committed.

<Transaction Support in Log Structure File System - exF2FS>

In this invention, we propose exF2FS, a transaction log structure file system. The proposed file system can be composed of three major components: Membership-Oriented Transaction, Stealing-Enable Transaction, and Shadow Garbage Collection.

The above membership-oriented transactions allow a transaction to span multiple files, where the application can explicitly specify which files are involved in the transaction.

The above stealing-enabled transactions allow application programs to execute transactions with a small amount of memory and encapsulate many updates (e.g., hundreds of files with a total size of tens of GB) into a single transaction.

The above shadow garbage collection allows the log-structured file system to perform garbage collection without affecting the error atomicity of ongoing transactions.

exF2FS's transaction support can be carefully tuned to meet the critical requirements of your application while minimizing code complexity and avoiding performance side effects.

Using exF2FS increases SQLite multifile transaction throughput by 24x over stock SQLite multifile transactions. Implementing compression as a filesystem transaction increases RocksDB throughput by 87%.

Modern applications often strive to protect data in a crash-consistent manner, splitting it across multiple file abstractions. Without proper transaction support from the underlying file system, application programs use complex protocols to ensure transactional updates across multiple files, generating long write sequences and fsync()s. Text editors such as vim and emacs use atomic rename() to atomically save updated files.

For transactions that update multiple database files, SQLite, a library-based embedded DBMS, maintains a separate journal file for each database file, resulting in excessive fdatasync() calls and large write amplification. The compaction operation of modern LSM-based key-value stores such as RocksDB maintains the merge-sort state in a separate journal file, known as the manifest file. To ensure failure-atomicity of the compaction operation, the key-value storage engine flushes the output files individually and flushes the global state of the compaction to the manifest file.

Transactional support in the file system allows application programs to replace multiple fsync()s for each output file and manifest file with a single file system transaction, eliminating redundant IO and rendering higher performance.

Despite the clear benefits of transaction support, challenges remain for operating systems and file systems.

Successfully deploying a transaction support system requires finding the right balance between four requirements: ease of use, code complexity, ACID support, and performance. Unfortunately, achieving one of these often comes at the expense of another. System-level support for transactions can be broadly categorized into four categories: native operating system support, kernel-level filesystems, user-level filesystems, and transactional block devices. Ideally, transactions should be supported as a first-class citizen of the operating system; however, this requires significant changes to the operating system. Transaction support in user-level filesystems utilizes a user-level DBMS to provide full ACID transactions. ACID support comes at the expense of performance. Transaction support in kernel-level filesystems can be further categorized by the degree of ACID support: full ACID semantics, ACD without isolation support, or AC without isolation and durability support. F2FS transactions support only atomicity and do not support isolation or durability.

F2FS transactions cannot span multiple files. Ironically, despite its minimal support for transactions, F2FS is the only filesystem to have successfully deployed transaction support to the public. F2FS's transaction support has a specific target application: SQLite. F2FS's atomic writes allow SQLite to implement transactions without a rollback journal file, eliminating the excessive flush overhead.

In this invention, we revisit the problem of providing file system level transaction support. In particular, we focus on log-structured file systems. Most of the prior art on transactional file systems uses journaling file systems as their underlying file systems. These prior art techniques utilize the journaling layer of the file system to provide transaction functionality. F2FS, a log-structured file system designed for flash storage, has recently become widespread on smartphone platforms and has begun to expand to cloud platforms. There is little research on transaction support in log-structured file systems. Although some prior art studies have addressed transaction support in log-structured file systems, these prior art studies are limited in terms of transaction support. In addition, these prior art studies do not support multi-file transactions, transaction stealing, and conflict handling between transactions and garbage collection.

In this paper, we present transaction support in a log-structured file system with three design goals: (i) a transaction should be able to span multiple files, including directories, (ii) a transaction should be able to handle a large number of updates, and (iii) a transaction should be immune to garbage collection operations. Each of these requirements seems trivial and essential from the perspective of an application program. Unfortunately, developing a transaction log-structured file system that satisfies these simple and trivial requirements is a non-trivial task that requires substantial changes to the underlying file system in terms of design and implementation; developing a new transaction model, redesigning the file system's page reclamation procedure, and redesigning the garbage collection procedure. Few modern transactional file systems address these essential requirements in terms of transaction management with sufficient maturity.

The present invention proposes a membership-oriented transaction model that allows transactions to span multiple files. It also proposes stealing for file system transactions to handle large transactions where a transaction may consist of hundreds of files with tens of GB of data. It also proposes shadow garbage collection to ensure that garbage collection does not interfere with ongoing transactions.

The main effects of the present invention are as follows.

First, according to the membership-oriented transaction of the present invention, the file system maintains a kernel object, a transaction file group, which specifies a set of files involved in a transaction, including a directory. Membership-oriented transactions allow applications to explicitly specify the target files of a transaction.

Second, stealing of the present invention allows dirty pages of uncommitted transactions to be evicted while ensuring the atomicity of the transaction. The present invention proposes delayed invalidation and relocation records to realize stealing in file system transactions. The delayed invalidation prevents old disk locations of evicted pages from being garbage collected until the transaction is committed. The relocation records maintain undo and redo information for aborting and committing evicted pages, respectively.

Third, by using the shadow garbage collection of the present invention, the garbage collection module can be prevented from making dirty pages of uncommitted transactions durable and recoverable early. Shadow garbage collection allows the file system to perform garbage collection transparently for ongoing transactions.

In this invention, we implement these features in F2FS. In this invention, we call this newly developed file system Extended F2FS (exF2FS). exF2FS improves SQLite performance by 24x compared to stock SQLite and reduces write volume by 1/6 compared to SQLite's PERSIST journal mode. It improves RocksDB performance by 87% on YCSB workload-A. Special care must be taken not to change the disk structure of the existing F2FS so that exF2FS can mount the existing F2FS partition.

<Multi-file Transaction>

Multi-file transactions are an essential part of modern software. Here are some examples of multi-file transaction methods in use today.

[Keeping browsing history in web browser] Chrome browser keeps user browsing activity such as visited URLs, list of downloaded files, access history for each URL, and list of most frequently visited URLs. Chrome keeps each of these in separate files and updates these files in a failure-atomic fashion. For failure-atomicity, Chrome uses SQLite to update these files, which renders excessive IO. SQLite transactions are inefficient.

[LSM-based Key-Value Storage Compression] Compression is the process of merging and sorting multiple SSTables with overlapping intervals into a sequence of non-overlapping output files. The error atomicity of the compaction operation is achieved by calling fsync() for each output file and its parent directory, and flushing the global state of the transaction to a special file called a manifest file. Under a "load" workload on YCSB, a single compaction in RocksDB can produce up to 198 output files (over 200 fsync()s) for a total of 13.3 GB.

[Software Installation] Updating or installing new software requires downloading and modifying hundreds of files and updating related directories in an atomic manner. Partial installations or updates often result in system instability.

[Mail client] MAILDIR IMAP format maintains mailboxes and messages as directories, respectively, and as files in the directories. The email client updates message files and associated directories in a transactional manner. If the underlying file system does not support transactions, the email client uses expensive atomic renames to manage mailboxes and messages in a transactional manner.

<Multi-file Transactions and SQLite>

SQLite is a widely used serverless embedded DBMS in various applications, such as mobile applications such as Android Mail and Facebook App, desktop applications such as Gmail and Apple iWork, and distributed file systems such as Lustre and Ceph. These applications use SQLite to manage updates to multiple files in a fault-atomic manner. To understand how SQLite can benefit from the transaction support of the underlying file system, we instrument the IO behavior of SQLite's multi-file transactions.

Using SQLite to persist data can make application programs simpler, but SQLite's file-backed journaling and page-granular physical logging cause significant write amplification and excessive flushing. A single insert() in SQLite causes 5 fdatasync()s along with a 40KB write(). There have been several studies to improve the extreme IO inefficiency of SQLite transactions. All of these efforts are limited to improving the IO overhead of transactions with a single database file.

SQLite constructs a multifile transaction as a collection of single-file transactions and several flushes to record the global state of the multifile transaction in a master journal file. SQLite implements a multifile transaction in four phases, as listed below. Phases 1 and 3 are for updating the master journal file. Phases 2 and 4 are for performing a series of single-file operations.

Figure 2 shows how each of these steps relates to IO operations through a physical experiment, where a transaction consists of three inserts into three different database files.

Step 1: Initialize the master journal file. SQLite records the name of the journal file in the master journal file. Then, it flushes the master journal file (S1 in Figure 2) and the updated directory to disk (S2 in Figure 2).

Step 2: Logging and Database Updates. SQLite writes the undo record to the journal file and updates the database files. Each file is updated in the same way as a single database transaction (S3 in Figure 2). There are three S3s in Figure 2, each corresponding to a single insert().

Step 3: Delete the master journal file. As a sign of a successful commit, SQLite deletes the master journal file and makes the linked directory durable (S4 in Figure 2).

Step 4: Reset the log. SQLite resets and flushes the journal file (S5 in Figure 2).

In Fig. 2, the X-axis and the Y-axis represent time and LBA, respectively. Here, the present invention explicitly specifies three areas of F2FS, namely, the metadata area, the data area of the main area, and the node area of the main area. When SQLite flushes a dirty file block through fdatasync(), the default F2FS flushes not only the data block but also the associated node block to the data area and the node area, respectively. When the master journal file (fd(mj)) is flushed in S1 of Fig. 2, two separate 4KB IOs are rendered to the disk. One is for flushing the data block and the other is for flushing the node block. The data block and the associated node block must be durable to ensure the integrity of the file system. There are three fdatasync() (S3) for each insert(). The first and second fdatasync() are for flushing the rollback journal file. The third is for flushing the database file. In S4, SQLite deletes the master journal file and maintains the parent directory. If the disconnection of the master journal file persists, the transaction is committed. In S5, SQLite resets the rollback journal file for a transaction.

As shown in Figure 2, the IO overhead of SQLite multi-file transactions is rather severe: inserting three 100-byte records results in 15 fdatasync()s and 180KB written to disk.

<Log-structured file system, F2FS and atomic writes>

The present invention uses F2FS as the basic log-structured file system. F2FS has several key design features that differentiate it from the original log-structured file system design. Among them, the two features that the present invention focuses on are the block allocation bitmap and the dual log partition layout. In order to realize stealing and shadow garbage collection, it is necessary to examine how F2FS manipulates and updates the block allocation bitmap and the two logs.

The first is the block allocation bitmap. The original log-structured filesystem design had no explicit data structure that specified whether a given block in a filesystem partition was allocated. The filesystem determines that a block in a filesystem partition is allocated if it is reachable through a file mapping. F2FS maintains a block allocation bitmap to indicate whether a given block in the filesystem is valid.

The second is the dual-log partition layout. Legacy log-structured file systems treat a file system partition as a single log. They cluster data blocks and their associated filemap1 together and flush them as a single unit. F2FS organizes a file system partition into two separate logs: the data area and the node area. F2FS places data blocks and node blocks in their associated areas, respectively. Unlike legacy log-structured file systems, F2FS writes data blocks and node blocks separately. To maintain file system integrity against system crashes, F2FS checks whether a data block is durable before its associated node block. Due to this ordering mechanism in F2FS, the block trace for a data block write appears before the block trace for a node block write in each write pair for a data block and a node block, as shown in Figure 2.

F2FS provides atomic write capability. Applications can write multiple blocks to a single file in an error-atomic manner. This feature is primarily intended to address the excessive IO overhead of single-file transactions in SQLite.

start_atomic_write(fd) ;

write(fd, block1) ;

write(fd, block2) ;

commit_atomic_write(fd) ;

For atomic writes, F2FS maintains a list of dirty pages for the inode. When a transaction updates a file block, it inserts the dirty page into the per-inode dirty page list and pins the dirty page to memory. When the transaction commits, the file system unpins the dirty page from the per-inode dirty page list and flushes the dirty page and its associated node block that holds the updated file mapping to disk. Since atomic writes pin dirty pages to memory until they are committed, by design F2FS cannot support stealing in atomic write transactions. When a transaction commits, F2FS sets the FSYNC_BIT flag in the node block. If more than one node block is flushed, the atomic write places the FSYNC_BIT flag in the last node block. F2FS sets the FSYNC_BIT flag in a node block to mark it as eligible for roll-forward recovery.

Log-structured file systems periodically checkpoint their state, including updated file mappings, updated bitmaps (F2FS only), and the disk location of the last block in each log. If the file system crashes, the recovery module recovers the state of the file system relative to the most recent checkpoint information. After rollback recovery, the recovery module scans the log from the last location and finds node blocks with FSYNC_BIT, i.e., transactions that completed successfully after the most recent checkpoint, and recovers the associated files.

The present invention defines three constraints that a transaction log structured file system must satisfy: (i) multi-file transactions, (ii) stealing, and (iii) transaction-aware garbage collection. The present invention proposes exF2FS, a transaction log structured file system that satisfies these constraints. The core technical components of exF2FS are membership-oriented transactions, stealing-enabled transactions, and shadow garbage collection. Each component is summarized below.

[Membership-oriented transaction] A transaction in F2FS cannot span multiple files because it maintains the dirty pages of the transaction in inode units. In the present invention, a new transaction model called membership-oriented transaction is developed. In a membership-oriented transaction, the file system defines a transaction file group, which is a set of files whose updates must be processed as transactions, and maintains the dirty pages of the transaction for each transaction file group. In a membership-oriented transaction, a transaction can span multiple files, and an application program can explicitly specify the files to which the transaction applies.

[Stealing-Enabled Transactions] In the case of stealing, when the file system reclaims dirty pages of uncommitted transactions, it checks the page reclamation procedure so that the page reclamation result can be undone. With stealing-enabled transactions, the proposed file system can support large transactions, such as hundreds of files containing tens of GB of data, with a small amount of memory.

[Shadow Garbage Collection] Garbage collection can make dirty pages associated with uncommitted transactions durable and can early checkpoint updated file mappings before the transaction is committed. Shadow Garbage Collection is developed to isolate garbage collection from uncommitted transactions.

<Membership-Oriented Transaction Model>

In this invention, we propose a new transaction model called membership-oriented transaction. In this model, a new kernel entity, transaction file group, is defined. The transaction file group is a set of files whose updates must be processed as a single transaction, and is composed of transaction membership (a set of inodes), a dirty page list, a relocation list, and a master commit block, as shown in Fig. 3. A hash table is used in the namespace of the transaction file group object, which is widely used to configure the namespace of kernel objects such as semaphores and pipes.

Transactional file groups allow an application to specify which files should be included in a transaction. A dirty page list is a set of dirty pages for a transaction member file. There are two separate dirty page lists in the dirty page list: a dirty data page list and a dirty node page list. A relocation list is a set of relocation records. A relocation record contains information about an evicted page (file ID, file offset, old disk location, and new disk location). A master commit block holds the disk location of the last node block for each file in the transaction membership. Using a transactional file group with a master commit block allows a transaction to span multiple files. The relocation list is used for stealing and shadow garbage collection.

<Transaction API>

An application creates a transaction file group with an explicit call. When an application creates a transaction file group, the ID of the transaction file group is returned to the application. The application can add or remove files from the transaction file group. To avoid conflicts between ongoing transactions, an application is prohibited from adding or removing files from the transaction file group of an ongoing transaction. When a transaction creates a file, the newly created file inherits membership from its parent directory, which is called membership inheritance. Membership inheritance saves files created by a transaction from transaction conflicts because newly created files are added to the transaction file group before they are made visible to the outside world. When a directory is removed from a transaction file group, the child files that inherited the membership are also removed from the transaction file group.

An application specifies the ID of a transaction file group when it starts a transaction. When a transaction starts, the file system sets a flag in the inode of the transaction member file to indicate that the file is associated with an ongoing transaction. An application specifies the ID of a transaction file group when it calls transaction commit. exF2FS provides APIs for aborting and deleting transactions. When an application requests to delete a transaction file group, if there are no ongoing transactions for the transaction file group, the transaction file group and its associated objects are deallocated. If an application requests to delete a transaction file group and there are ongoing transactions, exF2FS first aborts the transaction and then deletes the transaction file group.

In exF2FS, transactions can include directory updates such as rename(), unlink(), and create(). F2FS transactions do not support directory updates in transactions.

<Commit and Abort>

When a transaction updates a file in a transaction file group, the updated page cache entry is inserted into the list of dirty data pages in the transaction file group.

When committing a transaction, the file system prepares dirty data pages, dirty node pages, and a master commit block for the transaction commit. First, the file system inserts the dirty data pages in the dirty page list into the active data segment and obtains the disk location for each dirty data page. Second, the file system updates the associated node page with the new disk location for each data page, inserts the updated node page into the dirty node page list, and determines the disk location for each dirty node page. Third, the file system allocates a master commit block and stores the disk location of each node page in the dirty node page list of the master commit block. Then the file system sets the FSYNC_BIT flag in the master commit block.

After these steps are completed, exF2FS flushes dirty data pages, dirty node pages, and the master commit block. Only after the data blocks and node blocks are durable does the master commit block become durable. The master commit block is the core component that manipulates dirty pages from multiple files as a single multifile transaction. When the master commit block is persistent, the file system scans the relocation list and invalidates the old disk locations of the relocation records.

When a transaction is aborted, all entries in the dirty page list are deleted and the dirty page list becomes empty. If the aborted transaction has removed pages, the file mapping information is canceled to the original location based on the relocation record.

When the system crashes, the recovery module performs a rollback recovery and sets the filesystem state to the most recent checkpoint. Then, exF2FS performs a rollforward recovery. It scans the log starting from the last logging offset recorded in the checkpoint. When it encounters a master commit block, the recovery module examines it and identifies the node block disk locations of the files in the transaction. The recovery module of exF2FS then uses the rollforward recovery routine of the stock F2FS to recover the files associated with each node block. If the system crashes before the master commit block is persisted, the temporary state of the transaction held in memory is completely lost. Through this recovery mechanism, exF2FS guarantees the atomicity and durability of transactions.

<Concurrency Control and Isolation>

Since it is not a full-fledged DBMS, the present invention uses a rough file-level concurrency control. A file can belong to only one transaction file group at a time. When adding a file to a transaction file group, the application checks whether the file is already in another transaction file group. If the file is already in another transaction file group, add_tx_file_group returns an error.

In this invention, we leave isolation support up to the application, as other transactional file systems do. As a general-purpose file system, it is difficult to meet all different levels of isolation requirements simultaneously for various applications. We carefully consider that the limited support of the file system for isolation is redundant at best, unless the isolation level supported by the file system matches well with the isolation level required by the application program. Text editors, application installers, git, and compression for LSM-based key-value storage do not require isolation. SQLite and MySQL implement various levels of isolation themselves. For these applications, the limited support of the file system for isolation cannot be of much help. TxFS supports isolation for "repeatable read". It is too strong for text editors and too loose for some applications, such as SQLite's "Serializable Read". SQLite must implement "Serializable Read" isolation in its own database layer using shared locks, even when using TxFS as the underlying file system. File system support for isolation comes at a cost. Experiments show that isolation support in TxFS renders a 10% performance overhead due to the overhead of creating shadow copies of pages updated in a transaction. However, one limitation that arises due to the lack of isolation support is that other processes cannot concurrently add, delete, or rename files in directories involved in other processes' transactions. Support for concurrent directory modifications is left for future work.

Below, a stealing method within a file system transaction is described according to one aspect of the present invention.

Stealing, proposed in this invention, refers to a buffer management policy that allows dirty page eviction of uncommitted transactions. Stealing policy of DBMS and page reclamation of operating system (or file system) are different expressions of the same essential behavior, such as evicting dirty pages to disk and freeing up physical memory. These two share essential behavior but are at opposite ends of the spectrum. In case of stealing in database transaction, DBMS prevents evicted dirty pages from being visible to the outside (isolation) and undoes Steal in case of transaction abort (atomicity). When operating system reclaims file-backed dirty pages, the result of page eviction becomes visible to the outside and cannot be undone. In a journaling file system, an evicted page overwrites the old file block, and in a log-structured file system, the old file block of an evicted page becomes inaccessible due to file mapping updates.

<Stilling and Filesystem>

Stealing support in existing transactional file systems leaves significant room for improvement. TxFS, F2FS, Isotope, and Libnvmmio do not support stealing in transactions.

TxFS cannot support stealing in transactions due to a fundamental design limitation. TxFS support for transactions is built on top of EXT4 journaling. EXT4 journaling pins log blocks in memory until the journal transaction is committed. EXT4 limits the size of a journal transaction (by default 256MB). When the journal transaction size reaches the limit, the EXT4 journaling module commits the journal transaction. In EXT4, dirty pages associated with a single system call can be split across two or more journal commits. TxFS must ensure that this does not happen, as it would prematurely persist the transient state of the transaction, thereby compromising the atomicity of the transaction. To ensure atomicity, TxFS aborts the transaction if the transaction size exceeds the limit.

F2FS pins the dirty pages of a transaction in memory until they are committed. F2FS aborts all pending transactions when the dirty pages of uncommitted transactions exceed a certain threshold (by default, 15% of the total physical page frames). An example of this is illustrated in Figure 4.

Referring to Fig. 4, log blocks '1', '2', '3', '4', '5', and '6' can be pinned in memory (13). F2FS pins dirty pages of transactions in the page cache (133) in memory until they are committed. F2FS aborts all pending transactions when dirty pages of uncommitted transactions exceed a certain threshold (ex: 6 blocks as shown in Fig. 4).

The square (133) presented in Fig. 4 may mean a page cache of the memory.

CFS supports stealing. However, CFS relies on a non-existent transaction block device to support stealing.

AdvFS supports stealing with commodity hardware. AdvFS uses a writable file copy for transaction updates. When a transaction is committed, the file map is updated to reference the updated file block that was incorrectly written. This property allows AdvFS to support stealing freely. However, transactions in AdvFS can fragment files because the file system deletes old file blocks whenever a transaction is committed. The file defragmentation overhead of AdvFS is not yet known. Analysis of AdvFS is limited because AdvFS is a proprietary file system and the source code of the transaction module is not publicly available.

In Fig. 4, the page cache (133) may exist in the memory managed by the operating system of the host, for example, in DRAM. The storage (20) presented in Fig. 4 may be a separate device distinct from the host. Data stored in the nonvolatile memory in the storage (20) may be cached in the volatile memory in the storage (20). Again, the content cached in the volatile memory may be cached in the DRAM of the host. At this time, the unit of the caching may be referred to as a block in the storage (20). The block is not only a unit of caching, but also a write/read unit of the storage (20). The storage may be considered as an array of blocks. Each block is assigned a number, and this number may be considered as a disk location. When caching the content of the block, the host may use a page cache, which is a part of the DRAM. The caching unit of the page cache is a page. Therefore, the content of the block of the storage may be cached in a page of the page cache.

<Delayed invalidation and node page pinning>

The present invention enables stealing in file system transactions.

Below, the operation method of the log structure file system provided according to one embodiment is described with reference to FIGS. 5 and 6.

The rectangle presented within the memory (13) in FIGS. 5 and 6 represents the page cache (133).

FIG. 5 illustrates a page eviction method of a log structure file system provided according to one embodiment.

In this specification, a space in memory where data "X" is stored may be referred to as a "page", and a page where data "X" is stored may be referred to as a "page X". The "page X" may refer to data "X" stored in page X depending on the context. The memory may refer to memory (ex: DRAM) in a host managed by an operating system of the host. In this specification, a space in storage where data "X" is stored may be referred to as a "block", and a block where data "X" is stored may be referred to as a "block X". The "block X" may refer to data "X" stored in block X depending on the context. In this specification, depending on the context, "data X", "page X", and "block X" may all mean "data X". In this specification, depending on the context, "page X" may refer to a page where data X is stored, and "block X" may refer to a block where data X is stored.

A log-structured file system evicts dirty pages as follows: the evicted page is written to a new disk location (232), the old disk location (231) of the evicted page is invalidated, and the file mapping (node page in F2FS) is updated to refer to the new location (231) of the associated file block.

The above page evict method (page evict routine) cannot be used with the stilling provided according to one embodiment of the present invention for two important reasons.

The first is invalidation of the old disk location (231). When the old disk location (231) is invalidated, the previous file block (231) can be garbage collected and recycled before the transaction is committed. If the previous file block (231) is recycled before the transaction is committed, the transaction cannot be canceled when the transaction is aborted.

The file blocks and node pages presented in the storage (20) in Fig. 5 may be in volatile memory or nonvolatile memory within the storage (20). A block evicted during a transaction process may be written to the nonvolatile memory of the storage (20) even before the transaction is committed.

FIG. 5 shows a problem that occurs when applying the eviction process described above in the prior art. When a transaction is executed, the transaction can modify data A to data A'. At this time, the contents of data A' can be cached in a volatile memory within the storage (20), and this caching is intended to hide the slow speed of the storage (20). The contents cached in the volatile memory within the storage (20) can be cached once more in a volatile memory managed by the host, and this caching is intended to reduce the effort of the host to access the storage (20). The host can modify the contents cached in the host memory (= memory managed by the host, for example, DRAM) to A'. A' can be pinned to the host memory by the transaction. When a situation occurs where the host memory is insufficient, page A' can be evictioned as in step (S12) of FIG. 5 to transfer data A' to the storage (20). The above-described transmitted content may be stored in the volatile memory of the storage (20). Through the above-described eviction process, an empty space is secured in the host memory. The data A' transmitted to the storage (20) may be written to the non-volatile memory in the storage (20) when the host calls a flush command or when the volatile memory in the storage (20) runs out of empty space. Through the above-described eviction, the data A' is written to the block (232) instead of the block (231). Then, the host may treat the data written to the block (231) as invalidated data, and as a result, the block (231) may be cleaned by garbage collection thereafter. The step (S13) of FIG. 5 may be executed in a state where a commit is not called during the transaction. That is, when the host attempts to write data B to the storage (20), a situation may occur where there is an insufficient space in the non-volatile memory in the storage (20). At this time, the host may know that the data written to the block (231) is invalidated. Therefore, data B can be written to block (231). As a result, data A recorded in block (231) is changed to data B, and as a result, data A is lost. Now, if the transaction is canceled, a problem arises in that the data recovered due to the cancellation is B, not A.

FIG. 6 illustrates a checkpoint method of a log structure file system provided according to one embodiment.

The second is a premature checkpoint of the updated node page. When a dirty page is evicted, the updated node page (135) containing the updated file mapping information can be checkpointed if the file system performs a periodic checkpoint operation before the transaction is committed. Then, the updated node block (235) checkpointed on the disk (20) refers to the new disk location (A:2) of the evicted page of the uncommitted transaction. If the file system crashes before the transaction is committed, the recovery module can recover (S241) the evicted page (A') of the uncommitted transaction with respect to the most recent file mapping information found on the disk (20). As a result, the file system can be recovered to an incorrect state.

There are two major issues to be addressed to support the stealable transactions of the present invention in a log-structured file system: the first issue is to prevent old disk locations (231) from being garbage collected until a transaction is committed, and the second issue is to prevent evicted blocks (232) of uncommitted transactions from being recovered after a system crash. A system crash can occur across both the host and the storage.

In the present invention, a delayed invalidation method is proposed to solve the first issue. The delayed invalidation method is explained with reference to Fig. 7.

The rectangle presented within the memory (13) in Fig. 7 represents the page cache (133).

In the delayed invalidation method, after evicting dirty pages from an uncommitted transaction, the file system does not perform invalidation of the old disk location (231) until the transaction is committed.

In the present invention, a node page pinning method is proposed to solve the second issue. The node page pinning method is explained with reference to Fig. 8.

The rectangle presented within the memory (13) in Fig. 8 represents the page cache (133).

In the node page pinning method, the file system pins the updated node page (135) in memory until the transaction is committed to prevent the updated node page (135) from being checkpointed prematurely.

Hereinafter, in the drawings of this specification, a pinned page cache is indicated with an icon indicating pinning. For example, the pinning icon is indicated at the upper right of a square indicated by reference numeral 135 in FIG. 8.

For the above delayed invalidation method and node page pinning method, a new in-memory object, Relocation Record, is introduced. The Relocation Record holds information related to page evict. The Relocation Record includes the file block ID (inode number and file offset), the old disk location (231), and the new disk location (232) of the file block of the evicted page. Using the Relocation Record , the file system asynchronously invalidates the old disk location (231) when committing a transaction, rather than when evicting a dirty page (S33).

The above relocation record can be written to the host's DRAM. There is no problem even if the above relocation record disappears due to a system crash. This is because when rebooting after a system crash, the node page and block bitmap are not changed, so they are restored to the state before the transaction.

Each transaction file group maintains a set of relocation records called a relocation list . The file system creates a relocation record and adds it to the relocation list when it evicts dirty pages from a transaction.

Figure 9 shows an example of running stilling on exF2FS.

The rectangle presented within the memory (13) in Fig. 9 represents the page cache (133).

A dirty page of file block A is initially mapped to LBA 1 (S51). File block A is evicted to LBA 8 (S52). A node page (250) of memory (13) is updated to map file block A to LBA 8 (S53). A block bitmap (260) of LBA 8 is set (S54). The block bitmap (260) for LBA 1 is not invalidated upon eviction due to delayed invalidation. The file system creates a relocation record (271) and inserts the newly created record (271) into the relocation list (270) (S55). The newly created relocation record (271) includes a file block ID (file block A) of the evicted block, a previous location (LBA 1), and a new location (LBA 8). LBA 1 is evicted from disk (20) and is therefore removed from the dirty page list of the associated transaction file group. When the transaction is committed (S56), the LBA is invalidated (S57) and the updated node page is persisted (S58).

<Commit and Abort in Stilling>

When a transaction is committed (S56), the file system makes the previous location (LBA 1) of the evicted page no longer reachable. Before starting the dirty page flush, the file system searches the relocation list (270) in chronological order and invalidates the old disk location (LBA 1) of the evicted block (delayed invalidation) (S57). When this task is completed, the dirty data page of the transaction is flushed (S59). If the dirty page becomes durable, the file system unpins the node page (250) updated by the eviction and inserts it into the dirty node page list. Then, the file system flushes the dirty node page. The transaction is successfully committed only if the master commit block becomes durable.

In contrast, when the file system aborts a transaction, the file system searches the relocation list (270) in reverse chronological order. For each relocation record, the file system invalidates the new disk location (ex: LBA 8) and reverts the node page (250) in memory (13) to map the file block to the old disk location (LBA 1). After the node page (250) is reverted, the pinning is unpinned.

Figure 10 shows this example.

At the time of transaction abort (Tx Abort), three pages of 'A', 'E', and 'F' have already been evicted. The old and new locations of page 'A' correspond to '1' and '8', respectively. At the time of abort, the file system reverts the node pages (250) for 'A', 'E', and 'F' to refer to pages '1', '10', and '11', respectively, according to the relocation list (270). It also invalidates the bitmaps (260) for the new disk locations, LBA 8, LBA 29, and LBA 32.

In the event of a system crash, delayed invalidation can leave allocated but unreachable filesystem blocks. Delayed invalidation temporarily leaves both the old disk location (231) and the new disk location (232) valid from the time the page is evicted until the transaction is committed. If the system crashes during this period, the filesystem can be recovered with both the old disk location (231) and the new disk location (232) valid, but only the old disk location (231) mapped to a file. In this case, the new disk location (232) must be collected via fsck (offline) or an online variant.

According to one aspect of the present invention, a transaction execution method may be provided, including: an evict step in which an operating system of a host writes some of the write pages among the plurality of write pages belonging to the first transaction to storage if the size of the page cache is smaller than the sizes of the plurality of write pages; and a commit step in which the operating system commits the first transaction.

At this time, the data fixed in the page cache immediately before the commit is executed may be the remaining write pages excluding some of the write pages among the multiple write pages.

At this time, the commit step can be executed when the operating system receives a commit call of the first transaction from the application program.

At this time, the transaction execution method may further include, prior to the eviction step, a step in which the operating system receives a set of write operation calls regarding the plurality of write pages from an application program; and, between the eviction step and the commit step, a step in which the operating system receives a commit call of the first transaction from the application program.

At this time, the file system of the above operating system may be a log structure file system.

At this time, data of some of the write pages is data that replaces old data stored in a first set of old blocks in the storage, and data of some of the write pages is stored in a first set of new blocks in the storage by the evict step, and the operating system may be configured not to invalidate old blocks of the first group before the commit is executed.

At this time, the operating system may be configured to invalidate the old blocks of the first group simultaneously with the execution of the commit or after the execution of the commit.

At this time, data of some of the write pages is data that replaces old data stored in a first set of old blocks in the storage, and data of some of the write pages is stored in a first set of new blocks in the storage by the evict step, and before the evict step is executed, old mapping information that maps the old data and the old blocks of the first group to each other is recorded in the storage, and the operating system may be configured not to remove the old mapping information recorded in the storage before the commit is executed.

At this time, data of some of the write pages is data that replaces old data stored in a first set of old blocks in the storage, and data of some of the write pages is stored in a first set of new blocks in the storage by the eviction step, and the eviction step may include a step in which the operating system stores new mapping information indicating a mapping relationship between some of the write pages and the first set of new blocks in the page cache.

At this time, the operating system may be configured not to perform a checkpoint operation on the new mapping information stored in the page cache before the commit is executed. Alternatively, the operating system may be configured to perform a checkpoint operation on the new mapping information simultaneously with the execution of the commit or after the commit is executed.

According to another aspect of the present invention, a transaction execution method may be provided, including: a step in which an operating system of a host initiates a first transaction including a first data and a second data; an evict step in which the operating system writes the first data, pinned at a first page of a page cache of a memory, to a first new block of storage before receiving a commit call for the first transaction from an application; a step in which the operating system pins the second data at the first page; and a commit step of committing the first transaction, by the operating system.

At this time, the transaction execution method may further include, prior to the eviction step, a step in which the operating system receives a set of write operation calls regarding a plurality of data belonging to the first transaction from an application program; and the eviction step may be executed only when the size of the page cache is smaller than the size of the entire plurality of data.

At this time, the transaction execution method may further include, between the evict step and the commit step, a step of the operating system pinning first file mapping information indicating that the first data is mapped to the first new block at a first node page of the memory (S53); a step of the operating system modifying a block bitmap (260) so that the state of the first new block is in an in-use state (modifying a block bitmap so that the first new block is in an in-use state); a step of the operating system generating a first relocation record (271) including an identifier of the first data, a location of a first old block which is an old block of the first data, and a location of the first new block of the first data; and an insertion step of the operating system inserting the generated first relocation record into a relocation list (270).

At this time, the transaction execution method may further include, between the insertion step and the commit step, a step of the operating system searching the relocation list to confirm the location of the first old block of the first data; a step of the operating system invalidating the confirmed first old block of the first data; a step of the operating system flushing dirty pages of the page cache; a step of the operating system unpinning the first node page if the dirty pages are determined to be durable; a step of the operating system inserting the first node page into a dirty node page list; and a step of the operating system flushing the dirty node page list.

At this time, the transaction execution method may further include a step of the operating system searching the relocation list to confirm the location of the first new block of the first data if the first transaction is aborted; a step of the operating system invalidating the first new block of the first data; a step of the operating system recording file mapping information indicating that the first data is mapped to the first old block in the first node page; and a step of the operating system unpinning the first node page.

At this time, the first transaction may be committed only if the commit block is determined to be sustainable.

According to one aspect of the present invention, a host including a memory; and a processing unit executing an operating system; may be provided. The operating system may be configured to execute each step included in the transaction execution method described above.

According to the present invention, a technology can be provided for solving a problem in which the size of a transaction in a file system of an operating system supporting transactions is limited by the size of memory managed by the operating system.

Figure 1 illustrates the configuration of a host provided according to the prior art and one embodiment of the present invention.
Figure 2 shows the steps that SQLite takes to execute a multi-file transaction and their relationship to IO operations.
Figure 3 shows the configuration of a transaction file group.
Figure 4 shows an example of F2FS aborting an uncompleted transaction.
FIG. 5 illustrates a page eviction method of a log structure file system provided according to one embodiment.
FIG. 6 illustrates a checkpoint method of a log structure file system provided according to one embodiment.
FIG. 7 is intended to explain a delayed invalidation method provided according to one embodiment of the present invention.
FIG. 8 is a diagram for explaining a node page pinning method provided according to one embodiment of the present invention.
FIG. 9 shows an example of executing stilling in exF2FS provided according to one embodiment of the present invention.
FIG. 10 illustrates a method for handling a transaction interruption situation using a relocation list according to one embodiment of the present invention.
FIG. 11 shows an example of a method of executing shadow garbage collection provided according to one embodiment of the present invention.
FIG. 12 illustrates a method of migrating a victim block when the victim block of garbage collection corresponds to a previous version of a cached block of an uncommitted transaction, according to one embodiment of the present invention.
FIG. 13 illustrates a method of migrating a victim block of garbage collection when the victim block corresponds to a previous version of an evicted page, according to one embodiment of the present invention.
Figure 14 shows how to migrate a victim block for garbage collection when the victim block corresponds to a new version of an evicted page.
Figure 15 illustrates a concept in which a host writes information to storage according to one embodiment.
Figure 16 illustrates different transactions executed by the host.
FIG. 17 is a flowchart illustrating a commit method of a multi-file transaction provided according to one embodiment of the present invention.
Figure 18 shows the structure of a master commit block provided according to one aspect of the present invention.
Figure 19 shows the relationship between MCB and inode information stored in storage by the commit method of the multi-file transaction described in Figure 17.
FIGS. 20A and 20B are flowcharts illustrating a method for intermediately storing transaction data for a large-capacity transaction according to one embodiment of the present invention.
FIG. 21 is a flowchart illustrating a method for an operating system to execute a transaction according to one embodiment of the present invention.
FIG. 22 is a flowchart illustrating a method for an operating system to commit a transaction according to one embodiment of the present invention.
FIG. 23 is a flowchart illustrating a method for restoring the state of a file system to a state prior to the start of a cancelled transaction when a transaction is cancelled, according to one embodiment of the present invention.

Hereinafter, embodiments of the present invention will be described with reference to the attached drawings. However, the present invention is not limited to the embodiments described in this specification and may be implemented in various other forms. The terminology used in this specification is intended to help understanding of the embodiments and is not intended to limit the scope of the present invention. In addition, the singular forms used below also include the plural forms unless the phrases clearly indicate the opposite meaning.

Figure 15 illustrates a concept in which a host writes information to storage according to one embodiment.

The host (10) and the storage (20) may each be computing devices that operate by supplying power from a power supply. The host (10) and the storage (20) may exchange data and commands through one or more transmission channels (30). The transmission channels (30) may be wireless channels or wired channels. The host (10) and the storage (20) may share power provided from one power supply, or may each receive power from two different power supplies.

The above host (10) may include a CPU, memory, power supply, and communication device.

The above storage (20) may include a controller (21), volatile memory (22), and non-volatile memory (23).

The above host (10) can transmit various commands and data to the storage (20) through the above transmission channels (30). The commands may include a write command.

The controller (21) of the storage (20) can store data received from the transmission channels (30) in the volatile memory (22) based on the command received from the transmission channels (30). The data stored in the volatile memory (22) can be stored in the nonvolatile memory (23) according to the rule followed by the controller (21). The data stored in the volatile memory (22) can be deleted when the power supplied to the storage (20) is cut off, but the data stored in the nonvolatile memory (23) is not deleted even when the power supplied to the storage (20) is cut off.

The above host (10) can execute an application (11) and an operating system (12). The above application (11) and the operating system (12) may be executed by executing predetermined command codes stored in a memory accessed by the host (10) by a CPU included in the host (10).

In one embodiment, the application (11) may be a program that is executed or terminated by a user providing user input through a user interface provided by the host (10).

In one embodiment, the operating system (12) may be a program that is automatically executed by the host (10) when power is applied to the host (10) or a reset is performed.

The above application (11) can send various system calls to the operating system (12). The operating system (12) can execute a task corresponding to the system call.

The above host (10) can execute a transaction. It may take a certain amount of time from the time a specific transaction starts until it ends.

The application (11) can control the start and commit of a transaction. And the application (11) can control one or more operations to be executed during the transaction. The application (11) can transmit system calls including a start call, a set of operation calls, and a commit call to the operating system (12).

A specific transaction is started by the start call, commands to be transmitted from the host (10) to the storage (20) are prepared by the set of operation calls, and the prepared commands can be transmitted to the storage (20) through the transmission channels (30) by the commit call.

Figure 16 illustrates different transactions executed by the host.

A set of multiple operations can constitute a single transaction.

The first transaction (41) may consist of four write operations (WO#1 to WO#4). In Fig. 16, an example is presented in which only write operations are included in each transaction, but other types of operations may also be included.

FIG. 17 is a flowchart illustrating a commit method of a multi-file transaction provided according to one embodiment of the present invention.

In step (S110), the application (11) can transmit a start call to the operating system (12). This allows the first transaction to start. When the operating system (12) receives the start call, it can start a process for the first transaction.

In step (S121), the application (11) can call a write operation call (WO#1) for the first page of the first file to the operating system (12).

In step (S122), the application (11) can call a write operation call (WO#2) for the first inode of the first file to the operating system (12).

In step (S131), the application (11) can call a write operation call (WO#3) for the second page of the second file to the operating system (12).

In step (S132), the application (11) can call a write operation call (WO#4) for the second inode of the second file to the operating system (12).

In step (S140), the application (11) can call a commit call to the operating system (12).

In step (S150), the operating system (12) can process the first transaction in response to the commit call. That is, pages of all files included in the first transaction can be reflected in the storage (20).

Step (S150) may include steps (S151) to (S158).

In step (S151), the operating system (12) can create one MCB (Master Commit Block) having a structure according to one embodiment of the present invention.

Figure 18 shows the structure of a master commit block provided according to one aspect of the present invention.

In one implementation example, the total size of the master commit block (300) is N bytes (ex: N=4,096).

At this time, the number of inode block locations that the master commit block (300) has is stored in the uppermost N1 bytes (301) (ex: N1=4). In the remaining {N-N1} byte space of the master commit block (300), N/N1-1 block addresses of N1 byte size can be stored.

In each part (302, 303, 304) of the above master commit block (300), the block locations (block numbers) of the inodes written by the multi-file transaction by the above first transaction can be stored.

Here, the block location of each of the above inodes may be an address indicating the location of the block where the inode is stored within the storage (20).

For example, the block location of the first inode of the first file (File#1) (401) may be stored in the first part (302), and the block location of the second inode of the second file (File#2) (402) may be stored in the second part (303). Here, the first file (File#1) (401) and the second file (File#2) (402) are files included in the first transaction.

Instead of attaching the FSYNC_BIT flag to the inode block, the FSYNC_BIT flag (307) can be attached to the master commit block.

The order between inodes and transaction contents may not be guaranteed.

Instead, the order between the entire transaction contents including the inode and the master commit block (300) can be guaranteed.

If a crash occurs in a log-structured file system, a master commit block (300) with the FSYNC_BIT flag (307) can be found in storage.

The master commit block (300) is recorded in a state where the write order with the remaining transaction contents is guaranteed. Therefore, the discovery of the master commit block (300) means that all other transaction contents have been recorded.

Returning to FIG. 17 again, in step (S152), the operating system (12) may transmit a write command (WC#1, WC#2) corresponding to the write operation call (WO#1, WO#2) to the storage (20). The write command (WC#1, WC#2) may include information about the first inode (Inode#1) of the first file (File#1).

In step (S153), the operating system (12) can store the block location (block number) of the first inode (Inode#1) in a part of the master commit block (300).

Step (S153) of Fig. 17 is a step of reflecting the contents of the i-th file among the files included in the transaction to the storage. At this time, the file contents also include the inode of the i-th file. That is, since step (S153) of Fig. 17 is an operation immediately after the inode is stored in non-volatile memory, the operating system (12) can know the block location of the inode.

Steps (S152) and (S153) can be repeatedly executed for all other files included in the first transaction.

For example, in step (S154), the operating system (12) may transmit a write command (WC#3, WC#4) corresponding to the write operation call (WO#3, WO#4) to the storage (20). The write command (WC#3, WC#4) may include information about the third inode (Inode#3) of the third file (File#1).

In step (S155), the operating system (12) can store the block location (block number) of the second inode (Inode#2) in a part of the master commit block (300).

When all files included in the first transaction are written to the volatile memory (22) of the storage (20), the operating system (12) can transmit a flush command (FC) to the storage (20) in step (S157).

Next, in step (S158), the operating system (12) may transmit an MCB write command to the storage (20) to write the master commit block (300) to the storage (20). The MCB write command may include the contents of the master commit block (300).

The above storage (20) can perform the following steps in response to commands received from the operating system (12).

In step (S161), when the storage (20) receives the write command (WC#1, WC#2), it stores the first page (Page#1) and the first inode (Inode#1) in the volatile memory (22).

In step (S162), when the storage (20) receives the write command (WC#3, WC#4), it stores the second page (Page#2) and the second inode (Inode#2) in the volatile memory (22).

In step (S163), when the storage (20) receives the flush command (FC), the storage (20) stores information about the first transaction stored in the volatile memory (22) in the non-volatile memory (23).

In step (S164), the storage (20) can store the master commit block (300) in the non-volatile memory (23).

If a problem such as a power outage occurs in the storage (20) after step (S152) is started and before step (S164) is completed, the contents of the files related to the first transaction recorded in the non-volatile memory (23) are invalidated.

Figure 19 shows the relationship between MCB and inode information stored in storage by the commit method of the multi-file transaction described in Figure 17.

In FIG. 19, reference number 231 represents a first block (231) in which a first inode (Inode#1) is stored, reference number 232 represents a second block (232) in which a second inode (Inode#2) is stored, and reference number 233 represents a third block (233) in which the master commit block (300) is stored.

The first inode pointer (2331) included in the third block (233) has a value related to the address of the first block (231), and the second inode pointer (2332) has a value related to the address of the second block (232).

FIGS. 20A and 20B are flowcharts illustrating a method for intermediately storing transaction data for a large-capacity transaction according to one embodiment of the present invention.

FIG. 20a and FIG. 20b may be collectively referred to as FIG. 20.

At step (S210), the operating system (12) can receive a transaction start call from the application (11).

In step (S220), the operating system (12) can receive a first write operation call (WO#1) for the first to third pages (pages1~3) of the first file (fd#1) from the application (11).

In step (S310), the operating system (12) can pin the data of the first page to the data of the third page to the page cache of the memory (ex: DRAM) managed by the operating system (12).

The above step (S310) can be executed on the assumption that space for storing pages (the first to third pages in the example of FIG. 20) specified by the first write operation call (WO#1) in the page cache has already been prepared.

In step (S230), the operating system (12) can receive a second write operation call (WO#2) for the 4th to 8th pages (pages4~8) of the first file (fd#1) from the application (11).

If it is determined that there is no place prepared to store all of the pages (the 4th to 8th pages in the example of Fig. 20) specified by the second write operation call (WO#2) in the above page cache, the operating system (12) can execute step (S320).

Step (S320) may include steps (S321), (S322), and (S323) below.

In step (S321), the operating system (12) can pin all pages (4th to 6th pages in the example of FIG. 20) that can be stored in the remaining space of the page cache among the pages specified by the second write operation call (WO#2).

In step (S322), the operating system (12) may evict some of the eviction pages (the first to second pages in the example of FIG. 20), which are already pinned in the page cache, to storage (20) in order to secure space for storing standby pages (the seventh to eighth pages in the example of FIG. 20), which are pages not yet pinned in the page cache among the pages specified by the second write operation call (WO#2). To this end, the operating system (12) may transmit an eviction command for the eviction pages that were already pinned in the page cache to the storage (20).

At this time, the sizes of the above waiting pages and the sizes of the above evict pages may be the same.

In step (S410), when the storage (20) receives an Evict command for the Evict pages from the operating system (12), the storage (20) can store the Evict pages in the nonvolatile memory of the storage (20).

In step (S323), the operating system (12) can pin new file mapping information, which is mapping information between the Evict pages and blocks in the storage (20) where the Evict pages are stored, to the page cache.

In step (S330), the operating system (12) can pin the standby pages to the space occupied by the evict pages in the page cache.

At this time, the write priority for the above Evict pages may be higher than the write priority of the pages pinned in the page cache after execution of the Evict instruction.

In step (S240), the operating system (12) can receive a commit call from the application (11).

In step (S340), the operating system (12) can process transaction #1, and specifically, can include steps (S341) to (S345).

In step (S341), the operating system (12) may transmit a write command to the storage (20). At this time, the write command may be a write command for the first set of pages pinned to the page cache.

In step (S420), the storage (20) can store the first set of pages in the volatile memory within the storage (20). In the example of Fig. 20, the pages of the first set are the third to eighth pages.

In step (S342), the operating system (12) can transmit a flush command to the storage (20).

In step (S430), the storage (20) can store (flush) information stored in the volatile memory within the storage (20) to the non-volatile memory within the storage (20).

In step (S343), the operating system (12) can transmit a command to the storage (20) to invalidate old blocks that the Evict pages occupied before the execution of the Evict command within the storage (20).

In step (S440), the storage (20) can invalidate the old blocks.

In step (S344), the operating system (12) can release the pinning of the new file mapping information.

In step (S345), the operating system (12) can transmit a checkpoint command for the new file mapping information to the storage (20).

In step (S450), the storage (20) can store the new file mapping information in non-volatile memory within the storage (20).

In the method of processing a transaction presented in Fig. 20, the above steps (S345) and (S450) may be omitted.

FIG. 21 is a flowchart illustrating a method for an operating system to execute a transaction according to one embodiment of the present invention.

At step (S810), the host's operating system can start a first transaction including first data and second data.

In step (S820), the operating system can receive a set of write operation calls regarding a plurality of data belonging to a first transaction from an application program.

In step (S830), the operating system may execute an evict to write the first data pinned to the first page of the page cache of the memory to the first new block of the storage before receiving a commit call for the first transaction from the application.

The above Evict step can be executed only when the size of the page cache is smaller than the size of the entire plurality of data.

After the above step (S830), the operating system may execute a step of pinning the second data to the first page.

In step (S841), the operating system can pin first file mapping information indicating that the first data is mapped to the first new block to the first node page of the memory.

In step (S842), the operating system can modify the block bitmap (260) so that the status of the first new block becomes in-use.

In step (S843), the operating system can generate a first relocation record (271) including an identifier of the first data, a location of a first old block, which is an old block of the first data, and a location of the first new block of the first data.

In step (S844), the operating system can insert the generated first relocation record into the relocation list (270).

FIG. 22 is a flowchart illustrating a method for an operating system to commit a transaction according to one embodiment of the present invention.

The steps shown in Fig. 22 can be executed after step (S844) of Fig. 21.

In step (S851), the operating system can search the relocation list to confirm the location of the first old block of the first data.

In step (S852), the operating system can invalidate the first old block of the confirmed first data.

In step (S853), the operating system can flush dirty pages of the page cache.

In step (S854), if the operating system determines that the dirty pages are sustainable, it can unpin the first node page.

In step (S855), the operating system can insert the first node page into the dirty node page list.

In step (S856), the operating system can flush the dirty node page list.

At step (S870), the operating system can commit the first transaction.

At this time, the first transaction may be committed only if the commit block is determined to be sustainable.

FIG. 23 is a flowchart illustrating a method for restoring the state of a file system to a state prior to the start of a cancelled transaction when a transaction is cancelled, according to one embodiment of the present invention.

The steps shown in Fig. 23 can be executed after step (S844) of Fig. 21 under the condition that the first transaction is aborted.

In step (S861), the operating system can search the relocation list to confirm the location of the first new block of the first data.

In step (S862), the operating system can invalidate the first new block of the first data.

In step (S863), the operating system can record file mapping information indicating that the first data is mapped to the first old block in the first node page.

At step (S864), the operating system can unpin the first node page.

In this specification, pinning may mean the operation of preventing content written to the page cache from being written to storage.

By using the embodiments of the present invention described above, those who belong to the technical field of the present invention will be able to easily perform various changes and modifications within the scope that does not depart from the essential characteristics of the present invention. The content of each claim of the patent claims can be combined with other claims that do not have a citation relationship within the scope that can be understood through this specification.

Claims (15)

An evict step in which the host's operating system writes some of the write pages among the plurality of write pages to storage if the size of the page cache is smaller than the size of the plurality of write pages belonging to the first transaction; and
A commit step in which the above operating system commits the first transaction;
Including,
The data of the above-mentioned part of the write page is new data that replaces the old data stored in the old blocks of the first group within the above-mentioned storage,
The data of the above part of the write page is stored in the new blocks of the first group in the storage by the above Evict step,
The above operating system is configured not to invalidate the old blocks of the first group before the above commit is executed.
How to execute a transaction. A transaction execution method in claim 1, characterized in that the data fixed in the page cache immediately before the commit is executed are the remaining write pages excluding some of the write pages among the plurality of write pages. delete A transaction execution method in the first paragraph, wherein the operating system is configured to invalidate old blocks of the first group simultaneously with execution of the commit or after execution of the commit. In the first paragraph,
Before the above Evict step is executed, the storage records old mapping information that maps the old data and the old blocks of the first group to each other.
The above operating system is configured not to remove the old mapping information recorded in the storage before the above commit is executed.
How to execute a transaction. In the first paragraph,
The above Evict step includes a step in which the operating system stores new mapping information indicating a mapping relationship between some of the write pages and the new blocks of the first group in the page cache.
How to execute a transaction. A transaction execution method according to any one of claims 1, 2, and 4 to 6, characterized in that the file system of the operating system is a log structure file system. A step in which the host's operating system initiates a first transaction including first data and second data;
An evict step of writing the first data pinned to the first page of the page cache of the memory to the first new block of the storage before the operating system receives a commit call for the first transaction from the application;
The step of the above operating system pinning the second data to the first page; and
A commit step in which the above operating system commits the first transaction;
Including,
The above first data is new data that replaces the old data stored in the first old block in the storage,
The above first data is stored in the first new block within the storage by the above Evict step,
The above operating system is configured not to invalidate the first old block before the above commit is executed.
How to execute a transaction. In Article 8,
Before the above Evict step, the operating system further includes a step of receiving a set of write operation calls regarding a plurality of data belonging to a first transaction from an application program;
The above Evict step is characterized in that it is executed only when the size of the page cache is smaller than the size of the entire plurality of data.
How to execute a transaction. In Article 8,
Between the above Evict step and the above Commit step,
The step of the operating system pinning first file mapping information indicating that the first data is mapped to the first new block to the first node page of the memory;
The step of the above operating system modifying the block bitmap so that the status of the first new block becomes a used state;
The operating system generates a first relocation record including an identifier of the first data, a location of the first old block, and a location of the first new block of the first data; and
An insertion step in which the above operating system inserts the generated first relocation record into the relocation list;
Including more,
How to execute a transaction. In Article 10,
Between the above insert step and the above commit step,
The step of the above operating system searching the above relocation list to confirm the location of the first old block;
The step of the above operating system invalidating the confirmed first old block;
The step of the above operating system flushing dirty pages of the above page cache;
The step of the above operating system unpinning the first node page when the dirty pages are determined to be sustainable;
The step of the above operating system inserting the first node page into the dirty node page list; and
The step of the above operating system flushing the dirty node page list;
Including more,
How to execute a transaction. In Article 10,
If the above first transaction is aborted,
A step in which the above operating system searches the above relocation list to determine the location of the first new block;
The step of the above operating system invalidating the first new block;
The step of the operating system recording file mapping information indicating that the first data is mapped to the first old block in the first node page; and
The above operating system unpins the first node page;
Including more,
How to execute a transaction. A transaction execution method in accordance with claim 11, wherein the first transaction is committed only when the commit block is determined to be sustainable. A host including a memory; and a processing unit executing an operating system;
The above operating system,
If the size of the page cache is smaller than the size of a plurality of write pages belonging to the first transaction, an evict step of writing some of the write pages among the plurality of write pages to storage; and
A commit step in which the above operating system commits the first transaction;
is designed to run,
The data of the above-mentioned part of the write page is new data that replaces the old data stored in the old blocks of the first group within the above-mentioned storage,
The data of the above part of the write page is stored in the new blocks of the first group in the storage by the above Evict step,
The above operating system is configured not to invalidate the old blocks of the first group before the above commit is executed.
Host. In claim 14, the host is characterized in that the file system of the operating system is a log structure file system.

Images