[스프링팀] 검색 기술의 원리 발표 세션

안녕하세요, 스프링팀 김경환입니다. 지난 6월 11일 삼성역 하이퍼커넥트 사옥에서 매시업 전체 5차 세미나를 진행했습니다!

매시업 전체 세미나에서는 매 기수마다 모든 팀이 각각 두 세션 씩 주제를 정해서 발표를 하는데요,

12기 스프링팀에서는 개발자의 사실과 오해를 다룬 개발자 밈을 소개하는 세션과, 검색 기술의 원리를 소개하는 세션을 진행했습니다.

이번 세미나에서는 약 100명에 가까운 매시업 크루원분들이 참석해주셔서 그 어느때보다 더 활기찼는데요! 스프링팀 발표 세션에 뜨거운 호응 보내주신 점 감사드립니다!

스프링팀 세션 중 제가 발표한 검색 기술의 원리를 소개하는 세션 내용을 정리해서 공유하고자 합니다.

💡검색이란?

이미지출처:https://www.overpopulationatlas.com/post/where-s-wally

검색 기술을 소개하기 앞서, 윌리를 같이 찾아볼까요?

"윌리를 찾아라"는 수많은 사람들로 가득찬 큰 그림 속에서 청바지에 빨간색 줄무늬 스웨터와 모자를 쓴 윌리를 찾는 게임입니다!

여러분은 윌리를 찾을 때 어디서부터 찾으시나요?

눈을 가까이 대고 위에서부터 아래로, 혹은 왼쪽에서 오른쪽으로 한명 한명 들여다보며 찾기도 하고, 멀리 떨어져서 윌리가 있을 법한 장소를 물색해 그 부분을 자세히 들여다 보기도 합니다.

큰 그림 속 수많은 사람들 중에서 윌리를 찾는 일은 쉬운 일이 아닌데요, 혹시 찾으셨나요?

실제로 세미나에서 100명에 가까운 매시업 크루들이 같이 찾아봤지만 윌리를 찾는데는 꽤 오랜 시간이 걸렸습니다.

윌리와 상관 없는 많은 사람들 속에서 우리가 원하는 사람인 윌리를 찾는 것과 검색은 꽤나 유사한 면이 있는데요,

맛있는 식당을 찾기란 쉽지 않다

우리는 흔히 처음 가는 장소를 찾을 때나 맛집을 찾을 때 검색합니다. 가야할 장소와 상관 없는 수많은 건물 중 우리가 원하는 건물이 어디있는 지 검색하고, 수많은 음식점과 카페 중 맛집만을 가려내기 위해 검색합니다. 이처럼 검색이란 "많은 정보 중 원하는 정보만 찾아내는 것"으로 정의할 수 있습니다. 많은 사람들 중 윌리를 찾고, 많은 음식점 중 맛집만을 찾는것처럼요.

🔬그렇다면 검색을 어떻게 해야하지?

수많은 정보 중에서 우리가 원하는 정보를 어떻게 찾을 수 있을까요?

간단한 예시를 들어봅시다. 매시업 전체 5차 세미나는 삼성역 아셈타워에 있는 하이퍼커넥트에서 진행됐는데요,

하이퍼커넥트에 오기 위해 수많은 건물 중 아셈타워를 어떻게 찾을 수 있을까요?

아셈타워를 찾기 위해서는 많은 건물 이름 중 "아셈"이라는 글자가 들어간 건물을 찾아야 합니다.

컴퓨터는 아셈을 찾기 위해 하나하나씩 비교를 해볼 수 밖에 없습니다.

먼저 "남산"과 "아셈"이 일치하는지 확인하고, 다음 두글자인 "산전"과 "아셈"이 일치하는 지 확인하는 과정을 반복해 아셈타워를 찾을 수 있습니다.

이번 예제에서는 “남산”, “산전”, “전망”, “망대”, “아셈” 순으로 총 5번의 비교연산을 통해 아셈타워를 찾을 수 있겠지만 실제로 적용이 가능할까요?

