색인 갱신

색인 갱신은 바뀐 문서를 이미 만들어 둔 색인에 반영하는 일입니다. 문서가 새로 들어오거나 고쳐지거나 지워질 때마다 색인도 그만큼 손봅니다. 덕분에 검색 결과가 원본 데이터를 따라갑니다. 데이터베이스에서는 같은 일을 흔히 인덱스 갱신이라고 부릅니다.

상세

이 절은 이미 만든 색인을 고치는 일이 왜 까다로운지, 검색 엔진이 그 까다로움을 어떻게 피해 가는지를 봅니다. 예로는 쇼핑몰 상품 세 개를 씁니다. 상품 하나가 문서 한 건입니다.

인쇄된 책의 찾아보기

두꺼운 요리책 뒤에는 「두부 · 34쪽, 112쪽」 같은 찾아보기가 붙어 있습니다. 개정판을 내면서 두부 요리를 한 쪽 더 넣었다고 해 봅시다. 찾아보기의 「두부」 줄에도 그 쪽 번호를 보태야 합니다.

이미 인쇄한 책이라면 그 줄만 고쳐 쓸 수가 없습니다. 출판사는 책 끝에 「추가 찾아보기」 한 장을 끼워 넣습니다. 독자는 원래 찾아보기와 추가 찾아보기를 둘 다 봅니다. 다음 판을 찍을 때 둘을 하나로 합쳐 새로 인쇄합니다.

색인 갱신이라는 말

검색 엔진의 색인은 낱말마다 그 낱말이 든 문서 번호를 모아 둔 표입니다. 문서를 열면 낱말이 보이는 보통 방향을 뒤집었다고 해서 역색인이라고 부릅니다. 낱말 하나에 붙은 번호들은 아래에서 줄여 「목록」이라 하겠습니다.

문서 모음은 가만히 있지 않습니다. 새 상품이 올라옵니다. 설명이 고쳐지기도 하고 팔지 않는 상품이 지워지기도 합니다. 이 세 가지 변경을 색인에 옮기는 일을 색인 갱신이라고 합니다.

색인을 처음 만드는 일과는 다릅니다. 처음 만들 때는 빈 표에서 시작해 문서를 차례로 넣습니다. 갱신은 이미 채워진 표를 고칩니다. 그래서 그 표가 어떻게 저장돼 있는지가 갱신 비용을 정합니다.

세 가지 변경을 색인에 옮기기

상품 세 개가 아래처럼 있다고 해 봅시다.

이 세 상품으로 만든 색인은 아래와 같습니다. 낱말마다 그 낱말이 든 상품 번호가 붙어 있습니다.

새 문서를 넣을 때는 그 문서에 든 낱말마다 목록에 번호를 더합니다. 4번 「유선 마우스」가 들어오면 「유선」 목록과 「마우스」 목록에 4를 붙입니다.

문서를 지울 때는 그 문서에 든 낱말마다 목록에서 번호를 뺍니다. 문서를 고칠 때는 옛 낱말 목록에서 번호를 빼고 새 낱말 목록에 번호를 더합니다. 아래 코드는 4번은 빼고 처음 세 상품으로 돌아가, 2번 상품을 「무선 이어폰」으로 고칩니다.

index = {"무선": [1, 3], "유선": [2],
         "이어폰": [1, 2], "마우스": [3]}

old = ["유선", "이어폰"]  # 원문에서 읽는다
new = ["무선", "이어폰"]

for w in old:
    index[w].remove(2)
for w in new:
    index[w] = sorted(index.get(w, []) + [2])

index["유선"]    # []
index["무선"]    # [1, 2, 3]
index["이어폰"]  # [1, 2]

코드에서 눈여겨볼 줄은 old 입니다. 2번 문서에 어떤 낱말이 들어 있었는지는 역색인만 봐서는 알 수 없습니다. 역색인은 낱말에서 문서로 가는 방향입니다. 거꾸로 찾으려면 모든 목록을 뒤져야 합니다.

그래서 갱신하려면 문서의 옛 내용을 어딘가에 따로 들고 있어야 합니다. 검색 엔진이 넣은 문서의 원문 사본을 색인 옆에 함께 저장하는 까닭 하나가 이것입니다.

제자리에서 고치기가 비싼 까닭

앞의 코드는 메모리 위의 작은 사전이라 번호 하나를 빼고 넣는 일이 쉬웠습니다. 큰 색인은 사정이 다릅니다. 목록은 번호 순서로 정렬돼 있습니다. 공간을 아끼려고 압축도 해 둡니다. 디스크에는 목록끼리 빈틈없이 이어 붙여 저장합니다.

