검색 엔진

검색 엔진은 쌓아 둔 글 가운데 찾는 낱말과 잘 맞는 것을 골라 잘 맞는 순서대로 돌려줍니다. 글이 들어올 때 낱말마다 찾아보기를 미리 만들어 두기 때문에 글이 많아도 빨리 답합니다. 인터넷 전체를 뒤져 주는 웹 검색 사이트도 같은 이름으로 부릅니다. 이 편은 내 서비스 안에 들여놓고 쓰는 검색 서버를 중심으로 다룹니다.

쉽고 빠른 이해

검색 엔진은 낱말로 글을 찾아 주는 프로그램입니다. 쇼핑몰 검색창에 「무선 이어폰」을 치면 두 낱말이 다 든 상품부터 보여 주는 것이 이 일입니다.

이게 없으면 데이터베이스가 모든 글을 처음부터 끝까지 읽어야 합니다. 글이 늘수록 오래 걸립니다. 어느 결과가 더 잘 맞는지도 알려 주지 않습니다.

이렇게 돕니다:

1. 글이 들어오면 낱말로 쪼갭니다
2. 낱말마다 그 낱말이 든 글의 번호를 적어 둡니다
3. 검색어가 오면 같은 방식으로 쪼개 번호를 꺼냅니다
4. 꺼낸 글마다 얼마나 잘 맞는지 점수를 매겨 높은 순으로 돌려줍니다

대가도 있습니다. 찾아보기를 따로 두므로 저장 공간이 더 듭니다. 원본과 어긋나지 않게 계속 맞춰 줘야 합니다.

낱말로 찾고 잘 맞는 순서가 필요할 때 씁니다. 번호로 한 건을 꺼내거나 조건이 딱 떨어지는 조회는 데이터베이스가 맞습니다.

상세

두꺼운 요리책에서 마늘이 들어가는 요리를 찾는다고 해 봅시다. 첫 장부터 넘기는 사람은 없습니다. 책 뒤쪽 찾아보기에서 「마늘」을 찾습니다. 옆에 적힌 쪽 번호로 곧장 넘어갑니다.

검색 엔진도 이런 찾아보기를 만듭니다. 글이 들어올 때 낱말마다 찾아보기를 미리 적어 두고, 찾을 때는 그 찾아보기부터 엽니다.

검색 엔진은 모아 둔 글 가운데 찾는 낱말과 잘 맞는 것을 골라, 잘 맞는 순서로 돌려주는 시스템입니다. 쇼핑몰 검색창에서 이 일이 벌어집니다. 「무선 이어폰」을 치면 두 낱말이 다 든 상품이 맨 위에 옵니다. 하나만 든 상품은 그 아래에 옵니다.

먼저 낱말 둘을 정해 둡니다. 검색 엔진이 다루는 데이터 한 건이 문서입니다. 상품 하나, 게시글 하나, 로그 한 줄이 각각 문서 하나입니다. 검색 엔진에 보내는 물음은 질의입니다.

데이터베이스로는 모자란 대목

문서가 관계형 데이터베이스에 들어 있다면 LIKE '%이어폰%' 같은 조건으로도 찾을 수는 있습니다. 앞에 % 가 붙으면 낱말이 글의 어디에 있어도 된다는 뜻입니다. 이런 조건에는 조회를 빠르게 하려고 만들어 두는 인덱스가 듣지 않습니다. 결국 모든 행의 글을 하나씩 열어 봅니다.

속도만 문제가 아닙니다. LIKE 는 낱말이 들었는지 안 들었는지만 답합니다. 두 낱말이 다 든 상품과 하나만 든 상품을 가려 앞뒤로 세워 주지 않습니다.

글자 모양이 바뀌는 것도 못 따라갑니다. '%달리다%' 로 찾으면 「어제 한강을 달렸다」가 든 글을 놓칩니다. 사람 눈에는 같은 낱말인데 글자가 다르기 때문입니다.

글 전체를 대상으로 낱말로 찾는 일을 전문 검색이라고 부릅니다. 검색 엔진은 이 일을 맡으려고 만든 시스템입니다. 위의 세 문제를 풀도록 짜여 있습니다.