만약 건물 개수가 1000만개라면 최소 1000만번 이상의 비교 연산을 수행해야 하고, 건물 이름이 길다면 그 길이의 배수만큼 더 연산이 필요할 것입니다. 문자열 매칭 알고리즘을 사용한다면 (건물이름의 평균 길이 * 건물 개수) 만큼의 시간이 필요합니다.

매시업 세미나에 가기 위해 아셈타워를 검색하더라도 검색 결과가 나온 시간이 세미나가 끝난 시간이라면 검색은 의미가 없겠죠.

이처럼 검색은 데이터를 조회할 때 많은 연산이 필요합니다.

그렇다면 검색할 때마다 찾지 않고 데이터를 쓸 때 미리 찾아놓는 것은 어떨까요?

“검색될 데이터를 미리 찾아놓는다”는 말이 다소 모순적으로 들리는데요, 물론 미래에 사용자가 어떤 키워드로 검색을 할 지는 모릅니다!

대신 “검색이 될만한 문자열”로 미리 분리해놓을 수는 있습니다. 앞서 살펴본 예제에서 “남산전망대”라는 키워드에 “아셈”이 들어있는 지 확인할 때 “산전”, “망대”와 같이 의미없는 부분 문자열과도 비교 연산을 수행하는 것을 볼 수 있었습니다. “남산전망대” 라는 단어는 “남산” 과 “전망대”라는 명사가 합쳐진 단어입니다. 따라서 사용자는 “남산전망대”를 찾기 위해 주로 “남산” 혹은 “전망대”라는 키워드로 검색할 것이라고 추론할 수 있습니다. 이제 “남산전망대”라는 단어를 “남산”과 “전망대”라는 단어로 분리하여 각각 저장하고, 각 단어들이 “남산전망대”라는 원본 문서를 가르키도록 하면 어떨까요?

이처럼 데이터를 찾기 위해 추가적인 자료구조를 사용하는 것을 색인이라고 합니다.

검색에서 사용되는 색인은 데이터의 식별자를 사용하여 데이터를 찾는 일반적인 색인과 달리 데이터를 사용하여 데이터의 식별자를 찾는, 반대로된 색인이기 때문에 역색인(Inverted Index)라고 부릅니다.

앞선 예제를 역색인 구조로 나타낸 표는 다음과 같습니다. “아셈타워”가 “아셈”과 “타워”로, “롯데월드타워”는 “롯데월드”와 “타워”로 분리된 모습을 볼 수 있습니다.

좌측:역색인 구조 우측:원본 문서

마찬가지로 검색어를 사용해 검색이 될만한 문자열을 찾아야 하기 때문에 검색어 또한 검색이 될만한 문자열로 분리하는 과정이 필요합니다.

예를 들어 “포스코타워”로 검색한다면 “포스코” 와 “타워”로 검색어가 분리되고, “타워”라는 문자열과 일치해 검색어와 비슷한 “롯데월드타워”와 “아셈타워”를 찾을 수 있습니다.

잠깐 용어 정리를 하자면, 검색이 될만한 문자열을 짧게 줄여서 토큰이라고 부릅니다.

문자열을 토큰으로 만드는 과정을 토크나이징이라고 하고, 검색어가 토큰으로 분리되어 저장되는 과정을 인덱싱이라고 부릅니다. 주목해야할 점은 토큰은 원본 데이터를 검색이 될만한 문자열로 이기 때문에 검색어 토큰과 단순히 일치하는지만 확인한다는 점입니다.

따라서 토큰을 사전순으로 정렬하여 저장한다면 이진탐색을 활용해 특정 토큰을 빠르게 찾을 수 있습니다.

⭐️토크나이징 방법

앞서 살펴본 것처럼 데이터를 검색하기 위해서는 검색이 될만한 문자열로 분리하는 과정이 필수적입니다.

