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

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

---

알고리즘 실용화

가까운 예로 보는 이론, 연구의 실전 투입

• 속도를 중시하는 프로그램을 작성할 경우에 알고리즘과 데이터 구조의 선택은 중요하다. 이 때 대상이 되는 데이터가 크면 클수록 선택에 따른 차이가 현저해진다
• 알고리즘을 선택의 중요성과 알고리즘이 제품으로 만들어내기까지 어떤 과정을 거치는지 공부한다

알고리즘과 평가

| 데이터 규모와 계산량 차이

• 1000개의 데이터를 탐색할 때 선형탐색은 O(n), 이분탐색은 O(logn)이며 탐색 횟수의 최댓값은 각각 1000, 10 이다
• 탐색 횟수는 계산량이며 일반적으로 계산량이 적을수록 속도가 빠르다 그리고 데이터 건수가 커짐에 따라 차이가 심해진다
• 계산량이 크면 병목이 발생할 수 있으므로 그 지점을 해소하려면 작은 계산량을 가진 알고리즘을 사용해야한다

| 알고리즘이란

• 사전적 의미는 다음과 같다

어떤 값 또는 값의 집합을 입력으로 하고 어떤 값 또는 값의 집합을 출력으로 하는 명확하게 정의된 계산 절차이다 

• 즉 적당한 값을 입력하면 명확하게 정의된 계산절차에 따라 값이 출력으로 반환된다는 것이 알고리즘이다
• 넓은 의미로는 도메인 로직, 처리에 관해서 얘기할 수 있고 좁은 의미에 대해서는 명확하게 정의된 계산문제에 대해 정의된 계산절차를 수행하는 것으로 인식된다
• 7장에서 다루는 알고리즘은 모두 좁은 의미에 대한 알고리즘이다

| 알고리즘을 배우는 의의

컴퓨터의 자원은 유한, 엔지니어의 공통 언어

• CPU, 메모리 자원은 유한하므로 알고리즘에 대해 배우는 것은 중요하다(유한한 자원으로 문제를 해결)
• 디자인 패턴과 마찬가지로 엔지니어에게 공통언어이다(알고리즘명으로 빠른 의사소통 가능)
• 새로운 문제에 대처할 수 있다

ex) 베이지안 필터를 알면 데이터를 자동분류하는 프로그램(ex 스팸메일 필터)을 작성할 수 있다
ex2) 수억건의 레코드를 수 MB로 저장할 수 있는 데이터 구조가 있다면 프로그램을 부담없이 배포할 수 있다 

| 알고리즘 평가 - order 표기

• Order 표기는 알고리즘 입력 크기가 n일 대 대략 얼마정도의 계산량이 소요된다라는 것을 표기하는 기법이다

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O (n^3) <...< O(n^k) < O(2^n)

• n이 클 경우 실질적으로 실용성을 띄는 것은 O(nlogn)부근이고, 그 이상은 계산이 안끝나는 느낌을 주는 경우가 있다
• O(logn)은 O(n)에 비해 상당히 빠르고, O(n) 과 O(nlogn) 사이에는 그다지 차이가 없고 O(n), O(n^2)은 계산이 끝나고 끝나지 않는 정도의 격차가 있다
• 하지만 대상이 되는 계산에 따라 또 다르다(정렬은 O(nlogn) 보다 빠를 수 없다는 것이 증명돼있으므로 O(nlogn)이면 빠른 것이다)
• 계산량은 시간 뿐만 아니라 공간적인 양에서도 사용되며 메모리 사용량을 논할 때도 Order 표기를 사용한다
• 계산량이 지수적으로 증가하면 데이터량이 적어도 계산량이 많은 반면 지수의 역 대수적으로 증가하면(O(logn)) 데이터량이 커져도 적은 계산량으로 문제를 해결할 수 있다

| 알고리즘과 데이터 구조 - 뗄레야 뗄 수 없는 관계