이런 목록 하나에 번호를 끼우면 그 목록이 길어집니다. 뒤에 붙은 목록들을 밀어내거나, 그 목록을 디스크의 다른 곳으로 옮겨 새로 써야 합니다. 압축돼 있으니 번호 하나를 고치려 해도 목록을 풀었다 다시 묶어야 합니다.

문서 한 건에는 낱말이 수십에서 수백 개 들어 있습니다. 문서 하나를 넣을 때마다 목록 수백 개를 이렇게 고쳐 쓰는 셈입니다. 이처럼 저장된 데이터를 그 위치에서 바로 고치는 방식을 제자리 갱신이라고 부릅니다.

작은 색인에 모았다가 합치기

그래서 많은 검색 엔진은 큰 색인을 건드리지 않습니다. 새로 들어온 문서는 메모리에 모았다가 작은 색인을 따로 만듭니다. 검색할 때는 큰 색인과 작은 색인을 함께 봅니다. 앞의 비유에서 추가 찾아보기를 끼워 넣는 것과 같은 방식입니다.

검색 엔진들은 이렇게 한 번에 만든 작은 색인 하나를 세그먼트라고 부릅니다. 처음에 만든 큰 색인도 이렇게 보면 큰 세그먼트 하나입니다. 세그먼트는 한 번 써 두면 고치지 않습니다. 고치지 않으니 정렬과 압축을 처음부터 단단히 해 둘 수 있습니다.

세그먼트가 늘수록 검색 한 번에 열어 볼 곳도 늘어납니다. 작은 세그먼트가 어느 정도 쌓이면 몇 개를 골라 큰 세그먼트 하나로 새로 씁니다. 이 일을 세그먼트 병합이라고 부릅니다. 병합이 끝나면 옛 세그먼트들은 버립니다.

flowchart TD
    N["새 문서"] --> B["메모리에 모은다"]
    B --> S1["작은 세그먼트"]
    S0["큰 세그먼트"] --> Q1["병합 전 검색은 두 곳을 읽는다"]
    S1 --> Q1
    S0 --> M["세그먼트 병합"]
    S1 --> M
    M --> S2["새로 쓴 큰 세그먼트"]
    S2 --> Q2["병합 뒤 검색은 한 곳만 읽는다"]

그림은 두 단계를 보여 줍니다. 문서가 모여 세그먼트가 됩니다. 쌓인 세그먼트는 병합으로 하나가 됩니다. 그러면 검색이 읽을 곳도 둘에서 하나로 줄어듭니다.

지우기는 표시로

세그먼트를 고치지 않는다면 지우기는 어떻게 할까요. 목록에서 번호를 빼는 대신 「이 문서는 지웠음」이라는 표시만 따로 남깁니다. 검색은 후보를 고른 뒤 이 표시가 붙은 문서를 결과에서 걸러 냅니다.

이런 지움 표시를 툼스톤이라고 부릅니다. 묘비라는 뜻입니다. 데이터는 남아 있어도 죽은 것으로 칩니다.

표시된 문서는 세그먼트 병합 때 치웁니다. 새 세그먼트를 쓰면서 그 문서의 번호를 옮겨 적지 않습니다. 그때까지는 지운 문서도 디스크 공간을 차지합니다.

고치기는 지우고 다시 넣기

문서를 고칠 때는 먼저 옛 문서에 지움 표시를 남깁니다. 그다음 고친 문서를 새 문서처럼 넣습니다. 상품 가격 하나만 바꿨어도 그 문서 전체를 다시 낱말로 쪼개 넣습니다.

문서 한 건의 낱말은 수많은 목록에 흩어져 있습니다. 바뀐 부분만 골라 고치려면 그 목록들을 하나씩 찾아가야 합니다. 통째로 지우고 다시 넣는 쪽은 세그먼트를 고치지 않는다는 원칙과 맞습니다. 구현도 단순합니다.

대가는 쓰는 양입니다. 작은 수정에도 문서 한 건 분량을 새로 씁니다. 병합 때 같은 데이터를 또 옮겨 씁니다. 이렇게 원래 바꾼 양보다 디스크에 더 많이 쓰게 되는 현상을 쓰기 증폭이라고 부릅니다.

검색에 보이기까지

메모리에 모아 둔 새 문서는 아직 검색에 안 걸립니다. 작은 세그먼트로 만들어져 검색 대상에 올라야 걸립니다. 이 올리는 작업을 리프레시라고 부르는 검색 엔진이 많습니다.

리프레시를 자주 하면 새 문서가 빨리 보입니다. 대신 작은 세그먼트가 그만큼 많이 생겨 병합할 일이 늘어납니다. 드물게 하면 병합 부담이 줄어듭니다. 대신 문서를 넣고 한참 뒤에야 검색에 걸립니다.

