KR101456104B1

KR101456104B1 - Method, system for dual buffering file management with non-volatile memory and mass storage device using the same

Info

Publication number: KR101456104B1
Application number: KR1020130036737A
Authority: KR
Inventors: 반효경; 이은지; 장지은
Original assignee: 이화여자대학교 산학협력단
Priority date: 2013-04-04
Filing date: 2013-04-04
Publication date: 2014-11-04
Also published as: KR20140121013A

Abstract

본 발명의 듀얼 버퍼링 파일 관리 시스템은 체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록의 직전 버전 블록들을 비휘발성 스토리지에서 탐색하고, 탐색 결과에 따라 쓰기 대상 블록을 선정하는 쓰기 블록 선정부, 선정된 쓰기 대상 블록에 체크포인트 트랜잭션에 포함된 데이터를 비휘발성 스토리지에 쓰기 연산하는 쓰기 연산 처리부 및 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록 구성된 원본 트리 구조의 루트 노드를 호스트 시스템이 포인팅하도록 설정하는 트리 구조 관리부를 포함할 수 있다. 비휘발성 스토리지는 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하는 원본 트리 구조와, 직전 버전 블록들 및 갱신되지 않은 원본 블록들을 포인팅하는 직전 트리 구조를 저장할 수 있다.The dual buffering file management system of the present invention is a dual buffering file management system for searching a non-volatile storage for the previous version blocks of an original block corresponding to data included in a checkpoint transaction and selecting a write block according to a search result, A write operation processor for writing the data included in the checkpoint transaction to the nonvolatile storage in the write target block, and a root node of the source tree structure configured to point to the newly written data blocks and the unrecovered original blocks, And a tree structure management unit for setting the tree structure to be pointing. The non-volatile storage may store a source tree structure for pointing newly written data blocks and original blocks that have not been updated, and a previous tree structure for pointing to previous version blocks and original blocks that have not been updated.

Description

FIELD OF THE INVENTION [0001] The present invention relates to a dual buffering file management method, a file management system, and a mass storage apparatus for a nonvolatile memory.

본 발명은 파일 시스템에 관한 것으로, 더욱 상세하게는, 비휘발성 메모리를 위한 파일 시스템에 관한 것이다.FIELD OF THE INVENTION The present invention relates to file systems, and more particularly, to file systems for non-volatile memory.

최근 상변화 메모리(PCM) 기술, 자기 저항 메모리(MRAM) 등의 차세대 비휘발성 메모리 기술이 급격하게 발전하면서 곧 상용화될 것으로 예상된다.Recently, next generation nonvolatile memory technologies such as phase change memory (PCM) technology and magnetoresistive memory (MRAM) are expected to be commercialized soon after the rapid development.

차세대 메모리 기술들은 랜덤 액세스, 즉 임의의 주소에 곧바로 접근하여 읽기와 쓰기가 가능한 점에서 현재의 디램 기술을 대체할 수 있고, 비교적 저렴하게 대용량으로 생산될 수 있다는 점에서 현재의 플래시 메모리 기반의 대용량 스토리지 기술도 대체할 수 있어서, 차세대 비휘발성 메모리 기술을 이용한 비휘발성 메모리 소자들을 메인 메모리, 캐시 또는 스토리지로서 최대한 활용하기 위한 파일 관리 기법들도 폭넓게 개발되고 있다.The next generation memory technologies can replace the current DRAM technology in terms of random access, that is, access to arbitrary addresses and read and write, and can be produced at a relatively low cost. Therefore, Storage technologies can also be substituted, and file management techniques are being developed to take full advantage of nonvolatile memory devices using next generation nonvolatile memory technology as main memory, cache, or storage.

특히 PCM은 다른 기술에 비해 읽기 속도가 디램에 비견될 정도로 빠르고 저전력이며 집적도가 높아 유력한 기술로 전망되지만, 쓰기 시의 속도가 다소 느리고 전력 소비가 많으며 셀당 1 억번 정도로 쓰기 횟수 제한이 있다.In particular, PCM is expected to be a viable technology because it has a speed comparable to that of other technologies, but it is low in power and high in density. However, PCM is slow in writing, consumes a lot of power, and has a write limit of about 100 million times per cell.

따라서 PCM을 이용한 메모리 장치의 성능 향상을 위해서는 쓰기 연산을 효율적으로 수행하는 파일 관리 기술이 필요하다.Therefore, to improve the performance of the memory device using the PCM, a file management technique for efficiently performing the write operation is required.

DCW(Data-Comparison Write) 기법은 이러한 요청에 응답하여 제안된 것으로 갱신될 데이터를 쓰기 전에 기존에 저장된 데이터와 비교하여 변경된 부분만 PCM 기반 메모리 장치에 쓰기 연산하는 기법이다. 실제로 쓰기 연산되어야 하는 셀이 크게 줄어드므로 성능 향상을 기대할 수 있다. 그러나, 기존 데이터와 갱신 데이터 사이의 유사도가 높아야 효과가 있기 때문에 유사도가 높은 위치를 찾기 위해 해밍 거리(Hamming distance)를 연산하여야 하는 등 부가되는 오버헤드가 커서 실제로는 효과적으로 적용하기 어렵다.The DCW (Data-Comparison Write) technique is a technique that responds to such a request and writes the changed data to the PCM-based memory device by comparing the previously stored data with the previously stored data before writing the data to be updated. Since the number of cells that actually need to be written is greatly reduced, performance improvement can be expected. However, since the degree of similarity between the existing data and the update data is high, there is an additional overhead such that a Hamming distance is required to find a position having a high degree of similarity.

또한, 시스템 고장(system failure)이 일어난다면, 그 시점에 기록하고 있던 데이터는 갱신 전의 원본 데이터도 아니고 갱신된 후의 데이터도 아니어서 원자성(atomicity)을 보장할 수 없다.In addition, if a system failure occurs, the data recorded at that point can not guarantee atomicity since neither the original data before the update nor the updated data.

한편 어느 정도 원자성을 보장하기 위해, COW(Copy-on-wirte) 기법이 제안되었는데, 이는 작은 데이터의 경우에는 원본 위에 덮어 쓰고, 큰 데이터가 수정되면 원본 위에 덮어 쓰는 대신에 빈 공간을 선택하고 원본 중 수정되지 않은 부분을 복사한 다음 복사된 원본에 수정된 부분을 붙여(append) 하나의 수정된 블록을 완성하는 기법이다. 이를 통해 원자성을 어느 정도 보장할 수 있지만, 추가적인 수정 시에 빈 공간을 계속 찾아야 하므로 저장 공간에 여유가 줄어들면 성능이 급격히 저하할 것으로 예측된다.On the other hand, COW (copy-on-wirte) technique has been proposed in order to guarantee some atomicity, in which the original data is overwritten in the case of small data and the empty space is selected instead of overwriting the original data It is a technique of copying an unmodified portion of an original and then appending the modified portion to the copied original to complete one modified block. Although this can guarantee some degree of atomicity, it is expected that the performance will decrease drastically if the free space in the storage space is reduced because the vacant space must be continuously found in the additional modification.

본 발명이 해결하고자 하는 과제는 별도의 유사도 연산과 같은 오버헤드 없이 데이터 비교 쓰기 기법을 수행하여 쓰기 부하를 줄이면서 동시에 데이터의 일관성을 보장할 수 있는 비휘발성 메모리를 위한 듀얼 버퍼링 파일 관리 방법, 파일 관리 시스템 및 대용량 저장 장치를 제공하는 데에 있다.The present invention is directed to a dual buffering file management method for a nonvolatile memory capable of simultaneously ensuring data consistency while reducing a write load by performing a data comparison and writing technique without any overhead such as similarity calculation, Management system and a mass storage device.

본 발명의 일 측면에 따른 듀얼 버퍼링 파일 관리 시스템은,A dual buffering file management system according to an aspect of the present invention includes:

체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록의 직전 버전 블록들을 비휘발성 스토리지에서 탐색하고, 탐색 결과에 따라 쓰기 대상 블록을 선정하는 쓰기 블록 선정부;A write block selecting unit for searching, in the nonvolatile storage, the immediately preceding blocks of the original block corresponding to the data included in the checkpoint transaction and for selecting a write target block according to the search result;

상기 선정된 쓰기 대상 블록에 상기 체크포인트 트랜잭션에 포함된 데이터를 상기 비휘발성 스토리지에 쓰기 연산하는 쓰기 연산 처리부; 및A write operation processing unit for writing data included in the checkpoint transaction to the non-volatile storage in the selected write target block; And

새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록 원본 트리 구조를 구성하고, 호스트 시스템이 상기 구성된 원본 트리 구조의 루트 노드를 포인팅하도록 설정하는 트리 구조 관리부를 포함하고,And a tree structure management unit configured to configure a source tree structure to point to newly written data blocks and original blocks that have not been updated, and to set the host system to point to a root node of the configured source tree structure,

상기 비휘발성 스토리지는 상기 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하는 원본 트리 구조와, 상기 직전 버전 블록들 및 상기 갱신되지 않은 원본 블록들을 포인팅하는 직전 트리 구조를 포함할 수 있다.The non-volatile storage may include a source tree structure for pointing the newly written data blocks and original blocks that have not been updated, and a previous tree structure for pointing the previous version blocks and the unreheated original blocks .

일 실시예에 따라, 상기 쓰기 블록 선정부는,According to an embodiment, the write block selecting unit may include:

상기 체크포인트 트랜잭션에 포함된 데이터의 원본 블록에 대해 직전 버전 블록이 보전되어 있으면, 상기 비휘발성 스토리지에서 직전 버전이 저장된 블록들을 쓰기 대상 블록으로 선정하도록 동작할 수 있다.If the previous version block is stored in the original block of the data included in the checkpoint transaction, the non-volatile storage may be operable to select the block in which the previous version is stored as the block to be written.

상기 직전 트리 구조 및 활성화된 원본 트리 구조를 참조하여, 상기 체크포인트 트랜잭션에 포함된 데이터에 상응하는 데이터 블록에 대한 직전 트리 구조 내의 포인터와 현재 원본 트리 구조의 상응하는 포인터가 서로 다르면, 상기 비휘발성 스토리지에서 상기 직전 트리 구조 내의 포인터에 의해 포인팅되는 직전 버전이 저장된 데이터 블록을 쓰기 대상 블록으로 선정하도록 동작할 수 있다.If the pointers in the immediately preceding tree structure and the corresponding pointers in the current source tree structure for the data block corresponding to the data included in the checkpoint transaction are different from each other by referring to the previous tree structure and the activated original tree structure, And to select, as a block to be written, a block of data stored in the previous version pointed to by the pointer in the immediately preceding tree structure in the storage.

일 실시예에 따라, 상기 쓰기 블록 선정부는, According to an embodiment, the write block selecting unit may include:

만약 상기 체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록 또는 상기 원본 블록의 직전 버전 블록을 탐색할 수 없는 경우에는, 상기 비휘발성 스토리지에서 빈 블록을 쓰기 대상 블록으로 선정하도록 동작할 수 있다.If the original block corresponding to the data included in the checkpoint transaction or the previous version block of the original block can not be searched, an empty block may be selected as a write target block in the nonvolatile storage.

상기 체크포인트 트랜잭션에 포함된 데이터가 신규 파일의 데이터 또는 기존 파일의 부가 데이터인 경우에는 상기 비휘발성 스토리지에서 빈 블록을 쓰기 대상 블록으로 선정하도록 동작할 수 있다.If the data included in the checkpoint transaction is data of a new file or additional data of an existing file, the non-volatile storage may be operable to select an empty block as a block to be written.

상기 체크포인트 트랜잭션에 포함된 데이터가 기존 파일의 갱신 데이터로서 온전한 직전 트리 구조가 존재하지 않는 경우에는, 상기 비휘발성 스토리지에서 빈 블록을 쓰기 대상 블록으로 선정하도록 동작할 수 있다.If the data included in the checkpoint transaction does not exist in the previous tree structure as the update data of the existing file, the non-volatile storage may be operable to select an empty block as a write target block.

상기 직전 트리 구조 및 원본 트리 구조를 참조하여, 상기 체크포인트 트랜잭션에 포함된 데이터가 기존 파일의 갱신 데이터이고, 상기 직전 트리 구조가 온전히 존재하며, 해당 갱신 데이터에 상응하는 기존 파일의 데이터 블록에 대한 직전 트리 구조 내의 포인터와 현재 원본 트리 구조의 상응하는 포인터가 서로 동일한 경우에는, 상기 비휘발성 스토리지에서 빈 블록을 쓰기 대상 블록으로 선정하도록 동작할 수 있다.Wherein the data included in the checkpoint transaction is update data of an existing file, the previous tree structure is completely present, and the data structure of the existing file corresponding to the update data is updated by referring to the previous tree structure and the original tree structure, If the pointers in the immediately preceding tree structure and the corresponding pointers in the current source tree structure are the same, the non-volatile storage can be operated to select an empty block as a write target block.

일 실시예에 따라, 상기 쓰기 연산 처리부는,According to an embodiment, the write operation processing unit may include:

갱신될 데이터 블록 중에서 변경된 부분만 쓰기 연산하도록 동작할 수 있다.And to write only the changed portion of the data block to be updated.

일 실시예에 따라, 상기 트리 구조 관리부는,According to one embodiment, the tree structure management unit comprises:

직전 버전 블록들 및 직전 트리 구조가 온전히 보전되어 있는 경우에는, 직전 버전 블록들에 덮어 쓴 갱신 버전 블록들 및 원본 블록들을 포인팅하도록 상기 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 상기 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하도록 동작할 수 있다.When the previous version blocks and the previous tree structure are fully preserved, the previous tree structure is updated to point to the updated version blocks and original blocks overwritten to the previous version blocks to construct a new source tree structure, To point to the root node of the new source tree structure.

일 실시예에 따라, 상기 쓰기 블록 선정부는 According to one embodiment, the write block selecting unit

상기 직전 트리 구조가 저장된 블록들을 해당 데이터 블록의 갱신이 있기 전까지 쓰기 보호하도록 동작할 수 있다.And write-protect the blocks in which the previous tree structure has been stored until the data block is updated.

일 실시예에 따라, 상기 쓰기 블록 선정부는According to one embodiment, the write block selecting unit

상기 직전 트리 구조가 저장된 블록들을 빈 블록과 동등하게 또는 빈 블록에 비해 비우선적으로 쓰기 대상 블록으로 선정하도록 동작할 수 있다.It is possible to select the blocks in which the previous tree structure is stored as a target block to be written in a priority manner in comparison with an empty block or in an empty block.

상기 직전 버전 블록들의 위치를 상기 비휘발성 스토리지의 내부에, 또는 외부의 저장 공간에 저장하도록 동작할 수 있다.And store the location of the previous version blocks in the non-volatile storage or in an external storage space.

일 실시예에 따라, 상기 원본 트리 구조는 각각의 파일에 관하여 원본 블록을 포인팅하는 포인터와 상기 원본 블록의 직전 버전 블록을 포인팅하는 포인터를 하나의 쌍으로 포함 수 있다.According to an exemplary embodiment, the source tree structure may include a pointer for pointing an original block with respect to each file and a pointer for pointing to a previous version block of the original block.

상기 직전 트리 구조가 온전히 존재하고 상기 체크포인트 트랜잭션에 포함된 데이터가 신규 파일의 데이터인 경우에는, 새로 쓰기 연산된 데이터 블록들을 추가로 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하도록 동작할 수 있다.If the previous tree structure is completely present and the data included in the checkpoint transaction is data of a new file, a new original tree structure is constructed by updating the previous tree structure so as to further point to the newly written data blocks, And to set the host system to point to the root node of the new source tree structure.

상기 직전 트리 구조가 온전히 존재하고 상기 체크포인트 트랜잭션에 포함된 데이터가 기존 파일의 데이터이지만 직전 버전 블록이 존재하지 않은 경우에는, 새로 쓰기 연산된 갱신 버전 블록들 또는 부가 블록들 및 원본 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하도록 동작할 수 있다.If the previous tree structure is perfectly present and the data included in the checkpoint transaction is data of an existing file but there is no previous version block, the updated version blocks or additional blocks and original blocks are pointed Update the previous tree structure to construct a new source tree structure, and set the host system to point to the root node of the new source tree structure.