• 데이터구조는 배열, 트리구조와 같이 대상이 데이터를 저장 또는 표현하기 위한 구조를 말한다
• 알고리즘에서 자주 사용하는 조작에 맞춰 데이터 구조를 선택할 필요가 있다

ex) 트리구조로 데이터를 저장하면 탐색 처리를 단순화해 계산량을 줄일 수 있다 

| 계산량과 상수항 - 역시 측정이 중요

• Order 표기는 상수항을 무시한다
• 하지만 복잡한 구현이 되면 상수항을 무시할 수 없는데, 구현이 복잡하지 않더라도 캐시에 올리기 쉬운지, 분기 예측이 발생하지 않는지 등 계산량의 구조적인 특성에 의전하는 형태로 상수항에서 차이가 많이 나는 경우도 많다

ex) 정렬 알고리즘은 O(nlogn)이 하한이여서 O(nlogn)을 달성하는 알고리즘은 여러개다
하지만 같은 O(nlogn)이여도 일반적으로는 퀵 정렬이 가장 빠르다 
이유는 퀵정렬 특성상 CPU 캐시를 사용하기 쉽다는 장점이 있어서 -> 상수항이 빠르다는 것 

• Order 표기는 알고리즘을 비교할 때는 편리하지만 구현을 포함해서 생각할 때 그게 전부는 아니라는 것이다
• 상수항은 어떻게 구현하느냐에 의존하는 경우가 많아서 이를 줄이기 위해서는 구현에 노력을 기울여야한다
• 하지만 상수항을 줄이기 위해 처음부터 최적화를 수행하는 것은 잘못된 방침이다

ex) O(n^2)을 노력해서 상수항을 줄이는 것보다 O(nlogn)인 알고리즘으로 대체하는 것이 훨씬 이득
-> 결국 측정이 중요하다는 것이다 

• 알고리즘을 개선해야 할 지, 상수항을 줄여서 개선해야 할 지, 물리적 리소스를 확보하기 위해 하드웨어를 교환해 성능을 개선해야 할 지 측정을 통해 알아본다

| 알고리즘의 실제 활용- 단순한게 더 나을수도?

• 고도의 알고리즘이 반드시 최고의 해법인 것은 아니고, 고전적 알고리즘이 좋을 수도 있다

| 하테나 북마크 Firefox 확장 기능인 검색기능에서의 시행착오

• 하테나에서는 브라우저와 하테나 북마크를 통합해서 사용할 수 있는 firefox 확장프로그램을 제공했다
• 이 확장 기능에는 과거에 사용자 본인이 북마크한 데이터를 증분 검색할 수 있는 기능이 있었다

- 증분검색이라면 검색도 상당한 빈도로 발생하고 클라이언트에서만 계산되니 계산량을 적게 가져가야 한다고 판단했음 또 데이터 량이 사람에 따라서는 1만건 이상 됨
-> Suffix Array(텍스트 데이터 등을 고속으로 검색하기 위한 구조, 탐색은 빠르지만 미리 전처리를 거친 데이터 구조를 만들어야 하고 전처리 시간이 상당함)를 사용하겠다고 판단
-> IS법(선형시간에 Suffix Array 정렬을 마치는 알고리즘)을 Javascript를 이용해 구현했지만 만족스럽지 않음 
-> 속도가 나도 전처리시간에는 시간이 걸리고, 사용자가 북마크를 할 때마다 전처리를 수행하도록 하면 머신에 부하가 많이 걸림 
-> Suffix Array를 버리고 Firefox 확장기능이 내부에 가지고 있는 SQLite에 SQL로 like에 의한 부분일치 검색(선형탐색)을 하도록 함 
-> 오히려 속도가 개선된 것을 확인할 수 있었다

