수십억 개 웹페이지를 어떻게 저장할까? 검색엔진의 색인 압축 기술

부스트키워드 팀

검색 데이터로 키워드의 검색량, 트렌드, 검색 의도를 파악하고 마케팅 의사결정을 돕는 도구 부스트키워드를 만듭니다.

앞서 살펴본 역색인은 검색을 빠르게 만들어주는 훌륭한 자료구조지만, 한 가지 현실적인 문제가 있습니다. 전 세계 수십억 개의 웹페이지를 대상으로 역색인을 만들면, 그 크기 자체가 어마어마해진다는 점입니다. 저장 공간이 부족하면 아무리 좋은 알고리즘도 무용지물이 됩니다. 그래서 검색엔진은 역색인을 최대한 압축해서 저장하는 다양한 기술을 함께 사용합니다. 이 글에서는 검색엔진이 방대한 색인 데이터를 어떻게 효율적으로 압축하는지 살펴봅니다.

역색인은 생각보다 훨씬 크다

문서 번호를 있는 그대로 저장하면 벌어지는 일

역색인의 포스팅 리스트에는 각 단어가 등장하는 문서 번호들이 나열되어 있습니다. 만약 전체 문서가 수십억 개에 달한다면, 문서 번호 하나를 저장하는 데도 상당한 크기의 숫자(예를 들어 40억까지 표현하려면 4바이트 정도)가 필요합니다. 흔하게 등장하는 단어라면 이런 문서 번호가 수억 개씩 나열되어야 하므로, 압축하지 않은 상태로 저장하면 역색인 전체의 크기가 원본 문서 데이터보다 오히려 더 커지는 경우도 생깁니다.

압축이 필요한 두 가지 이유: 저장 공간과 처리 속도

색인을 압축해야 하는 이유는 단순히 저장 공간을 아끼기 위해서만은 아닙니다. 데이터의 크기가 작아지면, 디스크나 메모리에서 데이터를 읽어오는 속도도 함께 빨라집니다. 검색 요청이 들어올 때마다 방대한 포스팅 리스트를 읽어야 하므로, 이 데이터가 압축되어 있을수록 전체 검색 속도도 향상되는 효과가 있습니다.

사전(Dictionary)을 압축하는 방법

단어를 하나의 긴 문자열로 이어붙여 저장하기

역색인은 크게 사전(단어 목록)과 포스팅 리스트(문서 번호 목록) 두 부분으로 이루어져 있다고 앞서 설명했습니다. 먼저 사전을 압축하는 방법을 살펴보면, 일반적으로 각 단어를 별도의 문자열로 따로따로 저장하는 대신, 모든 단어를 하나의 매우 긴 문자열로 이어붙여 저장하는 방식이 사용됩니다. 이렇게 하면 각 단어의 경계를 구분하기 위한 최소한의 정보만 별도로 저장하면 되므로, 단어마다 불필요하게 반복되는 저장 공간을 절약할 수 있습니다.

비슷한 단어끼리 앞부분을 공유해서 중복 줄이기

사전에 알파벳(또는 가나다) 순서로 정렬된 단어들을 자세히 보면, 서로 앞부분이 겹치는 경우가 많습니다. 예를 들어 "제주도", "제주시", "제주은행"처럼 "제주"라는 공통된 앞부분을 가진 단어들이 사전에 연이어 등장하는 경우가 흔합니다. 이런 특성을 활용해, 바로 앞 단어와 겹치는 부분은 생략하고 겹치지 않는 나머지 부분만 저장하는 방식으로 중복을 줄일 수 있습니다.

포스팅 리스트를 압축하는 핵심 아이디어: 간격(Gap)으로 저장하기

문서 번호를 그대로 저장하지 않고 '차이'만 저장하는 발상

포스팅 리스트 압축에서 가장 핵심적인 아이디어는 '간격 부호화'입니다. 포스팅 리스트는 보통 문서 번호가 오름차순으로 정렬되어 저장되어 있습니다. 이때 각 문서 번호를 있는 그대로 저장하는 대신, 바로 앞 문서 번호와의 차이(간격)만 저장하는 방식을 사용합니다. 문서 번호는 매우 큰 숫자일 수 있지만, 연속된 두 문서 번호 사이의 간격은 대체로 훨씬 작은 숫자인 경우가 많기 때문에, 이렇게 저장하면 전체적으로 필요한 저장 공간이 크게 줄어듭니다.

간단한 예제로 직접 간격 압축해보기