직전 트리 구조가 온전하게 존재하지 않은 경우에는, 파일을 구성하는 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록, 상기 원본 트리 구조의 갱신되지 않는 부분과 상기 새로 쓰기 연산된 데이터 블록들을 위한 새로운 포인터들을 조합하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하도록 동작할 수 있다.In the case where the immediately preceding tree structure does not exist perfectly, the unrevealed part of the original tree structure and the newly written data block such that the newly written data blocks constituting the file and the unrevealed original blocks are pointed, To construct a new source tree structure, and to set the host system to point to the root node of the new source tree structure.

일 실시예에 따라, 상기 듀얼 버퍼링 파일 관리 시스템은According to one embodiment, the dual buffering file management system

호스트 시스템의 버퍼 캐시 내에서 쓰기 연산의 대상이 되는 더티 캐시들의 컨텐츠들을 비휘발성 스토리지에 기록하기 위한 상기 체크포인트 트랜잭션을 생성하는 체크포인트 트랜잭션 생성부를 더 포함할 수 있다.And a checkpoint transaction generator for generating the checkpoint transaction for writing the contents of the dirty caches to be written into the nonvolatile storage in the buffer cache of the host system.

호스트 시스템의 쓰기 연산의 대상이 되는 메모리 블록들의 컨텐츠들을 버퍼 캐시를 거치지 않고 비휘발성 스토리지에 기록하기 위한 상기 체크포인트 트랜잭션을 생성하는 체크포인트 트랜잭션 생성부를 더 포함할 수 있다.And a checkpoint transaction generating unit for generating the checkpoint transaction for writing the contents of the memory blocks subject to the write operation of the host system to the nonvolatile storage without going through the buffer cache.

본 발명의 다른 측면에 따른 비휘발성 스토리지 장치는A non-volatile storage device according to another aspect of the present invention includes:

상기 선정된 쓰기 대상 블록에 상기 체크포인트 트랜잭션에 포함된 데이터를 상기 비휘발성 스토리지에 쓰기 연산하는 쓰기 연산 처리부;A write operation processing unit for writing data included in the checkpoint transaction to the non-volatile storage in the selected write target block;

새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록 원본 트리 구조를 구성하고, 호스트 시스템이 상기 원본 트리 구조의 루트 노드를 포인팅하도록 설정하는 트리 구조 관리부; 및A tree structure management unit that configures a source tree structure to point to newly written data blocks and unrevealed original blocks, and sets the host system to point to a root node of the source tree structure; And

상기 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하는 원본 트리 구조와, 상기 직전 버전 블록들 및 상기 갱신되지 않은 원본 블록들을 포인팅하는 직전 트리 구조를 포함하는 비휘발성 스토리지를 포함할 수 있다.A source tree structure for pointing to the newly written data blocks and original blocks that have not been updated, and a non-volatile storage including a previous tree structure for pointing to the previous version blocks and the un-updated original blocks have.

본 발명의 또 다른 측면에 따른 비휘발성 스토리지를 가지는 컴퓨터에 의한 비휘발성 스토리지의 듀얼 버퍼링 파일 관리 방법에 있어서,
상기 컴퓨터가,According to another aspect of the present invention, there is provided a method of managing a dual buffering file of a nonvolatile storage by a computer having a nonvolatile storage,
The computer comprising:

(a) 체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록의 직전 버전 블록들을 비휘발성 스토리지에서 탐색하고, 탐색 결과에 따라 쓰기 대상 블록을 선정하는 단계;(a) searching for a previous version block of a source block corresponding to data included in a checkpoint transaction in a nonvolatile storage, and selecting a target block in accordance with a search result;

(b) 상기 선정된 쓰기 대상 블록에 상기 체크포인트 트랜잭션에 포함된 데이터를 상기 비휘발성 스토리지에 쓰기 연산하는 단계; 및(b) writing data included in the checkpoint transaction to the selected write target block into the nonvolatile storage; And

(c) 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록 구성한 원본 트리 구조의 루트 노드를 호스트 시스템이 포인팅하도록 설정하는 단계를 포함하고,(c) setting the host system to point to a root node of a source tree structure configured to point to newly written data blocks and unrecovered original blocks,

일 실시예에 따라, 상기 (a) 단계는,According to an embodiment, the step (a)

상기 체크포인트 트랜잭션에 포함된 데이터의 원본 블록에 대해 직전 버전 블록이 보전되어 있으면, 상기 비휘발성 스토리지에서 직전 버전이 저장된 블록들을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.And selecting a block in which the previous version is stored in the nonvolatile storage as a write target block if the previous version block is held for the original block of data included in the checkpoint transaction.

상기 직전 트리 구조 및 활성화된 원본 트리 구조를 참조하여, 상기 체크포인트 트랜잭션에 포함된 데이터에 상응하는 데이터 블록에 대한 직전 트리 구조 내의 포인터와 현재 원본 트리 구조의 상응하는 포인터가 서로 다르면, 상기 비휘발성 스토리지에서 상기 직전 트리 구조 내의 포인터에 의해 포인팅되는 직전 버전이 저장된 데이터 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.If the pointers in the immediately preceding tree structure and the corresponding pointers in the current source tree structure for the data block corresponding to the data included in the checkpoint transaction are different from each other by referring to the previous tree structure and the activated original tree structure, And selecting a data block storing a previous version pointed by a pointer in the immediately preceding tree structure as a write target block in the storage.

일 실시예에 따라, 상기 (a) 단계는, According to an embodiment, the step (a)

만약 상기 체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록 또는 상기 원본 블록의 직전 버전 블록을 탐색할 수 없는 경우에는, 상기 비휘발성 스토리지에서 빈 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.If the original block corresponding to the data included in the checkpoint transaction or the previous version block of the original block can not be searched, selecting an empty block as a write target block in the nonvolatile storage .

상기 체크포인트 트랜잭션에 포함된 데이터가 신규 파일의 데이터 또는 기존 파일의 부가 데이터인 경우에는 상기 비휘발성 스토리지에서 빈 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.And selecting an empty block as a write target block in the non-volatile storage when the data included in the checkpoint transaction is data of a new file or additional data of an existing file.

상기 체크포인트 트랜잭션에 포함된 데이터가 기존 파일의 갱신 데이터로서 온전한 직전 트리 구조가 존재하지 않는 경우에는, 상기 비휘발성 스토리지에서 빈 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.And selecting an empty block as a write target block in the nonvolatile storage when the data included in the checkpoint transaction does not exist in the previous tree structure as the updated data of the existing file.

상기 직전 트리 구조 및 원본 트리 구조를 참조하여, 상기 체크포인트 트랜잭션에 포함된 데이터가 기존 파일의 갱신 데이터이고, 상기 직전 트리 구조가 온전히 존재하며, 해당 갱신 데이터에 상응하는 기존 파일의 데이터 블록에 대한 직전 트리 구조 내의 포인터와 현재 원본 트리 구조의 상응하는 포인터가 서로 동일한 경우에는, 상기 비휘발성 스토리지에서 빈 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.Wherein the data included in the checkpoint transaction is update data of an existing file, the previous tree structure is completely present, and the data structure of the existing file corresponding to the update data is updated by referring to the previous tree structure and the original tree structure, And selecting an empty block as a write target block in the nonvolatile storage when the pointer in the immediately previous tree structure and the corresponding pointer in the current source tree structure are equal to each other.

일 실시예에 따라, 상기 (b) 단계는,According to an embodiment, the step (b)

만약 빈 블록이 쓰기 대상 블록으로 선정된 경우에는 데이터 블록 전체를 쓰기 연산하고, 만약 직전 버전 블록이 쓰기 대상 블록으로 선정된 경우에는, 데이터 비교 쓰기(Data-Comparison Write, DCW) 기법에 따라, 갱신될 데이터 블록 중에서 변경된 부분만 쓰기 연산하는 단계를 포함할 수 있다.If an empty block is selected as a write target block, the entire data block is written. If the previous version block is selected as a write target block, update is performed according to a data comparison write (DCW) technique. And writing only the changed portion of the data block to be updated.

일 실시예에 따라, 상기 (c) 단계는,According to an embodiment, the step (c)

직전 버전 블록들 및 직전 트리 구조가 온전히 보전되어 있는 경우에는, If the previous version blocks and the previous tree structure are fully preserved,

직전 버전 블록들에 덮어 쓴 갱신 버전 블록들 및 원본 블록들을 포인팅하도록 상기 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고,Updating the previous tree structure so as to point to the updated version blocks and original blocks overwritten to the previous version blocks to construct a new original tree structure,

호스트 시스템이 상기 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하는 단계를 포함할 수 있다.And setting the host system to point to the root node of the new source tree structure.

일 실시예에 따라, 상기 직전 트리 구조가 저장된 블록들은 해당 데이터 블록의 갱신이 있기 전까지 쓰기 보호될 수 있다.According to an embodiment, blocks in which the previous tree structure is stored may be write-protected until the corresponding data block is updated.

일 실시예에 따라, 상기 직전 트리 구조가 저장된 블록들은 빈 블록과 동등하게 또는 빈 블록에 비해 비우선적으로 쓰기 대상 블록으로 선정될 수 있다.According to an embodiment, the blocks in which the previous tree structure is stored may be selected as a target block to be written in a manner equivalent to an empty block or in preference to an empty block.

일 실시예에 따라, 상기 직전 버전 블록들의 위치는 상기 비휘발성 스토리지의 내부에, 또는 외부의 저장 공간에 저장되어 보전될 수 있다.According to one embodiment, the location of the previous version blocks may be stored within the non-volatile storage or may be stored in an external storage space.

일 실시예에 따라, 상기 원본 트리 구조는 각각의 파일에 관하여 원본 블록을 포인팅하는 포인터와 상기 원본 블록의 직전 버전 블록을 포인팅하는 포인터를 하나의 쌍으로 포함할 수 있다.According to an embodiment, the source tree structure may include a pointer for pointing an original block with respect to each file and a pointer for pointing to an immediately previous version block of the original block.

상기 직전 트리 구조가 온전히 존재하고 상기 체크포인트 트랜잭션에 포함된 데이터가 신규 파일의 데이터인 경우에는, 새로 쓰기 연산된 데이터 블록들을 추가로 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하는 단계를 포함할 수 있다.If the previous tree structure is completely present and the data included in the checkpoint transaction is data of a new file, a new original tree structure is constructed by updating the previous tree structure so as to further point to the newly written data blocks, And setting the host system to point to the root node of the new source tree structure.

상기 직전 트리 구조가 온전히 존재하고 상기 체크포인트 트랜잭션에 포함된 데이터가 기존 파일의 데이터이지만 직전 버전 블록이 존재하지 않은 경우에는, 새로 쓰기 연산된 갱신 버전 블록들 또는 부가 블록들 및 원본 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하는 단계를 포함할 수 있다.If the previous tree structure is perfectly present and the data included in the checkpoint transaction is data of an existing file but there is no previous version block, the updated version blocks or additional blocks and original blocks are pointed Updating the previous tree structure to construct a new source tree structure, and setting the host system to point to the root node of the new source tree structure.

직전 트리 구조가 온전하게 존재하지 않은 경우에는, 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록, 상기 원본 트리 구조의 갱신되지 않는 부분과 상기 새로 쓰기 연산된 데이터 블록들을 위한 새로운 포인터들을 조합하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하는 단계를 포함할 수 있다.If the previous tree structure does not exist perfectly, a new pointer for the unrecorded part of the original tree structure and the newly written data blocks, so as to point to the newly written data blocks and the unrevealed original blocks, To construct a new source tree structure, and to set the host system to point to the root node of the new source tree structure.

일 실시예에 따라, 상기 비휘발성 스토리지의 듀얼 버퍼링 파일 관리 방법은, 호스트 시스템의 버퍼 캐시에서 쓰기 연산의 대상이 되는 더티 캐시들의 컨텐츠들을 비휘발성 스토리지에 기록하기 위한 상기 체크포인트 트랜잭션을 생성하는 단계를 더 포함할 수 있다.According to one embodiment, the dual buffering file management method of the non-volatile storage includes: generating the checkpoint transaction for writing contents of dirty caches subject to a write operation in a buffer cache of a host system to non-volatile storage As shown in FIG.

일 실시예에 따라, 상기 비휘발성 스토리지의 듀얼 버퍼링 파일 관리 방법은, 호스트 시스템의 쓰기 연산의 대상이 되는 메모리 블록들의 컨텐츠들을 버퍼 캐시를 거치지 않고 비휘발성 스토리지에 기록하기 위한 상기 체크포인트 트랜잭션을 생성하는 단계를 더 포함할 수 있다.According to one embodiment, the dual buffering file management method of the non-volatile storage includes: generating the checkpoint transaction for writing contents of memory blocks subject to a write operation of a host system to a non-volatile storage without going through a buffer cache; The method comprising the steps of:

본 발명의 비휘발성 메모리를 위한 듀얼 버퍼링 파일 관리 방법, 파일 관리 시스템 및 대용량 저장 장치에 따르면, 매번 수정 기록시 전전 버전이 기록된 블록에 저장하므로, 종래 기술과 같이 유사한 블록을 찾기 위해 필요한 해밍 거리 연산과 같은 오버헤드가 없고, 평균적으로 높은 유사도를 가지는 블록에 데이터를 저장할 수 있다.According to the dual buffering file management method, the file management system, and the mass storage device for nonvolatile memory of the present invention, since the previous version is stored in the block in which the previous version is recorded each time, Data can be stored in a block having a high degree of similarity on average without overhead such as computation.

본 발명의 비휘발성 메모리를 위한 듀얼 버퍼링 파일 관리 방법, 파일 관리 시스템 및 대용량 저장 장치에 따르면, 매번 기록 때마다 직전 버전은 유지되므로 기록 시점에 시스템 고장이 일어나도 데이터의 일관성을 보장할 수 있다.According to the dual buffering file management method, the file management system, and the mass storage device for the nonvolatile memory of the present invention, since the immediately previous version is maintained every time of recording, consistency of data can be ensured even if a system failure occurs at a recording time.

본 발명의 비휘발성 메모리를 위한 듀얼 버퍼링 파일 관리 방법, 파일 관리 시스템 및 대용량 저장 장치에 따르면, 수정이 잦더라도 수정이 되는 블록들의 복사본을 유지할 공간만을 요구하므로 빈 공간이 줄어들 때 성능이 급격히 저하되는 현상을 방지할 수 있다.According to the dual buffering file management method, the file management system, and the mass storage device for the nonvolatile memory of the present invention, since only a space for holding a copy of blocks to be modified is required even if frequent modifications are made, The phenomenon can be prevented.

도 1은 본 발명의 일 실시예에 따른 듀얼 버퍼링 파일 관리 시스템을 예시한 개념도이다.
도 2 내지 도 4는 본 발명의 일 실시예에 따른 듀얼 버퍼링 파일 관리 시스템에서 블록들이 갱신될 때 파일 트리 구조의 변화를 예시한 개념도들이다.
도 5는 본 발명의 일 실시예에 따른 듀얼 버퍼링 대용량 스토리지 장치를 예시한 블록도이다.
도 6은 본 발명의 일 실시예에 따른 듀얼 버퍼링 파일 관리 방법을 예시한 순서도이다.1 is a conceptual diagram illustrating a dual buffering file management system according to an embodiment of the present invention.
FIGS. 2 to 4 are conceptual diagrams illustrating a change of a file tree structure when blocks are updated in a dual buffering file management system according to an embodiment of the present invention.
5 is a block diagram illustrating a dual buffering mass storage device according to an embodiment of the present invention.
6 is a flowchart illustrating a dual buffering file management method according to an embodiment of the present invention.

본문에 개시되어 있는 본 발명의 실시예들에 대해서, 특정한 구조적 내지 기능적 설명들은 단지 본 발명의 실시예를 설명하기 위한 목적으로 예시된 것으로, 본 발명의 실시예들은 다양한 형태로 실시될 수 있으며 본문에 설명된 실시예들에 한정되는 것으로 해석되어서는 아니 된다. For the embodiments of the invention disclosed herein, specific structural and functional descriptions are set forth for the purpose of describing an embodiment of the invention only, and it is to be understood that the embodiments of the invention may be practiced in various forms, The present invention should not be construed as limited to the embodiments described in Figs.