그렇다면 원본 데이터를 어떻게 분리해야 할까요? “남산전망대”의 예시처럼 여러개의 단어로 이루어진 명사의 경우 각 명사를 단위로 “남산”과 “전망대”로 쪼갤 수 있었습니다.

같은 원리로 “성장의 즐거움을 아는 친구들, IT 개발 동아리 매시업 블로그 입니다.” 라는 문자열을 쪼개면 조사나 마침표 등 문법적인 구성 요소를 제외하고, 명사나 동사만을 분리해 “성장”, “즐거움”, “알다”, “친구”, “IT”, “개발”, “동아리”, “매시업”, “블로그” 등으로 분리할 수 있습니다.

이처럼 문장을 구성하는 명사, 동사, 조사 등 각 단어의 형태소와 품사 정보를 활용해 문자열을 분리하는 규칙을 정할 수 있습니다.

하지만 단점또한 존재합니다. “아버지가방에들어셨다”와 같은 문장을 토크나이징하기 위해서는 상당히 애매모호한 부분이 존재합니다.

“아버지가방”에서 “가”를 조사로 인식해 “아버지” “방”으로 분리할 지, 혹은 “가방”으로 인식해 “아버지” 와 “가방”으로 분리할 지 결정해야 합니다.

규칙 기반 토크나이징의 모호함을 보완하기 위해 통계적인 방법을 활용해 토크나이징을 수행할 수도 있습니다.

하나의 문장을 데이터의 연결 관계(상태 변화)로 해석하여, 학습된 데이터 연결 관계를 활용해 현재 데이터가 다음 어떤 데이터로 변화(전이)할 지 추론하는 방법입니다.

쉽게 정리하자면 다음과 같습니다.

일반적으로 문장에서 첫 단어는 명사(주어)일 확률이 높고, 그 다음은 조사, 다음은 명사(목적어), 다시 조사, 마지막으로 동사(서술어)가 나올 확률이 높습니다.

“아버지가방에들어가셨다”라는 예시를 다시 보겠습니다.

“아버지”는 문장의 첫 단어이니 명사, “가”는 조사, “방”은 명사, “들어가다”는 동사로 토크나이징 하는게 확률적으로 더 올바른 토크나이징일것이라 추론할 수 있습니다.

토크나이징은 검색 품질에 많은 영향을 주는 동시에 상당히 까다로운 부분이기도 합니다.

언어별로 언어의 특성이 다르고 언어 활용 패턴도 달라 모든 문장에 적용할 수 있는 토크나이징 알고리즘은 찾기가 어렵습니다.

토크나이징은 국문학과 딥러닝을 활용하여 자연어처리 분야에서 활발하게 연구되는 분야입니다.

🍀역색인의 저장

지금까지 역색인 구조와 역색인 구조를 만들기 위한 토크나이징까지 알아봤습니다.

토크나이징 과정을 거쳐 역색인 구조를 만들수 있었지만 역색인 데이터를 실제로 저장하기 위해서는 여러 난관을 거쳐야 합니다.

앞서 “성장의 즐거움을 아는 친구들, IT 개발 동아리 매시업 블로그 입니다.” 라는 문자열을 역색인 구조로 만들기 위해 토크나이징하면 “성장”, “즐거움”, “알다”, “친구”, “IT”, “개발”, “동아리”, “매시업”, “블로그” 총 9개의 토큰으로 분리됐습니다.

즉 하나의 원본데이터를 인덱싱하기 위해서는 역색인 구조에 아홉번 쓰기를 해야합니다. 방금 예시로 든 문장은 30자 정도의 짧은 문장이었지만, 신문기사, 블로그글처럼 아주 긴 문자열을 토크나이징 할 경우 수백개 이상의 토큰으로 분리될 수 있습니다.

따라서 역색인 구조를 저장하기 위해서는 쓰기에 강한 자료구조가 필요합니다.