예를 들어 어떤 단어가 문서 번호 1004, 1010, 1011, 1032에 등장한다고 해봅시다. 이 숫자들을 그대로 저장하면 각각 4자리 숫자를 저장해야 합니다. 하지만 간격으로 바꾸어 저장하면 다음과 같이 훨씬 작은 숫자들로 표현할 수 있습니다.

• 원래 문서 번호: 1004, 1010, 1011, 1032
• 간격으로 변환: 1004, 6, 1, 21

첫 번째 숫자(1004)는 그대로 저장하지만, 그 뒤로는 각각 "바로 앞 번호와의 차이"만 저장하는 것입니다. 이렇게 하면 두 번째, 세 번째, 네 번째 숫자는 원래보다 훨씬 작은 값이 되어, 이를 표현하는 데 필요한 저장 공간도 함께 줄어듭니다. 흔하게 등장하는 단어일수록 문서 번호 사이의 간격이 더 촘촘하고 작아지므로, 압축 효과는 더욱 커집니다.

간격을 더 작은 비트로 표현하는 방법

가변 길이 바이트 코드(Variable Byte Code) 쉽게 이해하기

간격을 구했다고 해도, 이 숫자들을 실제로 컴퓨터가 이해할 수 있는 비트(0과 1)로 어떻게 표현할지가 또 다른 문제입니다. 가변 길이 바이트 코드는 작은 숫자는 적은 바이트로, 큰 숫자는 더 많은 바이트로 표현하는 방식입니다. 마치 짧은 단어는 짧게 쓰고 긴 단어는 길게 쓰는 것처럼, 숫자의 크기에 맞춰 필요한 만큼만 공간을 사용하도록 유연하게 조정하는 것입니다. 이렇게 하면 대부분의 간격이 작은 값을 갖는 흔한 단어의 경우, 저장 공간을 상당히 절약할 수 있습니다.

감마 코드(Gamma Code): 더 정교하게 압축하는 방법

감마 코드는 여기서 한 걸음 더 나아가, 바이트 단위가 아니라 훨씬 더 세밀한 비트 단위로 숫자를 표현하는 압축 방식입니다. 바이트 단위로 자를 때보다 낭비되는 공간이 줄어들어 압축률이 더 높아지지만, 그만큼 압축을 풀어 원래 숫자로 되돌리는 계산 과정이 조금 더 복잡해진다는 특징이 있습니다. 실제 검색엔진은 압축률과 처리 속도 사이의 균형을 고려해 이런 다양한 압축 방식 중 적절한 것을 선택해서 사용합니다.

압축이 실제로 얼마나 효과가 있을까

자주 등장하는 흔한 단어일수록 압축 효율이 높은 이유

앞서 지프의 법칙에서 살펴본 것처럼, 검색엔진이 다루는 단어들 중 극소수의 흔한 단어가 매우 많은 문서에 등장합니다. 이런 흔한 단어는 포스팅 리스트가 매우 길지만, 문서 번호 사이의 간격이 촘촘하고 작기 때문에 간격 압축의 효과를 크게 볼 수 있습니다. 반대로 드물게 등장하는 단어는 포스팅 리스트 자체가 짧기 때문에, 압축하지 않아도 애초에 차지하는 공간이 크지 않습니다. 결과적으로 압축 기술은 전체 색인 크기에서 가장 큰 비중을 차지하는 흔한 단어들의 저장 공간을 효과적으로 줄여주는 역할을 합니다.

압축과 검색 속도 사이의 균형

다만 압축을 지나치게 복잡한 방식으로 진행하면, 저장 공간은 절약되지만 검색할 때마다 압축을 해제하는 데 더 많은 계산이 필요해져 오히려 속도가 느려질 수 있습니다. 그래서 실제 검색엔진은 저장 공간 절약과 압축 해제 속도 사이의 균형을 고려해, 상황에 맞는 압축 방식을 신중하게 선택합니다.

정리하며

역색인은 검색을 빠르게 만들어주는 훌륭한 구조이지만, 그 자체로도 매우 방대한 크기를 갖습니다. 검색엔진은 사전을 하나의 긴 문자열로 이어붙이거나 공통된 접두사를 공유하는 방식으로, 그리고 포스팅 리스트를 문서 번호 대신 간격으로 저장하고 이를 다시 가변 길이 바이트 코드나 감마 코드 같은 방식으로 압축하는 등, 여러 층위의 압축 기술을 함께 활용해 방대한 웹 데이터를 효율적으로 저장하고 빠르게 처리할 수 있도록 설계되어 있습니다.