• 예측과 측정이 중요하다는 것과, 때에 따라서는 명쾌하게 단순한 구현을 시도해보는 것이 좋다는 것이다
• 대규모 데이터를 상정한 경우에는 최적화도 중요하지만 데이터 건수가 작은 경우에는 최적화 의미가 없다
• 데이터 건수가 '적다'는 것을 사람의 직감으로 추측하는 것은 좋지 않다

| 실제 사례를 보고 실전 감각 익히기

데이터 압축과 속도, 전체적인 처리량을 높이기 위한 방식

• 큰 파일을 압축시킬때는 머신파워를 사용하기 때문에 압축->무겁다 -> 느리다라고 생각할 수 있다
• 처리량 관점에서는 다루는 데이터를 압축해두는 편이 빠른 경우가 많다 (CPU에는 부담이 되지만 I/O 대기를 줄일 수 있다)
  ex) Http deflate 압축 통신 등

하테나 다이어리의 키워드 링크

| 키워드 링크란?

• 블로그를 작성하면 일부 키워드에 링크가 자동으로 걸리고, 그 링크는 키워드를 설명하는 페이지로 이동시킨다(링크 대상이 되는 키워드는 하테나 키워드에 사용자가 등록한 키워드들)
• 즉 특정 키워드를 HTML anchor 태그로 치환하는 것

| 최초 구현 및 문제 발생

• 처음에는 사전 내에 포함된 모든 단어를 OR 조건으로 잇는 정규표현을 만들어 사용했다
• 키워드가 적을 때에는 문제가 발생하지 않았지만, 키워드 수가 많아짐에 따라 정규 표현 처리에 시간이 걸리는 문제가 발생했다

1. 정규 표현 컴파일 처리
- 미리 정규표현을 만들어서 메모리나 디스크 상에 저장(캐싱)해둠으로써 회피할 수 있었다
2. 정규 표현 패턴 매칭 처리
- 2에 대해서는 처음에는 키워드 링크가 완료된 본문 텍스트를 캐싱하는 식으로 회피할 수 있었다 
- 하지만 새로 추가된 키워드를 키워드 링크에 반영시키기 위해서는 일정 시간에 캐시를 다시 구축할 필요가 있음
- 또 블로그 특성상 대부분을 차지하는 그다지 액세스가 없는 블로그에서는 캐시가 효과를 나타내기 어려움 등의 근본적인 해결에는 이르지 못함 

| 패턴 매칭에 의한 키워드 링크의 문제점

• 키워드 어휘수가 10만개가 넘어가고 하테나 다이어리 액세수가 늘어남에 따라 키워드 링크 처리 횟수도 늘어나 시스템이 혹사당하는 상태에 이르게 됨
• 링크 계산시간이 걸리는 문제의 원인은 정규표현 알고리즘이다
• 정규표현은 패턴매칭 구현에 오토마톤을 사용하고 있고 Perl의 정규표현 구현에는 NFA가 이용됨
• NFA는 패턴매칭을 앞에서부터 입력값을 살펴가면서 매칭에 실패하면 다음 단어를 시도하고 또 실패하면 그 다음 단어를 시도하는 단순한 방법으로 처리한다
  -> 키워드 갯수에 비례하는 계산량이 소요된다

| 정규표현 -> Trie (매칭 구현 변경)

• 계산량 문제를 해결하기 위해 정규표현을 기반으로 한 방법에서 Trie를 사용한 매칭 구현으로 변경을 했다
• Trie는 트리구조의 일종인 데이터 구조로, 탐색 대상 데이터의 공통 접두사를 모아서 트리구조를 이루는 것이 특징이다
  
• 입력문서를 Trie에 입력한 다음 엣지를 순회하면서 종단이 발견되면 해당 단어가 있는 것으로 간주하는 것이다
• 공통 접두사는 단 한 번 탐색으로 마칠 수 있게 된다

| AC 법 - Trie에 의한 매칭을 더 빠르게