애플리케이션에 적합한 자료구조를 설계하기 위해서는 부하에 대한 가정이 필요합니다. 부하란 “읽기 대 쓰기의 비율”, “단위 시간 당 읽기/쓰기 처리량”과 같이 구체적이고 정량적으로 서술됩니다.

일반적인 애플리케이션에서 데이터 구조는 SNS에 글을 올리는 빈도보다 SNS를 조회하는 빈도가 훨씬 많는 것 처럼 쓰기보다 읽기 처리가 더 많을것이라는 가정으로 설계됐습니다.

이미지 출처: https://benjamincongdon.me/blog/2021/08/17/B-Trees-More-Than-I-Thought-Id-Want-to-Know/

위 그림은 일반적으로 사용되는 색인 구조인 B+Tree입니다. 한눈에 데이터 구조가 복잡하다는 것을 파악할 수 있습니다.

데이터 구조와 구조를 변경하기 위한 규칙이 복잡하다는 것은 그만큼 찾으려는 데이터가 어디에 있고, 어떻게 접근할 수 있는지에 대해 더 많은 정보를 담고 있다는 것을 의미합니다.

따라서 읽기 시 데이터가 어떻게 저장되어 있는지에 대한 정보가 전혀 없이 탐색하는 선형탐색보다 훨씬 효율적으로 탐색할 수 있습니다. 약 250테라바이트 정도의 데이터에서 원하는 데이터를 4번정도의 접근을 통해 찾을 수 있을 정도로 빠릅니다.

하지만 쓰기 시에는 정반대로 많은 연산이 필요한데요, 특히 데이터 하나의 쓰기를 위한 연산의 수는 저장되어 있는 데이터 양에 비례해 크게 증가하는 경향을 보입니다.

예를들어 10건의 데이터가 저장되어 있을 때 새로운 데이터 하나를 저장하기 위해서는 기존 데이터를 변경하는 연산이 2번 필요했다면,

100건의 데이터가 저장되어 있을때는 새로운 데이터 하나를 저장하기 위해 기존 데이터를 변경하는 연산이 20번 필요할 수도 있습니다.

이를 쓰기 증폭이라고 하며, 한번 쓴 데이터가 미래에도 계속 쓰기를 유발하는 현상을 의미합니다.

정리하자면 색인에 복잡한 데이터 구조를 사용한다면 장점으로는 읽기 질의를 효율적으로 처리할 수 있지만

단점으로는 쓰기 비용의 증가와 쓰기 증폭으로 인한 IO 대역 증가 문제가 있습니다.

그렇다면 데이터 저장 구조를 아주 단순하게 구성하는 것은 어떨까요? 색인 데이터를 저장할 때 단순히 데이터를 입력된 순서대로 순차적으로 나열하기만 한다면 쓰기 비용을 크게 줄일 수 있습니다.

하지만 데이터를 읽을 때 중복되는(덮여쓰여진)데이터가 존재하고, 무작위 순서대로 저장되어 있기 때문에 모든 데이터를 순차적으로 읽어야하는 문제가 다시 발생합니다.

이 문제를 해결하기 위해 첫번째로 역색인을 해시테이블 형태로 구성하는 방법을 고려해볼 수 있습니다.

해시키를 토큰으로, 해시값을 토큰이 들어있는 문서 번호로 저장한다면 읽기시 빠르게 접근할 수 있고, 쓰기 연산 또한 단순해진다는 장점이 있으나

저장되어야 하는 토큰의 수가 많아 해시테이블을 디스크에 저장해야 하고, 해시 엔트리의 주소로 사용되는 토큰의 해시값이 무작위적이기 때문에 쓰기 시에 디스크 랜덤 액세스로 인해 성능이 크게 떨어지는 단점이 있습니다.

두번째로 역색인 구조를 순차적으로 저장하는 방식과 B+트리와 같이 복잡한 데이터 구조를 사용하는 방식 사이에서 균형점을 찾는 방식을 고려할 수 있습니다.

