[웹 개발자를 위한 대규모 서비스를 지탱하는 기술]Chapter 10(과제)

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

과제 부분에서 코드는 perl로 되어있으므로 생략하도록 하겠습니다(perl 유저가 아님)

| 대규모 데이터 처리의 대표 기술

전문 검색엔진 개발 과제

• 대상은 최근 엔트리 1만건
• 검색어를 포함하는 엔트리를 반환
• 반환하는 내용은 URL, 타이틀을 포함할 것
• 가능하면 스니핏도 표시
• 작성 일자순으로 정렬

추가
+ 검색 조건 추가: AND / OR 검색에 대응, 카테고리 분류에 대응 
+ 속도와 정확성 추구 : 실용적인 검색속도, 검색 누락이나 false-positive 회피 

• 위의 조건으로 북마크 검색과 같은 것을 만든다
• 데이터에는 각 엔트리의 본문을 추출한 데이터가 들어있으므로 타이틀이나 URL뿐만 아니라 본문에 검색어가 포함되어 있는지 여부도 체크해서 해당하는 엔트리를 반환하도록 한다
• 검색 결과로는 엔트리의 URL과 타이틀을 반환하도록 한다
• 스니핏으로 출력하기 위해서는 역 인덱스에 단어 출현위치를 넣을 필요가 있으므로 시간이 소요될 수도 있다

| 사전의 구성

• Dictionary + Postings를 만드는 과제
• Dictionary는 n-gram이 아닌 단어를 기반으로 만든다
• term 추출에는 AC법을 사용해도 되고, 형태소 분석기를 사용해도 됨(AC 법을 사용하면 전부 다 구현하는 기쁨😃을 맛볼 수 있다)
• postings의 압축은 VB Code 구현을 이용한다
• 압축한 데이터를 파일에 쓰지 않고 메모리에 보관해서 이를 사용해서 검색한다

| 인터페이스

어플리케이션의 인터페이스는 아래와 같이 검색할 수 있도록 한다

- 명령줄에서 실행
- 대화형 인터페이스 

| 기본적인 부분 + 심화 구현

• 기본적인 구현 외에 다음과 같은 심화 구현을 추가한다

- 전문 검색을 구현한다 
- AND / OR 검색을 할 수 있다 
- 카테고리에 따라 분류할 수 있다 

| 속도와 정확성으로 승부

• 다음과 같은 항목에 대해 평가를 진행한다

- 속도와 정확성으로 승부 
- 샘플 쿼리에 대한 검색결과 상위 5건을 평가(검색시간, 정확성, 검색누락)

응답 사례와 사고방식

• 역 인덱스를 만들어서 디스크에 기록하는 파일(indexer.pl)과 해당 인덱스를 로드해서 대화 프롬프트로 검색하는 파일(searcher.pl)을 만들었다
• 후자에서는 스니핏도 출력하도록 했다

| indexer.pl

• 해시를 이용해 역인덱스를 만든다
• Postings List의 압축은 차분을 구해서 VB Code를 적용(여기서는 Array::Gap 이라는 라이브러리 사용)
• 역 인덱스가 구축되면 디스크에 해시를 기록한다
  (여기서는 Storable을 사용해 해시 데이터 구조를 바이너리로 디스크로 기록하고 다른 프로그램에서 이것을 로드할 수 있도록 했다)

| searcher.pl

• 입력으로 주어진 데이터 파일을 읽어들이고 indexer.pl로 만든 인덱스 파일을 로드한다
• 검색용 인터페이스는 대화 프롬프트로서 제공하는데 이를 구현하기 위해서 Term:::ReadLine을 사용
• 역 인덱스로부터 검색은 사실 해시에 대해 키를 검색쿼리에 부여할 뿐임
• 키에 대응하는 값이 압축된 Postings List이므로 이를 Array::Gap으로 전개한다
• 이렇게 해서 문서 ID 목록을 손에 넣었으므로 그 다음은 텍스트 파일과 조합해서 출력 포맷을 정비해주면 된다
• 스니핏 출력은 여기서는 텍스트 내에서 쿼리가 일치하는 곳을 찾도록 구현했다
• 실용적인 시스템에서는 역인덱스에 검색어의 출현위치를 기억시켜두고 쿼리를 발견한 위치는 곧바로 찾아내지 말고 속도를 버는 편이 더 낫다

| 개선할 점

• And | Or 구현

And | or 검색을 구현하려면 쿼리를 분석해서 복수의 쿼리 단어를 얻었으면 단어에 대응하는 Postings List에 출현하는 공통의 문서 ID를 추출, 
즉 복수의 Postings List 사이에서 문서 ID의 교집합을 얻는다. 
OR 검색에서는 합집합을 얻는다 

• searcher.pl로 검색어도 분해한다

검색어를 그대로 역인덱스에 넣는 것이 아니라 실제 쿼리 단어도 형태소 분석한 후에 역 인덱스로 검색하는 편이 정확하다 

• 형태소 분석이 아닌 n-gram 방식을 사용한다
• 역 인덱스에 단어 출현위치를 기록해서 스니핏 출력에 도움이 되도록 한다

트위터의 스케일아웃 전략 
- 데이터를 메모리 내에서 처리할 수 있도록 파티셔닝 등으로 데이터를 분할해서 조정하는 것이 기본 
- MySQL + memcached에 파티셔닝 
- 사용자 ID가 아니라 트윗 작성일시(시간)을 축으로 하여 파티셔닝을 한다 
- fan out이라는 메일 전송과 비슷한 아키텍처를 MySQL + memcached에 채택해서 일부 기능을 실시간성을 잃지 않고 실현 
- Apache Cassandra라는 아키텍처 도입 예정(과거 얘기이므로 지금은 모름)