Method for updating inverted index of flash SSD

• US 9,715,446 B2
• Filed: 05/22/2014
• Issued: 07/25/2017
• Est. Priority Date: 05/22/2013
• Status: Active Grant

• Current Assignee: Industry Academic Cooperation Foundation
• Original Assignee: Industry Academic Cooperation Foundation
• Inventors: Jung, Won Mook, Roh, Hong Chan, Shin, Min Cheol, Park, Sang Hyun
• Primary Examiner(s): Shmatov, Alexey
• Assistant Examiner(s): MUELLER, KURT A
• Application Number:
  US14/285,270
• Publication Number:
  US 20140351490A1
• Time in Patent Office: 1,160 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies

Abstract

Disclosed is a method for updating an inverted index of a flash solid state disk (SSD). The method including: storing postings of a term that is present in only an in-memory inverted index in a block of an output buffer and reading postings of a last block of each posting list to be updated from an on-disk inverted index to be stored in each block of an input buffer, by scanning the on-disk inverted index and the in-memory inverted index; moving postings of the input buffer to the blocks of the output buffer for each block and attaching new postings of the in-memory inverted index to the block corresponding to the output buffer; and updating the on-disk inverted index by using the postings of each block of the output buffer.

Claims

1. A method for updating an inverted index of a flash solid state disk (SSD), the method comprising:

wherein an on-disk inverted index of the flash SSD is constituted by terms and a posting list which is a list of postings corresponding to the respective terms, and at least one block which has a predetermined size and is used for containing postings is provided for each term, and

wherein an in-memory inverted index of a memory is constituted by input terms and postings corresponding to the respective input terms,

storing postings of an input term that is present in only the in-memory inverted index in a block of an output buffer of the memory and reading out postings of a last block of a posting list of each term to be updated from the on-disk inverted index to thereby storing the read-out postings in a corresponding block of an input buffer of the memory, by scanning the on-disk inverted index and the in-memory inverted index;

moving the postings stored in the corresponding block of the input buffer to a corresponding block of the output buffer and attaching new postings of each term in the in-memory inverted index to the corresponding block of the output buffer; and

updating the on-disk inverted index by using the postings of each block of the output buffer,

wherein in the updating, the blocks of the output buffer to which the new postings are attached are overwritten to the blocks of the on-disk inverted index and the block of the output buffer storing the postings of the input term which is present in only the in-memory inverted index is written in a rear part of the on-disk inverted index.

2. The method of claim 1, wherein the on-disk inverted index includes a posting list maintained in a plurality of non-contiguous blocks.

3. The method of claim 1, wherein the input buffer is constituted by blocks of a predetermined number, and

scanning the on-disk inverted index and the in-memory inverted index is performed until all of the blocks of the input buffer are filled.

4. The method of claim 1, wherein reading out postings of a last block of a posting list of each term to be updated from the on-disk inverted index is simultaneously reading the corresponding blocks of the on-disk inverted index.

5. The method of claim 1, wherein while the new postings of the in-memory inverted index are attached to the corresponding block of the output buffer, if the corresponding block does not have a sufficient space to house the new postings, postings which are not housed in the space of the corresponding block among the new postings are stored in another block of the output buffer, and, if the corresponding block has the sufficient space to house the new postings, the new postings are stored in the corresponding block.

6. The method of claim 5, wherein in the updating, the block of the output buffer storing the new postings that are not housed in the space of the corresponding block is written to the rear part of the on-disk inverted index.

7. The method of claim 1, wherein in the updating, writing and overwriting blocks is simultaneously writing and overwriting the corresponding blocks.

8. A non-transitory computer-readable recording medium having stored thereon a program for executing a method for updating an inverted index of a flash solid state disk (SSD), which, when executed by a processor, performs a method comprising:

wherein an on-disk inverted index of the flash SSD is constituted by terms and a posting list which is a list of postings corresponding to the respective terms, at least one block which has a predetermined size and is used for containing postings is provided in each term, and

wherein an in-memory inverted index of a memory is constituted by input terms and postings corresponding to the respective input terms,

storing postings of an input term that is present in only an in-memory inverted index in a block of an output buffer of the memory and reading out postings of a last block of a posting list of each term to be updated from the on-disk inverted index to thereby storing the read-out postings in a corresponding block of an input buffer of the memory, by scanning the on-disk inverted index and the in-memory inverted index;

moving the postings stored in the corresponding block of the input buffer to a corresponding block of the output buffer and attaching new postings of each term in the in-memory inverted index to the corresponding block of the output buffer; and

updating the on-disk inverted index by using the postings of each block of the output buffer,

wherein in the updating, the blocks of the output buffer to which the new postings are attached are overwritten to the blocks of the on-disk inverted index and the block of the output buffer storing the postings of the input term which is present in only the in-memory inverted index is written in a rear part of the on-disk inverted index.

9. The non-transitory computer-readable recording medium of claim 8, wherein the on-disk inverted index includes a posting list maintained in a plurality of non-contiguous blocks.

10. The non-transitory computer-readable recording medium of claim 9, wherein in the updating, the block of the output buffer storing the new postings that are not housed in the space of the corresponding block is written to the rear part of the on-disk inverted index.

11. The non-transitory computer-readable recording medium of claim 8, wherein the input buffer is constituted by blocks of a predetermined number, and

scanning the on-disk inverted index and the in-memory inverted index is performed until all of the blocks of the input buffer are filled.

12. The non-transitory computer-readable recording medium of claim 8, wherein reading out postings of a last block of a posting list of each term to be updated from the on-disk inverted index is simultaneously reading the corresponding blocks of the on-disk inverted index.

13. The non-transitory computer-readable recording medium of claim 8, wherein the updating includes simultaneously writing and overwriting the corresponding blocks.

14. The non-transitory computer-readable recording medium of claim 8, wherein while the new postings of the in-memory inverted index are attached to the corresponding block of the output buffer, if the corresponding block does not have a sufficient space to house the new postings, postings which are not housed in the space of the corresponding block among the new postings are stored in another block of the output buffer, and, if the corresponding block has the sufficient space to house the new postings, the new postings are stored in the corresponding block.