증분 색인

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

상세

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

증분 색인은 검색 색인을 바뀐 문서만큼만 고치는 일입니다. 문서는 색인에 넣는 한 단위입니다. 상품 하나, 게시글 하나가 각각 문서 하나입니다. 원본이 데이터베이스면 대개 테이블의 행 하나가 문서 하나가 됩니다. 문서마다 번호가 붙습니다.

검색 엔진이 쓰는 색인은 대개 역색인입니다. 낱말마다 그 낱말이 든 문서의 번호를 모아 둔 표입니다. 「이어폰」을 찾으면 이 표에서 「이어폰」 줄의 번호 목록을 꺼내면 됩니다.

마지막 반영 시각

증분 색인이 돌려면 지난번에 어디까지 반영했는지 알아야 합니다. 그래서 반영을 마칠 때마다 시각 하나를 적어 둡니다. 이 값을 마지막 반영 시각이라고 부릅니다. 다음 번은 이 시각 뒤로 바뀐 문서부터 봅니다.

어떤 값을 적는지는 도구마다 다릅니다. 옮긴 문서 가운데 가장 늦게 고쳐진 문서의 수정 시각을 적기도 합니다. 조회를 돌린 시각을 적기도 합니다. 새 행마다 하나씩 커지는 번호를 적으면 그 번호가 마지막 반영 시각과 같은 구실을 합니다.

전체 색인에는 이런 값이 없습니다. 매번 처음부터 다 읽으니 기억할 것이 없습니다. 증분 색인은 돌 때마다 이 값을 남깁니다. 다음 번은 그 값을 읽어 이어 갑니다.

골라내기와 받아 넣기

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

받아 넣는 쪽에도 사정이 있습니다. 새 문서는 가장 큰 번호를 받으므로 번호 목록의 끝에 붙습니다. 그래도 그 문서에 든 낱말마다 목록을 하나씩 늘려야 합니다. 큰 색인은 대개 디스크에 있어서 이렇게 제자리에서 고치는 일이 비쌉니다.

그래서 큰 색인은 건드리지 않고 둡니다. 새로 들어온 문서로 작은 보조 색인을 따로 만듭니다. 검색할 때는 둘을 함께 봅니다. 지운 문서는 지움 표시만 해 두고 검색 결과에서 걸러 냅니다. 고친 문서는 옛 문서에 지움 표시를 하고 새 문서를 넣는 일이 됩니다.

보조 색인이 커지면 큰 색인에 합칩니다. 검색 엔진들은 이 작은 색인을 세그먼트라고 부릅니다. 합치는 일은 세그먼트 병합이라고 부릅니다.

한 바퀴를 그리면 아래와 같습니다. 마지막 반영 시각을 읽는 일과 옮겨 적는 일이 바퀴의 처음과 끝에 놓입니다.

flowchart TD
    A["마지막 반영 시각을 읽는다"] --> B["원본 데이터베이스에서 그 뒤로 바뀐 문서를 골라낸다"]
    B -->|"새 문서 · 고친 문서"| C["보조 색인에 넣는다"]
    B -->|"지운 문서 · 고친 문서의 옛것"| D["지움 표시를 한다"]
    C --> E["마지막 반영 시각을 앞으로 옮겨 적는다"]
    D --> E
    E -->|"다음 번"| A

전체 색인과의 차이

전체 색인은 원본에 있는 문서를 모두 다시 읽어 색인을 새로 짓습니다. 두 방식이 어디서 갈리는지는 아래 표와 같습니다.

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

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

배경

문서 모음은 가만히 있지 않습니다. 글이 백만 개 쌓인 게시판에도 하루에 새 글이 천 개쯤 올라옵니다. 색인을 처음부터 다시 지으면 이 천 개를 반영하려고 백만 개를 다시 읽어야 합니다.

다시 짓는 시간은 바뀐 양이 아니라 전체 문서 수를 따라 늘어납니다. 오래 걸리니 자주 돌릴 수 없습니다. 하루 한 번 돌린다면 아침에 올라온 글은 다음 날까지 검색에 안 잡힙니다.