이하, 첨부한 도면들을 참조하여, 본 발명의 바람직한 실시예를 보다 상세하게 설명하고자 한다. 도면상의 동일한 구성요소에 대해서는 동일한 참조부호를 사용하고 동일한 구성요소에 대해서 중복된 설명은 생략한다.Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. The same reference numerals are used for the same constituent elements in the drawings and redundant explanations for the same constituent elements are omitted.

본 발명은 중소기업청에서 주관하고 한국산학연협회에서 관리하는 산학연 공동기술개발 사업의 "NVRAM 기반 고신뢰성 클라우드 스토리지 솔루션 개발" 연구과제(정부과제고유번호 1425074642호)와, 지식경제부에서 주관하고 한국산업기술평가관리원에서 관리하는 SW컴퓨팅 산업 원천기술개발 사업의 "차세대 메모리 기반의 스마트 디바이스용 임베디드 시스템 소프트웨어 원천기술 개발" 연구과제(정부과제고유번호 1415122825호)의 지원으로 수행된 연구 결과를 토대로 한다.The present invention relates to a research project "Development of NVRAM-based high reliability cloud storage solution" (Government task assignment number: 1425074642) of Ministry of Knowledge Economy and supervised by Korea Industrial Technology Association Based on the results of research carried out with the support of "Development of original technology for embedded system software for smart devices based on next generation memory" (Government Project Assigned No. 1415122825) of SWComputing industrial technology development project managed by management personnel.

본 발명의 명세서 전체에 걸쳐, 달리 명시되지 않은 이상, 데이터 블록, 아이노드 블록, 아이노드, 포인터 및 파일 트리 구조에 관하여, 최신의 갱신 데이터의 체크포인트 연산이 실행되기 직전의 각각의 버전들을 원본, 또는 현재 원본이라고 하고, 현재 원본의 과거의 버전들을 직전 버전이라고 하며, 현재 버전의 갱신될 버전들을 갱신 버전 또는 새로운 원본이라고 부른다.Throughout the specification of the present invention, unless stated otherwise, each version immediately before the checkpoint operation of the latest update data is executed, with respect to the data block, the inode block, the inode, the pointer and the file tree structure, , Or the current source, and the past versions of the current source are referred to as the immediately previous version, and the versions to be updated of the current version are called the updated version or the new original.

에를 들어, 현재 시점의 파일 트리 구조는 원본 트리 구조이며, 현재의 원본 트리 구조에 의해 대체된 직전의 파일 트리 구조는 직전 트리 구조이며, 현재 원본에서 체크포인트 연산에 의해 갱신되는 버전은 갱신 트리 구조, 갱신 파일 트리 구조 또는 새로운 원본 트리 구조라고 불릴 수 있다.For example, the file tree structure at the present time is a source tree structure, the file tree structure immediately before being replaced by the current source tree structure is an immediate tree structure, and the version updated by the checkpoint operation in the current source is an update tree structure , An update file tree structure, or a new source tree structure.

도 1은 본 발명의 일 실시예에 따른 듀얼 버퍼링 파일 관리 시스템을 예시한 개념도이다.1 is a conceptual diagram illustrating a dual buffering file management system according to an embodiment of the present invention.

본 발명의 듀얼 파일링 파일 관리 시스템(10)을 설명하기에 앞서, 파일 시스템에 관하여 간단히 이해할 필요가 있다.Before describing the dual filing file management system 10 of the present invention, it is necessary to briefly understand the file system.

최신의 수많은 파일 시스템들은 원자성(atomicity)의 지원을 통해, 무결성, 일관성을 달성하는 것이 특징이다. 원자성은 어떤 일련의 세부 작업들로 구성된 트랜잭션이 완전히 성공한 경우에만 호스트 시스템에 반영되고, 그렇지 않으면 실패한 트랜잭션으로 규정되어 버려지며 직전의 호스트 시스템 상태에는 영향을 미치지 않음을 의미한다. 예를 들어, 쓰기 연산 중에 호스트 시스템이 오류를 일으킬 경우에, 만약 원본 위에 일부만 덮어쓰기된 블록은 원본도 아니고 그렇다고 갱신본도 아닌 아티팩트(artifact)가 되며, 롤백(rollback)도 불가능하므로, 이러한 상황은 허용되어서는 안된다. 따라서 원본을 두고 새로 빈 공간에 쓰기 연산이 이루어지는 것이 보통이다.Many modern file systems are characterized by achieving integrity and consistency through the support of atomicity. Atomicity means that a transaction consisting of a series of detailed operations is only reflected in the host system if it is completely successful, otherwise it is defined as a failed transaction and does not affect the state of the previous host system. For example, if the host system fails during a write operation, the block that is partially overwritten on the original is neither the original nor the updated version, and can not be rolled back. Should not be allowed. Therefore, it is normal that a write operation is performed on a new blank space with respect to the original.

이러한 파일 시스템에서는 원자성을 염두에 두고 저수준의 쓰기 연산들이 하나의 트랜잭션으로서 처리된다. 컴퓨터 공학 분야에서 트랜잭션은 데이터의 전송을 시작하는 시점부터 무결성을 보장하면서 완료하기까지 수행되는 일련의 동작들로 된 작업 단위를 가리키는 용어이다.In this file system, low-level write operations are treated as a transaction with atomicity in mind. In the field of computer engineering, a transaction is a term that refers to a unit of work consisting of a series of operations performed from the start of data transmission to the completion of ensuring integrity.

통상적으로, 호스트 시스템에서 쓰기 명령이 발생할 때마다 스토리지에 쓰기 연산을 하는 대신에, 실제로는 버퍼 캐시, 메인 메모리 등에 임시적으로 기록하다가, 누적된 변경을 한꺼번에 스토리지에 반영하는 경우가 많은데, 이러한 작업을 체크포인트(checkpoint)라고 한다. 예를 들어 버퍼 캐시를 이용하는 경우 소정 시간의 경과라든가 갱신 횟수와 같은 소정 조건이 만족되면, 버퍼 캐시 내에서 더티 캐시로 표시되는 블록들의 컨텐츠 즉 데이터들은 한꺼번에 스토리지에 반영되되, 원자성을 보장할 수 있도록 하나의 트랜잭션을 구성한다. 체크포인트를 위한 트랜잭션을 체크포인트 트랜잭션이라고 부른다.Generally, instead of writing to the storage every time a write command occurs in the host system, it is often the case that the accumulated data is temporarily stored in the buffer cache, main memory, and the like, and the accumulated changes are reflected in the storage at once. It is called a checkpoint. For example, when the buffer cache is used, if the predetermined condition such as the elapsed time or the number of updates is satisfied, the contents of the blocks indicated by the dirty cache in the buffer cache, that is, data are reflected to the storage at a time, A transaction is composed of A transaction for a checkpoint is called a checkpoint transaction.

만약 체크포인트 트랜잭션의 수행 중에 시스템 고장(운영체제의 치명적 오류나 전원 차단 등)이 일어나면, 해당 체크포인트 트랜잭션은 실패한 것으로써 무시되어야 하고, 체크포인트 전의 상태로 롤백되어야 하며, 따라서 스토리지는 체크포인트 트랜잭션이 성공적으로 완료되기 전까지는 시스템 고장 전, 즉 체크포인트 전의 데이터를 완전 무결하게 유지하고 있어야 한다.If a system failure (such as a fatal error or power failure of the operating system) occurs during the execution of a checkpoint transaction, the corresponding checkpoint transaction must be ignored as failed and rolled back to the state before the checkpoint, It is necessary to maintain the integrity of the data before the system failure, that is, before the checkpoint.

만약 체크포인트 트랜잭션을 구성하는 쓰기 연산들을 포함하는 일련의 동작들이 성공적으로 완료되면, 이는 체크포인트 트랜잭션에 포함된 컨텐츠들이 스토리지에 성공적으로 반영되었다는 것이다. If a series of operations including write operations that constitute a checkpoint transaction are successfully completed, then the contents included in the checkpoint transaction are successfully reflected in the storage.

통상적으로 체크포인트 연산에 의해 갱신당한 이전 버전의 데이터는 이제 쓸모가 없는(obsolete) 데이터가 되므로, 종래 기술들에서는, 그 데이터를 저장하던 블록은 비워지거나 또는 자유롭게 덮어쓰기 될 수 있다고 간주되었다.Conventionally, previous versions of data that have been updated by checkpoint operations are now obsolete data, so in the prior art it was considered that the block storing the data could be emptied or freely overwritten.

한편, 유닉스에 기반하는 수많은 파일 시스템은 아이노드(inode 또는 index node)라고 불리는 일종의 트리 구조의 데이터를 이용하여 파일, 디렉토리, 장치 노드, 소켓, 파이프 등을 관리한다. 각각의 파티션마다 소정의 위치 및 소정 크기의 지정된 블록 내에 각각의 파일, 디렉토리, 장치 노드, 소켓, 파이프 등을 위한 아이노드들의 리스트가 저장되고 또한 아이노드를 위한 저장 공간이 예비되어 파일의 생성과 함께 해당 파일의 아이노드도 생성되고 관리된다.On the other hand, many UNIX based file systems manage files, directories, device nodes, sockets, pipes, etc. using data of a kind of tree structure called an inode or an index node. A list of inodes for respective files, directories, device nodes, sockets, pipes, and the like is stored in a predetermined block of a predetermined position and a predetermined size for each partition, and storage space for the inodes is reserved, In addition, the inode of the file is also created and managed.

이러한 아이노드들이 저장된 아이노드 블록은 루트 노드 포인터에 의해 호스트 시스템으로부터 포인팅된다. 즉, 호스트 시스템은 등록된 루트 노드 포인터에 의해 아이노드 블록의 위치를 인식한다.The inode block in which these inodes are stored is pointed from the host system by the root node pointer. That is, the host system recognizes the position of the inode block by the registered root node pointer.

특히 파일을 관리하기 위한 각각의 아이노드는 파일에 관한 메타 데이터들, 예를 들어, 소유권, 접근 방식, 파일 타입, 크기, 아이노드 번호, 어드레스 포인터들을 저장한다. 파일의 이름은 아이노드가 아닌 디렉토리 파일에서 관리된다.In particular, each inode for managing a file stores metadata about the file, for example, ownership, approach, file type, size, inode number, and address pointers. The name of the file is managed in the directory file, not the inode.

호스트 시스템은 사용자가 원하는 파일의 이름을 디렉토리 파일에서 찾고, 디렉토리 파일 내에서 파일의 이름과 연결된 아이노드 번호를 가지는 아이노드를 아이노드 블록 내에서 찾는다.The host system searches the directory file for the name of the file that the user wants, and finds an inode in the inode block that has an inode number associated with the name of the file in the directory file.

아이노드 블록에 저장된 각각의 아이노드는 파일 데이터가 실제로 저장된 데이터 블록들을 가리키는 포인터들을 포함한다.Each inode stored in the inode block contains pointers to the data blocks in which the file data is actually stored.

파일 시스템마다, 디스크 크기마다 다를 수 있지만, 하나의 아이노드가, 메타 데이터들에 더불어, 파일의 위치를 지정하기 위한 용도로 13 개의 포인터들을 포함할 수 있다고 가정하면, 그 중 10 개의 포인터들은 그 파일의 각각의 일부들이 저장된 데이터 블록들의 위치를 직접 가리킬 수 있는 직접 포인터이고, 한 포인터는 해당 파일의 초과되는 부분들이 저장된 데이터 블록들의 위치를 가리키는 추가적인 포인터들만을 저장하는 포인터 블록의 위치를 가리키는 단순 간접 포인터(singly indirect pointer)이며, 다음의 한 포인터는 직접 포인터들을 저장하는 포인터 블록들의 위치를 가리키는 간접 포인터들을 저장하는 포인터 블록의 위치를 가리키는 이중 간접 포인터(doulby indirect pointer)이고, 마지막 한 포인터는 삼중 간접 포인터(triply indirect pointer)이다.For each file system, it may vary from disk size to size, but assuming that one inode can contain 13 pointers for specifying the location of the file, along with the metadata, Each of the files being a direct pointer that can directly point to the location of the stored data blocks and one pointer is a simple pointer indicating the location of the pointer block that stores only additional pointers indicating the locations of the data blocks where the excess portions of the file are stored The next pointer is a dullby indirect pointer indicating the position of a pointer block storing indirect pointers indicating the positions of pointer blocks storing direct pointers, and the last pointer is a pointer It is a triply indirect pointer.

만약 하나의 포인터로 1 KB의 데이터 블록을 포인팅할 수 있다고 하면, 아이노드가 10 개의 직접 포인터로써 직접 가리킬 수 있는 파일의 최대 크기는 10 KB이다. 파일 크기가 10 KB를 초과하면 초과된 데이터가 저장된 데이터 블록에 대한 포인터들은 단순 간접 포인터가 가리키는 포인터 블록에 저장된다. 각각의 포인터 블록이 256 개의 포인터들을 저장할 수 있다고 하면, 단순 간접 포인터로 가리킬 수 있는 파일의 최대 크기는 256 KB이다. 256 KB + 10 KB를 초과하는 데이터가 저장된 데이터 블록들의 포인터들은 이제 이중 간접 포인터가 가리키는 포인터 블록에 저장되는 최대 256 개의 포인터들이 가리키는 포인터 블록들의 각각에 저장된다. 이중 간접 포인터로 가리킬 수 있는 파일의 최대 크기는 16 MB + 256 KB + 10 KB이다. 이를 초과하는 데이터가 저장된 블록들의 포인터들은 삼중 간접 포인터가 가리키는 포인터 블록에 저장된 최대 256 개의 포인터들이 가리키는 256 개의 포인터 블록들의 각각에 저장된 최대 256 개의 포인터들이 다시 가리키는 포인터 블록들에 저장된다. 이와 같은 예시에서 삼중 간접 포인터까지 모두 동원하여 가리킬 수 있는 파일의 최대 크기는 16 GB + 16 MB + 256 KB + 10 KB가 된다.If a single pointer can point to a block of 1 KB, then the maximum size of a file that the inode can directly point to as 10 direct pointers is 10 KB. If the file size exceeds 10 KB, pointers to blocks of data that contain excess data are stored in pointer blocks pointed to by simple indirect pointers. Assuming that each pointer block can store 256 pointers, the maximum size of a file that can be pointed to by a simple indirect pointer is 256 KB. Pointers to data blocks that store data in excess of 256 KB + 10 KB are now stored in each of the pointer blocks pointed to by up to 256 pointers stored in the pointer block pointed to by the double indirect pointer. The maximum size of a file that can be pointed to as a double indirect pointer is 16 MB + 256 KB + 10 KB. The pointers of blocks in which data exceeding this are stored are stored in the pointer blocks pointed to by the maximum of 256 pointers stored in each of the 256 pointer blocks indicated by the maximum 256 pointers stored in the pointer block indicated by the triple indirect pointer. In this example, the maximum size of the file pointed to by the triple indirect pointer is 16 GB + 16 MB + 256 KB + 10 KB.

만약 아이노드 내에 포인터들의 수를 늘리거나, 포인터 블록의 크기를 늘리면 파일의 최대 크기를 적절히 증가시킬 수 있다.If you increase the number of pointers in the inode, or increase the size of the pointer block, you can increase the maximum size of the file appropriately.

본 발명에서는 호스트 시스템에서 인식하는 최상위의 루트 노드부터 각 파일마다의 아이노드들의 간접 포인터들까지 포함하는 전체 구조를 트리 구조 또는 파일 트리 구조라고 칭한다.In the present invention, the entire structure including the top root node recognized by the host system to the indirect pointers of the inodes of each file is referred to as a tree structure or a file tree structure.

이러한 파일 트리 구조에서, 어떤 파일에 데이터가 추가되거나 제거될 때에는 포인터들도 그에 따라 추가 또는 삭제되고, 만약 특정 데이터가 저장되는 위치가 변경될 때에는 포인터들도 변한다. In this file tree structure, when data is added to or removed from a file, pointers are added or deleted accordingly, and when the location where specific data is stored is changed, pointers also change.

이렇듯 데이터의 변경 후에는 파일 트리 구조 내의 아이노드 및 포인터들이 적절히 수정되어야 하는데, 이러한 아이노드 수정 작업 중에도, 호스트 시스템의 고장에 대비하여 원자성이 보장되어야 한다.After changing the data, the inode and pointers in the file tree structure should be modified appropriately. In order to prevent the host system from malfunctioning during the inode modification operation, the atomicity must be guaranteed.