• 실제로 개선할 때는 Aho-Corasick(AC) 법을 사용했다
• 사전 내에서 패턴매칭을 수행하는 오토마톤을 구축하고 입력 테스트에 대해 선형 계산 시간을 실현한다 -> 계산량이 사전 크기에 의존하지 않는 빠른 방법
• AC법은 Trie에서 패턴 매칭으로 매칭이 진행되다가 도중에 실패했을 때 되돌아오는 길의 엣지를 다시 Trie 에 추가한 데이터 구조를 사용하는 방법이다

| Regexp:: List로의 치환

• AC 법을 직접 구현한 라이브러리를 사용하다 나중에는 Regexp::List라는 라이브러리로 치환했음
• Trie에 최적화된 정규표현으로 변환하는게 이 라이브러리
• 계산량이 줄어들고 정규표현으로 사용할 수 있다는 장점이 있다 -> 정규표현의 옵션 조합, 언어적인 기능을 조합할 수 있어 유연성이 있다

| 키워드 링크 구현, 변이 및 고찰

• 심플한 구현이 주효할 때도 있다(공수 적고 유연성 풍부)
• 데이터가 커질 때는 본질적인 해결책이 필요하다

하테나 북마크의 기사 분류

• 하테나 북마크에 새로운 기사를 작성하면 북마크의 시스템은 해당 기사를 HTTP로 얻어서 본문 텍스트의 내용으로부터 분류해서 카테고리를 판정한다

| 베이지안 필터에 의한 케테고리 판정

• 스팸 필터 등에 사용된다

• 텍스트 문서 등을 입력으로 받아들이고 거기에 나이브 베이즈라는 알고리즘을 적용해서 확률적으로 해당 문서가 어느 카테고리에 속하는지를 판정하는 프로그램이다

• 미지의 문서의 카테고리 판정을 수행함에 있어서 과거에 분류가 끝난 데이터의 통계정보로부터 판정을 수행한다는 점이 특징(정해 데이터를 주고 프로그램 학습을 시킴, 기계 학습)

• 데이터가 많을수록 정밀도가 향상되는 경우가 드물지 않다

  | 대규모 데이터와 웹서비스- The google way of Science

• 구글에 검색을 잘못 했을 경우 '~~를 찾으려고 하셨나요'라고 제대로 정정해주는 기능이 있다

• 이 기능은 과거에 사용자가 검색한 쿼리로그를 정해 데이터로 해서 '~~게 잘못 입력했을 경우 다시 검색한다'라고 학습을 시켜 정해 데이터를 제시하고 있는 듯하다

• 꼭 대량의 로그가 있어야 프로그램을 만드는 것은 아니고 스펠링 오류 수정 기능을 탑재해도 만들 수 있다(구글은 아니고 하테나 방식)

• 그 방식은 다음과 같이 이루어진다

1. 정해 데이터로 27만단어 정도의 하테나 키워드를 사전으로 사용한다
2. 사용자가 입력한 검색 쿼리와 사전 내의 어구 사이의 편집거리를 구해서 '오류 정도'를 정량화한다
   • 편집 거리는 동적계획법으로 해결할 수 있다(하테나에서는 Levenshtein 거리를 발전시킨 Jaro-Winkler 사용)
3. 일정한 오류 정도를 기준으로 사전 내에 있는 단어군을 정해 후보로 얻어낸다
   • 사전에는 엄청 많은 단어가 있고 이를 모두 비교하는 것 좋지 않기 때문에 사전의 n-gram 인덱스를 만들어두고 입력어구와의 bi-gram의 중복 정도만 높은 단어를 추출해낼 수 있는 데이터 구조를 사용한다
4. 3의 정해 후보를 하테나 북마크 기사에서의 단어 이용빈도를 기준으로 정해에 가까운 순으로 정렬한다
   • 가장 자주 출현이라는 기준에는 DF(Document Frequency)를 사용한다(휴리스틱 기법)