필요한 것은 바뀐 몫만 처리하는 길이었습니다. 한 번에 할 일이 바뀐 양만큼이면 자주 돌릴 수 있습니다. 그러면 새 문서가 몇 분 만에 검색에 잡히게 할 수 있습니다. 늘어난 몫을 처리한다는 뜻에서 증분 색인이라고 합니다. 바뀐 몫을 델타라고 불러 델타 색인이라고도 합니다. 계속 바뀌는 문서 모음을 다룬다는 뜻에서 동적 색인(dynamic indexing)이라고도 부릅니다.

예시

Logstash 의 JDBC 입력 플러그인

Logstash 는 Elastic 의 데이터 수집 도구입니다. 입력 플러그인이 데이터를 받아 오면 출력 쪽이 그것을 다른 시스템으로 넘깁니다. JDBC(Java Database Connectivity) 입력 플러그인은 관계형 데이터베이스에 SQL(Structured Query Language) 조회를 던져 결과 행을 받아 옵니다. 출력을 검색 엔진 색인으로 두면 이 조회가 증분 색인의 골라내기 단계를 맡습니다.

이 플러그인에서 마지막 반영 시각 구실을 하는 값이 sql_last_value 입니다. 조회문 안의 :sql_last_value 에 이 값이 들어갑니다. 조회를 돌린 뒤에는 이 값이 새 값으로 바뀝니다.

input {
  jdbc {
    statement => "SELECT id, mycolumn1, mycolumn2 FROM my_table WHERE id > :sql_last_value"
    use_column_value => true
    tracking_column => "id"
    # ... other configuration bits
  }
}

이 설정은 use_column_value => true 라서 시각 대신 tracking_column 에 적은 id 열의 값을 sql_last_value 로 씁니다. 조회는 기록해 둔 id 보다 큰 행만 가져옵니다. 한 번도 안 돌았으면 이 값은 0 에서 시작합니다. 열 값을 안 쓰는 기본 설정에서는 마지막으로 조회를 돌린 시각이 들어갑니다. 이때 처음 값은 1970년 1월 1일입니다.

이 값은 파일에 남습니다. last_run_metadata_path 가 그 파일 경로입니다. 기본값은 <path.data>/plugins/inputs/jdbc/logstash_jdbc_last_run 입니다. Logstash 가 다시 뜨면 이 파일에서 값을 읽어 이어 갑니다. clean_run 을 켜면 이 값을 무시하고 한 번도 안 돈 것처럼 처음 값에서 시작합니다.

SQL Server 전문 색인의 증분 채우기

SQL Server 는 테이블 안의 글을 낱말로 찾게 해 주는 전문 색인을 데이터베이스 안에 둡니다. 이 색인을 채우는 방법이 셋입니다.

증분 채우기는 테이블에 timestamp 형 열이 있어야 돕니다. 마지막 채우기 뒤로 더해지거나 지워지거나 고쳐진 행을 반영합니다. 지난 채우기가 도는 동안 바뀐 행도 함께 반영합니다. 끝날 때 찾은 가장 큰 timestamp 값을 적어 둡니다. 다음 증분 채우기는 그 값에서 시작합니다.

돌리는 문장은 ALTER FULLTEXT INDEX 에 START INCREMENTAL POPULATION 절을 붙인 것입니다. 증분을 청해도 전부 채우기로 도는 경우가 셋 있습니다.

Google 웹 검색 색인과 Percolator

Google 은 웹 검색 색인을 한때 전체를 다시 돌려 만들었습니다. 날마다 문서 수십억 개를 새로 긁어 왔습니다. 그것을 이미 가진 문서 저장소와 함께 MapReduce 작업 100개에 차례로 흘렸습니다. MapReduce 는 큰 묶음을 만들어 효율을 내는 일괄 처리 시스템이라 작은 갱신을 하나씩 처리하지 못합니다.

새로 긁은 페이지만 돌려서는 안 됐습니다. 예를 들어 새 페이지와 나머지 웹 사이에는 링크가 걸려 있습니다. 그래서 옛 페이지까지 저장소 전체를 다시 돌려야 했습니다.

이렇게 하면 앞선 실행이 한 일을 버리게 됩니다. 지연은 갱신의 크기가 아니라 저장소의 크기에 비례합니다. 문서 하나가 검색 결과에 나오기까지 2~3일이 걸렸습니다.

