[웹 개발자를 위한 대규모 서비스를 지탱하는 기술]Chapter 9

이 글은 절판도서 "웹 개발자를 위한 대규모 서비스를 지탱하는 기술" 을 개인적인 용도로 정리한 글입니다. 모든 내용을 정리한 것이 아니라 필요한 부분만 정리했다는 점 양해 부탁드립니다
문제/오류가 있을 시 댓글로 알려주면 감사하겠습니다

과제 부분(8장) 은 정리 생략합니다

| 전문 검색기술 도전

대규모 데이터 처리의 노하우

전문 검색 기술의 응용 범위

| 하테나 데이터로 검색엔진 만들기- 검색 서비스 이외에 검색 시스템 이용

• 하테나는 키워드가 포함된 글들을 검색할 수 있는 시스템이 있었다(구글과는 달리 하테나 키워드에 포함되어 있는 단어만을 검색할 수 있었다)
• 일반적인 서버 메모리 용량인 8GB 정도의 리소스로 모든 글을 검색할 수 있었다
• 이전에는 이 기능을 RDB로 처리를 했다 하지만 확장성이 최악이었다(무겁고, 레코드 수가 너무 많다)

블로그 글 작성 시 해당 글의 키워드를 전부 추출 -> 단어와 블로그의 연관성을 DB 레코드로 저장

• 그래서 바꾼 방법은 검색 엔진을 만들어서 검색할 수 있도록 했다(포함하는 블로그)

• 사용자가 쿼리를 직접 날리는게 아니라 다른 곳(사용자가 보고 있는 페이지의 키워드 명) 에서 날라지고 이를 검색 시스템에 입력해서 결과를 얻는다(검색 시스템과 하는 일은 동일하지만 보여주는 방식이 다르다)

• 출력이 일자순으로만 나오면 되기 때문에 빠르고 컴팩트하다

• 또한 하테나 글 안에서만 검색하는 시스템이므로, 하테나 사양에 특화시킨 방법으로 저장이 빠르다(C++ 구현, perl로 통신)

| 하테나 북마크의 전문 검색 - 세세한 요구를 만족시키는 프로그램

• 하테나에는 자신이 북마크한 사이트만을 대상으로 한 전문 검색 엔진인 마이 북마크 검색이 있다
• 앞서 올린 글 검색과 다른 점은 시스템의 규모나 이용 목적이고, 검색 엔진의 기능적인 측면에서는 스니펫이 주로 나타나게 되어있다는 점이다
• 스니펫을 실현하려면 검색어가 문서 내의 어느 위치에 있는 단어와 매칭하는지 기록할 필요가 있는데 이를 고속으로 수행하려고 하면 데이터 구조가 복잡해진다
• 이 기능은 전체 데이터 검색이 아니라 각 개인이 북마크한 개인 데이터로부터 검색을 하는 시스템이므로 소규모이다(때문에 데이터베이스 측면의 한계가 있어 직접 구현)
• 각 개인 단위로 하면 DB에 모든 사용자의 데이터가 모아져 하나의 테이블에 들어가야 하는데 데이터가 크면 쉽게 할 수 없고, 또 검색 기능이므로 빨라야 하기 때문에 검색 시스템을 별도로 만들었다

사용자가 북마크를 추가하는 타이밍에 맞춰 각 사용자별로 검색 인덱스를 준비해두고 이를 갱신한다
-> 검색할 때는 해당 사용자의 인덱스에서만 검색 

검색 시스템의 아키텍처

| 검색 시스템이 완성되기까지

전문 검색은 다음과 같은 순서로 이루어진다 
크롤링 -> 저장 -> 인덱싱 -> 검색 -> 스코어링 -> 결과표시 