다시 말해, 파일 트리 구조에서 원자성을 보장하기 위해서는 데이터가 저장되는 블록 뿐 아니라 아이노드 블록, 간접 포인터 블록들 내지 루트 노드 포인터도 체크포인트 트랜잭션 시에 적절하게 관리되어야 한다.In other words, in order to ensure atomicity in the file tree structure, inode blocks, indirect pointer blocks, and root node pointers as well as blocks in which data is stored must be properly managed at the time of checkpoint transaction.

이를 위해, 본 발명의 듀얼 버퍼링 파일 관리 시스템(10)은 체크포인트 트랜잭션 생성부(11), 쓰기 블록 선정부(12), 쓰기 연산 처리부(13) 및 트리 구조 관리부(14)를 포함할 수 있고, 비휘발성 스토리지(20)의 블록들에 대하여 쓰기 연산 및 읽기 연산을 관리할 수 있다.To this end, the dual buffering file management system 10 of the present invention may include a checkpoint transaction generation unit 11, a write block selection unit 12, a write operation processing unit 13 and a tree structure management unit 14 , And write and read operations for blocks of non-volatile storage 20.

비휘발성 스토리지(20)는, 아이노드 기반의 활성화된 원본 트리 구조(21)에 의해 포인팅되는 예시적인 파일(26)이 존재한다고 할 경우에, 호스트 시스템에 의해 활성화된 파일 시스템으로 인식되어 있는 원본 트리 구조(21), 파일(26)을 구성하는 데이터 블록들(261, 262, 263, 264) 및 추가로 데이터를 쓸 수 있도록 예비된 빈 블록(271)을 가진다.The non-volatile storage 20 may be configured to store an original file 26 that is recognized as a file system that is activated by the host system, if an exemplary file 26 that is pointed to by the inode- A tree structure 21, data blocks 261, 262, 263 and 264 constituting the file 26 and an empty block 271 reserved for further data writing.

원본 트리 구조(21)는 원본 루트 노드(210), 권한, 타입, 크기, 아이노드 번호 등의 메타 데이터와 직접 포인터(213), 단순 간접 포인터(214), 이중 간접 포인터(215) 및 삼중 간접 포인터(216)로 각각 구성되는 아이노드들(212)을 포함하는 원본 아이노드 블록(211)과, 아이노드(212)의 단순 간접 포인터(214), 이중 간접 포인터(215) 및 삼중 간접 포인터(216)를 이용하여 각각 포인팅되는 단순 간접 포인터 블록(23), 이중 간접 포인터 블록들(24, 241) 및 삼중 간접 포인터 블록들(25, 251, 252)을 포함한다.The source tree structure 21 includes meta data such as source root node 210, authority, type, size and inode number, direct pointer 213, simple indirect pointer 214, double indirect pointer 215, A pointer 212 and a pointer 212. The pointer 212 is a pointer to an original inode block 211 including the inodes 212 and 212. The pointer 212 is a simple indirect pointer 214, a double indirect pointer 215 and a triple indirect pointer Indirectly pointer blocks 23, double indirect pointer blocks 24 and 241 and triple indirect pointer blocks 25, 251 and 252, respectively, which are pointed at using the indirect pointer blocks 216 and 216, respectively.

파일(26)을 구성하는 데이터 블록(261)은 직접 포인터(213)에 의해 직접 포인팅되며, 데이터 블록(262)은 단순 간접 포인터(214)와 단순 간접 포인터 블록(23)의 간접 포인터(231)에 의해 포인팅되며, 데이터 블록(263)은 이중 간접 포인터(215)와 이중 간접 포인터 블록들(24, 241) 및 간접 포인터(242)에 의해 포인팅되고, 데이터 블록(264)은 삼중 간접 포인터(216)와 삼중 간접 포인터 블록들(25, 251, 252) 및 간접 포인터(253)에 의해 포인팅된다.The data block 261 constituting the file 26 is directly pointed by the direct pointer 213 and the data block 262 is indirectly pointers to the indirect pointer 231 of the simple indirect pointer block 23 and the indirect indirect pointer 214. [ The data block 264 is pointed by the double indirect pointer 215 and double indirect pointer blocks 24 and 241 and the indirect pointer 242 and the data block 264 is pointed by the triple indirect pointer 216 And triple indirect pointer blocks 25, 251, and 252 and an indirect pointer 253.

한편, 비휘발성 스토리지(20)는 아이노드 기반의 비활성화된 파일 시스템인 직전 트리 구조(22)도 포함할 수 있다. 직전 트리 구조(22)는 직전 루트 노드(220), 예시적인 파일(26)의 직전 버전을 구성하는 데이터 블록들(261, 262, 263)을 포인팅하는 아이노드 블록(221)과 아이노드(222), 그리고 아이노드(222)가 이용하던 포인터들이 저장되었던 포인터 블록들(223)을 포함한다.Non-volatile storage 20 may also include an immediate tree structure 22, which is an inactive file system based on an inode. The previous tree structure 22 includes an immediate node 220, an inode block 221 that points to data blocks 261, 262, and 263 that make up the immediate version of the illustrative file 26, And pointer blocks 223 in which pointers used by the inode 222 are stored.

다시 말해, 원본 트리 구조(21)는 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들로 구성되는 최신 버전의 파일(26)을 포인팅하며, 직전 트리 구조(22)는 직전 버전 블록들 및 갱신되기 전의 원본 블록들로 구성되는 직전 버전의 파일을 포인팅한다.In other words, the source tree structure 21 points to the latest version of the file 26, which is composed of newly written data blocks and unrevealed original blocks, and the previous tree structure 22 points to the previous version blocks and Pointing to the file of the previous version which is made up of original blocks before being updated.

직전 트리 구조(22)와 원본 트리 구조(21)는 서로 다른 위치에서 각각의 최상부 엔트리인 루트 노드(220, 210)를 각각 가지며, 아이노드 블록들(221, 211)도 각각 가진다. 하지만, 갱신되는 데이터 블록들을 제외하면 각각의 하위 포인터 블록들의 상당 부분은 갱신되지 않은 원본 블록들을 함께 포인팅할 수 있기 때문에, 직전 트리 구조(22)와 원본 트리 구조(21)의 하위 엔트리들은 부분적으로 중첩될 수 있다. 다시 말해, 갱신되지 않은 원본 블록들을 포인팅하는 포인터들은 원본 트리 구조(21)와 직전 트리 구조(22)가 공유할 수 있다.The previous tree structure 22 and the original tree structure 21 have root nodes 220 and 210, respectively, which are uppermost entries at different positions, respectively, and also have inode blocks 221 and 211, respectively. However, except for the data blocks to be updated, most of the lower-order pointer blocks can point to un-updated original blocks together, so that the lower-level entries of the previous-tree structure 22 and the original-tree structure 21 are partially Can be overlapped. In other words, the pointers that point to the original blocks that have not been updated can be shared by the original tree structure 21 and the previous tree structure 22.

체크포인트 트랜잭션 생성부(11)는 시간의 경과 또는 버퍼 캐시(100) 내에 신규 생성되거나 부가(append)되거나 또는 갱신(update)된 더티 캐시(dirty cache) 블록들의 갯수와 같은 소정의 조건이 만족하면, 버퍼 캐시(100) 내에서 쓰기 연산의 대상이 되는 더티 캐시들의 컨텐츠들을 스토리지(20)에 기록하기 위한 체크포인트 트랜잭션을 생성한다.The checkpoint transaction generating unit 11 generates a checkpoint transaction when the predetermined condition such as the elapsed time or the number of newly created or appended or updated dirty cache blocks in the buffer cache 100 is satisfied , And creates a checkpoint transaction to write the contents of the dirty caches to be written into the buffer 20 in the storage 20.

체크포인트 트랜잭션 생성부(11)는, 일 실시예에서는, 비휘발성 스토리지(20)의 파일 시스템을 관리하기 위한 듀얼 버퍼링 파일 관리 시스템(10)의 일부일 수 있지만, 다른 실시예에서는, 버퍼 캐시(100)를 관리하는 버퍼 캐시 관리부(101)의 일부일 수도 있다.The checkpoint transaction generator 11 may be part of a dual buffering file management system 10 for managing the file system of the nonvolatile storage 20 in one embodiment but in another embodiment the buffer cache 100 The buffer cache management unit 101 may be a part of the buffer cache management unit 101.

또 다른 실시예에서, 체크포인트 트랜잭션 생성부(11)는 스토리지(20)로 쓰기 연산되기 위한 체크포인트 트랜잭션을 메인 메모리로부터 직접 생성하거나, 또는 스토리지(20)가 별도로 가지는 쓰기 버퍼로부터 생성할 수도 있다.In another embodiment, the checkpoint transaction generator 11 may generate a checkpoint transaction for writing to the storage 20 directly from the main memory or from a write buffer that the storage 20 has separately .

이 경우에는, 체크포인트 트랜잭션 생성부(11)는 시간의 경과와 같은 소정의 조건이 만족하면, 쓰기 연산의 대상이 되는 메모리 블록들의 컨텐츠들을 버퍼 캐시를 거치지 않고 직접 스토리지(20)에 기록하기 위한 체크포인트 트랜잭션을 생성한다.In this case, the checkpoint transaction generating unit 11 may write the contents of the memory blocks to be written into the storage 20 directly without going through the buffer cache if a predetermined condition such as the lapse of time is satisfied Create a checkpoint transaction.

이제, 스토리지(20) 내에 체크포인트 트랜잭션에 포함된 데이터가 저장될 블록이 선정되어야 한다.Now, a block in which data included in the checkpoint transaction is to be stored in the storage 20 should be selected.

이를 위해 쓰기 블록 선정부(12)는, 체크포인트 트랜잭션에 포함된 데이터의 원본 블록의 직전 버전이 저장된 직전 버전 블록들을 비휘발성 스토리지(20)에서 탐색하고, 탐색 결과에 따라 쓰기 대상 블록을 선정한다.To this end, the write block selecting unit 12 searches the nonvolatile storage 20 for the previous version blocks in which the previous version of the original block of the data included in the checkpoint transaction is stored, and selects the write target block according to the search result .

다만, 쓰기 블록 선정부(12)는, 만약 체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록 또는 원본 블록의 직전 버전 블록을 탐색할 수 없는 경우, 다시 말해 만약 신규 파일이거나, 기존 파일에 부가(append)되거나 기존 파일의 갱신되는 부분이 처음으로 갱신되는 경우로서 원본 블록의 직전 버전 블록이 존재하지 않거나, 참조할 비활성화된 직전 트리 구조(22)가 없거나 손상된 경우에는, 비휘발성 스토리지(20)에서 빈 블록을 쓰기 대상 블록으로 선정할 수 있다.However, if the write block selection unit 12 can not find the previous block of the original block or the original block corresponding to the data included in the checkpoint transaction, that is, if it is a new file, if the previous version block of the original block does not exist, or if the inactive previous tree structure 22 to be referenced is missing or damaged, the non-volatile storage 20 An empty block can be selected as a write target block.

구체적으로, 쓰기 블록 선정부(12)는 체크포인트 트랜잭션에 포함된 데이터가 신규 파일의 데이터 또는 기존 파일의 부가 데이터인 경우에는 비휘발성 스토리지(20)에서 빈 블록을 쓰기 대상 블록으로 선정한다.More specifically, when the data included in the checkpoint transaction is data of a new file or additional data of an existing file, the write block selecting unit 12 selects an empty block as a write target block in the nonvolatile storage 20.

또한 쓰기 블록 선정부(12)는 체크포인트 트랜잭션에 포함된 데이터가 기존 파일의 갱신 데이터이지만 직전 트리 구조가 존재하지 않은 경우에는, 비휘발성 스토리지(20)에서 빈 블록을 쓰기 대상 블록으로 선정한다.If the data included in the checkpoint transaction is update data of an existing file but the previous tree structure does not exist, the write block selecting unit 12 selects an empty block as a write target block in the nonvolatile storage 20.

또한, 쓰기 블록 선정부(12)는 직전 트리 구조(22) 및 원본 트리 구조(21)를 참조하여, 체크포인트 트랜잭션에 포함된 데이터가 기존 파일의 갱신 데이터이고, 직전 트리 구조(22)가 온전히 존재하며 해당 갱신 데이터에 상응하는 기존 파일의 데이터 블록에 대한 직전 트리 구조(22) 내의 포인터와 현재 원본 트리 구조(21)의 상응하는 포인터가 서로 동일한 경우에는, 직전 버전 블록이 보전된 적이 없는 최초 갱신 데이터로 판정하고, 비휘발성 스토리지(20)에서 빈 블록을 쓰기 대상 블록으로 선정한다.The write block selection unit 12 refers to the previous tree structure 22 and the original tree structure 21 to determine whether the data included in the checkpoint transaction is update data of an existing file and the previous tree structure 22 And the pointer in the previous tree structure 22 for the data block of the existing file corresponding to the update data is the same as the corresponding pointer in the current source tree structure 21, And the empty block in the nonvolatile storage 20 is selected as the write target block.

반면에, 체크포인트 트랜잭션에 포함된 데이터의 원본 블록에 대해 직전 버전 블록이 보전되어 있는 경우에는, 쓰기 블록 선정부(12)는 비휘발성 스토리지(20)에서 직전 버전 블록들을 쓰기 대상 블록으로 선정한다.On the other hand, when the previous version block is held for the original block of the data included in the checkpoint transaction, the write block selection unit 12 selects the previous version blocks as the write target block in the nonvolatile storage 20 .

좀더 구체적으로, 쓰기 블록 선정부(12)는 직전 트리 구조(22) 및 활성화된 원본 트리 구조(21)를 참조하여, 직전 트리 구조(22)가 온전히 존재하고 해당 갱신 데이터에 상응하는 기존 파일의 데이터 블록에 대한 직전 트리 구조(22) 내의 포인터와 현재 원본 트리 구조(21)의 상응하는 포인터가 서로 다르면, 직전 버전 블록이 보전되어 있는 경우로 판정하고, 비휘발성 스토리지(20)에서 직전 트리 구조(22) 내의 포인터에 의해 포인팅되는 직전 버전 블록을 쓰기 대상 블록으로 선정한다.More specifically, the write block selection unit 12 refers to the previous tree structure 22 and the activated original tree structure 21 to determine whether the previous tree structure 22 is completely present and the existing file corresponding to the update data If the pointer in the previous tree structure 22 for the data block and the corresponding pointer in the current source tree structure 21 are different from each other, it is determined that the previous version block has been held. In the nonvolatile storage 20, The previous version block pointed by the pointer in the block 22 is selected as the block to be written.

한편, 만약 체크포인트 트랜잭션에 포함된 데이터가 갱신 데이터가 아닌 이미 존재하는 파일에 부가(append)되는 데이터라면, 기존 파일에 관한 데이터이기는 하지만 갱신할 원본이라고 볼 대상이 없기 때문에, 쓰기 블록 선정부(12)는, 신규 파일의 경우와 유사하게, 비휘발성 스토리지(20)에서 빈 블록을 쓰기 대상 블록으로 선정한다.On the other hand, if the data included in the checkpoint transaction is data that is appended to an existing file rather than update data, since it is data about an existing file but is not regarded as an original to be updated, 12 selects an empty block as a write target block in the nonvolatile storage 20 similarly to the case of a new file.

쓰기 연산 처리부(13)는 비휘발성 스토리지(20)에서 선정된 쓰기 대상 블록에 체크포인트 트랜잭션에 포함된 데이터를 쓰기 연산한다.The write operation processing unit 13 writes data included in the checkpoint transaction into the write target block selected in the nonvolatile storage 20.

구체적으로, 쓰기 연산 처리부(13)는 데이터 비교 쓰기(Data-Comparison Write, DCW) 기법에 따라, 쓰기 연산되는 데이터 블록 내에서도 실제로 변경이 있는 부분만 쓰기 연산할 수 있다.More specifically, the write operation processing unit 13 can write only the part actually changed in the data block to be written in accordance with the data-comparison write (DCW) technique.

실시예에 따라, 만약 빈 블록이 쓰기 대상 블록으로 선정된 경우에는 DCW 기법 대신에 데이터 블록 전체를 쓰기 연산하고, 만약 직전 버전 블록이 쓰기 대상 블록으로 선정된 경우에는, DCW 기법에 따라 변경이 있는 부분만 쓰기 연산할 수 있다.If an empty block is selected as a write target block, the entire data block is written in place of the DCW technique. If the previous version block is selected as a write target block, there is a change according to the DCW technique Only partial write operations are possible.

다시 말해, 어떤 기존 파일에 관하여 활성화된 원본 블록과 비활성화된 직전 버전 블록이 유지되고 있는 중에, 원본 블록에 대해 갱신되는 데이터는 직전 버전 블록 위에 덮어쓰기된다.In other words, while an active original block and an inactive previous version block are held for an existing file, the data updated for the original block is overwritten on the previous version block.

이러한 쓰기 연산에 의해, 직전 버전 블록 위에 쓰기 연산된 블록이 이제 새로운 활성화된 원본 블록으로, 쓰기 연산 전까지의 원본 블록은 이제 비활성화된 직전 버전 블록으로 각각 설정될 준비가 된다.By this write operation, the block written on the previous version block is now ready to be set as the new activated original block, and the original block before the write operation is now set as the inactive previous version block, respectively.

실시예에 따라, 직전 버전 블록은 해당 데이터 블록의 갱신이 있기 전까지는 다른 파일들의 데이터가 덮어쓰기 되지 않도록 쓰기 보호 및 유지될 수 있는데, 이 경우 추후의 갱신 시에 효율적으로 선정될 수 있도록 관리될 수 있는 반면에, 보호된 직전 버전 블록들이 저장 공간을 과도하게 차지할 수도 있다.According to the embodiment, the previous version block may be write protected and maintained so that data of other files are not overwritten until the corresponding data block is updated. In this case, it is managed so as to be efficiently selected at a later update time While protected previous version blocks may over-occupy storage space.

다른 실시예에서는, 직전 버전 블록은, 다른 파일들의 데이터를 위한 쓰기 연산 대상 블록의 선정 시에, 쓰기 보호되지 않고 빈 블록과 마찬가지로 취급되거나, 또는 쓰기 보호되지는 않지만 빈 블록보다는 상대적으로 비우선적으로 데이터 쓰기 연산의 대상 블록에 선정될 수 있는데, 이 경우에는 저장 공간은 효율적으로 사용될 수 있지만 직전 버전의 갱신 효율이 다소 저하될 수 있다.In another embodiment, the previous version block is treated as if it were not write-protected and is treated as an empty block at the time of selection of a write operation target block for data of other files, or is not write-protected but is relatively non- May be selected in the target block of the data write operation. In this case, the storage space may be efficiently used, but the updating efficiency of the previous version may be somewhat lowered.

한편, 데이터 블록들의 쓰기 연산이 진행 중에 호스트 시스템이 멈추거나 고장을 일으키는 경우에 원자성의 보장에 관하여 설명하면, 예를 들어 완전히 신규한 파일 데이터의 쓰기 연산이 완료되기 전에 호스트 시스템이 실패하더라도, 체크포인트 트랜잭션이 일어나기 전에 해당 파일이 애초에 존재하지 않았던 상태의 호스트 시스템으로 복구될 수 있다.If the host system stops or a failure occurs during the write operation of the data blocks, the assurance of the atomicity will be described. For example, even if the host system fails before the write operation of completely new file data is completed, Before a point transaction occurs, the file can be restored to a host system that did not exist in the original.

또한 예를 들어 기존 파일에 대한 부가 데이터 또는 갱신 데이터를 빈 블록에 쓰기 연산하기가 완료되기 전에 호스트 시스템이 실패하더라도, 체크포인트 트랜잭션이 일어나기 직전의 원본 블록과 원본 트리 구조는 전혀 영향을 받지 않고 그대로 유지되므로 체크포인트 트랜잭션 이전의 호스트 시스템으로 복구될 수 있다.In addition, for example, even if the host system fails before writing the additional data or update data to the existing block in the existing file, the original block immediately before the checkpoint transaction occurs and the original tree structure are not affected at all It can be restored to the host system before the checkpoint transaction.

체크포인트 트랜잭션에 포함된 데이터의 쓰기 연산이 성공적으로 완료된 후에는, 최신의 파일 시스템을 구성하는 원본 블록들 및 갱신 버전 블록들을 각각 가리키는 포인터들을 적절히 생성, 삭제 내지 변경하여 파일 트리 구조를 적절하게 수정하고, 변경된 파일 트리 구조를 호스트 시스템에 연결하여야 한다.After the write operation of the data included in the checkpoint transaction is successfully completed, the file tree structure is appropriately modified to properly create, delete or change pointers indicating the original blocks and the update version blocks constituting the latest file system And connect the modified file tree structure to the host system.

이를 위해, 트리 구조 관리부(14)는 직전 트리 구조가 온전히 존재하는 경우에는, 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.In order to do this, the tree structure management unit 14 constructs a new source tree structure by updating the immediately preceding tree structure so as to point to the newly written data blocks and the original blocks that have not been updated, Set the host system to point to the root node of the new source tree structure.

이러한 새로운 원본 트리 구조의 루트 노드를 호스트 시스템에 연결함으로써, 갱신 전의 원본 블록들을 가리키던 갱신 전의 원본 트리 구조의 루트 노드는 호스트 시스템으로부터 분리되고, 비활성화 상태의 직전 트리 구조로 자연스럽게 전환된다.By connecting the root node of the new original tree structure to the host system, the root node of the original tree structure before the update pointing to the original blocks before the update is separated from the host system and is naturally switched to the inactive tree structure in the inactive state.

경우를 나누어 구체적으로 설명하면, 먼저, 신규한 파일을 생성하는 경우에는, 트리 구조 관리부(14)는 새로 쓰기 연산된 데이터 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.In the case of generating a new file, the tree structure management unit 14 updates the previous tree structure so as to point to newly-written data blocks, forms a new source tree structure, Set the system to point to the root node of the new source tree structure.

기존 파일의 원본 블록을 최초로 갱신하는 경우, 직전 버전 블록이 손상 내지 유실된 경우 또는 기존 파일의 원본 블록에 부가 데이터를 부가하는 경우와 같이 직전 버전 블록이 온전히 존재하지 않는 경우에는, 트리 구조 관리부(14)는 새로 쓰기 연산된 갱신 버전 블록들 또는 부가 블록들 및 원본 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.In the case where the previous version block is not completely present, such as when the original block of the existing file is first updated, when the previous version block is damaged or lost, or when additional data is added to the original block of the existing file, 14) updates the previous tree structure to point to the updated version blocks or the additional blocks and the original blocks that have been newly written, constitutes a new source tree structure, and sets the host system to point to the root node of the new source tree structure .

