증분 색인

증분 색인은 검색용 색인을 처음부터 다시 만들지 않고 바뀐 문서만 반영하는 일입니다. 지난번 색인 뒤로 들어오거나 고쳐지거나 지워진 문서만 골라 색인에 옮깁니다. 문서가 아무리 많아도 한 번에 할 일은 바뀐 양만큼입니다. 반대편에는 모든 문서를 다시 읽어 색인을 새로 짓는 전체 색인이 있습니다.

상세

도서관이 새 책 스무 권을 들였다고 해 봅시다. 사서는 목록 카드 수만 장을 전부 새로 쓰지 않습니다. 새 책 스무 권의 카드만 써서 목록에 더합니다.

검색 엔진에서 문서는 색인에 넣는 한 단위입니다. 상품 하나, 게시글 하나가 각각 문서 하나입니다. 문서마다 번호가 붙어 있어서 검색 결과는 이 번호의 목록으로 나옵니다.

검색 엔진은 대개 역색인이라는 색인을 씁니다. 낱말마다 그 낱말이 든 문서의 번호를 모아 둔 표입니다. 「이어폰」을 찾으면 이 표에서 「이어폰」 줄의 번호 목록을 꺼내면 끝납니다. 문서를 처음부터 끝까지 읽지 않아도 되는 까닭이 이 표에 있습니다.

증분 색인은 이 표를 바뀐 문서만큼만 고치는 일입니다. 매번 지난번 뒤로 바뀐 문서만 골라 색인에 옮깁니다. 바뀐 몫을 델타라고 불러 델타 색인이라고도 합니다.

그러려면 지난번에 어디까지 반영했는지 적어 두어야 합니다. 흔히 그때 옮긴 문서 가운데 가장 늦게 고쳐진 문서의 수정 시각을 적습니다. 이 시각을 마지막 반영 시각이라고 합니다. 다음 번은 이 시각 뒤로 바뀐 문서부터 봅니다.

전체 색인과의 차이

이 소절은 증분 색인을 반대편 방식과 나란히 놓고 봅니다. 전체 색인은 원본에 있는 문서를 모두 다시 읽어 색인을 새로 짓습니다. 둘이 어디서 갈리는지는 아래 표가 보입니다.

표의 셋째 줄이 두 방식의 성격을 가장 크게 가릅니다. 전체 색인은 원본에 없는 문서를 새 색인에 안 넣으면 끝입니다. 증분 색인은 문서가 없어졌다고 누군가 알려 줘야 그 문서를 뺄 수 있습니다.

둘은 서로를 대신하지 않고 번갈아 쓰입니다. 색인을 처음 만들 때는 전체 색인을 돌립니다. 그 뒤로는 증분 색인으로 원본을 따라갑니다.

전체 색인만 쓸 때 생기는 지연

상품이 백만 개인 쇼핑몰을 생각해 봅니다. 하루 동안 가격이나 재고가 바뀌는 상품은 그중 몇천 개일 수 있습니다. 전체 색인만 쓰면 몇천 개를 반영하려고 백만 개를 다시 읽는 셈입니다.

전체 색인은 문서가 늘수록 오래 걸립니다. 그래서 자주 돌리기 어렵습니다. 하루 한 번 돌린다면 아침에 바꾼 가격이 다음 날까지 검색 결과에 옛 값으로 나옵니다.

증분 색인은 한 번에 할 일이 바뀐 양만큼이라 짧게 끝납니다. 짧으니 몇 분마다, 또는 변경이 생길 때마다 돌릴 수 있습니다. 원본이 바뀐 뒤 검색에 잡히기까지 걸리는 시간이 그만큼 줄어듭니다.

바뀐 문서를 골라내는 세 방법

증분 색인은 두 단계로 나뉩니다. 먼저 원본에서 무엇이 바뀌었는지 골라냅니다. 다음으로 검색 엔진이 그 문서를 받아 넣습니다. 이 소절은 앞 단계를 다룹니다.

골라내는 방법은 흔히 셋입니다. 셋은 지운 문서를 알아채는 능력에서 가장 크게 갈립니다.

수정 시각 비교가 가장 손쉽습니다. 테이블에 updated_at 처럼 행을 고친 시각을 담는 열이 있으면 조회 한 번으로 바뀐 행이 나옵니다. 아래는 상품 테이블에서 바뀐 행을 가져오는 조회입니다.

SELECT id, name, price, updated_at
FROM product
WHERE updated_at > :last_indexed_at
ORDER BY updated_at;