1) 크롤링 
- 대상 문서가 웹에 있다면 웹 크롤러를 만들어서 대량 문서를 가져오는 작업이 필요 
2) 저장 
- 가져온 문서를 저장 
- 이 때 DB에 넣는다면 DB가 깨졌을 때 복구할 수 없으므로 분산 DB에 저장을 한다 
3) 인덱싱 
- 인덱스 : 고속으로 검색하기 위한 구조(cf 책의 색인)
4) 검색 
- 검색 쿼리를 포함하는 문서가 검색 결과로 반환 
5) 스코어링 or 랭킹 
- 검색 결과를 어떤 순서로 표시해줄 것인가라는 것은 굉장히 중요한 문제  
6) 결과표시
- 결과를 표시하는 것으로 스니핏을 표시한다거나, 빠르게 표시한다거나 등의 요건이 있다

아래에서는 인덱싱, 검색에 대해서 설명

| 다양한 검색엔진

grep : 디렉터리를 지정해서 해당 디렉터리에 있는 문서를 전부 살펴보고 원하는 단어가 포함되어 있는 문서를 찾아준다 
Namazu : 오픈소스 전문 검색 엔진의 선구자, 지금은 잘 안씀
Hyper Estraier : 모던한 설계 
Apache Lucene : 설계가 모던해서 최근 검색엔진 구현에 참고가 많이 된다 
Senna : PostgreSQL, MySQL 등의 데이터베이스 내부를 검색할 수 있는 검색엔진(데이터 바인딩 포함 되어있었지만, 지금은 별도의 프로젝트에서 제공)
Sedue : 북마크 전체를 검색하는 곳에 사용하고 있는 상용 검색 시스템, 내부 기술이 다른 시스템과 다름
Lux : 모던함

과 같은 검색엔진들이 있다

| 전문 검색의 종류

• 전문 검색의 아키텍처에는 종류가 꽤 많은 듯 하며 grep형, Suffix형, 역 인덱스형을 정리할 것이다

| grep형

• 검색 대상 문서를 처음부터 읽어가는 단순한 아키텍처
• 검색 대상의 text(길이 m), 검색하려는 검색어(길이 n)가 있을 때 O(mn)만큼 걸린다
• KMP법이나 BM법 등을 사용할 수 있지만 단순구현만으로는 데이터가 늘어나면 힘겨워질 수 있다
• AC법에서 검색어 하나만 입력한 패턴이 KMP법
• order가 크지만 즉시성은 좋다(문서가 갱신돼도 바로 검색이 가능하고, 검색 누락이 없다)
• 병렬화, 쿼리 확장이 용이하다
• 대규모의 환경에서 하면 무리가 있을 것이다

| Suffix형

• 검색 대상 전문을 검색 가능한 형태로 가지고 있다
• Trie, Suffix Array, Suffix Tree 등이 있다
• 문서를 검색 가능한 형태로 가지고 있으며 전부 메모리에 올릴 수 있는 형태가 된다
• 정보량이 크므로 이론적으로는 검색 가능해진다는 것을 알지만 실제로 이 아키텍처를 가진 엔진은 좀처럼 구현하기 어렵다
  -PFI의 Sedue는 Suffix Array를 상당히 압축해 보유함으로 이를 실현했다(Comporesed Suffix Array)

| 역 인덱스형

• 현재 주류
• 단어(term)와 문서를 연관짓는 것이다
• 역 인덱스를 문서와는 별개로 만들어야한다(검색하기 전에 인덱스를 전처리로 만들어야 한다 )
• 이 때문에 grep과 같이 문서 변경이 이루어지면 검색 결과도 바뀌는 것은 안된다(즉시성 떨어짐, 검색 누락 발생)
• 하지만 인덱스를 압축하면서 컴팩트하게 가져갈 수 있고 대규모화하기도 쉽고 구현도 적절한 공수로 끝낼 수 있어 많이 채택되는 아키텍쳐이다

역 인덱스의 구조

• 역인덱스의 구조는 Dictionary와 Postings라는 두 파트로 나뉜다
• 각각의 문서에는 번호가 달려있다