5. 가장 이용 빈도가 높은 단어를 정해로 간주하고 이용자에게 제시한다
   • Jaro-Winkler과 DF를 적당히 곱해서 스코어로 만든 다음 일정 스코어 이상을 획득한 것을 표시한다

• 하지만 구글의 방식에 비해 하테나의 방식은 약간의 덤 정도의 개선에 불과하다(살아있는 성해 바탕으로 산출하는 것이 좋다)

| 베이지안 필터의 원리

• 베이지안 필터의 핵심은 나이브 베이즈라는 알고리즘이다
• 나이브 베이즈는 특정 문서 D가 주어졌을 때 이 문서가 어떤 카테고리 C에 속하는게 가장 그럴듯한가를 구하는 문제이다
  (문제 D가 주어졌을 때 카테고리 C인 조건부 확률을 구하는 문제, P(C|D))
• 여러 카테고리 중에 이 확률이 가장 높은 값을 나타낸 C가 최종적으로 선택되는 카테고리가 된다

P(C|D)를 직접 구하는 것은 어렵지만 여러가지 변형식을 이용해 구할 수 있다
P(C|D) = P(D|C) * P(C) / P(D)

우리가 원하는 것은 구체적인 확률값이 아니라 각 카테고리를 비교해 어떤 확률이 가장 높은 지를 나타내는 순위이다 
-P(D)는 문서가 등장할 확률이므로 모든 문서에 대해 1이다 
-P(C)는 특정 카테고리가 출현할 확률이므로 학습데이터 중 여러 데이터가 어떤 카테고리로 분류되었는지 그 횟수를 저장해두면 나중에 계산할 수 있다
-P(D|C)는 문서 D라는 것은 임의의 단어 W가 연속해서 출현하는 것으로 간주하고  P(D|C) -> P(W1|C)*P(W2|C)....P(Wn|C)로 근사해서 알 수 있다 
- 문서 D를 단어로 분할해두고 그 단어마다 어떤 카테고리로 분류됐는지 그 횟수를 보존해두면 P(D|C)를 구할 수 있다 

• 즉 나이브 베이즈에서는 정해 데이터가 주어지면 해당 정해 데이터가 사용된 횟수나 단어 출현횟수와 같이 간단한 수치만 저장해두면 나중에 확률만 계산하면 카테고리를 추정할 수 있다는 것이다 -> 그 밖의 데이터는 전부 파괴해도 상관 X
• 그래서 구현 자체는 쉬운 편이다
• 구현은 다음 과정으로 이루어졌다

- 분류 엔진은 C++로 개발(이 엔진을 서버화)
- 서버와 통신해서 결과를 얻는 Perl 클라이언트를 작성하고 웹 애플리케이션에서 호출 
- 학습 데이터를 정기적으로 백업할 수 있도록 C++ 엔진에 데이터 덤프/로드 기능 추가 
- 학습 데이터 1000건 수작업 준비 
- 바람직한 정밀도가 나오는지 추적하기 위한 통계 구조 구축. 자동 페일 오버는 공수가 많이 소요되므로 백업에서 로드할 수 있는 정도로 타협
- 웹 애플리케이션에 사용자 인터페이스를 마련한다 

• 알고리즘 구현은 쉽지만 실제 실무 면에서는 고려해야 할 점이 많다 특히 서버를 별도로 준비하는 경우

| 수비, 공격자세- 기사 분류 구현으로부터 고찰

• 데이터 정렬 등의 알고리즘은 발생하는 문제를 얼마나 잘 받아들이느냐의 수비적인 자세로 사용되는 알고리즘
• 기계학습, 패턴인식 등은 적극적으로 대규모 데이터를 응용하고 결과에 따라 애플리케이션에 부가적인 가치를 추가한다는 점에서 공격적인 자세로 사용되는 알고리즘
• 확실한것은 알고리즘을 알고 있어야 둘 중 하나라도 할 수 있다는 점이다