:last_indexed_at 자리에 마지막 반영 시각이 들어갑니다. 이번 조회를 다 옮기고 나면 가져온 행 가운데 가장 늦은 수정 시각으로 이 값을 바꿉니다. 다음 번 조회는 거기서 시작합니다.

이 방법은 지운 행을 못 봅니다. 지운 행은 테이블에 없어서 조회에 걸리지 않습니다. 그래서 행을 지우는 대신 「지워짐」 열을 켜 두는 소프트 삭제를 함께 씁니다. 증분 색인은 이 열이 켜진 행을 보고 그 문서를 색인에서 뺍니다.

변경 데이터 캡처는 데이터베이스가 원래 남기는 변경 로그를 읽습니다. 데이터베이스는 장애 뒤에 되살아나려고 바뀐 행을 차례로 로그에 적어 둡니다. 이 로그에는 삭제도 남으므로 지운 문서를 놓치지 않습니다. 로그를 읽어 검색 엔진으로 옮겨 주는 도구를 따로 굴려야 한다는 부담이 붙습니다.

이중 쓰기는 애플리케이션이 원본에 쓴 직후 검색 엔진에도 한 번 더 씁니다. 따로 돌릴 작업이 없어 만들기 가장 쉽습니다. 둘째 쓰기가 실패하면 원본과 색인이 어긋난 채 남습니다.

수정 시각으로 고를 때 빠지는 문서

트랜잭션은 여러 쓰기를 한 덩어리로 묶어 한꺼번에 확정하는 단위입니다. 확정하는 순간을 커밋이라고 합니다. 커밋 전까지는 다른 연결이 그 트랜잭션이 고친 행을 보지 못합니다.

수정 시각 비교는 여기서 구멍이 생깁니다. 수정 시각은 행을 고친 순간에 찍힙니다. 그런데 증분 색인이 그 행을 볼 수 있는 것은 커밋한 뒤입니다. 긴 트랜잭션과 짧은 트랜잭션이 섞이면 아래처럼 됩니다.

sequenceDiagram
    participant L as 긴 트랜잭션
    participant S as 짧은 트랜잭션
    participant T as 상품 테이블
    participant I as 증분 색인
    L->>T: 10:00 행 A 를 고친다
    S->>T: 10:01 행 B 를 고치고 커밋한다
    I->>T: 마지막 반영 시각 뒤로 바뀐 행을 찾는다
    T-->>I: B 만 보인다 · 마지막 반영 시각은 10:01
    L->>T: 10:02 커밋한다
    I->>T: 10:01 뒤로 바뀐 행을 찾는다
    T-->>I: 없다 · A 는 10:00 이라 빠진다

행 A 는 10시 00분에 고쳐졌지만 10시 02분에야 보였습니다. 그사이 마지막 반영 시각이 10시 01분으로 올라가 버려서 A 는 다음 조회의 범위 밖에 놓입니다. 오류도 나지 않으므로 누구도 빠진 줄 모릅니다.

흔한 대처는 조회 범위를 앞 조회와 조금 겹치게 잡는 것입니다. 마지막 반영 시각에서 몇 분을 빼고 찾으면 늦게 커밋한 행도 걸립니다. 대신 같은 문서가 두 번 들어오므로 색인 쪽은 번호가 같은 문서를 덮어쓰게 둡니다. 여러 번 해도 결과가 한 번 한 것과 같은 이 성질을 멱등성이라고 부릅니다.

검색 엔진이 바뀐 문서를 받아 넣는 방식

이 소절은 뒤 단계, 검색 엔진 안쪽을 봅니다. 문서 하나를 역색인에 넣는 일이 왜 비싼지, 그리고 검색 엔진이 그 비용을 어떻게 피하는지가 내용입니다.

역색인에서 낱말마다 붙은 번호 목록은 정렬되어 있습니다. 문서 하나에는 낱말이 수십에서 수백 개 들어 있습니다. 그 문서를 넣으려면 낱말 수만큼의 목록을 찾아 중간에 번호를 끼워야 합니다. 디스크에 촘촘히 적힌 목록 가운데에 끼우려면 뒤쪽을 밀어내야 해서 비쌉니다.

그래서 흔히 쓰는 방법은 기존 색인을 고치지 않는 것입니다. 새로 들어온 문서들로 작은 역색인을 하나 따로 만듭니다. 이 조각을 세그먼트라고 부릅니다. 검색할 때는 세그먼트 여럿을 모두 찾아 결과를 합칩니다.

지울 때도 세그먼트를 고치지 않습니다. 지운 문서의 번호에 지움 표시만 남기고 검색에서 건너뜁니다. 문서를 고치는 일은 옛 문서에 지움 표시를 하고 새 문서를 넣는 일이 됩니다.