Percolator 는 큰 데이터 모음에 들어오는 갱신을 증분으로 처리하는 시스템입니다. 이것으로 지은 새 색인 시스템 Caffeine 은 문서를 긁어 오는 대로 하나씩 흘립니다. 하루에 처리하는 문서 수는 이전과 같습니다. 검색 결과 속 문서의 평균 나이는 50% 줄었습니다. 문서 하나가 시스템을 지나는 시간은 중앙값으로 이전 시스템보다 100배 넘게 빨라졌습니다.

갈래

증분 색인은 원본에서 바뀐 문서를 무엇으로 알아내느냐로 갈립니다. 주로 쓰는 방법은 셋입니다. 셋은 지운 문서를 알아채느냐에서 가장 크게 갈립니다.

데이터베이스에 생긴 변경을 알아내 다른 시스템으로 넘기는 일을 변경 데이터 캡처라고 부릅니다. 조회를 되풀이해 바뀐 행을 찾는 쪽을 조회 기반 변경 데이터 캡처라고 합니다. 데이터베이스의 로그를 읽는 쪽은 로그 기반 변경 데이터 캡처입니다. 표의 앞 두 방법이 각각 이 둘에 해당합니다.

수정 시각 비교

조회 하나로 바뀐 행을 고르는 방식입니다. 행을 쓸 때마다 갱신되고 값이 계속 커지는 수정 시각 열이 테이블마다 있어야 합니다. 쓰는 애플리케이션이나 트리거가 이 열을 빠짐없이 챙겨야 합니다. 트리거는 행이 바뀔 때 데이터베이스가 저절로 돌리는 작업입니다. 값이 행마다 다를 필요는 없어서 같은 시각을 단 행이 여럿일 수 있습니다.

이 방식은 지운 행을 못 봅니다. 지운 행은 테이블에 없어서 조회에 걸리지 않습니다. 두 조회 사이에 들어왔다가 지워진 행은 한 번도 안 잡힙니다. 수정 시각 대신 계속 커지는 번호 열로 고르면 새 행만 보입니다. 고친 행과 지운 행은 둘 다 안 보입니다.

데이터베이스 안에 든 전문 색인은 사정이 다릅니다. SQL Server 의 timestamp 기반 증분 채우기는 지워진 행도 반영합니다. 지운 행을 어떻게 알아내는지는 Microsoft 문서가 밝히지 않습니다.

변경 로그 읽기

데이터베이스가 남기는 변경 로그를 차례로 읽는 방식입니다. 로그 기반 변경 데이터 캡처가 이쪽입니다. PostgreSQL 의 논리 디코딩은 이 로그를 데이터베이스 내부 구조를 몰라도 읽을 수 있는 꼴로 꺼내 줍니다.

논리 디코딩은 행 하나의 변경을 한 건씩 내줍니다. 넣기·고치기·지우기가 행마다 하나씩 나옵니다. 문장 하나가 여러 행을 바꿔도 행마다 따로 나옵니다. 지우기도 이렇게 나오니 지운 문서를 놓치지 않습니다.

이 방식은 받는 순서에서도 수정 시각 비교와 다릅니다. 트랜잭션은 여러 쓰기를 한 덩어리로 묶어 한꺼번에 확정하는 단위입니다. 확정하는 순간을 커밋이라고 합니다. 논리 디코딩은 동시에 돈 트랜잭션을 커밋한 순서로 내보냅니다. 되돌린 트랜잭션은 아예 안 내보냅니다.

SQL Server 의 변경 추적도 이쪽입니다. 바뀐 행을 따로 테이블에 적어 두므로 그 테이블을 관리하는 작은 부담이 붙습니다. 적어 둔 변경을 전문 색인에 언제 옮길지는 자동과 수동 가운데 고릅니다. 자동이면 데이터가 바뀌는 대로 옮깁니다. 다만 색인을 백그라운드에서 갱신하므로 옮긴 변경이 바로 안 보일 수 있습니다. 수동(CHANGE_TRACKING MANUAL)이면 START UPDATE POPULATION 을 돌릴 때까지 옮기지 않습니다.

