JP6242711B2 - Storage apparatus and data management method - Google Patents
Storage apparatus and data management method Download PDFInfo
- Publication number
- JP6242711B2 JP6242711B2 JP2014033162A JP2014033162A JP6242711B2 JP 6242711 B2 JP6242711 B2 JP 6242711B2 JP 2014033162 A JP2014033162 A JP 2014033162A JP 2014033162 A JP2014033162 A JP 2014033162A JP 6242711 B2 JP6242711 B2 JP 6242711B2
- Authority
- JP
- Japan
- Prior art keywords
- version
- data
- logical
- page
- physical address
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
本発明の実施形態は、ストレージ装置及びデータ管理方法に関する。 Embodiments described herein relate generally to a storage apparatus and a data management method.
近年では、例えばＮＡＮＤ型フラッシュメモリのような不揮発性の半導体記憶装置を備えたストレージ装置（ＮＡＮＤ型フラッシュメモリストレージ）が知られている。このストレージ装置には、例えばＮＡＮＤ型フラッシュメモリを使用したデータベースへのアクセスを制御するデータベースシステムが実装される。 In recent years, a storage device (NAND flash memory storage) including a nonvolatile semiconductor memory device such as a NAND flash memory is known. In this storage apparatus, for example, a database system for controlling access to a database using a NAND flash memory is mounted.
ところで、このようなストレージ装置に実装されるデータベースシステムにおいては、マルチユーザ環境におけるデータベースの性能を向上させるために、多版同時実行制御（ＭＶＣＣ：MultiVersion Concurrency Control）が実行される。このＭＶＣＣによれば、例えばデータベースに格納される任意のデータにおける変更状態を複数保持しておくことで、データアクセスの依存関係を解決することができる。 By the way, in a database system implemented in such a storage apparatus, multi-version concurrent control (MVCC) is executed in order to improve the performance of the database in a multi-user environment. According to this MVCC, for example, by retaining a plurality of change states in arbitrary data stored in a database, it is possible to solve data access dependency relationships.
しかしながら、上記したＭＶＣＣを実行するデータベースシステムでは、データが更新される度に、当該更新前後の複数のデータを格納しておく必要がある。このため、データベース内では、不要なデータが大量に発生する。これは、データベースの性能の低下を招く。 However, in the database system that executes the above-described MVCC, each time data is updated, it is necessary to store a plurality of data before and after the update. For this reason, a large amount of unnecessary data is generated in the database. This leads to a decrease in database performance.
そこで、データベースシステムにおいては、データベース動作の効率性を上げるための不要データ領域の回収やデータ再編成のためにバキューム処理が実行される。このバキューム処理によれば、データベース内の不要データの消去等が行われる。 Therefore, in the database system, a vacuum process is performed for collecting unnecessary data areas and improving data reorganization in order to increase the efficiency of database operations. According to the vacuum process, unnecessary data in the database is erased.
上記したようにＭＶＣＣを実行するデータベースシステムにおいてはバキューム処理が必須であるが、当該バキューム処理が実行されている間はデータベースをロックする必要がある。 As described above, in the database system that executes MVCC, vacuum processing is essential, but the database must be locked while the vacuum processing is being executed.
この場合、バキューム処理中はデータベースへのアクセスができないため、データベースの運用上好ましくない。 In this case, the database cannot be accessed during the vacuum process, which is not preferable for database operation.
したがって、バキューム処理を実行することなく不要データの消去等を行う仕組みが望まれている。 Therefore, a mechanism for erasing unnecessary data without executing vacuum processing is desired.
そこで、本発明が解決しようとする課題は、バキューム処理を実行することなく不要データの消去を行うことが可能なストレージ装置及びデータ管理方法を提供することにある。 Therefore, the problem to be solved by the present invention is to provide a storage device and a data management method capable of erasing unnecessary data without executing a vacuum process.
実施形態によれば、各種データを記憶する不揮発性の半導体記憶装置を備え、当該半導体記憶装置を使用したデータベースへの多版同時実行制御を実行するデータベースシステムが実装されるストレージ装置が提供される。実施形態に係るストレージ装置は、前記半導体記憶装置に記憶されているデータのバージョンを管理し、ガベージコレクションの実行時に不要なバージョンのデータを自動的に消去するコントローラと、前記データベースシステムにおいて用いられる論理アドレスの各々に対応づけて当該論理アドレスに対応するデータの物理アドレスを保持する論物変換テーブル及び更新履歴リストを記憶するメモリとを具備する。前記半導体記憶装置は、ＮＡＮＤ型フラッシュメモリを含み、前記物理アドレスは、前記ＮＡＮＤ型フラッシュメモリにおけるブロックを構成するページを特定し、前記データの消去は、複数のページから構成されるブロック単位で行われる。前記コントローラは、データ更新手段と、登録手段と、テーブル更新手段と、無効化手段と、コピー手段と、消去手段とを含む。前記データ更新手段は、ユーザによって指定された論理アドレスに対応する第１のデータを第２のデータに更新するためのデータ更新要求が前記データベースシステムから入力された場合、当該第２のデータを当該第１のデータの第１の物理アドレスとは異なる第２の物理アドレスによって特定されるページに書き込む。前記登録手段は、前記ユーザによって指定された論理アドレス及び当該論理アドレスに対応づけて前記論物変換テーブルに保持されている第１の物理アドレスを、前記第１のデータに割り当てられたバージョンを示すバージョン情報に対応づけて前記更新履歴リストに登録する。前記テーブル更新手段は、前記ユーザによって指定された論理アドレスに対応づけて前記論物変換テーブルに保持されている第１の物理アドレスを前記第２の物理アドレスに更新する。前記無効化手段は、前記更新履歴リストに登録されたバージョン情報に基づいて、当該バージョン情報に対応づけて前記更新履歴リストに登録された第１の物理アドレスによって特定されるページの状態を無効とする。前記コピー手段は、前記状態が無効とされたページを含む第１のブロックを構成する複数のページのうち、状態が無効であるページの割合が閾値以上である場合、当該複数のページのうち状態が有効であるページに書き込まれている第３のデータを前記第１のブロック以外の第２のブロックを構成するページにコピーする。前記消去手段は、前記第１のブロックを構成する複数のページに書き込まれているデータを消去する。 According to the embodiment, there is provided a storage device that includes a nonvolatile semiconductor storage device that stores various data, and in which a database system that executes multi-version simultaneous execution control on a database using the semiconductor storage device is mounted. . The storage device according to the embodiment manages a version of data stored in the semiconductor storage device, and automatically deletes unnecessary version data when executing garbage collection, and a logic used in the database system A logical-physical conversion table that retains a physical address of data corresponding to the logical address in association with each address, and a memory that stores an update history list. The semiconductor memory device includes a NAND flash memory, the physical address specifies a page constituting a block in the NAND flash memory, and the erasure of data is performed in units of a block composed of a plurality of pages. Is called. The controller includes data update means, registration means, table update means, invalidation means, copy means, and erase means. When the data update request for updating the first data corresponding to the logical address designated by the user to the second data is input from the database system, the data update means stores the second data Write to a page specified by a second physical address different from the first physical address of the first data. The registration means indicates a version assigned to the first data, a logical address designated by the user and a first physical address held in the logical-physical conversion table in association with the logical address. It is registered in the update history list in association with version information. The table updating means updates the first physical address held in the logical-physical conversion table in association with the logical address designated by the user to the second physical address. The invalidation means invalidates the state of the page specified by the first physical address registered in the update history list in association with the version information based on the version information registered in the update history list. To do. The copy means, when a ratio of pages in which the state is invalid is equal to or more than a threshold value among a plurality of pages constituting the first block including the page in which the state is invalid, The third data written in the page in which is valid is copied to the page constituting the second block other than the first block. The erasing unit erases data written in a plurality of pages constituting the first block .
以下、図面を参照して、実施形態について説明する。 Hereinafter, embodiments will be described with reference to the drawings.
図１は、本実施形態に係るストレージ装置のハードウェア構成を示すブロック図である。ストレージ装置１０は、各種データを記憶する不揮発性の半導体記憶装置を備えている。図１においては、不揮発性の半導体記憶装置の一例としてＮＡＮＤ型フラッシュメモリ１１が示されている。
FIG. 1 is a block diagram showing the hardware configuration of the storage apparatus according to this embodiment. The
このＮＡＮＤ型フラッシュメモリ１１に対しては、ページと称される単位でデータの書き込み及び読み出しが行われる。また、ＮＡＮＤ型フラッシュメモリ１１に記憶されたデータの消去は、ブロックと称される単位で行われる。このブロックは、複数のページから構成されるものとする。
Data is written to and read from the NAND
また、ＮＡＮＤ型フラッシュメモリ１１においては、データを上書きすることはできない。このため、ＮＡＮＤ型フラッシュメモリ１１に記憶されているデータが更新される場合には、常に別のページ（物理アドレス）にデータが書き込まれる。また、データの更新によって不要となったデータの領域（ページ）に対する他のデータの書き込みを可能とするためには、当該ページ（のデータ）を一旦消去する必要がある。上記したようにＮＡＮＤ型フラッシュメモリ１１におけるデータ消去は、複数のページから構成されるブロック単位で行われる。
In the
なお、本実施形態に係るストレージ装置１０には、ＮＡＮＤ型フラッシュメモリ１１を使用したデータベースへのアクセスを制御するデータベースシステムが実装されているものとする。このデータベースシステム上では、データベースに格納される各データは、例えばＬＢＡ（Logical Block Address）のような論理アドレスを用いて管理される。なお、データベースにおけるデータ登録はレコードと称されるが、本実施形態においては、便宜的に、レコードと上記したページのサイズは同一であるものとする。また、データベースシステムにおいては、マルチユーザ環境におけるデータベースの性能向上のために、多版同時実行制御（ＭＶＣＣ）が実行される。
It is assumed that the
更に、ストレージ装置１０は、図１に示すように、入出力部１２、コントローラ１３及びメモリ１４を備える。
Furthermore, the
入出力部１２は、ストレージ装置１０に実装されているデータベースシステムとの入出力処理を行う。
The input /
コントローラ（ＮＡＮＤコントローラ）１３は、メモリ１４に記憶されている各種情報に基づいて、ＮＡＮＤ型フラッシュメモリ１１に記憶されているデータを管理し、当該ＮＡＮＤ型フラッシュメモリ１１へのデータの書き込み及び読み込みを制御する。
The controller (NAND controller) 13 manages data stored in the
コントローラ１３は、データ更新部１３１、保存バージョン設定部１３２、バージョン確定部１３３、バージョン復元部１３４及びデータ消去部１３５を含む。また、メモリ１４には、論物変換テーブル１４１、ページ状態テーブル１４２、消去済みページリスト１４３、更新履歴リスト１４４及び設定テーブル１４５が記憶される。
The
なお、メモリ１４は揮発性メモリであり、例えばストレージ装置１０の起動時等に他の不揮発性メモリ領域に記憶されていた論物変換テーブル１４１、ページ状態テーブル１４２、消去済みページリスト１４３、更新履歴リスト１４４及び設定テーブル１４５がメモリ１４に記憶されるものとする。
Note that the
論物変換テーブル１４１には、データベースシステムにおいて用いられる論理アドレスの各々に対応づけて当該論理アドレスに対応するデータの物理アドレス（当該データが記憶されているＮＡＮＤ型フラッシュメモリ１１上の位置）が保持される。なお、物理アドレスは、ＮＡＮＤ型フラッシュメモリ１１におけるブロックに割り当てられた番号（以下、ブロック番号と表記）及び当該ブロックを構成するページに割り当てられた番号（以下、ページ番号と表記）を含む。このブロック番号及びページ番号により、ＮＡＮＤ型フラッシュメモリ１１上の一意の位置（特定のブロックを構成する特定のページ）を特定することができる。
The logical-physical conversion table 141 holds physical addresses of data corresponding to the logical addresses (positions on the
ページ状態テーブル１４２は、ＮＡＮＤ型フラッシュメモリ１１における各ブロックを構成するページの状態を管理するためのテーブルである。
The page status table 142 is a table for managing the status of pages constituting each block in the
消去済みページリスト１４３は、ＮＡＮＤ型フラッシュメモリ１１における各ページのうち、データを消去済みのページ（つまり、データを書き込み可能なページ）のリストである。
The erased
データ更新部１３１は、入出力部１２を介して入力されたデータ更新要求（書き込み要求）に基づいて、ＮＡＮＤ型フラッシュメモリ１１に記憶されているデータを更新する。なお、データ更新要求は、例えばユーザによって指定された論理アドレスに対応するデータ（第１のデータ）を他のデータ（第２のデータ）に更新する際にデータベースシステムから入力される。以下の説明では、便宜的に、ユーザによって指定された論理アドレスに対応するデータを更新前データと称し、当該更新前データを更新するための他のデータを更新後データと称する。データ更新要求には、ユーザによって指定された論理アドレス及び更新後データが含まれる。
The
データ更新部１３１は、データ更新要求が入力された場合、ＮＡＮＤ型フラッシュメモリ１１の更新前データの物理アドレス（第１の物理アドレス）とは異なる物理アドレス（第２の物理アドレス）に更新後データを書き込む。この場合、データ更新部１３１は、上記した消去済みページリストからページ（書き込み可能なページ）を取得し、当該ページに対して書き込み処理を実行する。
When a data update request is input, the
更新後データがＮＡＮＤ型フラッシュメモリ１１に書き込まれると、データ更新部１３１は、データ更新要求に含まれる論理アドレス及び当該論理アドレスに対応づけて論物変換テーブル１４１に保持されている物理アドレス（つまり、更新前データの物理アドレス）を取得する。データ更新部１３１は、取得された論理アドレス及び物理アドレスを、更新前データに割り当てられたバージョンを示すバージョン情報（例えば、当該バージョンを表すバージョン番号）に対応づけて更新履歴リスト１４４に登録する。
When the updated data is written in the
また、データ更新部１３１は、データ更新要求に含まれる論理アドレスに対応づけて論物変換テーブル１４１に保持されている物理アドレス（ブロック番号及びページ番号）を、更新後データが書き込まれた物理アドレスに更新する。
In addition, the
このようにデータ更新部１３１によってデータの更新が行われると、論物変換テーブル１４１には最新のデータに関する論理アドレスと物理アドレスとの対応関係が保持される。一方、更新履歴リスト１４４には、古いバージョンの論理アドレスと物理アドレスとの対応関係が登録される。すなわち、更新履歴リスト１４４によれば、各バージョンのデータを管理することができる。
When data is updated by the
なお、データ更新部１３１は、データの更新処理に応じて、上記したページ状態テーブル及び消去済みページリストを更新する。
The
保存バージョン設定部１３２は、データを保存すべきバージョンを設定テーブル１４５に設定する。データを保存すべきバージョンが設定テーブル１４５に設定された場合、保存バージョン設定部１３２は、当該バージョンより過去の（古い）バージョンを示すバージョン情報に対応づけて更新履歴リスト１４４に登録された物理アドレスによって特定されるページ（の状態）を無効とする。このページの無効は、ページ状態テーブル１４２に登録される。
The saved
バージョン確定部１３３は、更新履歴リスト１４４において同一のバージョンとして管理される範囲を確定（設定）する。具体的には、バージョン確定部１３３は、入出力部１２を介してユーザの指示に基づくバージョン確定要求が入力された場合、当該バージョン確定要求が入力されるまでに更新履歴リスト１４４に登録された論理アドレス及び物理アドレスを同一のバージョンとして確定する。
The
バージョン復元部１３４は、入出力部１２を介して入力されたバージョン復元要求に基づいて、更新履歴リスト１４４に登録された論理アドレスと物理アドレスを論物変換テーブル１４１に復元する。なお、バージョン復元要求は、ユーザによって指定されたバージョンを示すバージョン情報を含む。
The
具体的には、バージョン復元部１３４は、バージョン復元要求に含まれるバージョン情報に対応づけて更新履歴リスト１４４に登録された論理アドレスを取得する。バージョン復元部１３４は、取得された論理アドレス及び当該論理アドレスに対応づけて論物変換テーブル１４１に登録された物理アドレスを、当該物理アドレスに記録されているデータに割り当てられたバージョンを示すバージョン情報に対応づけて更新履歴リストに登録する。また、バージョン復元部１３４は、バージョン復元要求に含まれるバージョン情報に対応づけて更新履歴リスト１４４に登録された論理アドレス及び物理アドレスを、論物変換テーブル１４１に復元する。
Specifically, the
データ消去部１３５は、例えば上記したように保存バージョン設定部１３２によって設定テーブル１４５に設定されたバージョンに基づいて無効にされたページから構成されるブロック（のデータ）を消去する。この場合、データ消去部１３５は、ＮＡＮＤ型フラッシュメモリ１１における書き込み領域の確保処理であるガベージコレクション（ＧＣ）を実行する。なお、ガベージコレクションの詳細については後述する。
For example, as described above, the
図２は、図１に示す論物変換テーブル１４１のデータ構造の一例である。図２に示すように、論物変換テーブル１４１には、論理アドレス及び物理アドレスが対応づけて保持される。なお、論理アドレスは、データベースシステムにおいて用いられるアドレスである。一方、物理アドレスは、当該物理アドレスに対応づけられている論理アドレスに対応するデータが記憶されているＮＡＮＤ型フラッシュメモリ１１上のアドレスである。物理アドレスは、ＮＡＮＤ型フラッシュメモリ１１におけるブロックに割り当てられたブロック番号及び当該ブロックを構成するページに割り当てられたページ番号を含む。
FIG. 2 shows an example of the data structure of the logical-physical conversion table 141 shown in FIG. As shown in FIG. 2, the logical-physical conversion table 141 holds logical addresses and physical addresses in association with each other. The logical address is an address used in the database system. On the other hand, the physical address is an address on the
図２に示す例では、論物変換テーブル１４１には、論理アドレス「１」とブロック番号「１」及びページ番号「４」を含む物理アドレスとが対応づけて保持されている。これによれば、論理アドレス「１」に対応するデータが、ブロック番号「１」が割り当てられたブロックを構成する複数のページのうちページ番号「４」が割り当てられたページ（の領域）に記憶されていることが示されている。 In the example illustrated in FIG. 2, the logical-physical conversion table 141 holds a logical address “1” and a physical address including a block number “1” and a page number “4” in association with each other. According to this, the data corresponding to the logical address “1” is stored in the page (area) to which the page number “4” is assigned among the plurality of pages constituting the block to which the block number “1” is assigned. It has been shown that.
同様に、論物変換テーブル１４１には、論理アドレス「２」とブロック番号「１」及びページ番号「５」を含む物理アドレスとが対応づけて保持されている。これによれば、論理アドレス「２」に対応するデータが、ブロック番号「１」が割り当てられたブロックを構成する複数のページのうちページ番号「５」が割り当てられたページ（の領域）に記憶されていることが示されている。 Similarly, the logical-physical conversion table 141 holds a logical address “2” and a physical address including a block number “1” and a page number “5” in association with each other. According to this, the data corresponding to the logical address “2” is stored in the page (area) to which the page number “5” is assigned among the plurality of pages constituting the block to which the block number “1” is assigned. It has been shown that.
ここでは論理アドレス「１」及び「２」についてのみ説明したが、他の論理アドレスについても同様であるため、その詳しい説明を省略する。 Although only the logical addresses “1” and “2” have been described here, the same applies to other logical addresses, and thus detailed description thereof is omitted.
図３は、図１に示すページ状態テーブル１４２のデータ構造の一例を示す。ページ状態テーブル１４２はＮＡＮＤ型フラッシュメモリ１１におけるブロック毎に用意されているが、図３においてはブロック番号「１」が割り当てられたブロックのページ状態テーブル１４２が示されている。
FIG. 3 shows an example of the data structure of the page state table 142 shown in FIG. The page state table 142 is prepared for each block in the
図３に示すように、ページ状態テーブル１４２には、ブロックを構成するページ毎に、当該ページに割り当てられたページ番号及び当該ページの状態が対応づけて保持される。なお、ページの状態には、当該ページのデータが有効であることを示す「００」、当該ページのデータが無効であることを示す「０１」及び当該ページのデータが消去済みであることを示す「１０」が含まれる。 As shown in FIG. 3, the page state table 142 stores the page number assigned to the page and the state of the page in association with each page constituting the block. The page status includes “00” indicating that the data on the page is valid, “01” indicating that the data on the page is invalid, and that the data on the page has been erased. “10” is included.
図３に示すページ状態テーブル１４２の例では、ブロック番号「１」が割り当てられたブロックがページ番号「１」〜「８」の各々が割り当てられた複数のページから構成されていることが示されている。また、この複数のページのうち、ページ番号「１」〜「５」が割り当てられたページの状態が有効（つまり、「００」）であり、ページ番号「６」〜「８」が割り当てられたページの状態が消去済み（つまり、「１０」）であることが示されている。 The example of the page state table 142 shown in FIG. 3 indicates that the block to which the block number “1” is assigned is composed of a plurality of pages to which the page numbers “1” to “8” are assigned. ing. Further, among the plurality of pages, the state of the page assigned with the page numbers “1” to “5” is valid (that is, “00”), and the page numbers “6” to “8” are assigned. It is indicated that the state of the page is erased (that is, “10”).
ここではブロック番号「１」が割り当てられたブロックのページ状態テーブル１４２についてのみ説明したが、他のブロックのページ状態テーブル１４２についても同様であるため、その詳しい説明を省略する。 Although only the page state table 142 of the block to which the block number “1” is assigned has been described here, the same applies to the page state table 142 of other blocks, and detailed description thereof is omitted.
なお、上述した消去済みページリスト１４３には、ＮＡＮＤ型フラッシュメモリ１１におけるブロック毎に、ページ状態テーブル１４２において状態「１０」に対応づけられているページ番号が登録（追加）される。図３に示すページ状態テーブル１４２の場合には、ページ番号「１」〜「８」のうち、ページ番号「６」〜「８」が消去済みページリスト１４３に登録される。なお、消去済みページリスト１４３へのページ番号の登録処理は、ページ状態テーブル１４２の更新に伴って実行される。
In the erased
図４は、図１に示す更新履歴リスト１４４のデータ構造の一例を示す。図４に示すように、更新履歴リスト１４４には、バージョン情報に対応づけて、論理アドレス及び物理アドレスが登録される。バージョン情報は、当該バージョン情報に対応づけられている物理アドレスに記憶されているデータ（つまり、更新前データ）に割り当てられたバージョンを表す例えばバージョン番号を含む。なお、バージョン番号は、例えば値が大きいほど新しいバージョンであることを示すものとする。
FIG. 4 shows an example of the data structure of the
図４に示す例では、更新履歴リスト１４４には、バージョン番号「２」に対応づけて、論理アドレス「２」とブロック番号「１」及びページ番号「３」を含む物理アドレスとが登録されている。これによれば、論理アドレス「２」に対応するバージョンが２であるデータが、ブロック番号「１」が割り当てられたブロックを構成するページ番号「３」が割り当てられたページ（の領域）に格納されていることが示されている。
In the example shown in FIG. 4, the
また、更新履歴リスト１４４には、バージョン番号「２」に対応づけて、論理アドレス「１」とブロック番号「１」及びページ番号「１」を含む物理アドレスとが登録されている。これによれば、論理アドレス「１」に対応するバージョンが２であるデータが、ブロック番号「１」が割り当てられたブロックを構成するページ番号「１」が割り当てられたページ（の領域）に格納されていることが示されている。
In the
このように同一のバージョン（番号）に対して異なる複数の論理アドレス（及び物理アドレス）が登録されても構わない。 In this way, a plurality of different logical addresses (and physical addresses) may be registered for the same version (number).
また、図４に示す例では、更新履歴リスト１４４には、バージョン番号「１」に対応づけて、論理アドレス「２」とブロック番号「１」及びページ番号「２」を含む物理アドレスとが登録されている。これによれば、論理アドレス「２」に対応するバージョンが１であるデータが、ブロック番号「１」が割り当てられたブロックを構成するページ番号「２」が割り当てられたページ（の領域）に格納されていることが示されている。
In the example illustrated in FIG. 4, the logical address “2”, the physical address including the block number “1” and the page number “2” are registered in the
なお、ブロック番号「１」が割り当てられたブロックを構成するページ番号「２」が割り当てられたページに格納されているデータ（つまり、論理アドレス「２」に対応するバージョンが１であるデータ）は、上記したブロック番号「１」が割り当てられたブロックを構成するページ番号「３」が割り当てられたページに格納されているデータ（つまり論理アドレス「２」に対応するバージョンが２であるデータ）より古いバージョンのデータである。 Note that the data stored in the page to which the page number “2” constituting the block to which the block number “1” is assigned is stored (that is, data whose version corresponding to the logical address “2” is 1). From the data stored in the page to which the page number “3” constituting the block to which the block number “1” is assigned is stored (that is, the version corresponding to the logical address “2” is 2). Old version of data.
次に、図５のフローチャートを参照して、本実施形態に係るストレージ装置１０において実行されるデータ更新処理の処理手順について説明する。このデータ更新処理は、ユーザによって指定された論理アドレスに対応するデータを更新する際の処理であり、データベースシステムからデータ更新要求が入力された場合に実行される。なお、データ更新要求には、ユーザによって指定された論理アドレス（更新前データに対応する論理アドレス）及び更新後データが含まれる。
Next, with reference to a flowchart of FIG. 5, a processing procedure of data update processing executed in the
まず、データ更新部１３１は、入出力部１２を介して入力されたデータ更新要求を取得する（ステップＳ１）。
First, the
データ更新要求が取得されると、データ更新部１３１は、消去済みページリスト１４３から更新後データを書き込み可能なページ（の物理アドレス）を取得する（ステップＳ２）。以下の説明では、ステップＳ２において取得されたページを便宜的に書き込み先物理ページと称する。
When the data update request is acquired, the
データ更新部１３１は、ＮＡＮＤ型フラッシュメモリ１１にアクセスし、更新後データを書き込み先物理ページに書き込む（ステップＳ３）。
The
次に、データ更新部１３１は、データ更新要求に含まれる論理アドレス（以下、対象論理アドレスと表記）及び当該対象論理アドレスに対応づけて論物変換テーブル１４１に保持されている物理アドレス（つまり、更新前データの物理アドレス）を更新履歴リスト１４４に追加（登録）する（ステップＳ４）。この場合における対象論理アドレス及び更新前データの物理アドレスは、当該更新前データに割り当てられたバージョンを表すバージョン番号に対応づけて登録される。これにより、更新履歴リスト１４４において、更新前データのバージョンが管理される。
Next, the
データ更新部１３１は、対象論理アドレスに対応づけて論物変換テーブル１４１に保持されている物理アドレスを更新後データが書き込まれたページ（つまり、書き込み先物理ページ）の物理アドレス（ブロック番号及びページ番号）に更新することによって、当該論物変換テーブル１４１を更新する（ステップＳ５）。
The
また、データ更新部１３１は、ページ状態テーブル１４２に保持されている書き込み先物理ページの状態を消去済みから有効に変更することによって、ページ状態テーブル１４２を更新する（ステップＳ６）。具体的には、データ更新部１３１は、更新後データが書き込まれたページの物理アドレスに含まれるブロック番号が割り当てられたブロックのページ状態テーブル１４２において、当該物理アドレスに含まれるページ番号に対応づけられている状態を「１０」から「００」に変更する。なお、書き込み先物理ページ（に割り当てられたページ番号）は、消去済みページリスト１４３から削除される。
The
ここで、図６を参照して、上記したデータ更新処理が実行された場合における論物変換テーブル１４１及び更新履歴リスト１４４の遷移について具体的に説明する。
Here, with reference to FIG. 6, the transition of the logical-physical conversion table 141 and the
図６に示すように、データ更新処理が実行される前の論物変換テーブル１４１ｘには、論理アドレス「１」とブロック番号「１」及びページ番号「４」を含む物理アドレスとが対応づけて保持されているものとする。同様に、論物変換テーブル１４１ｘには、論理アドレス「２」とブロック番号「１」及びページ番号「３」を含む物理アドレスとが対応づけて保持されているものとする。 As shown in FIG. 6, in the logical-physical conversion table 141x before the data update process is executed, the logical address “1” is associated with the physical address including the block number “1” and the page number “4”. It shall be retained. Similarly, in the logical-physical conversion table 141x, it is assumed that the logical address “2” and the physical address including the block number “1” and the page number “3” are held in association with each other.
また、データ更新処理が実行される前の更新履歴リスト１４４ｘには、バージョン番号「１」に対応づけて、論理アドレス「２」とブロック番号「１」及びページ番号「２」を含む物理アドレスとが登録されているものとする。 In addition, in the update history list 144x before the data update process is executed, the physical address including the logical address “2”, the block number “1”, and the page number “2” is associated with the version number “1”. Is registered.
この場合において、論理アドレス「２」を含むデータ更新要求が入出力部１２を介して入力された場合を想定する。このとき、消去済みページリスト１４３から取得された書き込み先物理ページの物理アドレスにはブロック番号「１」及びページ番号「５」が含まれているものとする。
In this case, it is assumed that a data update request including the logical address “2” is input via the input /
データ更新要求に含まれる更新後データが書き込み先物理ページに書き込まれると、更新履歴リスト１４４ｘには、論物変換テーブル１４１ｘに保持されている論理アドレス「２」及び物理アドレス（ブロック番号「１」及びページ番号「３」）がバージョン番号「２」に対応づけて登録される。これによれば、更新履歴リスト１４４ｘは、更新履歴リスト１４４ｙに遷移する。
When the updated data included in the data update request is written to the write destination physical page, the update history list 144x includes the logical address “2” and the physical address (block number “1”) held in the logical-physical conversion table 141x. And page number “3”) are registered in association with version number “2”. According to this, the update history list 144x transitions to the
一方、論物変換テーブル１４１ｘに保持されている論理アドレス「２」に対応づけられている物理アドレス（ブロック番号「１」及びページ番号「３」）は、書き込み物理ページの物理アドレス（ブロック番号「１」及びページ番号「５」）に更新される。これによれば、論物変換テーブル１４１ｘは、論物変換テーブル１４１ｙに遷移する。 On the other hand, the physical address (block number “1” and page number “3”) associated with the logical address “2” held in the logical-physical conversion table 141 x is the physical address (block number “ 1 ”and page number“ 5 ”). According to this, the logical-physical conversion table 141x transitions to the logical-physical conversion table 141y.
上記したようなデータ更新処理によれば、データの更新時に、更新前データが記憶されている物理アドレスを当該データが更新された論理アドレスとともに更新履歴リスト１４４に登録することができる。
According to the data update process as described above, when updating data, the physical address where the pre-update data is stored can be registered in the
次に、図７のフローチャートを参照して、本実施形態に係るストレージ装置１０において実行される保存バージョン設定処理の処理手順について説明する。この保存バージョン設定処理は、データを保存すべきバージョンを設定する際の処理であり、保存バージョン設定要求が入力された場合に実行される。なお、保存バージョン設定要求（Version_set(int ver_num)）には、データを保存すべきバージョンを示す値（以下、保存バージョン数と表記）が含まれる。この保存バージョン数は、ユーザによって指定される。
Next, with reference to the flowchart of FIG. 7, the processing procedure of the saved version setting process executed in the
ここでは、上述したデータ更新処理が実行されることによって、更新履歴リスト１４４には各バージョン番号に対応づけて論理アドレス及び物理アドレスが登録されているものとする。
Here, it is assumed that the logical address and the physical address are registered in the
まず、保存バージョン設定部１３２は、入出力部１２を介して入力された保存バージョン設定要求を取得する（ステップＳ１１）。
First, the saved
次に、保存バージョン設定部１３２は、保存バージョン設定要求に含まれる保存バージョン数を設定テーブル１４５に設定する（ステップＳ１２）。
Next, the saved
保存バージョン設定部１３２は、設定テーブル１４５に設定された保存バージョン数に基づいてページ状態テーブル１４２を更新する（ステップＳ１３）。この場合、保存バージョン設定部１３２は、バージョン番号の大きい順に保存バージョン数分のバージョンを残し、当該バージョンより過去のバージョンの物理アドレスによって特定されるページの状態を無効とするようにページ状態テーブル１４２を更新する。これにより、保存バージョン数分のバージョン以外のバージョンのデータが無効とされる。
The saved
ここで、図８及び図９を参照して、ステップＳ１３におけるページ状態テーブル１４２の更新処理について具体的に説明する。 Here, with reference to FIG. 8 and FIG. 9, the update process of the page state table 142 in step S13 will be specifically described.
まず、図８は、保存バージョン設定処理が実行される前の論物変換テーブル１４１、ページ状態テーブル１４２及び更新履歴リスト１４４のデータ構造の一例を示す。
First, FIG. 8 shows an example of the data structure of the logical-physical conversion table 141, the page state table 142, and the
図８に示すように、履歴更新リスト１４４には、バージョン番号「１」及び「２」に対応づけて、論理アドレス及び物理アドレスが登録されているものとする。また、論物変換テーブル１４１に保持されている物理アドレスによって特定されるページ及び更新履歴リスト１４４に登録されている物理アドレスによって特定されるページの状態は、ページ状態テーブル１４２において全て「００」（つまり、有効）であるものとする。
As illustrated in FIG. 8, it is assumed that the logical address and the physical address are registered in the
ここで、保存バージョン数「１」を含む保存バージョン設定要求が入出力部１２を介して入力された場合を想定する。この場合には、バージョン番号が最も大きい１つのバージョン以外のバージョンの物理アドレスによって特定されるページの状態は無効とする。
Here, it is assumed that a stored version setting request including the stored version number “1” is input via the input /
具体的には、図９に示すように、バージョン番号「１」に対応づけて履歴更新リスト１４４に登録されている物理アドレス（ブロック番号「１」及びページ番号「２」）によって特定されるページの状態は「０１」（つまり、無効）に変更される。
Specifically, as shown in FIG. 9, the page specified by the physical address (block number “1” and page number “2”) registered in the
なお、論物変換テーブル１４１に保持されている物理アドレスによって特定されるページ及びバージョン番号「２」に対応づけて履歴更新リスト１４４に登録されている物理アドレスによって特定されるページの状態は「００」（つまり、有効）のままとする。
Note that the page specified by the physical address stored in the logical-physical conversion table 141 and the state of the page specified by the physical address registered in the
上記したような保存バージョン設定処理によれば、ユーザによって指定されたバージョン（つまり、保存バージョン数分のバージョン）のデータを残し、当該バージョンより過去のバージョンのデータについては無効とすることができる。このように過去のバージョンのデータが無効とされたことは、例えば入出力部１２を介してデータベースシステムに通知されることにより、当該データベースシステム側で認識することができる。
According to the saved version setting process as described above, the data of the version designated by the user (that is, the version corresponding to the number of saved versions) is left, and the data of the version earlier than the version can be invalidated. The fact that the past version of the data is invalidated in this way can be recognized on the database system side by notifying the database system via the input /
なお、上記した保存バージョン数としては０を指定することも可能である。この場合には、更新履歴リスト１４４に登録されている物理アドレスによって特定されるページの全ての状態が無効とされる（つまり、論物変換テーブル１４１に保持されている物理アドレスに対応するページのみが有効とされる）。
Note that it is possible to specify 0 as the number of stored versions. In this case, all the states of the page specified by the physical address registered in the
本実施形態においては保存バージョン数がユーザによって指定されるものとして説明したが、データを保存すべきバージョンまたはデータを保存すべきでない（つまり、データを無効とすべき）バージョンを表すバージョン番号がユーザによって直接指定されても構わない。 In this embodiment, the number of stored versions is described as being specified by the user. However, a version number indicating a version in which data is to be stored or a version in which data is not to be stored (that is, data should be invalidated) It may be specified directly by.
次に、図１０のフローチャートを参照して、本実施形態に係るストレージ装置１０において実行されるバージョン確定処理の処理手順について説明する。このバージョン確定処理は、同一のバージョンとして管理される範囲を確定させる際の処理であり、バージョン確定要求が入力された場合に実行される。なお、バージョン確定要求（version_commit()）はユーザの指示に応じて入力される。
Next, with reference to a flowchart of FIG. 10, a processing procedure of version confirmation processing executed in the
なお、以下の説明においては、更新履歴リスト１４４に対応づけて登録されている論理アドレス及び物理アドレスの組を便宜的に論物アドレスと称する。
In the following description, a set of logical addresses and physical addresses registered in association with the
まず、バージョン確定部１３３は、入出力部１２を介して入力されたバージョン確定要求を取得する（ステップＳ２１）。
First, the
バージョン確定要求が取得されると、バージョン確定部１３３は、バージョンが確定されていない論物アドレスが更新履歴リスト１４４に存在する（つまり、バージョン未確定の論物アドレスがある）か否かを判定する（ステップＳ２２）。
When the version determination request is acquired, the
バージョン未確定の論物アドレスがあると判定された場合（ステップＳ２２のＹＥＳ）、バージョン確定部１３３は、更新履歴リスト１４４に登録されている当該論物アドレスを同一のバージョンとして確定する（ステップＳ２３）。つまり、複数のバージョン未確定の論物アドレス（論理アドレス及び物理アドレスの組）が更新履歴リスト１４４に登録されている場合には、当該論物アドレスの全てが同一のバージョンとして確定される。
If it is determined that there is a version-unconfirmed logical / physical address (YES in step S22), the
上記したようにデータ更新処理が実行されることによって更新履歴リスト１４４には、バージョン番号に対応づけて論理アドレス及び物理アドレスが登録されるが、当該データ更新処理（更新履歴リスト１４４への登録処理）の後にバージョン確定部１３３によってバージョンが確定されることによって、当該バージョンの論物アドレスが有効なものとなる。なお、バージョン確定処理によって確定されたバージョンを表すバージョン番号は、入出力部１２を介して出力され、ユーザに対して通知される。これにより、ユーザは、更新履歴リスト１４４に登録されているバージョンについて把握することができる。
By executing the data update process as described above, the logical address and the physical address are registered in the
上記したステップＳ２３の処理によれば、更新履歴リスト１４４において新たなバージョンが追加されることになる（つまり、バージョンが増える）。このため、バージョン確定部１３３は、上記したように設定テーブル１４５に設定された保存バージョン数に基づいてページ状態テーブル１４２を更新する（ステップＳ２４）。なお、このステップＳ２４の処理は、上述した図７に示すステップＳ１３の処理と同様であるため、その詳しい説明を省略する。
According to the processing in step S23 described above, a new version is added to the update history list 144 (that is, the version increases). For this reason, the
上記したようなバージョン確定処理によれば、バージョン確定要求が入力されるまでに更新履歴リスト１４４に登録される論物アドレスを同一のバージョンとして管理することができる（つまり、同一のバージョン番号に対応づけられる）。なお、バージョン確定処理が実行された後にデータ更新処理が実行された場合には、次のバージョンを示すバージョン情報に対応づけて論物アドレスが更新履歴リストに登録されることになる。
According to the version determination process as described above, the logical and physical addresses registered in the
また、バージョン確定要求が入力されるまでに論理アドレスが共通する複数の論物アドレスが更新履歴リスト１４４に登録される場合には、後に実行されるデータ更新処理による論物アドレスのみが登録される。
In addition, when a plurality of logical / physical addresses having a common logical address are registered in the
また、上記したバージョン確定処理（つまり、バージョン確定要求の入力）は、例えば一連の処理（トランザクション）単位で行われるものとする。 Further, it is assumed that the above-described version confirmation process (that is, input of a version confirmation request) is performed in a series of processes (transactions), for example.
次に、図１１のフローチャートを参照して、本実施形態に係るストレージ装置１０において実行されるバージョン復元処理の処理手順について説明する。このバージョン復元処理は、特定のバージョンの状態に論物変換テーブル１４１を復元する際の処理であり、バージョン復元要求が入力された場合に実行される。なお、バージョン復元要求（version_restore(int ver_num)）には、復元の対象となるバージョンを表すバージョン番号が含まれる。このバージョン番号は、ユーザによって指定される。
Next, with reference to the flowchart of FIG. 11, a processing procedure of version restoration processing executed in the
ここでは、上述したデータ更新処理及びバージョン確定処理が実行されることによって、更新履歴リスト１４４には各バージョン情報に対応づけて論物アドレス（論理アドレス及び物理アドレス）が登録されているものとする。
Here, it is assumed that the logical address (logical address and physical address) is registered in the
まず、バージョン復元部１３４は、入出力部１２を介して入力されたバージョン復元要求を取得する（ステップＳ３１）。
First, the
次に、バージョン復元部１３４は、バージョン復元要求に含まれるバージョン番号に対応づけて更新履歴リスト１４４に登録されている論理アドレスを取得する（ステップＳ３２）。以下の説明においては、ステップＳ３２において取得された論理アドレスを対象論理アドレスと称する。
Next, the
バージョン復元部１３４は、対象論理アドレスに対応づけて論物変換テーブル１４１に保持されている物理アドレスを取得する（ステップＳ３３）。
The
バージョン復元部１３４は、対象論理アドレス及びステップＳ３３において取得された物理アドレスを更新履歴リスト１４４に追加する（ステップＳ３４）。
The
次に、バージョン復元部１３４は、バージョン復元要求に含まれるバージョン番号に対応づけて更新履歴リスト１４４に登録されている論理アドレス（対象論理アドレス）及び物理アドレスを取得する（ステップＳ３５）。
Next, the
バージョン復元部１３４は、ステップＳ３５において取得された論理アドレスに対応づけて論物変換テーブル１４１に保持されている物理アドレスを、ステップＳ３５において取得された物理アドレスに変更する（ステップＳ３６）。これによって、ユーザによって指定されたバージョンの論物アドレスが論物変換テーブル１４１に復元される。
The
ここで、図１２を参照して、上記したバージョン復元処理が実行された場合における論物変換テーブル１４１及び更新履歴リスト１４４の遷移について具体的に説明する。
Here, with reference to FIG. 12, the transition of the logical-physical conversion table 141 and the
ここでは、図１２に示すように、バージョン復元処理が実行される前の論物変換テーブル１４１ａには、論理アドレス「１」とブロック番号「１」及びページ番号「４」を含む物理アドレスとが対応づけて保持されているものとする。同様に、論物変換テーブル１４１ａには、論理アドレス「２」とブロック番号「１」及びページ番号「５」を含む物理アドレスとが対応づけて保持されているものとする。 Here, as shown in FIG. 12, the logical-physical conversion table 141a before the version restoration process is executed includes a logical address “1”, a physical address including a block number “1”, and a page number “4”. Assume that they are held in correspondence. Similarly, in the logical-physical conversion table 141a, it is assumed that the logical address “2” is associated with the physical address including the block number “1” and the page number “5”.
また、バージョン復元処理が実行される前の更新履歴リスト１４４ａには、バージョン番号「２」に対応づけて、論理アドレス「２」とブロック番号「１」及びページ番号「３」を含む物理アドレスとが登録されているものとする。同様に、更新履歴リスト１４４ａには、バージョン番号「２」に対応づけて、論理アドレス「１」とブロック番号「１」及びページ番号「１」を含む物理アドレスとが登録されているものとする。更に、更新履歴リスト１４４ａには、バージョン番号「１」に対応づけて、論理アドレス「２」とブロック番号「１」及びページ番号「２」を含む物理アドレスとが登録されているものとする。 In addition, in the update history list 144a before the version restoration process is executed, the physical address including the logical address “2”, the block number “1”, and the page number “3” is associated with the version number “2”. Is registered. Similarly, in the update history list 144a, a logical address “1”, a physical address including a block number “1” and a page number “1” are registered in association with the version number “2”. . Furthermore, it is assumed that a logical address “2”, a physical address including a block number “1” and a page number “2” are registered in the update history list 144a in association with the version number “1”.
ここで、バージョン番号「２」を含むバージョン復元要求が入出力部１２を介して入力された場合を想定する。この場合、バージョン復元部１３４は、バージョン復元要求に含まれるバージョン番号「２」に対応づけて更新履歴リスト１４４ａに登録されている論理アドレスを取得する。図１２に示す例では、論理アドレス「１」及び論理アドレス「２」が更新履歴リスト１４４ａから取得される。
Here, it is assumed that a version restoration request including the version number “2” is input via the input /
このように複数の論理アドレスが取得された場合には、当該論理アドレスの各々について上述した図１１に示すステップＳ３２以降の処理が実行される。 When a plurality of logical addresses are acquired in this way, the processing after step S32 shown in FIG. 11 described above is executed for each of the logical addresses.
まず、論理アドレス「１」に関する処理について説明する。この場合、バージョン復元部１３４は、論理アドレス「１」に対応づけて論物変換テーブル１４１ａに保持されている物理アドレスを取得する。図１２に示す論物変換テーブル１４１ａによれば、ブロック番号「１」及びページ番号「４」を含む物理アドレスが取得される。
First, processing related to the logical address “1” will be described. In this case, the
この場合、バージョン復元部１３４は、論理アドレス「１」及び取得された物理アドレス（ブロック番号「１」及びページ番号「４」）を更新履歴リスト１４４ａに追加する。この場合における論理アドレス及び物理アドレスは、バージョン番号「３」（つまり、新しいバージョン）に対応づけて更新履歴リスト１４４に登録される。これによれば、更新履歴リスト１４４ａは、更新履歴リスト１４４ｂに遷移する。
In this case, the
一方、バージョン復元部１３４は、バージョン復元要求に含まれるバージョン番号「２」に対応づけて更新履歴リスト１４４ｂに登録されている論物アドレスを取得する。ここでは、論理アドレス「１」とブロック番号「１」及びページ番号「１」を含む物理アドレスとが取得される。
On the other hand, the
この場合、バージョン復元部１３４は、ブロック番号「１」及びページ番号「１」を含む物理アドレスを、論理アドレス「１」に対応づけて論物変換テーブル１４１ａに書き込む。これによれば、論物変換テーブル１４１ａは、論物変換テーブル１４１ｂに遷移する。
In this case, the
次に、論理アドレス「２」に関する処理について説明する。この場合、バージョン復元部１３４は、論理アドレス「２」に対応づけて論物変換テーブル１４１ｂに保持されている物理アドレスを取得する。図１２に示す論物変換テーブル１４１ｂによれば、ブロック番号「１」及びページ番号「５」を含む物理アドレスが取得される。
Next, processing relating to the logical address “2” will be described. In this case, the
この場合、バージョン復元部１３４は、論理アドレス「２」及び取得された物理アドレス（ブロック番号「１」及びページ番号「５」）を更新履歴リスト１４４ｂに追加する。この場合における論理アドレス及び物理アドレスは、バージョン番号「３」に対応づけて更新履歴リスト１４４ｂに登録される。これによれば、更新履歴リスト１４４ｂは、更新履歴リスト１４４ｃに遷移する。
In this case, the
一方、バージョン復元部１３４は、バージョン復元要求に含まれるバージョン番号「２」に対応づけて更新履歴リスト１４４ｂに登録されている論物アドレスを取得する。ここでは、論理アドレス「２」とブロック番号「１」及びページ番号「３」を含む物理アドレスとが取得される。
On the other hand, the
この場合、バージョン復元部１３４は、ブロック番号「１」及びページ番号「３」を含む物理アドレスを、論理アドレス「２」に対応づけて論物変換テーブル１４１ｂに書き込む。これによれば、論物変換テーブル１４１ｂは、論物変換テーブル１４１ｃに遷移する。
In this case, the
上記したようなバージョン復元処理によれば、ユーザによって指定されたバージョン番号（によって表されるバージョン）の論物アドレスが論物変換テーブル１４１に復元されるとともに、当該論物変換テーブル１４１に保持されていた論物アドレスが更新履歴リスト１４４に登録される。
According to the version restoration process as described above, the logical / physical address of the version number designated by the user (the version represented by) is restored to the logical / physical conversion table 141 and held in the logical / physical conversion table 141. The stored logical address is registered in the
なお、バージョン復元要求に含まれるバージョン番号が更新履歴リスト１４４に存在しない場合、または上述した保存バージョン設定処理及びバージョン確定処理によって当該バージョン番号に対応づけて更新履歴リスト１４４に登録されている物理アドレスによって特定されるページの状態が無効とされている場合には、エラーがユーザに対して通知されるものとする。
Note that if the version number included in the version restoration request does not exist in the
次に、図１３のフローチャートを参照して、前述したデータ消去部１３５によって実行されるガベージコレクション（ＧＣ）の処理手順について説明する。なお、ガベージコレクションは、ＮＡＮＤ型フラッシュメモリ１１における書き込み領域の確保処理であり、例えば予め定められた期間毎に実行される。
Next, a garbage collection (GC) processing procedure executed by the
ガベージコレクションにおいては、ＮＡＮＤ型フラッシュメモリ１１における各ブロックについて以下のステップＳ４１〜Ｓ４５の処理が実行される。以下、この処理の対象となるブロックを対象ブロックと称する。
In the garbage collection, the following steps S41 to S45 are executed for each block in the
まず、データ消去部１３５は、対象ブロックのページ状態テーブル１４２を参照して、当該対象ブロックを構成する複数のページのうち、状態が無効であるページ（以下、無効ページと表記）の割合が閾値以上であるか否かを判定する（ステップＳ４１）。
First, the
無効ページの割合が閾値以上であると判定された場合（ステップＳ４１のＹＥＳ）、データ消去部１３５は、対象ブロック以外の各ブロックのページ状態テーブル１４２を参照して、消去済みブロックを特定する（ステップＳ４２）。なお、消去済みブロックは、状態が消去済みであるページのみから構成されるブロックである。
When it is determined that the ratio of invalid pages is equal to or greater than the threshold (YES in step S41), the
次に、データ消去部１３５は、対象ブロックのページ状態テーブル１４２を参照して、当該対象ブロックを構成する複数のページのうち、状態が有効であるページ（以下、有効ページと表記）のデータをＮＡＮＤ型フラッシュメモリ１１から取得する。なお、このデータは、対象ブロックに割り当てられたブロック番号及び有効ページに割り当てられたページ番号（つまり、物理アドレス）に基づいて取得される。データ消去部１３５は、取得されたデータを、上記した消去済みブロック（を構成するページ）にコピーする（ステップＳ４３）。以下、有効ページのデータがコピーされたページをコピー先ページと称する。
Next, the
なお、ページ状態テーブル１４２において、上記したように消去済みブロックを構成する各ページの状態は消去済みである。したがって、上記したステップＳ４４の処理が実行された場合には、ページ状態テーブル１４２におけるコピー先ページの状態（当該ページに割り当てられたページ番号に対応づけてページ状態テーブル１４２に保持されている状態）は、消去済みから有効に更新される。 In the page state table 142, the state of each page constituting the erased block is erased as described above. Therefore, when the process of step S44 described above is executed, the status of the copy destination page in the page status table 142 (the status held in the page status table 142 in association with the page number assigned to the page). Are effectively updated from erased.
また、有効ページの物理アドレスが論物変換テーブル１４１に保持されている場合、当該論物変換テーブル１４１において、当該有効ページの物理アドレスは、コピー先ページの物理アドレスに更新される。同様に、有効ページの物理アドレスが更新履歴リスト１４４に登録されている場合には、当該更新履歴リスト１４４において、当該有効ページの物理アドレスは、コピー先ページの物理アドレスに更新される。
Further, when the physical address of the valid page is held in the logical-physical conversion table 141, the physical address of the valid page is updated to the physical address of the copy destination page in the logical-physical conversion table 141. Similarly, when the physical address of the valid page is registered in the
次に、データ消去部１３５は、対象ブロック（を構成する複数のページ）のデータを消去する（ステップＳ４４）。これによれば、対象ブロックは、消去済みブロックとなり、データの書き込みが可能となる。
Next, the
このように対象ブロックが消去済みブロックとなる場合、当該対象ブロックのページ状態テーブル１４２における各ページの状態は消去済みに更新される。 When the target block becomes an erased block in this way, the status of each page in the page status table 142 of the target block is updated to erased.
ここで、ＮＡＮＤ型フラッシュメモリ１１における全てのブロックについてステップＳ４１〜Ｓ４４の処理が実行されたか否かが判定される（ステップＳ４５）。 Here, it is determined whether or not the processing of steps S41 to S44 has been executed for all blocks in the NAND flash memory 11 (step S45).
全てのブロックについて処理が実行されていないと判定された場合（ステップＳ４５のＮＯ）、上述したステップＳ４１に戻って処理が繰り返される。この場合、ステップＳ４１〜Ｓ４４の処理が実行されていないブロックを対象ブロックとして処理が実行される。 If it is determined that the processing has not been executed for all the blocks (NO in step S45), the process returns to step S41 described above and the processing is repeated. In this case, the process is executed with a block for which the process of steps S41 to S44 is not executed as a target block.
一方、全てのブロックについて処理が実行されたと判定された場合（ステップＳ４５のＹＥＳ）、ガベージコレクションは終了される。 On the other hand, if it is determined that the processing has been executed for all the blocks (YES in step S45), the garbage collection is terminated.
なお、上記したステップＳ４１において無効ページの割合が閾値以上でないと判定された場合には、ステップＳ４５の処理が実行される。 If it is determined in step S41 that the ratio of invalid pages is not greater than or equal to the threshold value, the process of step S45 is executed.
上記したようなガベージコレクションによれば、保存バージョン設定処理及びバージョン確定処理によって状態が無効とされたページ（から構成されるブロック）がコントローラ１３側で自動的に削除される。
According to the garbage collection as described above, a page (a block constituted by a state) invalidated by the saved version setting process and the version confirmation process is automatically deleted on the
上記したように本実施形態においては、ＮＡＮＤ型フラッシュメモリ（不揮発性の半導体記憶装置）１１に記憶されているデータを管理するコントローラ（ＮＡＮＤコントローラ）１３が、データの更新時に論物変換テーブル１４１に保持されている論理アドレス及び物理アドレスをバージョン情報に対応づけて更新履歴リスト１４４に登録し、当該更新履歴リスト１４４に登録されたバージョン情報に基づいて当該バージョン情報に対応づけて更新履歴リスト１４４に登録された物理アドレスに記憶されているデータを消去する。
As described above, in the present embodiment, the controller (NAND controller) 13 that manages the data stored in the NAND flash memory (nonvolatile semiconductor storage device) 11 is stored in the logical-physical conversion table 141 when the data is updated. The held logical address and physical address are registered in the
すなわち、本実施形態においては、ストレージ装置１０が備えるコントローラ（ＮＡＮＤコントローラ）１３がデータのバージョン管理を行い、当該コントローラ１３によるガベージコレクションの実行時に不要なバージョンのデータが自動的に消去される。このため、本実施形態においては、データベースのロックを伴うバキューム処理等がデータベースシステム側で実行されることなく不要データの消去を行うことが可能となる。
That is, in this embodiment, the controller (NAND controller) 13 included in the
また、本実施形態においては、ユーザによって指定されたバージョン（つまり、保存バージョン数分のバージョン）より過去のバージョンのデータが消去されるため、ユーザの意図するバージョンのデータを消去することができる。 In the present embodiment, data of a past version is erased from versions specified by the user (that is, versions corresponding to the number of saved versions), so that the version data intended by the user can be erased.
更に、本実施形態においては、ユーザによって指定されたバージョン番号に対応づけて更新履歴リスト１４４に登録されている論物アドレスを論物変換テーブル１４１に復元することにより、例えば誤ってデータが書き込まれた場合や最新のデータ（つまり、論物変換テーブル１４１に保持されている物理アドレスに記憶されているデータ）が破損したような場合に、必要に応じて過去のバージョンのデータを利用することが可能となる。
Furthermore, in this embodiment, by restoring the logical / physical address registered in the
また、本実施形態においては、バージョン確定要求が入力されるまでに更新履歴リストに登録された論物アドレスが同一のバージョンとして管理されることにより、例えば一連の処理（トランザクション）単位でのバージョン管理、データの復元及び消去等が可能となる。 In this embodiment, logical addresses registered in the update history list are managed as the same version until a version confirmation request is input, so that version management in a series of processing (transactions), for example, is performed. Data can be restored and erased.
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。 Although several embodiments of the present invention have been described, these embodiments are presented by way of example and are not intended to limit the scope of the invention. These embodiments can be implemented in various other forms, and various omissions, replacements, and changes can be made without departing from the spirit of the invention. These embodiments and their modifications are included in the scope and gist of the invention, and are also included in the invention described in the claims and the equivalents thereof.
１０…ストレージ装置、１１…ＮＡＮＤ型フラッシュメモリ、１２…入出力部、１３…コントローラ、１４…メモリ、１３１…データ更新部、１３２…保存バージョン設定部、１３３…バージョン確定部、１３４…バージョン復元部、１３５…データ消去部、１４１…論物変換テーブル、１４２…ページ状態テーブル、１４３…消去済みページリスト、１４４…更新履歴リスト、１４５…設定テーブル
DESCRIPTION OF
Claims (5)
前記半導体記憶装置に記憶されているデータのバージョンを管理し、ガベージコレクションの実行時に不要なバージョンのデータを自動的に消去するコントローラと、
前記データベースシステムにおいて用いられる論理アドレスの各々に対応づけて当該論理アドレスに対応するデータの物理アドレスを保持する論物変換テーブル及び更新履歴リストを記憶するメモリと
を具備し、
前記半導体記憶装置は、ＮＡＮＤ型フラッシュメモリを含み、
前記物理アドレスは、前記ＮＡＮＤ型フラッシュメモリにおけるブロックを構成するページを特定し、
前記データの消去は、複数のページから構成されるブロック単位で行われ、
前記コントローラは、
ユーザによって指定された論理アドレスに対応する第１のデータを第２のデータに更新するためのデータ更新要求が前記データベースシステムから入力された場合、当該第２のデータを当該第１のデータの第１の物理アドレスとは異なる第２の物理アドレスによって特定されるページに書き込むデータ更新手段と、
前記ユーザによって指定された論理アドレス及び当該論理アドレスに対応づけて前記論物変換テーブルに保持されている第１の物理アドレスを、前記第１のデータに割り当てられたバージョンを示すバージョン情報に対応づけて前記更新履歴リストに登録する登録手段と、
前記ユーザによって指定された論理アドレスに対応づけて前記論物変換テーブルに保持されている第１の物理アドレスを前記第２の物理アドレスに更新するテーブル更新手段と、
前記更新履歴リストに登録されたバージョン情報に基づいて、当該バージョン情報に対応づけて前記更新履歴リストに登録された第１の物理アドレスによって特定されるページの状態を無効とする無効化手段と、
前記状態が無効とされたページを含む第１のブロックを構成する複数のページのうち、状態が無効であるページの割合が閾値以上である場合、当該複数のページのうち状態が有効であるページに書き込まれている第３のデータを前記第１のブロック以外の第２のブロックを構成するページにコピーするコピー手段と、
前記第１のブロックを構成する複数のページに書き込まれているデータを消去する消去手段と
を含む
ことを特徴とするストレージ装置。 In a storage device equipped with a non-volatile semiconductor storage device that stores various data, and in which a database system that executes multi-version simultaneous execution control to a database using the semiconductor storage device is mounted,
A controller for managing a version of data stored in the semiconductor storage device, and automatically erasing unnecessary version data at the time of garbage collection ;
A logical-physical conversion table that holds a physical address of data corresponding to the logical address in association with each logical address used in the database system, and a memory that stores an update history list.
The semiconductor memory device includes a NAND flash memory,
The physical address specifies a page constituting a block in the NAND flash memory,
The erasing of the data is performed in units of blocks composed of a plurality of pages,
The controller is
When a data update request for updating the first data corresponding to the logical address designated by the user to the second data is input from the database system, the second data is changed to the first data of the first data. Data updating means for writing to a page specified by a second physical address different from the one physical address;
The logical address designated by the user and the first physical address held in the logical-physical conversion table in association with the logical address are associated with version information indicating the version assigned to the first data. Registration means for registering in the update history list;
Table updating means for updating a first physical address held in the logical-physical translation table in association with a logical address designated by the user to the second physical address;
Based on the version information registered in the update history list, invalidating means for invalidating the state of the page specified by the first physical address registered in the update history list in association with the version information ;
Among the plurality of pages constituting the first block including the page in which the state is invalid, when the ratio of pages in which the state is invalid is equal to or greater than the threshold, the page in which the state is valid among the plurality of pages A copy means for copying the third data written in to a page constituting a second block other than the first block;
An erasing unit for erasing data written on a plurality of pages constituting the first block .
前記登録手段は、ユーザの指示に基づくバージョン確定要求が入力されるまでは同一のバージョンを示すバージョン情報に対応づけて前記論理アドレス及び前記第１の物理アドレスを前記更新履歴リストに登録し、
前記バージョン確定手段は、前記バージョン確定要求が入力された場合に前記更新履歴リストに登録された論理アドレス及び第１の物理アドレスを前記同一のバージョンとして確定する
ことを特徴とする請求項１記載のストレージ装置。 The controller further includes a version determining means,
The registration means registers the logical address and the first physical address in the update history list in association with version information indicating the same version until a version confirmation request based on a user instruction is input,
2. The version determination unit according to claim 1, wherein the version determination unit determines the logical address and the first physical address registered in the update history list as the same version when the version determination request is input. Storage device.
ユーザによって指定された論理アドレスに対応する第１のデータを第２のデータに更新するためのデータ更新要求が前記データベースシステムから入力された場合、当該第２のデータを当該第１のデータの第１の物理アドレスとは異なる第２の物理アドレスによって特定されるページに書き込むステップと、
前記ユーザによって指定された論理アドレス及び当該論理アドレスに対応づけて前記論物変換テーブルに保持されている第１の物理アドレスを、前記第１のデータに割り当てられたバージョンを示すバージョン情報に対応づけて前記更新履歴リストに登録するステップと、
前記ユーザによって指定された論理アドレスに対応づけて前記論物変換テーブルに保持されている第１の物理アドレスを前記第２の物理アドレスに更新するステップと、
前記更新履歴リストに登録されたバージョン情報に基づいて、当該バージョン情報に対応づけて前記更新履歴リストに登録された第１の物理アドレスによって特定されるページの状態を無効とするステップと、
前記状態が無効とされたページを含む第１のブロックを構成する複数のページのうち、状態が無効であるページの割合が閾値以上である場合、当該複数のページのうち状態が有効であるページに書き込まれている第３のデータを前記第１のブロック以外の第２のブロックを構成するページにコピーするステップと、
前記第１のブロックを構成する複数のページに書き込まれているデータを消去するステップと
を具備することを特徴とするデータ管理方法。 A storage device in which a database system that executes multi-version simultaneous execution control to a database using a nonvolatile semiconductor storage device that stores various data is mounted, and the version of the data stored in the semiconductor storage device is A controller that manages and automatically erases unnecessary versions of data when executing garbage collection, and holds the physical address of the data corresponding to the logical address in association with each logical address used in the database system. A memory for storing a physical conversion table and an update history list , wherein the semiconductor memory device includes a NAND flash memory, the physical address specifies a page constituting a block in the NAND flash memory, and erases the data Is it multiple pages In the storage device Ru performed in configured block, a data management method in which the controller performs,
When a data update request for updating the first data corresponding to the logical address designated by the user to the second data is input from the database system, the second data is changed to the first data of the first data. Writing to a page specified by a second physical address different from the one physical address;
The logical address designated by the user and the first physical address held in the logical-physical conversion table in association with the logical address are associated with version information indicating the version assigned to the first data. Registering in the update history list,
Updating a first physical address held in the logical-physical translation table in association with a logical address designated by the user to the second physical address;
Based on the version information registered in the update history list, invalidating the state of the page specified by the first physical address registered in the update history list in association with the version information ;
Among the plurality of pages constituting the first block including the page in which the state is invalid, when the ratio of pages in which the state is invalid is equal to or greater than the threshold, the page in which the state is valid among the plurality of pages Copying the third data written to the page constituting the second block other than the first block;
And a step of erasing data written in a plurality of pages constituting the first block .
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2014033162A JP6242711B2 (en) | 2014-02-24 | 2014-02-24 | Storage apparatus and data management method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2014033162A JP6242711B2 (en) | 2014-02-24 | 2014-02-24 | Storage apparatus and data management method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2015158797A JP2015158797A (en) | 2015-09-03 |
| JP6242711B2 true JP6242711B2 (en) | 2017-12-06 |
Family
ID=54182743
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2014033162A Expired - Fee Related JP6242711B2 (en) | 2014-02-24 | 2014-02-24 | Storage apparatus and data management method |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP6242711B2 (en) |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FI109620B (en) * | 1999-10-26 | 2002-09-13 | Tellabs Oy | Method and arrangement for implementing atomic updates using a logical flash memory device |
| US7243088B2 (en) * | 2003-08-06 | 2007-07-10 | Oracle International Corporation | Database management system with efficient version control |
| JP5137413B2 (en) * | 2006-11-28 | 2013-02-06 | 株式会社日立製作所 | Semiconductor memory device |
| JP4623318B2 (en) * | 2007-01-24 | 2011-02-02 | 日本電気株式会社 | Write-once database management system, unnecessary area repair processing method, and unnecessary area repair program |
| US9251214B2 (en) * | 2010-04-08 | 2016-02-02 | Microsoft Technology Licensing, Llc | In-memory database system |
| CN103270487B (en) * | 2011-02-02 | 2016-06-22 | 株式会社日立制作所 | Storage system and data control method thereof |
-
2014
- 2014-02-24 JP JP2014033162A patent/JP6242711B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2015158797A (en) | 2015-09-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110678836B (en) | Persistent memory for key value storage | |
| EP2203825B1 (en) | Apparatus using flash memory as storage and method of operating the same | |
| US9183236B2 (en) | Low level object version tracking using non-volatile memory write generations | |
| KR101965549B1 (en) | Methods, devices and systems for two stage power-on map rebuild with free space accounting in a solid state drive | |
| US8762661B2 (en) | System and method of managing metadata | |
| US20080120488A1 (en) | Apparatus and method of managing nonvolatile memory | |
| JP5120455B2 (en) | Garbage collection program, garbage collection method, and garbage collection system | |
| JP2012203443A (en) | Memory system and control method of memory system | |
| KR101336258B1 (en) | Apparatus and method of processing data of non-volatile memory | |
| JP2005242897A (en) | Flash disk drive | |
| JP5183662B2 (en) | Memory control device and memory control method | |
| TWI676933B (en) | Firmware updating method | |
| KR20110046118A (en) | Adaptive logging apparatus and method | |
| JP2009205689A (en) | Flash disk device | |
| JP6242711B2 (en) | Storage apparatus and data management method | |
| JP4513786B2 (en) | Memory controller, memory system, and memory control method | |
| JP6788386B2 (en) | File access provision methods, computers, and software products | |
| US20130311716A1 (en) | Memory controller | |
| JP2023056222A (en) | Storage system and data copying method for storage system | |
| JP2013109404A (en) | Information processing device | |
| TWI850721B (en) | In-memory journal | |
| US12039193B2 (en) | Apparatus, method and computer program for managing memory page updates within non-volatile memory | |
| US11150940B2 (en) | System and method for recording transaction associated with a page-oriented non-volatile memory | |
| TWI856880B (en) | Non-transitory computer-readable medium, storage device and storage method | |
| JP6644427B2 (en) | FAT file system and its program |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20160923 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20170714 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20170725 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20170922 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20171010 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20171108 |
|
| R151 | Written notification of patent or utility model registration |
Ref document number: 6242711 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R151 |
|
| LAPS | Cancellation because of no payment of annual fees |