또한, 직전 버전 블록과 직전 트리 구조가 온전히 존재하고 기존 파일의 원본 블록을 갱신하는 경우에는, 트리 구조 관리부(14)는 직전 버전 블록들에 덮어 쓴 갱신 버전 블록들 및 원본 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.When the previous version block and the immediately preceding tree structure exist completely and the original block of the existing file is updated, the tree structure management unit 14 updates the previous version tree and the previous version tree so as to point to the updated version blocks and the original blocks overwritten to the previous version blocks. Updates the structure to construct a new source tree structure, and sets the host system to point to the root node of the new source tree structure.

실시예에 따라서, 트리 구조 관리부(14)는 직전 트리 구조를 구성하는 아이노드 블록 및 포인터 블록들을 해당 데이터 블록의 갱신이 있기 전까지 다른 파일들을 덮어쓰지 않도록 쓰기 보호할 수 있는데, 이 경우 추후의 갱신에 대비할 수 있는 반면에, 보호된 직전 버전 블록들이 저장 공간을 과도하게 차지할 수도 있다. According to the embodiment, the tree structure management unit 14 can write-protect the inode block and the pointer blocks constituting the immediately preceding tree structure so as not to overwrite other files until the corresponding data block is updated. In this case, While the protected previous version blocks may take up too much storage space.

다른 실시예에서는, 다른 파일들을 위한 트리 구조를 저장하기 위한 쓰기 연산 대상 블록 선정 시에, 직전 트리 구조를 구성하는 아이노드 블록 및 포인터 블록들은 쓰기 보호되지 않고 빈 블록과 마찬가지로 취급되거나, 또는 쓰기 보호되지는 않더라도 빈 블록보다는 비우선적으로 대상 블록에 선정될 수 있는데, 이 경우에는 저장 공간은 효율적으로 사용될 수 있지만 직전 버전의 갱신 효율이 다소 저하될 수 있다.In another embodiment, in selecting a write operation target block for storing a tree structure for other files, the inode block and the pointer blocks constituting the previous tree structure are treated as if they are not write-protected and empty blocks, It is possible to select the target block in priority to the target block rather than the empty block. In this case, the storage space can be efficiently used, but the updating efficiency of the previous version may be somewhat lowered.

또 다른 실시예에서는, 직전 버전 블록들의 위치는 스토리지(20) 내부에 특별히 마련된 영역에, 또는 외부의 저장 공간, 예를 들어, 버퍼 캐시 또는 메인 메모리에 저장되어 유지될 수 있다.In another embodiment, the location of the previous version blocks may be stored in an area specially provided within the storage 20 or in an external storage space, for example, a buffer cache or main memory.

또 다른 실시예에서는, 하나의 트리 구조가 어떤 파일에 관하여 현재 버전의 데이터 블록을 포인팅하는 포인터와 그 데이터 블록의 직전 버전의 데이터 블록을 포인팅하는 포인터를 하나의 쌍으로 포함할 수도 있다. 이 경우, 직전 버전 블록의 위치를 O(1)의 낮은 시간 복잡도로 탐색할 수 있는 장점이 있지만 공간 효율성을 저하시키는 트레이드오프 관계가 발생한다. 따라서, 설계 목적에 따라 실시예들을 탄력적으로 선택할 수 있다.In another embodiment, one tree structure may include a pointer that points to the current version of the data block with respect to a file, and a pointer that points to the data block of the previous version of the data block. In this case, although there is an advantage in that the position of the previous version block can be searched with a low temporal complexity of O (1), a tradeoff relationship that lowers space efficiency occurs. Therefore, embodiments can be flexibly selected according to the design purpose.

만약, 직전 트리 구조가 보호되지 않아 덮어쓰기되거나, 그 밖의 이유로 직전 트리 구조가 온전하게 존재하지 않은 경우에는, 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록, 직전 트리 구조 대신에, 원본 트리 구조의 갱신되지 않는 부분과 새로 쓰기 연산된 데이터 블록들을 위한 새로운 포인터들을 조합하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.If the previous tree structure is not protected and is overwritten, or if the previous tree structure is not perfectly present for other reasons, it is possible to replace the previous tree structure by pointing to newly written data blocks and un- , A new source tree structure is constructed by combining the unrecovered portion of the source tree structure and the new pointers for the newly written data blocks, and the host system is set to point to the root node of the new source tree structure.

데이터 블록들의 쓰기 연산이 완료되고 직전 트리 구조가 갱신되는 중에 또는 신규한 트리 구조가 생성되는 중에, 호스트 시스템이 멈추거나 고장을 일으키더라도, 체크포인트 트랜잭션이 일어나기 직전의 원본 트리 구조 및 루트 노드는 여전히 온전하게(intact) 존재하므로 호스트 시스템은 문제없이 복구될 수 있다.Even if the write operation of the data blocks is completed and the host system stops or fails while the previous tree structure is being updated or a new tree structure is being created, the source tree structure and the root node just before the checkpoint transaction takes place are still Because it is intact, the host system can be recovered without problems.

이렇듯, 본 발명의 듀얼 버퍼링 파일 관리 시스템(10)은 지속적으로 갱신되는 어떤 파일에 관하여, 최신 버전의 데이터 블록들을 포인팅하는 활성화된 원본 트리 구조와 직전 버전의 데이터 블록들을 포인팅하는 비활성화된 직전 트리 구조를 유지하며, 만약 갱신이 있으면 비활성화된 직전 트리 구조를 참조하여 선정한 직전 버전의 데이터 블록 위에 갱신된 데이터를 DCW 기법으로 저장함으로써 쓰기 연산을 최소화하고, 직전 트리 구조를 갱신한 최신 버전의 트리 구조를 호스트 시스템에 연결함으로써, 원자성을 제공할 수 있다. As described above, the dual buffering file management system 10 according to the present invention includes an active source tree structure for pointing a latest version of data blocks and a deactivated direct tree structure pointing to a previous version data block If there is an update, the latest version of the tree structure that updates the previous tree structure is minimized by storing the updated data on the selected previous data block by the DCW method with reference to the inactive previous tree structure. By connecting to a host system, atomicity can be provided.

또한 본 발명의 듀얼 버퍼링 파일 관리 시스템(10)은, 종전까지의 최신 버전이 직전 버전으로 전환되기 때문에, 별도로 데이터 비교 쓰기를 할 최적의 블록을 선정하기 위해 해밍 거리 연산 등을 통해 가장 유사한 블록을 찾을 필요없이, 단지 직전 버전이 차지하고 있던 블록을 쓰기 대상 블록으로 선정할 수 있다. 실제로 최신의 갱신된 버전은 직전 버전에 비해 단지 갱신이 두 차례만 있는 버전(즉, 직전 버전 - 현재 원본 - 갱신 버전)이므로, 해당 블록에 저장할 버전은 저장된 버전에 대해 상당 부분에서 유사할 것이고, 데이터 비교 쓰기 연산 효율도 높을 것으로 예상된다.In the dual buffering file management system 10 of the present invention, since the latest version up to the previous version is switched to the previous version, the most similar block is selected through the hamming distance calculation or the like in order to select the optimum block for data comparison writing separately You do not need to look up, you can just select the block that the previous version occupied as the write target block. Since the latest updated version is actually a version that has only two updates compared to the previous version (i.e., the previous version-the current version-the current version), the version to be stored in the block will be substantially similar to the stored version, The data comparison write operation efficiency is expected to be high.

다만, 높은 수준의 원자성 및 쓰기 연산 부하 절감을 제공하기 위해 비활성화된 상태의 직전 버전을 관리하여야 하므로, 저장 공간 측면에서 다소 불리한 점이 있으나, 이러한 저장 공간 오버헤드는 파일 단위가 아닌 블록 단위로 직전 버전과 현재 원본을 유지함으로써 최소화할 수 있다.However, in order to provide a high level of atomicity and write operation load reduction, it is necessary to manage the previous version of the deactivated state, which is somewhat disadvantageous in terms of storage space. However, It can be minimized by maintaining the version and current source.

예를 들어, 100 개의 블록으로 이루어진 파일에서 지금까지 10 개의 블록들은 갱신되어 왔고 90 개의 블록들은 한 번도 갱신되지 않은 경우에, 갱신이 일어난 10 개의 블록에 대해서만 원본 버전과 직전 버전이 유지 관리되고, 90 개의 블록들은 원본만 유지하는 식으로 파일 트리 구조가 관리될 수 있다. 이 경우, 공간 오버헤드는 100%가 아닌 10%에 불과하다.For example, if 10 blocks have been updated in a file of 100 blocks so far and 90 blocks have not been updated at all, only the original version and the previous version are maintained for 10 blocks that have been updated, The file tree structure can be managed in such a manner that 90 blocks are retained only in the original. In this case, the space overhead is only 10%, not 100%.

또한 실제의 컴퓨터 시스템에서, 설치된 파일들의 대부분은 갱신되지 않고 유지되며, 갱신되는 파일에서도 대부분의 컨텐츠는 유지되기 때문에, 실제로도 공간 오버헤드로 인한 손실은 원자성 보장과 쓰기 성능 향상이라는 이득에 비해 매우 작아 무시할 만하다.Also, in a real computer system, most of the installed files are kept un-updated, and most of the contents are maintained in the updated file. In fact, the loss due to space overhead is in contrast to the benefit of atomicity guarantee and write performance improvement It is small and negligible.

잠시 도 2 내지 도 4를 참조하면, 도 2 내지 도 4는 본 발명의 일 실시예에 따른 듀얼 버퍼링 파일 관리 시스템에서 블록이 갱신될 때 파일 트리 구조의 순차적인 변화를 예시한 개념도들이다.Referring to FIGS. 2 to 4, FIG. 2 to FIG. 4 are conceptual diagrams illustrating sequential changes of a file tree structure when a block is updated in a dual buffering file management system according to an embodiment of the present invention.