글을 낱말로 쪼개는 분석

문서가 들어오면 검색 엔진은 먼저 글을 낱말 단위로 쪼갭니다. 이 일이 토큰화입니다. 쪼개진 낱말 하나하나는 토큰입니다.

쪼갠 뒤에는 낱말의 모양을 하나로 맞춥니다. 대문자는 소문자로 바꿉니다. 「달렸다」와 「달리는」은 「달리다」 하나로 모읍니다.

한국어는 낱말 끝에 조사와 어미가 붙어서 이 일이 특히 중요합니다. 이 몫은 낱말을 뜻의 가장 작은 단위로 나누는 형태소 분석이 맡습니다.

쪼개고 모양을 맞추는 일을 한데 묶은 부품이 분석기입니다. 문장 두 개를 넣으면 이렇게 나옵니다.

두 줄 다 조사와 어미, 대문자와 복수형이 떨어져 나갔습니다. 검색 엔진은 이 모양으로 낱말을 적어 둡니다. 질의도 같은 분석기로 쪼갭니다. 넣을 때와 찾을 때 둘 다 「달리다」가 되어야 서로 만나기 때문입니다.

역색인

책 뒤의 찾아보기와 데이터베이스의 인덱스는 같은 것을 다르게 부른 이름입니다. 둘 다 찾기 쉽게 미리 정리해 둔 표이고, 우리말로는 색인이라고 합니다.

검색 엔진이 만드는 찾아보기가 역색인입니다. 역색인은 낱말을 열쇠로 삼아 그 낱말이 든 문서 번호를 늘어놓은 색인입니다. 분석기가 쪼갠 낱말은 여기에 적힙니다.

「역」이 붙는 까닭은 방향입니다. 문서를 열면 그 안의 낱말이 보이는 것이 보통 방향입니다. 역색인은 이 방향을 뒤집어 낱말에서 문서로 갑니다. 그래서 문서가 아무리 많아도 찾는 낱말의 줄 하나만 읽으면 후보가 나옵니다.

문서 셋을 넣어 보겠습니다.

이 셋을 넣으면 역색인은 아래처럼 됩니다. 낱말이 줄마다 하나씩 섭니다. 그 낱말이 든 문서 번호가 옆에 붙습니다.

「이어폰」을 찾으면 셋째 줄 하나만 읽고 1번과 2번을 얻습니다. 문서가 셋이든 천만이든 읽는 줄은 하나입니다.

후보를 추리고 점수를 매기는 순서

질의가 오면 검색 엔진은 먼저 질의를 분석기로 쪼갭니다. 「무선 이어폰」은 「무선」과 「이어폰」 두 낱말이 됩니다. 역색인에서 두 줄을 읽으면 「무선」은 1·3번을, 「이어폰」은 1·2번을 내줍니다.

꺼낸 번호를 합치면 후보가 됩니다. 두 낱말이 다 든 문서만 원하면 겹치는 1번만 남깁니다. 하나라도 든 문서를 원하면 1·2·3번이 다 후보입니다. 이렇게 「그리고」·「또는」으로 후보를 거르는 방식을 불리언 검색이라고 부릅니다.

후보가 여럿이면 순서를 정해야 합니다. 검색 엔진은 후보마다 관련도를 셉니다. 관련도는 문서가 질의와 얼마나 잘 맞는지를 나타낸 점수입니다. 앞 예에서는 두 낱말이 다 든 1번이 하나만 든 2·3번보다 높습니다.

점수를 움직이는 신호는 대개 셋입니다.

앞의 두 신호를 곱해 수식 하나로 묶은 것이 TF-IDF(Term Frequency-Inverse Document Frequency, 낱말 빈도-역문서 빈도)입니다. 낱말 빈도는 표의 첫 줄, 곧 낱말이 문서에 나온 횟수입니다. 역문서 빈도는 그 낱말이 든 문서가 적을수록 커지는 값입니다. 표의 둘째 줄 「얼마나 드문가」가 이것입니다.

셋째 신호인 문서 길이까지 넣어 다듬은 수식이 BM25(Best Matching 25)입니다. 같은 낱말이 같은 횟수 나와도 짧은 문서가 더 높은 점수를 받습니다.