애플리케이션이 직접 보냄

애플리케이션이 원본 데이터베이스에 쓴 직후 검색 엔진에도 같은 문서를 보내는 방식입니다. 따로 돌릴 골라내기 작업이 없습니다. Elasticsearch 에 이미 있는 문서 번호로 문서를 다시 넣으면 기존 문서를 고칩니다. 버전 번호도 하나 올립니다. 같은 문서를 여러 번 보내도 덮어쓸 뿐입니다.

대신 두 곳에 따로 쓰므로 한쪽만 성공할 수 있습니다. 둘째 쓰기가 실패하면 원본과 색인이 어긋난 채 남습니다. 지울 때도 애플리케이션이 색인에 지움을 따로 보내야 합니다.

대가

증분 색인은 다시 짓는 시간을 줄이는 대신 상태를 들고 다닙니다. 마지막 반영 시각 하나가 틀어지거나 변경 하나를 놓치면 색인이 원본과 어긋납니다. 이 어긋남은 오류를 내지 않아서 조용히 남습니다.

놓친 변경이 남기는 어긋남

변경을 놓치는 길은 여럿입니다. 아래 표는 그중 메커니즘이 분명한 셋입니다.

셋째는 Logstash 에서 생깁니다. sql_last_value 를 쓰는 입력이 여럿이면 입력마다 last_run_metadata_path 를 따로 둬야 합니다. 안 그러면 모두 같은 기본 파일에 값을 적어 서로의 sql_last_value 를 덮어씁니다.

늦게 커밋한 행이 빠지는 경계

수정 시각 비교에는 시각이 찍히는 때와 행이 보이는 때가 어긋나는 구멍이 있습니다. PostgreSQL 의 now() 는 지금 트랜잭션이 시작된 시각을 돌려줍니다. 한 트랜잭션 안의 여러 수정이 같은 시각을 달게 하려는 설계입니다. 이 함수로 수정 시각을 찍으면 트랜잭션 끝 무렵에 고친 행도 시작 시각을 답니다.

격리 수준은 동시에 도는 트랜잭션끼리 서로의 변경을 얼마나 보는지 정하는 설정입니다. PostgreSQL 의 기본 격리 수준인 Read Committed 에서 조회는 그 조회가 시작되기 전에 커밋된 데이터만 봅니다. 시작은 일찍 했는데 커밋은 늦은 트랜잭션이 끼면 아래처럼 됩니다.

sequenceDiagram
    participant L as 긴 트랜잭션
    participant S as 짧은 트랜잭션
    participant T as 상품 테이블
    participant I as 증분 색인
    L->>T: 10:00 시작 · 행 A 를 고친다 · 수정 시각 10:00
    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 는 다음 조회 범위 밖에 놓입니다. 오류도 나지 않으므로 빠진 줄 모릅니다.

Confluent 의 JDBC 소스 커넥터도 수정 시각 열로 바뀐 행을 골라 갑니다. 이 커넥터는 이 틈을 줄이려고 기다림을 넣을 수 있게 해 둡니다. 어떤 시각을 단 행이 나타나면 timestamp.delay.interval.ms 만큼 기다린 뒤에 결과에 넣습니다. 이른 시각을 단 트랜잭션이 그사이 끝나게 하려는 값입니다.

기본값은 0 이라 따로 정하지 않으면 기다리지 않습니다. 정해 두어도 시작부터 커밋까지 기다림보다 오래 걸린 트랜잭션의 행은 여전히 빠질 수 있습니다. 기다림을 길게 잡으면 그만큼 색인에 늦게 들어갑니다.

변경 로그를 읽는 방식에는 이 경계가 없습니다. 커밋한 순서로 받기 때문입니다.

순서가 뒤바뀐 도착

같은 문서가 짧은 간격으로 두 번 바뀌면 색인 쪽에 나중 변경이 먼저 도착할 수 있습니다. 색인 작업을 비동기로 보내면 도착 순서가 정해져 있지 않기 때문입니다. 이때 옛 값이 새 값을 덮습니다.