세그먼트가 늘면 검색 한 번에 돌아야 할 조각도 늘어 느려집니다. 그래서 검색과 따로 돌면서 작은 세그먼트 몇 개를 큰 것 하나로 합칩니다. 이 작업을 세그먼트 병합이라고 합니다. 병합 때 지움 표시가 된 문서가 비로소 빠지고 디스크 공간이 돌아옵니다.

두 단계를 한 번에 이으면 아래와 같습니다. 고친 문서는 두 갈래를 모두 지난다는 점이 그림에서 보입니다.

flowchart TD
    subgraph OUT["앞 단계 · 원본에서 골라낸다"]
        A["원본 데이터베이스"] --> B["마지막 반영 시각 뒤로 바뀐 문서"]
    end
    subgraph IN["뒤 단계 · 검색 엔진이 받아 넣는다"]
        C["새 세그먼트"]
        E["옛 문서에 지움 표시"]
        C --> D["세그먼트 병합"]
        E --> D
    end
    B -->|"새 문서 · 고친 문서"| C
    B -->|"지운 문서 · 고친 문서"| E

전체 색인으로 돌아가야 하는 때

증분 색인이 있어도 전체 색인을 다시 돌려야 하는 경우가 있습니다. 이미 있는 색인을 전체 색인으로 다시 짓는 일을 재색인이라고 부릅니다.

분석기는 문서를 낱말로 쪼개고 낱말 모양을 다듬는 부품입니다. 「이어폰을」을 「이어폰」으로 바꿔 적는 일이 분석기의 몫입니다. 색인에 적히는 낱말은 이 분석기가 정합니다.

재색인하는 동안에도 검색은 옛 색인으로 돕니다. 새 색인을 옆에 다 지은 뒤 검색이 보는 색인을 바꿔 끼웁니다. 짓는 동안 들어온 변경은 증분 색인으로 새 색인에 마저 옮깁니다.

반대로 증분 색인을 둘 까닭이 적은 경우도 있습니다. 문서가 적어서 전체 색인이 금방 끝나면 매번 전체 색인을 돌리는 편이 단순합니다. 마지막 반영 시각도, 지운 문서를 쫓을 장치도 필요 없기 때문입니다.

증분 색인이 치르는 대가

첫째 대가는 조용한 어긋남입니다. 놓친 변경은 오류를 내지 않고 색인에서 빠진 채 남습니다. 그래서 원본과 색인의 문서 수를 가끔 견주어 어긋남을 찾습니다.

둘째 대가는 순서입니다. 같은 문서가 짧은 간격으로 두 번 바뀌면 나중 변경이 먼저 도착할 수 있습니다. 여러 작업자가 변경을 나눠 보내면 누가 먼저 끝낼지 정해져 있지 않기 때문입니다. 그러면 옛 값이 새 값을 덮습니다.

막는 방법은 문서마다 수정 시각이나 버전 번호를 함께 보내는 것입니다. 색인 쪽은 이미 가진 것보다 옛것이 오면 버립니다.

셋째 대가는 늦게 보인다는 점입니다. 원본이 바뀐 순간과 색인에 반영된 순간 사이에는 늘 틈이 있습니다. 그 틈 동안 검색 결과는 옛 모습을 보입니다. 시간이 지나면 결국 같아지는 이런 성질을 결과적 일관성이라고 부릅니다.

관련 항목

증분 색인이 고쳐 가는 색인 구조

색인 · 역색인 · 포스팅 리스트 · 문서 · 세그먼트 · 분석기

증분 색인과 맞세워지는 다시 짓기 방식

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

원본에서 바뀐 문서를 골라내는 수단

변경 데이터 캡처 · 이중 쓰기 · 소프트 삭제 · 타임스탬프 · 트랜잭션 로그 · 아웃박스 패턴

검색 엔진이 변경을 받아 넣는 처리 단계

세그먼트 병합 · 툼스톤 · 리프레시 · 커밋 · 근실시간 검색 · 색인 갱신

증분 색인이 어긋남을 막으려고 기대는 성질

멱등성 · 결과적 일관성 · 트랜잭션 · 낙관적 잠금

증분 색인을 채택한 검색 제품

검색 엔진 · Apache Lucene · Elasticsearch · OpenSearch · Apache Solr · 전문 검색

바뀐 몫만 다시 처리하는 같은 계열의 기법

증분 백업 · 증분 빌드 · 구체화 뷰 · 증분 계산