서론

광범위한 데이터에 액세스 할 때 → 국소성을 발견하고 그에 맞게 구성을 변경 데이터 내에서 특정한 부분만 접근하는 경우가 아니라 쪼갤 수 없는 대량의 데이터 자체에 접근(데이터마이닝, 전문(全文) 검색 등)하는 경우에는 어떻게 할 것인지?

[대규모 서비스를 지탱하는 기술 - 이토 나오야] 책을 보고 이해한 내용을 정리한 글입니다.

인덱스와 시스템 구성

대규모 데이터를 다룰 때 전문 검색이나, 유사 문서 탐색, 데이터마이닝 등은 RDBMS로는 한계가 있다. 이럴때에는 배치 처리로 RDBMS에서 데이터를 추출해서 별도의 인덱스 서버를 만들고, 이 인덱스 서버에 웹 어플리케이션에서 RPC(Remote Procedure Call)등으로 액세스 하는 방법을 사용한다

RDBMS로는 한계일 때

• 배치 처리로 데이터 추출

• 별도 인덱스 서버를 만들어서 웹API로 처리

용도 특화형 인덱싱

• RDBMS는 데이터를 정렬하거나, 통계처리가 가능하거나, JOIN 하는 등 다양한 목적에 사용할 수 있도록 설계

• 특정한 목적을 위한 튜닝을 거친 데이터 구조가 RDBMS에 비해 압도적으로 빠르다. → 용도 특화형 인덱싱

---

예시1 : 하테나의 키워드 링크

하테나의 키워드 링크 기능. 강조해 놓은부분이 자동링크기능이 사용된 곳.

특정 문서가 20만 이상의 키워드 중에 무엇을 포함하는지 찾아야 하는 상황 일일이 DB내에 있는 키워드 목록과 문서 내용을 맞춰보게 되면 DB에 과부하가 걸리게 된다.

배치 처리로 20만 건의 키워드를 추출해둔다. 예전에는 10만 건의 정규표현이 들어간 거대한 파일을 만들어서 이를 메모리에 읽어들인 후 매칭 시키는 방식. 해당 방식은 DB에 직접 질의하는 것보다는 빠르지만 정규표현만으로는 여전히 성능이 좋지 않다.

Trie 기반의 정규표현을 사용해서 Common Prefix Search(공통접두사검색)를 수행한다. 이 알고리즘은 링크가능한 키워드 목록을 DB에서 사전에 추출해서 만들어두고 매칭하는 방식이다. 해당 알고리즘에 대한 자세한 내용은 따로 글로 쓰겠습니다.

---

예시2 : 하테나 북마크의 텍스트 분류기

하테나 북마크. 하테나 북마크는 생활, 기술 등 기사의 카테고리를 자동분류하고있다

북마크의 자동분류에 사용된 알고리즘 : Complement Navie Bayes 알고리즘을 사용해서 자동으로 머신러닝을 통해 분류 (이는 후에 다시 포스팅 할 예정)

Complement Navie Bayes 알고리즘을 사용할 때 문서에 포함된 단어의 출현확률이 필요하다. 문서의 카테고리를 판정할 때 문서 속에 어떤 단어가 들어있고 단어는 몇 건 있는지 쿼리를 통해 질의하면 시간이 상당히 걸린다.

예를 들어 트위터 라는 단어가 기사에 들어있는지, 몇건 들어있는지 조회하는것은 상당히 오랜 시간이 걸린다.

출현빈도만을 저장하는 서버를 가동해둔다. 이 서버에 질의하면 순식간에 응답이 반환된다.

---

전문 검색엔진

전문(全文) 검색은 아래 포인트를 어떻게 쿼리할 것인가 하는 점이 관건

• 대량의 데이터에서 검색하고자 한다

• 빠르게 검색하고자 한다

• 좋은 느낌(Feeling Lucky)과 같은 문서를 상위로

특히 세 번째, 좋은 느낌(Feeling Lucky)에 해당하는 문장을 상위로 가져오는 것이 가장 어려운데 이를 이해서는 스코어링 처리를 수행한다. 스코어링에서는 검색대상인 문서가 가지고 있는 다양한 정보를 복합적으로 이용한다.

특정 칼럼으로만 정렬할 수 있는 RDBMS에서 스코어링은 무리 → 검색 인덱스를 직접 만들어 해결 검색 엔진을 직접 구현한다면 스코어링 알고리즘도 자유롭게 선택할 수 있으므로 검색 결과를 나열하는 방법은 RDBMS를 사용하는 것보다 훨씬 유연하다.

---

이론과 실전 양쪽과의 싸움

웹 애플리케이션 세계는 이론과 실전 양쪽에서 공격해야 한다.

RDBMS에서 JOIN을 사용하지 않는 것 과 같은 방법은 배드 노하우. 이런 말은 교과서에는 적혀 있지 않다. 즉 JOIN을 사용하지마라 라는 노하우는 실전이다.

한편, 역 인덱스의 스코어를 구하는 등의 작업은 고전적인 이론(벡터공간모델)을 사용하면 매우 간단히 할 수 있다. 이런건 교과서에 적혀있다.

대규모 웹 애플리케이션에 있어서 이론과 실전

1️⃣대규모 웹 애플리케이션을 개발, 운용하려고 하면 이론과 실전 사이에서 균형을 잘 맞춰야 한다.

• 이론을 너무 추구해서 지식만 갖추면 → 구현하기 위한 배드 노하우가 부족하고

• 반대로 배드 노하우만 알고 있으면 → 대규모 데이터가 눈앞에 나타났을 때 ‘어떻게 처리 해야할 지’ 모르는 상태가 된다.

2️⃣또 하나 중요한 것은 하고자 하는 것을 컴퓨터의 문제로 전환해서 해결하는 길을 찾을 수 있는지 여부

키워드로 자동 링크 하고 싶다 → Double Array Trie를 만들어서 Common Prefix Search라는 알고리즘을 적용시켜 주면 잘 해결된다.

만약 키워드로 자동링크 하고 싶다라는 실현하고자 하는 것만 머릿속에 있다면 어떤 방법이 좋은지 쉽게 떠올릴 수 없다. 알고리즘/데이터 구조라는 배경 지식을 통해 어떤 게 가능한 지를 어느 정도 머릿속에 넣어두는 것이 중요.