Python Xapian 저장 구조

프로젝트에서 검색 서비스를 지원하기 위해 Xapian을 백엔드 검색 엔진으로 사용합니다. 좋은 성능과 사용 편의성으로 인해 인기가 높습니다.

import xapian
import posixpath
def get_db_path():
    XAPIAN_ROOT = '/tmp/'
    xapian_user_database_path = posixpath.join(XAPIAN_ROOT, u'user_index')
    return xapian_user_database_path
def add_document(database, words):
    doc = xapian.Document()
    for w in words:
        doc.add_term(w)
    database.add_document(doc)
def build_index():
    user_database = xapian.WritableDatabase(get_db_path(), xapian.DB_CREATE_OR_OPEN)
    words = ['a', 'b', 'c']
    add_document(user_database, words)
def search(words, offset=0, length=10):
    user_database = xapian.Database(get_db_path())
    enquire = xapian.Enquire(user_database)
    query = xapian.Query(xapian.Query.OP_AND, words)
    enquire.set_query(query)
    return enquire.get_mset(int(offset), int(length))
def _show_q_results(matches):
    print '%i results found.' % matches.get_matches_estimated()
    print 'Results 1 - %i:' % matches.size()
    for match in matches:
        print '%i: %i%% docid=%i [%s]' % (match.rank + 1,
                                          match.percent,
                                          match.docid,
                                          match.document.get_data()
                                          )
if __name__ == '__main__':
    #index 
    build_index()
    
    #search
    _show_q_results(search(['a','b']))

사용하기는 매우 간단하지만 스토리지 엔진이 항상 궁금했기 때문에 최신 스토리지 엔진 브라스의 구현을 살펴보았습니다. 전체 데이터 디렉토리의 계층 구조는 다음과 같습니다. 🎜>/tmp/user_index
flintlock
iamchert
postlist.baseA
postlist.baseB
postlist.DB //모든 용어를
record.baseA
에 저장합니다. Record.baseB
record.DB //해당 데이터 매핑에 모든 docid 저장
termlist.baseA
termlist.baseB
termlist.DB //해당 용어에 대한 모든 docid 매핑 저장

황동 스토리지 엔진에서 사용하는 데이터 구조는 BTree입니다. 따라서 위의 각 *.DB는 BTree를 저장합니다. *.baseA/B는 이 대형의 어떤 데이터 블록을 포함하여 해당 .DB의 메타 정보를 저장합니다.
BTree는 Xapian에서 N레벨로 표현되며, 이 레이어의 커서는 유지됩니다. 이는 현재 액세스 중인 특정 데이터 블록과 데이터 블록의 특정 위치를 가리키는 데 사용됩니다.

from @brass_table.cc
/* A B-tree comprises (a) a base file, containing essential information (Block
   size, number of the B-tree root block etc), (b) a bitmap, the Nth bit of the
   bitmap being set if the Nth block of the B-tree file is in use, and (c) a
   file DB containing the B-tree proper. The DB file is divided into a sequence
   of equal sized blocks, numbered 0, 1, 2 ... some of which are free, some in
   use. Those in use are arranged in a tree.
   Each block, b, has a structure like this:
     R L M T D o1 o2 o3 ... oN <gap> [item] .. [item] .. [item] ...
     <---------- D ----------> <-M->
   And then,
   R = REVISION(b)  is the revision number the B-tree had when the block was
                    written into the DB file.
   L = GET_LEVEL(b) is the level of the block, which is the number of levels
                    towards the root of the B-tree structure. So leaf blocks
                    have level 0 and the one root block has the highest level
                    equal to the number of levels in the B-tree.
   M = MAX_FREE(b)  is the size of the gap between the end of the directory and
                    the first item of data. (It is not necessarily the maximum
                    size among the bits of space that are free, but I can&#39;t
                    think of a better name.)
   T = TOTAL_FREE(b)is the total amount of free space left in b.
   D = DIR_END(b)   gives the offset to the end of the directory.
   o1, o2 ... oN are a directory of offsets to the N items held in the block.
   The items are key-tag pairs, and as they occur in the directory are ordered
   by the keys.
   An item has this form:
           I K key x C tag
             <--K-->
           <------I------>
   A long tag presented through the API is split up into C tags small enough to
   be accommodated in the blocks of the B-tree. The key is extended to include
   a counter, x, which runs from 1 to C. The key is preceded by a length, K,
   and the whole item with a length, I, as depicted above.

위의 Xapian 주석은 다음과 같습니다. 각 블록의 데이터 구조를 명확하게 설명했습니다. 데이터 외에도 메타 정보는 항목으로 구성된 작은 데이터 단위입니다. 각 작은 항목에는 I(전체 데이터 단위의 길이), K(데이터 단위 키의 길이 + x(키 식별자)) 및 C(해당 키는 몇 개의 항목으로 구성되어 있습니까? 를 나타냅니다. 특정 키에 해당하는 값이 너무 크면 값 분할이 수행되므로 C는 총 포인트 수를 나타냅니다. 그리고 앞의 x는 이 장치가 어떤 데이터인지 나타냅니다. 이 키의 큰 값 전체를 읽어야 하는 경우 일련 번호 x에 따라 병합할 수 있습니다.) 태그는 방금 키에 해당하는 값입니다. 언급했지만 Xapian은 이를 태그로 정의합니다. 따라서 이 정의도 상대적으로 합리적입니다. 예를 들어 BTree의 리프가 아닌 노드 태그는 데이터 블록의 다음 계층의 주소를 저장합니다. 리프 노드에 관련 데이터가 저장됩니다. 이제 전체 트리의 저장 구조가 명확하게 표시되었습니다.

여기서 흥미로운 문제가 있는데, 바로 postlist의 저장입니다. word에는 예를 들어 100만 개에 달하는 수많은 docid가 포함되어 있습니다. 그런 다음 증분 업데이트를 수행할 때 이 용어에서 특정 docid를 삭제하려는 경우 가능한 한 빨리 이 docid가 어떤 데이터 블록에 있는지 확인할 수 있습니까? 저자는 이 문제를 해결하기 위해 term+docid를 사용합니다. 값은 모두 이 docid보다 크며, 이를 통해 블록 대신 문서 ID를 최대한 빨리 찾을 수 있습니다.

Xapian은 증분 업데이트를 위해 다중 리더와 단일 스레드 쓰기도 지원하므로 데이터베이스에서 MVCC와 유사한 방식을 채택하므로 업데이트로 인해 읽기 작업이 차단되지 않습니다.

현재 저자는 다른 머신에 대한 증분 업데이트를 지원할 수 있는 복제 방법을 개발 중입니다. 이러한 방식으로 데이터는 신뢰할 수 있습니다(단일 머신 디스크 손상으로 인해 발생하지 않음). 고가용성(단일 머신을 사용할 수 없으며 애플리케이션 계층을 백업 머신으로 전환할 수 있음)

BTW: 지난 이틀 동안 Xapian 개발자 메일링 리스트를 읽었지만 제출한 것은 없습니다. 질문을 읽었습니다. 저자(Olly Betts)는 모든 질문에 인내심을 갖고 자세하게 답변해 줍니다. 나는 그를 매우 존경합니다.