ex) 
doc 1 : 하테나의 마스코트인 시나몬은 도쿄에 없다 
doc 2 : 훗가이도에 살았던 kurain 
doc 3 : 하테나 교토의 시나몬에는 익숙한 kurian

• 이 문서를 인덱스화 하게되고, 나열된 단어들을 term이라고 한다
• term들의 집합을 dictionary라고 한다
• term을 포함하고 있는 문서는 몇 번인지를 나타낸 것이 우측의 배열이고 이를 postings이라고 한다

term- posting
   
하테나 - 1, 3
시나몬 - 1, 3
도쿄 - 1
훗카이도  - 2 
교토 - 3
훗카이도 - 2 
kurain - 2, 3 

• 역 인덱스 = Dictionary + Postings, 인덱스를 보면 바로 어떤 문서에 어떤 단어가 포함되어 있는지를 알 수 있다

| Dictionary 만드는 법 - 역 인덱스 작성법 #1

• dictionary는 term을 어떻게 선택하느냐라는 문제가 있다
• 단어를 term으로 해서 다루는 방식 선택
• 사전에 AC법과 같은 것으로 단어를 분리하는 방법, 형태소 분석을 사용하는 방법 같은 것이 있다
• 또는 단어가 아니라 n-gram이라는 기법으로 문자를 적당한 단위로 나누고 이를 term 으로 사용할 수도 있다

| 언어의 단어를 term으로 하는 두가지 방법

• 이 때 문제가 되는 것은 어떻게 해서 검색하고자 하는 대상 문서에 해당 단어가 있는지를 찾을 수 있는건가에 대한 부분이다
• 영어라면 공백으로 구분해서 문장이 쓰이므로 공백으로 구분하면 문서를 단어로 분해할 수 있다
• 하지만 일본어(하테나가 일본 기업임)는 공백이 없고 단어의 분기점이 있는지 모른다는 문제가 있다

1. AC 법

• 사전이 곧 검색 시스템의 단어공간이 된다
• 즉 사전에 들어가있는 단어만 검색할 수 있다

2. 형태소 분석기(형태소를 단어로 간주해서 term으로 한다)

• 형태소 분석기에서 가장 요구되는 기능은 '유형파악과 분리' 기능이다
• 문장을 형태소로 나눠서 품사를 추정하는 것이다
• 사전을 이용해서 알 수도 있고, 신조어 같은 경우에도 단어의 배열을 고려해서 기계학습으로 학습해 알 수 있다
  ex) 명사 다음에는 조사가 온다, 조사와 동사 사이에 포함되어 있는 것은 명사일 수 있다
• 형태소 분석기를 커스터마이즈 할 경우도 있다

| 검색 누락

• 단어 안의 단어는 검색이 안될 경우가 있다(ex Gears를 검색하는데 Gear이라는 단어는 검색이 될 수 있게 설계할 수 도 있고, 안되게 설계할 수도 있다)
• 동사의 활용에 따라서도 검색이 누락될 수 있다 -> 어근/원형을 기반으로 dictionary를 만들면 해결이 가능

| n-gram을 term으로 다루기

• n-gram을 이용해 dictionary를 다루는 방법도 있다
• n-gram은 텍스트를 n자씩 잘라낸 것이다(세문자의 경우 트라이그램)

ex) abracadabra -> aba, bra, rac, ...

• n-gram이 어느 문서에 포함되어 있는지 조사해서 역 인덱스를 만드는 것이다
• Postings를 교집합(intersection)처리 해서 글을 구하게 된다
• n-gram으로는 이따금 검색어를 포함하지 않는 결과를 반환하는 문제를 발생히킨다

ex) 가나타워와 나다타워라는 문서를 인덱싱 
-> 가나다로 검색하면 검색이 이루어진다 
-> 하지만 문서 내에 가나다는 없는 것을 알 수 있다 