핵심 아이디어는 전체 데이터를 정렬한 상태를 유지하기 보다는 “부분적으로만 정렬된 상태를 유지하자”는 것입니다. 중복을 포함하여 1000개의 토큰이 순서대로 저장되는 상황을 가정해봅시다.

먼저 순서대로 토큰을 메모리 상에서 정렬하여 저장합니다.

전체 데이터가 아닌 일부 데이터만 정렬 상태를 유지하는 것이므로 데이터 크기가 작아 메모리에 저장할 수 있고, 메모리에 저장된다면 복잡한 데이터 구조라도 디스크보다 훨씬 빠르게 정렬된 상태를 유지할 수 있습니다. 다음으로 메모리에 저장된 토큰의 수가 일정 개수 이상이 되거나, 어느정도의 시간이 지났다면 정렬된 순서를 유지하면서 디스크에 파일로 순차적으로 저장합니다.

Segment는 하나의 파일이다. 이미지출처: https://yetanotherdevblog.com/lsm/

일정 개수를 100개로 가정한다면 디스크에는 100개씩 데이터가 담긴 파일 10개가 생성되고, 각 파일 내에서는 데이터가 정렬된 상태를 유지하고 있습니다. 데이터 검색 요청이 들어올 때, 저장된 10개의 파일을 순차적으로 읽습니다.

파일 내에서는 데이터가 정렬되어 있기 때문에 이진탐색을 활용하여 데이터를 효율적으로 찾을 수 있습니다. 모든 파일에서 데이터를 읽은 결과를 종합하여 중복을 제거하는 과정을 거쳐 검색 결과를 반환할 수 있습니다.

시간이 지남에 따라 데이터가 점점 더 많아져 파일 개수가 많아지고, 중복되는 데이터가 많아진다면 읽기의 효율성 또한 점점 감소하게 됩니다. 따라서 여러개의 파일을 하나로 합치고 덮여쓰여진 데이터를 삭제하면서 정렬해 새로운 파일을 만드는 작업을 주기적으로 실행해야 합니다.

이 과정은 각 파일이 정렬되어 있기 때문에 빠르게 수행할 수 있습니다. 예를들어 한 파일에는 데이터 1, 3, 5가, 다른 파일에는 1’, 2, 4, 5가 저장되어 있다면 (1’은 데이터 1이 새로 쓰여진 데이터) 두 개의 포인터를 활용하여 덮어쓰여진 데이터를 지우고 새로운 파일로 두 파일의 데이터를 모두 정렬하여 저장하고 기존의 두 파일은 삭제하면 데이터를 효율적으로 저장할 수 있고, 새롭게 생성된 파일은 더 많은 데이터가 정렬된 상태로 저장되어 있어 읽기 성능을 유지할 수 있습니다.

이와 같은 구조를 LSM 트리(Log Structure Merge Tree)라고 합니다. LSM 트리 구조는 검색엔진 외에도 높은 쓰기 처리량을 지원하는 데이터베이스에도 흔히 사용되며, 대표적으로 HBase, Cassandra가 있습니다.

추가적으로 데이터를 메모리에 임시적으로 저장하기 때문에 데이터의 보존을 위해 쓰기 요청 시 변경 로그를 디스크에 기록해야할 필요성이 있습니다. 변경 로그는 데이터가 디스크에 최종적으로 반영되기 전 장애 발생 시 복구를 위해 사용됩니다.

🥃 정리

지금까지 검색 기술을 지탱하는 원리에 대해 살펴봤습니다.

검색이란 “많은 데이터 중에서 원하는 데이터를 찾는 것”으로 정의할 수 있었습니다. 검색을 효율적으로 수행하기 위해 토크나이징으로 역색인 구조를 구성할 수 있었습니다.

토크나이징 방법으로는 규칙 기반과 통계 기반 토크나이징 방법이 있었으며 역색인 구조를 저장하기 위해 쓰기 처리에 강한 LSM 트리 구조를 사용함을 알 수 있었습니다.

감사합니다.