대규모 서비스를 지탱하는 기술 (7)

ordilov / 2022. 3. 18

속도를 중요시하는 프로그램인 경우 데이터가 클수록 알고리즘의 영향을 많이 받습니다.

먼저 알고리즘이란 적당한 값을 입력하면 명확하게 정의된 계산절차에 따라 값이 출력으로 반환됩니다. 알고리즘이 필요한 이유는 CPU나 메모리등의 유한한 자원으로 시간내에 문제를 해결해야 하기 때문입니다. 알고리즘을 익혀야 하는 이유는 엔지니어에게 있어서 커뮤니케이션의 도구가 되고, 새로운 문제의 해결책이 될 수 있습니다.

알고리즘과 자료구조는 세트로 많이 논의 되는데 알고리즘에 따라 데이터 구조를 선택할 필요가 있어서입니다. 예를 들어 탐색구조에서는 트리로 구현하는 경우 탐색을 단순화시킬 수 있어 계산량을 줄일 수 있습니다.

Order 표기법에서 상수항을 무시하지만 상수항에 따라 캐시에 올리기 쉬운지, 분기예측을 발생시키는지등 영향을 끼칩니다. 예를 들어 같은 O(n log n) 이더라도 정렬 알고리즘 중에선 퀵정렬이 빠르다고 합니다. 그 이유는 특성상 CPU 캐시를 사용하기 쉬운데 이는 상수항이 빠르다는 예입니다.

실제로 운용에 있어서는 고도의 알고리즘보다 단순한 알고리즘이 효과적일 수 있습니다. 특히 탐색 자체는 빠르더라도 데이터 구조 전처리릉 위해 시간이 필요한 경우 단순한 탐색 알고리즘이 더 유용할 수 있습니다. 컴퓨터의 성능 향상으로 탐색속도는 생각보다 유의미하게 나지 않을지 모릅니다.

키워드 링크는 특정 키워드에 매칭되는 부분을 링크로 치환시켜줍니다. 이때 키워드 매칭 시 링크로 바꿀 때 단순하게 구현하면 정규표현식으로 교체 가능합니다. 키워드가 늘어가면서 속도가 내려가자 미리 자주 쓰이는 정규표현을 만들어서 캐싱 처리를 하려했지만 효과가 부족했습니다.

특히 정규표현식에서 (foo | bar | baz) 을 매칭 시키는 경우 각 단어마다 한 글자씩 비교하며 비교합니다. 즉 키워드의 크기와 개수에 비례해서 계산량이 증가합니다.

Trie는 트리 구조의 일종으로 공통 접두사를 이용해 부분 문자열을 관리합니다. Trie를 이용해 비교하면 부분 문자열을 비교하며 내려가 단순 비교보다 더 빠르게 매칭을 확인할 수 있습니다.

베이지안 필터는 나이브 베이즈 알고리즘을 적용해서 해당 문서가 어느 카테고리에 해당하는지 분류합니다. 분류를 위해서는 정답에 해당하는 데이터 셋이 필요하며 이를 학습시켜두면 새로운 데이터를 학습 결과에 따라 분류합니다. 이를 기계학습이라고 하며 패턴에 따라 분리하기에 패턴 인식 분야이기도 합니다.

대규모 데이터를 사용한다면 그만큼 운용이 어려워지지만 학습 데이터의 정밀성이 올라갈 수 있습니다. 그리고 그 결과로 추천 서비스들을 제공할 수 있습니다.

구글 검색엔진에서도 조금 잘못된 글자를 검색하더라도 비슷한 결과물을 보여줍니다. 이는 이렇게 잘못 검색한 사람이 다시 검색할 때 이렇게 하더라 하는 데이터에 의한 방법이기도 합니다.