점수를 다 매기면 높은 순으로 줄 세워 위에서 몇 개만 돌려줍니다. 사람은 대개 첫 화면만 봅니다. 나머지는 다음 쪽을 누를 때 꺼냅니다.

두 길이 만나는 곳

지금까지 본 것은 두 길입니다. 문서를 넣는 길과 질의로 찾는 길입니다. 한 그림에 모으면 이렇습니다.

flowchart TD
    subgraph IN["넣는 길"]
        D["문서"] --> A1["분석기 · 낱말로 쪼갠다"]
    end
    A1 --> I["역색인"]
    subgraph OUT["찾는 길"]
        Q["질의"] --> A2["분석기 · 같은 방식으로 쪼갠다"]
        A2 --> L["낱말마다 문서 번호를 꺼낸다"]
        L --> S["관련도 점수를 매긴다"]
        S --> R["점수 높은 순 결과"]
    end
    I --> L

분석기는 두 길에 다 있습니다. 두 길은 역색인에서 만납니다. 넣을 때와 찾을 때 낱말을 같은 모양으로 맞춰 두어야 그 만남이 이뤄집니다.

문서가 한 대에 안 들어갈 때

문서가 늘어 역색인이 한 대의 디스크와 메모리를 넘으면 여러 대로 나눕니다. 문서를 몇 묶음으로 가릅니다. 묶음마다 역색인을 따로 만듭니다. 이 묶음 하나가 샤드입니다.

질의를 처음 받은 서버 한 대가 모든 샤드에 질의를 나눠 보냅니다. 샤드마다 자기 몫에서 점수 높은 문서를 추려 돌려줍니다. 처음 받은 그 서버가 이것들을 한데 모아 다시 줄 세웁니다.

샤드마다 사본을 하나 더 두기도 합니다. 한 대가 죽어도 사본이 대신 답해 검색이 이어집니다. 사본을 두는 일을 복제라고 부릅니다.

데이터베이스와 나눠 맡는 법

검색 엔진은 대개 원본 저장소로 쓰지 않습니다. 원본 저장소는 데이터를 처음 받아 지키는 곳입니다. 이 소절은 그 까닭과, 원본을 쥔 데이터베이스 옆에 검색 엔진을 붙이는 흔한 모양을 봅니다.

검색 엔진은 찾기 좋게 정리하는 데 힘을 씁니다. 그래서 넣은 문서가 역색인에 반영되기까지 틈이 생기기도 합니다. 여러 건을 한꺼번에 성공시키거나 한꺼번에 되돌리는 트랜잭션도 대개 약합니다. 돈이나 재고처럼 틀리면 안 되는 값을 맡기기에는 맞지 않습니다.

그래서 흔히 원본은 데이터베이스에 둡니다. 검색 엔진에는 찾을 때 필요한 내용만 복사해 넣습니다. 찾을 때는 검색 엔진에서 문서 번호를 받습니다. 자세한 내용은 그 번호로 데이터베이스에서 읽습니다.

sequenceDiagram
    participant 앱
    participant 데이터베이스
    participant 검색 엔진
    앱->>데이터베이스: 상품을 저장한다
    Note over 데이터베이스,검색 엔진: 바뀐 내용을 검색 엔진에 옮겨 적는다
    앱->>검색 엔진: 낱말로 찾는다
    검색 엔진-->>앱: 점수 높은 문서 번호
    앱->>데이터베이스: 번호로 원본을 읽는다

그림의 가운데 줄, 바뀐 내용을 옮겨 적는 방법은 둘로 갈립니다. 하나는 앱이 데이터베이스와 검색 엔진에 차례로 쓰는 이중 쓰기입니다. 만들기는 쉽지만, 둘째 쓰기가 실패하면 두 곳의 내용이 어긋납니다.

다른 하나는 데이터베이스의 변경 기록을 씁니다. 데이터베이스는 대개 바뀐 행을 차례로 적어 두는 기록을 따로 갖고 있습니다. 이 기록을 읽어 검색 엔진에 옮겨 주는 방법이 변경 데이터 캡처입니다. 앱은 데이터베이스 한 곳에만 쓰므로 한쪽만 성공하는 일이 없습니다. 옮기다 멈춰도 기록이 남아 있어 멈춘 곳부터 다시 읽으면 따라잡습니다.