도 2 내지 도 4에서, 도 1의 비휘발성 스토리지(20)의 원본 트리 구조(21)는, 최상위에 루트 노드(210)에 의해 포인팅되는 아이노드 블록(211)이 있고, 아이노드 블록(211) 내에 특정 파일(26)을 가리키는 아이노드(212)가 있다.2 to 4, the original tree structure 21 of the nonvolatile storage 20 of FIG. 1 has an inode block 211 that is pointed by the root node 210 at the top, and an inode block 211 There is an inode 212 pointing to a specific file 26 in the file name.

도 2를 참조하면, 파일(26)의 데이터 블록들 중 네 개의 데이터 블록(D1, D2, D3, D4)가 예시되어 있고, 각 데이터 블록들(D1 내지 D4)은 원본 트리 구조(21)의 포인터 블록들에 저장된 포인터들에 의해 포인팅된다.Referring to FIG. 2, four data blocks D1, D2, D3 and D4 among the data blocks of the file 26 are illustrated, and each of the data blocks D1 to D4 corresponds to the data block of the original tree structure 21 And is pointed by the pointers stored in the pointer blocks.

특정 파일(26)은 D1 내지 D4의 최초의 버전이 저장되고 아직 갱신이 일어나지 않은 상태이다.The specific file 26 is a state in which the first version of D1 to D4 is stored and the update has not yet occurred.

한편 스토리지(20) 내에는 사용되지 않은 빈 블록(271)이 예비되어 있다.On the other hand, an unused empty block 271 is reserved in the storage 20.

도 3은 도 2의 파일 트리 구조에서, 파일의 최초 갱신이 있을 경우에, 데이터 블록의 신규 생성과, 새로운 원본 트리 구조의 생성 및 시스템 연결을 예시하고, 도 4는 도 3의 1차 갱신된 파일 트리 구조에서 재갱신이 있을 경우의 데이터 블록의 갱신과, 직전 트리 구조의 갱신 및 시스템 연결을 예시한다.FIG. 3 illustrates the creation of a new block of data, the creation of a new source tree structure and the system connection when the file is first updated in the file tree structure of FIG. 2, The update of the data block in the case of re-updating in the file tree structure, the updating of the previous tree structure, and the system connection are illustrated.

도 3을 참조하면, 기존의 도 2의 파일(26)의 데이터 블록들(D1 내지 D4) 중 일부 데이터 블록(D4)에 대하여 갱신이 있을 경우에, 갱신된 데이터 블록(D4')이 도 2에서 사용되지 않던 빈 블록(271)에 쓰기 연산되어 갱신된 파일(26')이 된다.3, when there is an update to some data blocks D4 among the data blocks D1 to D4 of the existing file 26 of FIG. 2, the updated data block D4 ' Is written into the empty block 271 that has not been used in the file 26 '.