몇 초 안쪽의 틈을 두고 새 문서를 보여 주는 검색을 근실시간 검색이라고 부릅니다. 넣자마자 찾아야 하는 화면이라면 이 틈을 먼저 따져야 합니다. 예를 들어 게시글을 쓰고 바로 목록에서 검색해 보는 화면이 그렇습니다.

세 가지 갱신 방식

이미 만든 색인을 고치는 방식은 크게 셋입니다. 무엇을 아끼고 무엇을 치르는지가 서로 다릅니다.

오늘날 검색 엔진은 대개 셋째를 기본으로 씁니다. 다시 짓기는 따로 꺼낼 일이 있을 때 씁니다. 모든 문서를 다시 넣어 색인을 새로 만드는 이 일을 재색인이라고도 합니다.

다시 짓기가 꼭 필요한 때는 분석기를 바꿀 때입니다. 분석기는 문서와 검색어를 낱말로 쪼개는 규칙입니다. 둘을 같은 규칙으로 쪼개야 검색어의 낱말이 색인의 낱말과 맞습니다.

예를 들어 「이어폰」을 「이어」와 「폰」으로 쪼개도록 분석기를 바꿨다고 해 봅시다. 색인에는 옛 규칙대로 「이어폰」 한 낱말만 적혀 있습니다. 검색어 「이어폰」은 이제 「이어」와 「폰」으로 쪼개져 아무것도 안 걸립니다. 이런 어긋남은 갱신으로 못 고치니 모든 문서를 새 규칙으로 다시 넣습니다.

평소에는 거의 안 바뀌다가 바뀔 때 한꺼번에 바뀌는 문서 모음도 있습니다. 매일 밤 상품 목록 전체가 새로 들어오는 경우가 그렇습니다. 이런 모음은 갱신을 따로 챙기기보다 밤마다 다시 짓는 쪽이 단순합니다.

증분 색인과의 관계

색인 갱신은 검색 엔진 안에서 변경 한 건을 받아 반영하는 일입니다. 그 변경을 누가 골라 보내는지는 따지지 않습니다.

증분 색인은 그 앞단입니다. 원본 데이터베이스에서 지난번 뒤로 바뀐 문서만 골라 검색 엔진에 보냅니다. 검색 엔진은 받은 문서를 색인 갱신으로 반영합니다. 둘을 이어 붙이면 원본이 바뀐 뒤 검색 결과가 따라가기까지의 길 하나가 됩니다.

데이터베이스 인덱스의 갱신

데이터베이스의 인덱스도 행이 바뀔 때마다 갱신됩니다. 다만 방식이 다릅니다. 행을 쓰는 트랜잭션 안에서 인덱스도 함께 고칩니다. 트랜잭션이 커밋되면 바뀐 행과 인덱스가 함께 보입니다.

흔히 쓰는 B-tree 인덱스는 제자리 갱신을 씁니다. B-tree 는 데이터를 페이지라는 고정 크기 칸에 나눠 담습니다.

칸마다 빈 공간을 조금 남겨 둡니다. 그래서 값 하나를 끼울 때 그 페이지만 고치면 됩니다. 페이지가 가득 차면 둘로 나눕니다.

덕분에 데이터베이스는 쓰는 즉시 인덱스로 찾을 수 있습니다. 대가는 쓰기 비용입니다. 한 테이블에 인덱스가 다섯 개면 행 하나를 넣을 때 인덱스 다섯 개를 모두 고칩니다.

관련 항목

색인 갱신이 고치는 구성 요소

색인 · 역색인 · 포스팅 리스트 · 포스팅 · 세그먼트 · 원문 사본 · 문서

색인 갱신이 거치는 처리 단계

리프레시 · 세그먼트 병합 · 툼스톤 · 커밋 · 플러시 · 트랜잭션 로그

색인 갱신과 맞세워지는 다시 짓기 방식

재색인 · 전체 색인 · 색인 별칭 · 배치 처리

색인 갱신에 바뀐 문서를 대 주는 수단

증분 색인 · 변경 데이터 캡처 · 이중 쓰기 · 아웃박스 패턴 · 폴링

색인 갱신이 치르는 비용과 지연

쓰기 증폭 · 근실시간 검색 · 결과적 일관성 · 제자리 갱신 · 읽기 증폭

고치지 않고 모았다가 합치는 같은 계열의 저장 구조

LSM 트리 · SSTable · 컴팩션 · 로그 구조 저장 · 불변 데이터

데이터베이스 쪽의 인덱스 갱신

인덱스 · B-tree · 페이지 분할 · 트랜잭션 · 인덱스 유지 비용

색인 갱신을 해 주는 검색 라이브러리와 엔진

Apache Lucene · Elasticsearch · OpenSearch · Solr

색인 갱신이 속하는 상위 분류

검색 엔진 · 검색 · 전문 검색 · 정보 검색