Elasticsearch 는 이것을 외부 버전으로 막습니다. version_type=external 로 원본 데이터베이스가 가진 버전 번호를 함께 보내면, 저장된 문서의 버전보다 큰 번호일 때만 색인합니다. 같거나 작으면 버전 충돌로 거절합니다. 이때 HTTP(HyperText Transfer Protocol) 상태 코드 409 를 돌려줍니다.

PUT my-index-000001/_doc/1?version=2&version_type=external

원본의 버전 번호를 쓰는 한 비동기 색인 작업의 순서를 엄격히 지킬 필요가 없습니다. 순서가 뒤바뀌어 도착해도 가장 새 버전만 남습니다.

늦게 보이는 검색 결과

증분 색인을 자주 돌려도 원본이 바뀐 순간과 검색에 보이는 순간 사이에는 틈이 남습니다. 골라내는 주기가 한 번 걸립니다. 검색 엔진이 받은 문서를 검색에 열어 주는 주기가 또 걸립니다.

Elasticsearch 는 받은 문서를 새 세그먼트에 쓰고 그 세그먼트를 열어야 검색에 보입니다. 이 일을 리프레시라고 부릅니다. 기본으로 1초마다 합니다. 다만 최근 30초 안에 검색 요청을 하나 이상 받은 색인에만 합니다. SQL Server 의 자동 채우기도 색인을 백그라운드에서 갱신하므로 변경이 바로 안 보일 수 있습니다.

시간이 지나면 결국 원본과 같아지는 이런 성질을 결과적 일관성이라고 부릅니다.

가끔 전체를 다시 짓는 일

증분 색인을 써도 전체를 다시 짓는 일은 사라지지 않습니다. 처음 한 번은 반영할 기준이 없어 전부 읽습니다. 색인에 영향을 주는 정의가 바뀌면 이미 넣은 문서도 새 정의로 다시 지어야 합니다. SQL Server 는 이때 증분을 청해도 전부 채우기로 돕니다. 지운 행을 못 보는 방식이라면 테이블 전체를 주기적으로 다시 내려받아 지운 행을 털어 내기도 합니다.

다시 짓는 동안에도 검색은 멈추지 않아야 합니다. 새 색인을 옆에 다 지은 뒤 검색이 보는 이름을 새 색인으로 옮기면 됩니다. Elasticsearch 의 별칭 API(Application Programming Interface)는 옛 대상 떼기와 새 대상 붙이기를 원자적인 작업 하나로 처리합니다. 원자적이라는 것은 중간 상태 없이 한꺼번에 일어난다는 뜻입니다.

아래는 Elastic 문서의 예입니다. 별칭 logs 가 가리키는 대상을 logs-nginx.access-prod 에서 logs-my_app-default 로 바꿉니다. 다시 지은 색인으로 갈아탈 때는 이 두 칸에 옛 색인 이름과 새 색인 이름이 들어갑니다.

POST _aliases
{
  "actions": [
    { "remove": { "index": "logs-nginx.access-prod", "alias": "logs" } },
    { "add": { "index": "logs-my_app-default", "alias": "logs" } }
  ]
}

이 요청이 도는 동안 별칭 logs 는 끊기는 순간이 없습니다. 옛 대상과 새 대상을 한꺼번에 가리키는 순간도 없습니다.

이 대가를 치르지 않으려면 매번 전체를 다시 짓는 쪽이 남습니다. 문서가 적어 전체 색인이 금방 끝나면 마지막 반영 시각도, 지운 문서를 쫓는 장치도 필요 없습니다.

관련 항목

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

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

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

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

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

변경 데이터 캡처 · 이중 쓰기 · 소프트 삭제 · 타임스탬프 · 트랜잭션 로그 · 아웃박스 패턴 · 논리 디코딩 · 변경 추적 · 폴링 · 트리거

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

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

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

멱등성 · 결과적 일관성 · 트랜잭션 · 낙관적 잠금 · 격리 수준 · Read Committed · 원자성

원본에서 검색 엔진으로 변경을 나르는 도구

Logstash · Kafka Connect · Debezium · JDBC

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

검색 엔진 · Apache Lucene · Elasticsearch · OpenSearch · Apache Solr · 전문 검색 · SQL Server · Sphinx · Percolator

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

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