• 이를 위해 실제 검색 결과를 조사해서 확인하는 필터링을 거치게 된다
• 하지만 필터링 할 때 반환된 결과의 전문을 조사해야하니 grep형과 동일한 검색시간이 소요되므로 문제가 있다
• 타이틀, 코멘트 url을 대상으로 검색할 때는 n-gram을 사용하는 편이 검색누락이 없고 길이도 짧아 필터링도 빠르다
• 본문 검색에서는 n-gram을 사용하지 않고 단어 기반을 사용한다
• 최근에는 두 인덱스에 쿼리를 날려 결과를 병합하는 연구를 한다

| 재현률(Recall)과 적합률(Precision)

• 재현률과 적합률은 어떤 결과가 나와야 타당한가에 대한 정량적 기준이다
• 재현률은 어느 정도의 양, 결과를 반환하는지를, 적합률은 검색 결과로 반환한 것 중 명백히 타당한 결과를 얼마나 반환하고 있는가를 말한다

사람들의 선호 유형은 다음과 같다(이 둘은 상반관계)
- 많은 양의 옳은 검색 결과 + 꽝도 좀 많이 섞인 경우 
- 정말 옳은 검색 결과만 들어있고 대신 그 양이 적은 경우 

| 검색 시스템 평가와 재현률/적합률

• 형태소 분석은 검색되었으면 하는 것이 검색되지 않는 경유가 있지만 의도하지 않은 결과가 나오는 경우는 적으므로 적합률이 우선시된다
• n-gram은 검색누락은 발생하지 않지만 의도하지 않은 결과가 반환되는(필터링 필요) 경우가 있으므로 재현률이 우선시된다고 할 수 있다

| Postings 작성법 - 역 인덱스 작성법 #2

• postings는 해당 단어를 포함하는 문서 번호 또는 ID를 지니고 있는 배열로 생각하면 된다
• term 이 해당 문서 내의 어느 위치에 출현하는지 그 출현 위치를 저장하는 경우도 있다(Full Inverted Index) 이 경우 좋은 점은 스니핏을 뽑아낼 때 이 단어가 문장 내의 어디에 포함되어 있는지를 바로 알 수 있다는 점이다
• 단어 사이의 근접도로 스코어링 할 때 단어 출현 위치를 사용하기도 한다
• n-gram을 이용한 필터링을 할 경우에도 사용할 수 있다(두 단어가 위치면에서 연결되어 있다면 문제 없음)

| 출현 위치를 저장하지 않고 문서ID만을 저장하는 타입

• Inverted File Index : 출현 위치를 저장하지 않고 문서 ID만을 저장하는 경우
• 출현 위치를 저장하지 않으면 크기가 작고 구현에 용이하다
• 츨현 위치를 저장하지 않으면 처음 본 것처럼 term에 대응하는 문서ID가 나열된 배열에 불과하므로 데이터 구조로는 단순하다(문서 ID는 정렬해둔다 -> 정수열 압축이 가능해 VB Code로 압축 가능)
• 역 인덱스는 key(term), value(postings list) 쌍으로 생각할 수 있으며, 이 구조는 key-value 스토어로 저장할 수 있다
• 검색엔진은 역 인덱스를 저장하기 위한 key-value 스토어를 독자적으로 가지고 있는 경우가 많다

| 스코어링에 대한 보충

• 검색결과를 어떤 순서로 표시할 건지는 상당히 중요한 문제이다
• 문서의 중요성을 고려해 랭킹을 매긴 것은 google이며, Google의 랭킹 알고리즘은 PageRank(+ a)이다
• 검색 결과의 랭킹을 결정하는 데에는 여러 기법을 생각해볼 수 있는데 검색한 단어가 문서 내에서 얼마나 중요성을 갖고 있는지 가늠해 이 문서에서 중요도가 높다고 생각하면 문서의 순위를 높이는 것도 가능하다(TF/IDF 이용 가능)
• 검색어가 많이 주어졌을 때 검색 대상 문서에 포함되어 있는 단어의 열을 보고 이 문장과 주어진 단어열이 비슷한지 예측할 수도 있다