이어서, 갱신된 데이터 블록(D4')을 위한 실선의 포인터들이 지정되고, 갱신이 없는 기존의 원본 블록들(D1 내지 D3)을 가리키는 포인터들과 함께 새로운 원본 트리 구조인 갱신 파일 트리 구조(22)를 형성한다.Then, the pointers of the solid line for the updated data block D4 'are designated, and the update file tree structure 22, which is a new source tree structure together with pointers to the existing original blocks D1 to D3, .

이어서, 갱신 파일 트리 구조(22)의 최상위 엔트리인 루트 노드(220)를 포인팅하도록 호스트 시스템에 연결함으로써 갱신 파일 트리 구조(22)를 활성화한다. 갱신 파일 트리 구조(22)는 새로운 원본 트리 구조가 되고, 도 2의 기존의 원본 트리 구조(21)는 호스트 시스템과 연결이 끊어지고 비활성 상태의 직전 트리 구조(21')로 전환된다.The update file tree structure 22 is then activated by connecting to the host system to point to the root node 220, which is the top entry of the update file tree structure 22. The update file tree structure 22 becomes a new source tree structure, and the existing source tree structure 21 of FIG. 2 is disconnected from the host system and converted into the inactive tree structure 21 '.

호스트 시스템은 갱신 파일 트리 구조(22)를 통해 갱신된 파일(26')이 데이터 블록들(D1 내지 D3과 D4')로 구성되는 것으로 인식한다.The host system recognizes via the update file tree structure 22 that the updated file 26 'is composed of the data blocks D1 to D3 and D4'.

도 4를 참조하면, 도 3에서 갱신된 파일(26')에 대해 일부 데이터 블록(D')에 대하여 재갱신이 있을 경우에, 재갱신된 데이터 블록(D'')이 도 3에 직전 버전으로 설정된 데이터 블록(D4) 위에 각각 덮어쓰기 연산되어 갱신된 파일(26'')이 된다.Referring to FIG. 4, if there is a re-update for some data block D 'for the updated file 26' in FIG. 3, the re-updated data block D ' Is overwritten on the data block D4 set to be the updated file 26 ".

이어서, 도 3의 직전 트리 구조(21')를 참조하여, 재갱신된 데이터 블록(D4'')을 위한 실선의 포인터들이 지정되고, 갱신이 없는 기존의 원본 블록들(D1 내지 D3)을 가리키는 포인터들과 함께 재갱신 파일 트리 구조(21'')를 형성한다.Next, referring to the previous tree structure 21 'of Fig. 3, the solid line pointers for the re-updated data block D4 " are designated, and the original original blocks D1 to D3 And forms a re-update file tree structure 21 " together with pointers.

이어서, 재갱신 파일 트리 구조(21'')의 최상위 엔트리인 루트 노드(210'')를 포인팅하도록 호스트 시스템에 연결함으로써 재갱신 파일 트리 구조(21'')를 활성화한다. 재갱신 파일 트리 구조(21'')는 새로운 원본 트리 구조가 되고, 도 3의 갱신 파일 트리 구조(22)는 호스트 시스템과 연결이 끊어지고 비활성 상태의 직전 트리 구조(22')로 전환된다.It then activates the re-update file tree structure 21 " by connecting to the host system to point to the root node 210 ", which is the top entry of the re-update file tree structure 21 ". The re-update file tree structure 21 " becomes a new source tree structure, and the update file tree structure 22 of FIG. 3 is disconnected from the host system and switched to the inactive tree structure 22 '.

호스트 시스템은 재갱신 파일 트리 구조(21'')를 통해 재갱신된 파일(26'')이 데이터 블록들(D1 내지 D3과 D4'')로 구성되는 것으로 인식한다.The host system recognizes that the re-updated file 26 '' is composed of the data blocks D1 to D3 and D4 '' through the re-update file tree structure 21 ''.

도 5는 본 발명의 일 실시예에 따른 듀얼 버퍼링 대용량 스토리지 장치를 예시한 블록도이다.5 is a block diagram illustrating a dual buffering mass storage device according to an embodiment of the present invention.

도 5를 참조하면, 듀얼 버퍼링 대용량 스토리지 장치(50)는 체크포인트 트랜잭션 생성부(51), 쓰기 블록 선정부(52), 쓰기 연산 처리부(53), 트리 구조 관리부(54) 및 비휘발성 스토리지(55)를 포함할 수 있다.5, the dual buffering mass storage device 50 includes a checkpoint transaction generating unit 51, a write block selecting unit 52, a write operation processing unit 53, a tree structure managing unit 54, and a nonvolatile storage 55).

비휘발성 스토리지(55)의 구조는 도 1의 비휘발성 스토리지(20)와 실질적으로 동일하므로 설명을 생략한다.The structure of the non-volatile storage 55 is substantially the same as that of the non-volatile storage 20 of FIG.

체크포인트 트랜잭션 생성부(51)는 소정 시간의 경과, 또는 외부의 버퍼 캐시(100) 내에 신규 생성되거나 부가된 클린 캐시 블록 또는 갱신된 더티 캐시 블록들의 갯수와 같은 소정의 조건이 만족하면, 버퍼 캐시 내에서 쓰기 연산의 대상이 되는 더티 캐시들의 컨텐츠들을 비휘발성 스토리지(55)에 기록하기 위한 체크포인트 트랜잭션을 생성한다.When a predetermined condition such as a predetermined time or a number of newly created or added clean cache blocks or updated dirty cache blocks in the external buffer cache 100 is satisfied, the checkpoint transaction generating unit 51 generates a checkpoint transaction In the non-volatile storage 55, the contents of the dirty caches subject to the write operation.

체크포인트 트랜잭션 생성부(51)는, 일 실시예에서는, 비휘발성 스토리지(55)의 파일 시스템을 관리하기 위한 듀얼 버퍼링 대용량 스토리지 장치(50)의 일부일 수 있지만, 다른 실시예에서는, 버퍼 캐시(100)를 관리하는 버퍼 캐시 관리부(101)의 일부일 수도 있다.The checkpoint transaction generator 51 may be part of a dual buffering mass storage device 50 for managing the file system of the non-volatile storage 55 in one embodiment, but in another embodiment, the buffer cache 100 The buffer cache management unit 101 may be a part of the buffer cache management unit 101.

또 다른 실시예에서, 체크포인트 트랜잭션 생성부(51)는 비휘발성 스토리지(55)로 쓰기 연산되기 위한 체크포인트 트랜잭션을 메인 메모리로부터 직접 생성할 수도 있다.In another embodiment, the checkpoint transaction generator 51 may generate a checkpoint transaction for writing to the nonvolatile storage 55 directly from the main memory.

이 경우에는, 체크포인트 트랜잭션 생성부(51)는 시간의 경과와 같은 소정의 조건이 만족하면, 쓰기 연산의 대상이 되는 메모리 블록들의 컨텐츠들을 버퍼 캐시를 거치지 않고 직접 비휘발성 스토리지(55)에 기록하기 위한 체크포인트 트랜잭션을 생성한다.In this case, when the predetermined condition such as the lapse of time is satisfied, the checkpoint transaction generating unit 51 writes the contents of the memory blocks targeted for the write operation directly to the nonvolatile storage 55 without going through the buffer cache Create a checkpoint transaction to do this.

쓰기 블록 선정부(52)는, 체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록의 직전 버전 블록들을 비휘발성 스토리지(55) 내에서 탐색하고, 탐색 결과에 따라 쓰기 대상 블록을 선정한다.The write block selection unit 52 searches the nonvolatile storage 55 for the previous version blocks of the original block corresponding to the data included in the checkpoint transaction and selects the block to be written according to the search result.

다만, 쓰기 블록 선정부(52)는, 만약 체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록 또는 원본 블록의 직전 버전 블록을 탐색할 수 없는 경우, 다시 말해 쓰기될 데이터가 만약 신규 파일이거나, 기존 파일에 부가되거나 기존 파일의 갱신되는 부분이 처음으로 갱신되는 경우로서 원본 블록의 직전 버전 블록이 비휘발성 스토리지(55) 내에 존재하지 않거나, 비휘발성 스토리지(55) 내에 참조할 비활성화된 직전 트리 구조가 없는 경우에는, 비휘발성 스토리지(55) 내의 빈 블록을 쓰기 대상 블록으로 선정할 수 있다.However, if the write block selecting unit 52 can not find the previous block of the original block or the original block corresponding to the data included in the checkpoint transaction, that is, if the data to be written is a new file, File or an updated portion of an existing file is updated for the first time, if the immediately previous version block of the original block is not present in the non-volatile storage 55, or if the deactivated previous tree structure to be referenced in the non-volatile storage 55 is If there is no empty block, the empty block in the nonvolatile storage 55 can be selected as a write target block.

구체적으로, 쓰기 블록 선정부(52)는 체크포인트 트랜잭션에 포함된 데이터가 신규 파일의 데이터인 경우에는 비휘발성 스토리지(55) 내의 빈 블록을 쓰기 대상 블록으로 선정한다.Specifically, when the data included in the checkpoint transaction is data of a new file, the write block selecting unit 52 selects an empty block in the nonvolatile storage 55 as a write target block.

또한 쓰기 블록 선정부(52)는 체크포인트 트랜잭션에 포함된 데이터가 비휘발성 스토리지(55) 내에 이미 존재하는 파일의 갱신 데이터로서 직전 트리 구조가 존재하지 않는 경우에는 비휘발성 스토리지(55) 내의 빈 블록을 쓰기 대상 블록으로 선정한다.If the data included in the checkpoint transaction does not exist in the previous tree structure as update data of a file already existing in the nonvolatile storage 55, the write block selection unit 52 sets the empty block in the nonvolatile storage 55 Is selected as the write target block.

또한 쓰기 블록 선정부(52)는 비휘발성 스토리지(55) 내의 직전 트리 구조 및 원본 트리 구조를 참조하여, 직전 트리 구조가 존재하고 해당 갱신 데이터에 상응하는 기존 파일의 데이터 블록에 대한 직전 트리 구조 내의 포인터와 현재 원본 트리 구조의 상응하는 포인터가 서로 동일한 경우에는, 직전 버전 블록이 보전된 적이 없는 경우로 판정하고, 비휘발성 스토리지(55) 내의 빈 블록을 쓰기 대상 블록으로 선정한다.The write block selection unit 52 also refers to the previous tree structure and the original tree structure in the nonvolatile storage 55 to determine whether or not the previous tree structure exists and which is in the previous tree structure for the data block of the existing file corresponding to the update data If the pointer and the corresponding pointer of the current source tree structure are equal to each other, it is determined that the previous version block has not been held, and an empty block in the nonvolatile storage 55 is selected as the write target block.

반면에, 체크포인트 트랜잭션에 포함된 데이터의 원본 블록에 대해 직전 버전 블록이 보전되어 있는 경우에는, 쓰기 블록 선정부(52)는 직전 버전 블록들을 쓰기 대상 블록으로 선정한다.On the other hand, when the previous version block is held for the original block of the data included in the checkpoint transaction, the write block selection unit 52 selects the previous version blocks as the write target block.

좀더 구체적으로, 쓰기 블록 선정부(52)는 직전 트리 구조 및 원본 트리 구조를 참조하여, 직전 트리 구조가 존재하고 해당 갱신 데이터에 상응하는 기존 파일의 데이터 블록에 대한 직전 트리 구조 내의 포인터와 현재 원본 트리 구조의 상응하는 포인터가 서로 다르면, 직전 버전 블록이 보전되어 있는 경우로 판정하고, 비휘발성 스토리지(55) 내에서 직전 트리 구조 내의 포인터에 의해 포인팅되는 직전 버전 블록을 쓰기 대상 블록으로 선정한다.More specifically, the write block selection unit 52 refers to the immediately preceding tree structure and the source tree structure, and finds a pointer in the immediately preceding tree structure for the data block of the existing file corresponding to the corresponding update data, If the corresponding pointers of the tree structure are different from each other, it is determined that the previous version block is held, and the previous version block pointed by the pointer in the previous tree structure in the nonvolatile storage 55 is selected as the write target block.

한편, 만약 체크포인트 트랜잭션에 포함된 데이터가 갱신 데이터가 아닌 이미 존재하는 파일에 부가되는 데이터라면, 기존 파일에 관한 데이터이기는 하지만 갱신할 원본이라고 할 대상이 없기 때문에, 쓰기 블록 선정부(52)는, 신규 파일의 경우와 유사하게, 빈 블록을 쓰기 대상 블록으로 선정한다.On the other hand, if the data included in the checkpoint transaction is data to be added to an existing file rather than update data, since there is no object to be updated although it is data on an existing file, the write block selecting section 52 , An empty block is selected as a write target block, similarly to the case of a new file.

쓰기 연산 처리부(53)는 선정된 쓰기 대상 블록에 체크포인트 트랜잭션에 포함된 데이터를 쓰기 연산한다.The write operation processing unit 53 writes data included in the checkpoint transaction into the selected write target block.

구체적으로, 쓰기 연산 처리부(53)는 데이터 비교 쓰기(DCW) 기법에 따라, 쓰기 연산되는 데이터 블록 내에서도 실제로 변경이 있는 부분만 쓰기 연산할 수 있다.Specifically, the write operation processing unit 53 can write only the portion that has actually changed even in the data block to be written in accordance with the data comparison write (DCW) technique.

다시 말해, 어떤 기존 파일에 관하여 활성화된 원본 블록과 비활성화된 직전 버전 블록이 유지되고 있는 중에, 원본 블록에 대해 갱신되는 갱신 데이터는 직전 버전 블록 위에 덮어쓰기된다.In other words, while an active original block and a deactivated previous version block are held for an existing file, the update data updated for the original block is overwritten on the previous version block.

이러한 쓰기 연산에 의해, 쓰기 연산된 블록이 이제 새로운 원본 블록이고, 쓰기 연산 전까지의 원본 블록은 이제 직전 버전 블록으로 설정된다.By this write operation, the write operation block is now a new original block, and the original block before the write operation is now set to the previous version block.

실시예에 따라, 직전 버전 블록은 해당 블록의 갱신이 있기 전까지 쓰기 보호 및 유지될 수 있다.According to an embodiment, the previous version block may be write protected and maintained until there is an update of that block.

다른 실시예에서는, 직전 버전 블록은 쓰기 보호되지 않고 빈 블록과 마찬가지로 취급되거나 또는 전적으로 쓰기 보호되지는 않더라도 빈 블록보다는 비우선적으로 데이터 쓰기 연산의 대상 블록에 선정될 수 있다.In another embodiment, the previous version block is not write-protected and may be handled like an empty block, or may be selected in the target block of the data write operation in preference to an empty block, even if it is not entirely write-protected.

이어서, 트리 구조 관리부(54)는 비휘발성 스토리지(55) 내에서 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록 구성된 새로운 원본 트리 구조의 루트 노드를 호스트 시스템이 포인팅하도록 설정한다.Then, the tree structure management unit 54 sets the host system to point to the root node of the new source tree structure configured to point to the newly written data blocks and the unrecovered original blocks in the non-volatile storage 55.

경우를 나누어 구체적으로 설명하면, 먼저, 신규한 파일을 생성하는 경우에는, 트리 구조 관리부(54)는 비휘발성 스토리지(55) 내에서 새로 쓰기 연산된 데이터 블록들을 추가로 포인팅되도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.In the case of generating a new file, the tree structure management unit 54 updates the previous tree structure so as to additionally point the newly written data blocks in the nonvolatile storage 55 To construct a new source tree structure, and to set the host system to point to the root node of the new source tree structure.

기존 파일의 원본 블록을 최초로 갱신하는 경우, 직전 버전 블록이 손상 내지 유실된 경우 또는 기존 파일의 원본 블록에 부가 데이터를 부가하는 경우와 같이 직전 트리 구조는 존재하지만 직전 버전 블록이 온전히 존재하지 않는 경우에는, 트리 구조 관리부(54)는 비휘발성 스토리지(55) 내에서 새로 쓰기 연산된 갱신 버전 블록들 또는 부가 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.When the original block of the existing file is updated first, the previous version block is damaged or lost, or the previous tree structure exists, such as when additional data is added to the original block of the existing file, but the previous version block is not completely present , The tree structure management unit 54 constructs a new source tree structure by updating the immediately preceding tree structure so as to point to the updated version blocks or the additional blocks newly written in the nonvolatile storage 55, Set to point to the root node of the tree structure.

또한, 직전 버전 블록이 있으면서 기존 파일의 원본 블록을 갱신하는 경우에는, 트리 구조 관리부(54)는 비휘발성 스토리지(55) 내에서 직전 버전 블록들에 덮어 쓴 갱신 버전 블록들에 관한 포인터들 및 원본 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.When updating the original block of the existing file with the previous version block, the tree structure management unit 54 stores pointers about the update version blocks overwritten in the previous version blocks in the nonvolatile storage 55, Updates the previous tree structure to point to the blocks, constructs a new source tree structure, and sets the host system to point to the root node of the new source tree structure.

실시예에 따라서, 트리 구조 관리부(54)는 직전 트리 구조를 구성하는 아이노드 블록 및 포인터 블록들을 해당 데이터 블록의 갱신이 있기 전까지 쓰기 보호할 수 있다. According to the embodiment, the tree structure management unit 54 can write-protect the inode block and the pointer blocks constituting the previous tree structure until the corresponding data block is updated.

다른 실시예에서는, 직전 트리 구조를 구성하는 아이노드 블록 및 포인터 블록들은 쓰기 보호되지 않고 빈 블록과 마찬가지로 취급되거나, 또는 쓰기 보호되지는 않더라도 빈 블록보다는 비우선적으로 데이터 쓰기 연산의 대상 블록에 선정될 수 있다.In another embodiment, the inode block and the pointer blocks constituting the immediately preceding tree structure are handled in the same manner as the empty block without being write-protected, or even if they are not write-protected, .

또 다른 실시예에서는, 직전 버전 블록들의 위치는 비휘발성 스토리지(55) 내부에 특별히 마련된 영역에, 또는 외부의 저장 공간, 예를 들어, 버퍼 캐시 또는 메인 메모리에 저장되어 유지될 수 있다.In yet another embodiment, the location of the previous version blocks may be stored in an area specifically provided within the nonvolatile storage 55 or in an external storage space, e.g., a buffer cache or main memory.

또 다른 실시예에서는, 하나의 트리 구조가 어떤 파일에 관하여 현재 버전의 데이터 블록을 포인팅하는 포인터와 그 데이터 블록의 직전 버전의 데이터 블록을 포인팅하는 포인터를 하나의 쌍으로 포함할 수도 있다.In another embodiment, one tree structure may include a pointer that points to the current version of the data block with respect to a file, and a pointer that points to the data block of the previous version of the data block.

또 다른 실시예에서, 직전 트리 구조가 온전하게 존재하지 않은 경우에는, 트리 구조 관리부(54)는, 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록, 원본 트리 구조의 갱신되지 않는 부분과 새로 쓰기 연산된 데이터 블록들을 위한 새로운 포인터들을 조합하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정할 수 있다.In another embodiment, when the previous tree structure is not perfectly present, the tree structure management unit 54 updates the data structure of the original tree structure so as to point to the newly written data blocks and the original blocks that have not been updated And new pointers for newly written data blocks are combined to form a new source tree structure, and the host system can be set to point to the root node of the new source tree structure.

도 6은 본 발명의 일 실시예에 따른 듀얼 버퍼링 파일 관리 방법을 예시한 순서도이다.6 is a flowchart illustrating a dual buffering file management method according to an embodiment of the present invention.

도 6을 참조하면, 비휘발성 스토리지의 듀얼 버퍼링 파일 관리 방법은 단계(S61)에서, 쓰기 연산의 대상이 되는 컨텐츠들을 스토리지에 기록하기 위한 체크포인트 트랜잭션을 생성한다.Referring to FIG. 6, in step S61, a dual buffering file management method of non-volatile storage creates a checkpoint transaction for writing contents to be subjected to a write operation to storage.

구체적으로, 단계(S61)에서, 버퍼 캐시 내에서 쓰기 연산의 대상이 되는 더티 캐시들의 컨텐츠들을 스토리지에 기록하기 위한 체크포인트 트랜잭션을 생성할 수 있다.Specifically, in step S61, a checkpoint transaction may be created to write the contents of the dirty caches subject to the write operation in the buffer cache to the storage.

이때, 체크포인트 트랜잭션의 생성은 소정 시간의 경과, 또는 버퍼 캐시 내에 신규 생성되거나 부가된 또는 갱신된 더티 캐시 블록들의 갯수와 같은 소정의 조건에 기초하여 수행될 수 있다.At this time, the generation of the checkpoint transaction may be performed based on predetermined time elapsed or predetermined conditions such as the number of newly created or added or updated dirty cache blocks in the buffer cache.

다른 실시예에서, 단계(S61)는 쓰기 연산의 대상이 되는 메모리 블록들의 컨텐츠들을 버퍼 캐시를 거치지 않고 직접 스토리지에 기록하기 위한 체크포인트 트랜잭션을 생성할 수 있다.In another embodiment, step S61 may generate a checkpoint transaction to write the contents of the memory blocks subject to the write operation directly to the storage without going through the buffer cache.

이 경우에는, 체크포인트 트랜잭션의 생성은 시간의 경과와 같은 소정의 조건에 기초하여 수행될 수 있다.In this case, the generation of the checkpoint transaction may be performed based on a predetermined condition such as the passage of time.

단계(S62)에서, 체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록의 직전 버전 블록들을 비휘발성 스토리지 내에서 탐색하고, 탐색 결과에 따라 쓰기 대상 블록을 선정한다.In step S62, the previous version blocks of the original block corresponding to the data included in the checkpoint transaction are searched in the nonvolatile storage, and the block to be written is selected according to the search result.

구체적으로, 단계(S62)는, 만약 체크포인트 트랜잭션에 포함된 데이터에 상응하는 원본 블록 또는 원본 블록의 직전 버전 블록을 탐색할 수 없는 경우, 다시 말해, 쓰기될 데이터가 만약 신규 파일이거나, 기존 파일에 부가되거나 기존 파일의 갱신되는 부분이 처음으로 갱신되는 경우로서 원본 블록의 직전 버전 블록이 비휘발성 스토리지 내에 존재하지 않거나, 비휘발성 스토리지 내에 참조할 비활성화된 직전 트리 구조가 없는 경우에는, 비휘발성 스토리지 내의 빈 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.Specifically, step S62 is executed if it is not possible to search the original block or the previous version block of the original block corresponding to the data included in the checkpoint transaction, in other words, if the data to be written is a new file, Or the updated portion of the existing file is updated for the first time and the previous block of the original block is not present in the non-volatile storage or there is no deactivated previous tree structure to be referenced in the non-volatile storage, As an object block to be written.

좀더 구체적으로, 단계(S62)는, 체크포인트 트랜잭션에 포함된 데이터가 신규 파일의 데이터인 경우에는 비휘발성 스토리지 내의 빈 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.More specifically, if the data included in the checkpoint transaction is data of a new file, step S62 may include selecting an empty block in non-volatile storage as a block to be written.

또한 단계(S62)는, 체크포인트 트랜잭션에 포함된 데이터가 비휘발성 스토리지 내에 이미 존재하는 파일의 갱신 데이터로서 직전 버전 블록이 보전된 적이 없는 경우에도 비휘발성 스토리지 내의 빈 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다. In addition, in step S62, even if the data included in the checkpoint transaction has not been stored as update data of a file already existing in the nonvolatile storage, the empty block in the nonvolatile storage is selected as the write target block Step < / RTI >

좀더 구체적으로, 단계(S62)는, 비휘발성 스토리지 내의 직전 트리 구조 및 원본 트리 구조를 참조하여, 직전 트리 구조가 존재하고 해당 갱신 데이터에 상응하는 데이터 블록에 대한 직전 트리 구조 내의 포인터와 현재 원본 트리 구조의 상응하는 포인터가 서로 동일하면, 체크포인트 트랜잭션에 포함된 데이터를 직전 버전 블록이 보전된 적이 없는 경우로 판정하고, 비휘발성 스토리지 내의 빈 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.More specifically, in step S62, referring to the previous tree structure and the original tree structure in the non-volatile storage, a pointer in a previous tree structure for a data block corresponding to the corresponding update data exists, Determining that the data included in the checkpoint transaction is the case where the previous version block has not been retained and selecting an empty block in the non-volatile storage as a write target block if the corresponding pointers of the structures are equal to each other .

단계(S62)는, 반면에, 체크포인트 트랜잭션에 포함된 데이터의 원본 블록에 대해 직전 버전 블록이 보전되어 있는 경우에는, 직전 버전 블록들을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.If the previous version block is held for the original block of data included in the checkpoint transaction, step S62 may include selecting the previous version blocks as the write target block.

좀더 구체적으로, 단계(S62)는 직전 트리 구조 및 원본 트리 구조를 참조하여, 직전 트리 구조가 존재하고 해당 갱신 데이터에 상응하는 기존 파일의 데이터 블록에 대한 직전 트리 구조 내의 포인터와 현재 원본 트리 구조의 상응하는 포인터가 서로 다르면, 체크포인트 트랜잭션에 포함된 데이터를 직전 버전 블록이 보전되어 있는 경우로 판정하고, 비휘발성 스토리지 내에서 직전 트리 구조 내의 포인터에 의해 포인팅되는 직전 버전 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.More specifically, referring to the previous tree structure and the original tree structure, a previous tree structure exists and a pointer in a previous tree structure to a data block of an existing file corresponding to the corresponding update data, If the corresponding pointers are different from each other, the data included in the checkpoint transaction is judged to be the case where the previous version block is held, and the previous version block pointed by the pointer in the previous tree structure in the nonvolatile storage is selected as the write target block .

한편, 단계(S62)는, 만약 체크포인트 트랜잭션에 포함된 데이터가 갱신 데이터가 아닌 이미 존재하는 파일에 부가되는 데이터라면, 기존 파일에 관한 데이터이기는 하지만 갱신할 원본이라고 할 대상이 없기 때문에, 신규 파일의 경우와 유사하게, 빈 블록을 쓰기 대상 블록으로 선정하는 단계를 포함할 수 있다.On the other hand, if the data included in the checkpoint transaction is data added to an existing file but not the update data, since there is no object to be updated, , It may include a step of selecting an empty block as a write target block.

이어서, 단계(S63)에서, 선정된 쓰기 대상 블록에 체크포인트 트랜잭션에 포함된 데이터를 쓰기 연산한다.Subsequently, in step S63, data included in the checkpoint transaction is written to the selected block to be written.

구체적으로, 단계(S63)는, 데이터 비교 쓰기 기법에 따라 쓰기 연산되는 데이터 블록 중에서 변경된 부분만 쓰기 연산하는 단계를 포함할 수 있다.Specifically, step S63 may include writing only the changed portion of the data block to be written in accordance with the data comparison and writing technique.

좀더 구체적으로 단계(S63)은, 만약 빈 블록이 쓰기 대상 블록으로 선정된 경우에는 데이터 블록 전체를 쓰기 연산하고, 만약 직전 버전 블록이 쓰기 대상 블록으로 선정된 경우에는, 데이터 비교 쓰기 기법에 따라 갱신될 데이터 블록 중에서 변경된 부분만 쓰기 연산하는 단계를 포함할 수 있다.More specifically, in step S63, if the empty block is selected as the write target block, the entire data block is written. If the previous version block is selected as the write target block, And writing only the changed portion of the data block to be updated.

실시예에 따라, 직전 버전 블록은 해당 데이터 블록의 갱신이 있기 전까지 쓰기 보호 및 유지될 수 있다.According to an embodiment, the previous version block may be write protected and maintained until there is an update of the corresponding data block.

다른 실시예에서는, 직전 버전 블록은 쓰기 보호되지 않고 빈 블록과 마찬가지로 취급되거나 또는 쓰기 보호되지는 않더라도 빈 블록보다는 비우선적으로 데이터 쓰기 연산의 대상 블록에 선정될 수 있다.In another embodiment, the previous version block is not write-protected and may be handled like an empty block, or may be selected in the target block of the data write operation in preference to an empty block, even if it is not write protected.

이어서, 단계(S64)에서 비휘발성 스토리지 내에서 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.Next, in step S64, the previous tree structure is updated to point to the data blocks newly written in the nonvolatile storage and the unrevealed original block to construct a new original tree structure, and the host system creates a new original tree structure Set to point to the root node.

이러한 새로운 원본 트리 구조의 루트 노드를 호스트 시스템에 연결함으로써, 기존의 원본 블록들을 가리키던 기존의 원본 트리 구조의 루트 노드는 호스트 시스템으로부터 분리되고, 비활성화 상태의 직전 트리 구조로 자연스럽게 전환된다.By connecting the root node of the new source tree structure to the host system, the root node of the original source tree structure that points to the original source blocks is separated from the host system and is naturally switched to the inactive tree structure.

경우를 나누어 구체적으로 설명하면, 단계(S64)는 먼저, 신규 파일을 생성하는 경우에는, 비휘발성 스토리지 내에서 새로 쓰기 연산된 데이터 블록들을 추가로 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정한다.In step S64, first, in the case of generating a new file, the previous tree structure is updated so that newly written data blocks in the nonvolatile storage are further pointed, Configure the host system to point to the root node of the new source tree structure.

또한, 단계(S64)는, 직전 트리 구조가 온전히 존재하고 체크포인트 트랜잭션에 포함된 데이터가 기존 파일의 데이터이지만 직전 버전 블록이 존재하지 않은 경우에는, 비휘발성 스토리지 내에서 새로 쓰기 연산된 갱신 버전 블록들 또는 부가 블록들 및 원본 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하는 단계를 포함할 수 있다.If the previous tree structure is perfectly present and the data included in the checkpoint transaction is data of an existing file but the previous version block does not exist, then the step S64 updates the updated version block in the nonvolatile storage Updating the previous tree structure so as to point to the additional blocks and the original blocks to construct a new original tree structure, and setting the host system to point to the root node of the new original tree structure.

또한, 단계(S64)는, 직전 버전 블록이 있으면서 기존 파일의 원본 블록을 갱신하는 경우에는, 비휘발성 스토리지 내에서 직전 버전 블록들에 덮어 쓴 갱신 버전 블록들 및 원본 블록들을 포인팅하도록 직전 트리 구조를 갱신하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정하는 단계를 포함할 수 있다.In addition, in the case of updating the original block of the existing file with the immediately preceding version block, the preceding tree structure is used to point to the updated version blocks and the original blocks overwritten to the previous version blocks in the nonvolatile storage And constructing a new source tree structure, and setting the host system to point to a root node of the new source tree structure.

실시예에 따라서, 직전 트리 구조를 구성하는 아이노드 블록 및 포인터 블록들은 해당 데이터 블록의 갱신이 있기 전까지 쓰기 보호될 수 있다. According to the embodiment, the inode block and the pointer blocks constituting the immediately preceding tree structure can be write-protected until the corresponding data block is updated.

다른 실시예에서는, 직전 트리 구조를 구성하는 아이노드 블록 및 포인터 블록들은 쓰기 보호되지 않고 빈 블록과 마찬가지로 취급되거나, 또는 쓰기 보호되지는 않지만 빈 블록보다는 비우선적으로 데이터 쓰기 연산의 대상 블록에 선정될 수 있다.In another embodiment, the inode block and the pointer blocks constituting the immediately preceding tree structure are handled in the same manner as the empty block without being write-protected, or are not write-protected, but are selected in the target block of the data write operation in preference to the empty block .

또 다른 실시예에서는, 직전 버전 블록들의 위치는 비휘발성 스토리지 내부에 특별히 마련된 영역에, 또는 외부의 저장 공간, 예를 들어, 버퍼 캐시 또는 메인 메모리에 저장되어 유지될 수 있다.In yet another embodiment, the location of previous version blocks may be stored in an area specifically provided within the non-volatile storage or in an external storage space, e.g., a buffer cache or main memory.

또 다른 실시예에서, 직전 트리 구조가 온전하게 존재하지 않은 경우에는, 파일을 구성하는 새로 쓰기 연산된 데이터 블록들 및 갱신되지 않은 원본 블록들을 포인팅하도록, 원본 트리 구조의 갱신되지 않는 부분과 새로 쓰기 연산된 데이터 블록들을 위한 새로운 포인터들을 조합하여 새로운 원본 트리 구조를 구성하고, 호스트 시스템이 새로운 원본 트리 구조의 루트 노드를 포인팅하도록 설정할 수 있다.In yet another embodiment, if the previous tree structure does not exist intact, the unrecovered portion of the original tree structure and the newly written portion of the original tree structure are updated to point to the newly written data blocks constituting the file and the un- New pointers for the computed data blocks may be combined to form a new source tree structure and the host system may be configured to point to the root node of the new source tree structure.

이상과 같이 본 발명은 비록 한정된 실시예와 도면에 의해 설명되었으나, 본 발명이 상기의 실시예에 한정되는 것은 아니며, 이는 본 발명이 속하는 분야에서 통상의 지식을 가진 자라면 이러한 기재로부터 다양한 수정 및 변형이 가능하다. 따라서, 본 발명의 사상은 아래에 기재된 특허청구범위에 의해서만 파악되어야 하고, 이와 균등하거나 또는 등가적인 변형 모두는 본 발명 사상의 범주에 속한다 할 것이다.While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is to be understood that the invention is not limited to the disclosed exemplary embodiments, but, on the contrary, Modification is possible. Accordingly, the spirit of the present invention should be understood only in accordance with the following claims, and all of the equivalent or equivalent variations will fall within the scope of the present invention.

또한, 본 발명에 따른 장치는 컴퓨터로 읽을 수 있는 기록매체에 컴퓨터가 읽을 수 있는 코드로서 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 기록매체의 예로는 ROM, RAM, 광학 디스크, 자기 테이프, 플로피 디스크, 하드 디스크, 비휘발성 메모리 등이 있으며, 또한 캐리어 웨이브(예를 들어 인터넷을 통한 전송)의 형태로 구현되는 것도 포함한다. 또한 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어 분산방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다.Further, the apparatus according to the present invention can be implemented as a computer-readable code on a computer-readable recording medium. A computer-readable recording medium includes all kinds of recording apparatuses in which data that can be read by a computer system is stored. Examples of the recording medium include a ROM, a RAM, an optical disk, a magnetic tape, a floppy disk, a hard disk, a nonvolatile memory, and the like, and a carrier wave (for example, transmission via the Internet). The computer-readable recording medium may also be distributed over a networked computer system so that computer readable code can be stored and executed in a distributed manner.

10 듀얼 버퍼링 파일 관리 시스템
11 체크포인트 트랜잭션 생성부 12 쓰기 블록 선정부
13 쓰기 연산 처리부 14 트리 구조 관리부
20 비휘발성 스토리지
21 원본 트리 구조 210 원본 루트 노드
211 원본 아이노드 블록 212 아이노드
213 직접 포인터 214 단순 간접 포인터
215 이중 간접 포인터 216 삼중 간접 포인터
22 직전 트리 구조 220 직전 루트 노드
221 직전 아이노드 블록 222 아이노드
223 포인터 블록
23 단순 간접 포인터 블록
24, 241 이중 간접 포인터 블록
25, 251, 252 삼중 간접 포인터 블록
231, 242, 253 간접 포인터
261, 262, 263, 264 데이터 블록
271 빈 블록
50 듀얼 버퍼링 대용량 스토리지 장치
51 체크포인트 트랜잭션 생성부 52 쓰기 블록 선정부
53 쓰기 연산 처리부 54 트리 구조 관리부
55 비휘발성 스토리지10 Dual Buffered File Management System
11 checkpoint transaction generation unit 12 write block selection unit
13 write operation processing unit 14 Tree structure management unit
20 Nonvolatile Storage
21 Source tree structure 210 Source root node
211 Original inode block 212 Inode
213 Direct pointers 214 Simple indirect pointers
215 Double Indirect Pointer 216 Triple Indirect Pointer
22 previous tree structure 220 immediate previous root node
221 immediate previous inode block 222 inode
223 Pointer Block
23 Simple indirect pointer block
24, 241 Double Indirect Pointer Block
25, 251, 252 Triple indirect pointer block
231, 242, 253 Indirect pointers
261, 262, 263, 264 data blocks
271 empty blocks
50 Dual-Buffered Mass Storage Devices
51 checkpoint transaction generation unit 52 write block selection unit
53 write operation processing unit 54 Tree structure management unit
55 Nonvolatile Storage

Claims

A write block selecting unit for searching, in the nonvolatile storage, the immediately preceding blocks of the original block corresponding to the data included in the checkpoint transaction and for selecting a write target block according to the search result;
A write operation processing unit for writing data included in the checkpoint transaction to the non-volatile storage in the selected write target block; And
And a tree structure management unit configured to configure a source tree structure to point to newly written data blocks and original blocks that have not been updated, and to set the host system to point to a root node of the configured source tree structure,
Wherein the non-volatile storage includes a source tree structure for pointing the newly written data blocks and original blocks that have not been updated, and an immediately preceding tree structure for pointing to the previous version blocks and the unreheared original blocks Dual buffered file management system.

The apparatus of claim 1,
Wherein the controller is operable to select, as a block to be written, blocks in which the previous version is stored in the nonvolatile storage, if the previous version block is stored in the original block of the data included in the checkpoint transaction.

The apparatus of claim 2,
If the pointers in the immediately preceding tree structure and the corresponding pointers in the current source tree structure for the data block corresponding to the data included in the checkpoint transaction are different from each other by referring to the previous tree structure and the activated original tree structure, And a storage block for storing a previous version pointed to by the pointer in the previous tree structure in the storage is selected as a write target block.

The apparatus of claim 1,
Volatile storage as a block to be written if the original block corresponding to the data included in the checkpoint transaction or the previous version block of the original block can not be searched. Dual buffering file management system.

5. The apparatus of claim 4,
Volatile storage as a write target block when the data included in the checkpoint transaction is data of a new file or additional data of an existing file.

5. The apparatus of claim 4,
Volatile storage as a write-target block when the data included in the checkpoint transaction does not exist as the update data of the existing file. system.

5. The apparatus of claim 4,
Wherein the data included in the checkpoint transaction is update data of an existing file, the previous tree structure is completely present, and the data structure of the existing file corresponding to the update data is updated by referring to the previous tree structure and the original tree structure, Volatile storage to select a free block as a write target block if the pointer in the previous tree structure and the corresponding pointer in the current source tree structure are equal to each other.

The data processing apparatus according to claim 1,
And to write only the changed portion of the data block to be updated.

The system according to claim 1,
When the previous version blocks and the previous tree structure are fully preserved, the previous tree structure is updated to point to the updated version blocks and original blocks overwritten to the previous version blocks to construct a new source tree structure, Is set to point to a root node of the new source tree structure.

The apparatus of claim 9, wherein the write block selection unit
Wherein the buffer management unit operates to write-protect the blocks in which the previous tree structure is stored until the data block is updated.

The apparatus of claim 9, wherein the write block selection unit
Wherein the operation of selecting the blocks in which the previous tree structure is stored is selected as a target block to be written in priority to the empty block or in preference to the empty block.

The system according to claim 9,
And to store the previous tree structure in the non-volatile storage or in an external storage space.

The dual buffering file management system according to claim 9, wherein the source tree structure includes a pair of pointers for pointing an original block and a pointer for pointing to a previous version block of the original block with respect to each file.

The system according to claim 1,
If the previous tree structure is completely present and the data included in the checkpoint transaction is data of a new file, a new original tree structure is constructed by updating the previous tree structure so as to further point to the newly written data blocks, And to set the host system to point to the root node of the new source tree structure.

The system according to claim 1,
If the previous tree structure is perfectly present and the data included in the checkpoint transaction is data of an existing file but there is no previous version block, the updated version blocks or additional blocks and original blocks are pointed Wherein the buffer structure is configured to update a previous tree structure to form a new source tree structure, and to set the host system to point to a root node of a new source tree structure.

The system according to claim 1,
In the case where the immediately preceding tree structure does not exist perfectly, the unrevealed part of the original tree structure and the newly written data block such that the newly written data blocks constituting the file and the unrevealed original blocks are pointed, To construct a new source tree structure by combining new pointers for the source tree structure and to set the host system to point to the root node of the new source tree structure.

The system of claim 1, further comprising a checkpoint transaction generator for generating the checkpoint transaction for writing contents of dirty caches to be written into the nonvolatile storage in the buffer cache of the host system Buffered file management system.

The dual buffering file management system according to claim 1, further comprising: a checkpoint transaction generation unit for generating the checkpoint transaction for writing contents of memory blocks to be written in the host system to nonvolatile storage .

A computer readable recording medium storing a program for operating a computer as a dual buffering file management system according to any one of claims 1 to 18.

A write block selecting unit for searching, in the nonvolatile storage, the immediately preceding blocks of the original block corresponding to the data included in the checkpoint transaction and for selecting a write target block according to the search result;
A write operation processing unit for writing data included in the checkpoint transaction to the non-volatile storage in the selected write target block;
A tree structure management unit that configures a source tree structure to point to newly written data blocks and unrevealed original blocks, and sets the host system to point to a root node of the source tree structure; And
A non-volatile storage including a source tree structure for pointing to the newly written data blocks and original blocks that have not been updated, and a previous tree structure for pointing to the previous version blocks and the un- Volatile storage device.

A dual buffering file management method for nonvolatile storage by a computer having nonvolatile storage, the method comprising:
The computer comprising:
(a) searching for the previous version blocks of the original block corresponding to the data included in the checkpoint transaction in the nonvolatile storage, and selecting a block to be written according to the search result;
(b) writing data included in the checkpoint transaction to the selected write target block into the nonvolatile storage; And
(c) setting the host system to point to a root node of a source tree structure configured to point to newly written data blocks and unrecovered original blocks,
Wherein the non-volatile storage includes a source tree structure for pointing to the newly written data blocks and original blocks that have not been updated, and an immediately preceding tree structure for pointing to the previous version blocks and the original blocks that have not been updated A method for managing dual buffering of nonvolatile storage.

22. The method of claim 21, wherein (a)
Volatile storage as blocks to be written in the non-volatile storage, if the previous version block is stored in the original block of data included in the checkpoint transaction. How to manage dual buffering files.

23. The method of claim 22, wherein (a)
If the pointers in the immediately preceding tree structure and the corresponding pointers in the current source tree structure for the data block corresponding to the data included in the checkpoint transaction are different from each other by referring to the previous tree structure and the activated original tree structure, And selecting, as a write target block, a data block stored in the storage of a previous version pointed by a pointer in the previous tree structure.

22. The method of claim 21, wherein (a)
And selecting an empty block as a block to be written in the nonvolatile storage if the original block corresponding to the data included in the checkpoint transaction or the previous version block of the original block can not be searched A method for managing dual buffering of nonvolatile storage.

25. The method of claim 24, wherein (a)
And selecting an empty block as a write target block in the non-volatile storage when the data included in the checkpoint transaction is data of a new file or additional data of an existing file. How to Manage Files.

25. The method of claim 24, wherein (a)
And selecting an empty block as a write target block in the nonvolatile storage when the data included in the checkpoint transaction does not exist in the previous tree structure as an update data of an existing file. How to manage dual buffering files in storage.

25. The method of claim 24, wherein (a)
Wherein the data included in the checkpoint transaction is update data of an existing file, the previous tree structure is completely present, and the data structure of the existing file corresponding to the update data is updated by referring to the previous tree structure and the original tree structure, And selecting an empty block as a write target block in the nonvolatile storage if the pointer in the immediately preceding tree structure and the corresponding pointer in the current source tree structure are identical to each other. Way.

22. The method of claim 21, wherein step (b)
If an empty block is selected as a write target block, the entire data block is written. If the previous version block is selected as a write target block, update is performed according to a data comparison write (DCW) technique. And writing only the changed portion of the data block to be stored in the non-volatile storage.

22. The method of claim 21, wherein step (c)
If the previous version blocks and the previous tree structure are fully preserved,
Updating the previous tree structure so as to point to the updated version blocks and original blocks overwritten to the previous version blocks to construct a new original tree structure,
And setting the host system to point to a root node of the new source tree structure. &Lt; Desc / Clms Page number 19 >

The method as claimed in claim 29, wherein the blocks in which the previous tree structure is stored are write-protected until the corresponding data block is updated.

The method as claimed in claim 29, wherein the blocks storing the previous tree structure are selected as a write target block in a priority order, equal to an empty block or compared to an empty block.

29. The method of claim 29, wherein the previous tree structure is stored in the non-volatile storage or in an external storage space.

The method of claim 29, wherein the source tree structure comprises a pair of pointers for pointing an original block and a pointer for pointing to a previous version block of the original block with respect to each file, How to Manage Files.

22. The method of claim 21, wherein step (c)
If the previous tree structure is completely present and the data included in the checkpoint transaction is data of a new file, a new original tree structure is constructed by updating the previous tree structure so as to further point to the newly written data blocks, And setting the host system to point to the root node of the new source tree structure.

22. The method of claim 21, wherein step (c)
If the previous tree structure is perfectly present and the data included in the checkpoint transaction is data of an existing file but there is no previous version block, the updated version blocks or additional blocks and original blocks are pointed Updating the previous tree structure to form a new source tree structure, and setting the host system to point to a root node of a new source tree structure.

22. The method of claim 21, wherein step (c)
If the previous tree structure does not exist perfectly, a new pointer for the unrecorded part of the original tree structure and the newly written data blocks, so as to point to the newly written data blocks and the unrevealed original blocks, And configuring the host system to point to a root node of a new source tree structure. The method of claim 1,

23. The method of claim 21, further comprising generating the checkpoint transaction for writing contents of dirty caches subject to write operations in a buffer cache of a host system to non-volatile storage, How to manage buffered files.

22. The method of claim 21, further comprising generating the checkpoint transaction for writing contents of memory blocks subject to a write operation of a host system to non-volatile storage, Way.

A computer readable recording medium storing a program for implementing a dual buffering file management method of a nonvolatile storage according to any one of claims 21 to 38.