언제 쓰고 언제 안 쓰나

어느 쪽을 고를지는 질문의 모양이 정합니다.

표의 마지막 줄은 데이터베이스에 든 전문 검색 기능입니다. PostgreSQL 전문 검색처럼 관계형 데이터베이스 가운데에는 역색인과 점수 계산을 제 안에 갖춘 것이 있습니다. 이쪽을 쓰면 굴릴 서버를 하나 더 두지 않아도 됩니다.

검색 엔진을 들이면 치르는 것도 있습니다. 원본과 역색인을 따로 두므로 저장 공간이 더 듭니다. 굴릴 서버가 하나 늘어납니다. 두 곳이 어긋나지 않게 늘 맞춰 줘야 합니다.

서버로 띄워 쓰는 검색 엔진

이 편이 말하는 검색 엔진은 대개 서버 프로그램으로 띄워 네트워크 너머에서 부릅니다. Elasticsearch, OpenSearch, Apache Solr 가 그런 제품입니다. 셋은 속에 Lucene 이라는 검색 라이브러리를 품고 있습니다.

라이브러리는 프로그램 안에 넣어 함수로 부르는 부품입니다. Lucene 은 분석기와 역색인과 점수 계산을 한 기계 안에서 해 줍니다. 서버 제품들은 그 위에 요청을 받는 입구와 여러 대로 나눠 담는 기능을 얹었습니다.

같은 이름으로 부르는 웹 검색

인터넷에서 웹 페이지를 찾아 주는 웹 검색 사이트도 검색 엔진이라고 부릅니다. 속은 이 편에서 본 것과 같습니다. 페이지를 낱말로 쪼개 역색인을 만듭니다. 질의가 오면 점수를 매겨 줄 세웁니다.

다른 점은 문서를 스스로 모으러 다닌다는 것입니다. 링크를 따라 페이지를 돌며 내용을 긁어 오는 프로그램이 크롤러입니다. 점수에도 낱말 말고 다른 신호를 더 씁니다. 다른 페이지가 이 페이지를 얼마나 가리키는지가 대표적입니다.

웹 검색 결과에 잘 오르도록 페이지를 다듬는 일은 검색 엔진 최적화라고 부릅니다. 이 이름의 검색 엔진은 웹 검색 사이트 쪽을 가리킵니다.

관련 항목

검색 엔진이 속한 상위 분야

검색 · 전문 검색 · 데이터베이스 · 질의 · 문서

글을 넣을 때 거치는 처리 단계

분석기 · 토큰화 · 토큰 · 형태소 분석 · 어간 추출 · 표제어 추출 · 불용어 · 동의어 사전

검색 엔진 안에 쌓이는 색인 구조

색인 · 역색인 · 포스팅 리스트 · 증분 색인 · 세그먼트

후보를 고르는 검색 방식

불리언 검색 · 구문 검색 · 퍼지 검색 · 자동 완성 · 패싯 · 벡터 검색 · 시맨틱 검색 · 하이브리드 검색

결과 순서를 정하는 점수 모델

관련도 · 랭킹 · TF-IDF · BM25 · 벡터 공간 모델 · 재순위화

검색 결과가 잘 맞는지 재는 지표

정밀도 · 재현율 · nDCG · MRR

검색 엔진을 여러 대로 나눠 담는 구조

샤드 · 레플리카 샤드 · 복제 · 샤딩 · 노드 · 클러스터

검색 엔진 노릇을 하는 제품

Elasticsearch · OpenSearch · Apache Solr · Apache Lucene · Meilisearch · Typesense · Vespa · Algolia · PostgreSQL 전문 검색

원본 데이터베이스와 검색 엔진을 맞추는 방법

이중 쓰기 · 변경 데이터 캡처 · CQRS · 결과적 일관성 · 트랜잭션

웹 검색 엔진을 이루는 구성 요소

크롤러 · PageRank · 검색 엔진 최적화 · robots.txt · 사이트맵 · 소프트 404