개발공부 기록지

목차

• 엔터프라이즈 vs. 웹 서비스
  • 웹 서비스의 인프라
  • 소단원
• 클라우드 vs. 자체 구축 인프라
  • 클라우드의 장단점
  • 자체구축 인프라의 장점
  • 하테나에서 클라우드 서비스 사용 예시

엔터프라이즈 vs. 웹 서비스

엔터프라이즈 vs 웹 서비스

신뢰성

엔터프라이즈

• 장애가 발생해서 데이터가 없어지거나 하면 실제로 돈이 사라지기도 한다.
• 만일 장애가 발생되면 피해자로부터 손해배상 청구를 받게 되거나 구해야하는 사람 목숨을 구하지 못하는 등의 사태도 발생할 수 있다.

웹 서비스

• 높은 레벨의 신뢰성이 요구 되지 않는다.

웹 서비스의 인프라

웹 서비스의 인프라에서 중요시되는 것

1. 저비용 고효율 - 100% 신뢰성 목표로 하지 않고 비용을 낮추어 효율을 높이는 방향
2. 확장성이나 응답성 - 서비스의 성장속도를 모를때 장래를 위한 확장성, 사용자 경험(UX)를 위한 서비스의 응답성을 위한 설계
3. 유연성 - 서비스 사양이 바뀌는 경우에 유연하게 대응할 수있는 인프라를 위한 설계
4. 개발속도를 중시한 인프라 - 서비스에 대해 기동성 있게 리소스를 제공
   • 앱 배포를 가능한 한 간편하게, 또한 배포할 때 마침 처리 중인 요청에 영향이 없도록 인프라 구성
   • 필요한 서버를 즉시 추가할수 있도록 인프라 구성
   • 배포한 코드에 문제가 발견됐을 때에 곧바로 이전 상태로 돌아갈 수 있도록 인프라 구성

클라우드 vs.  자체 구축 인프라

클라우드의 장단점

클라우드 컴퓨팅?

• 인터넷을 통해 원격으로 컴퓨팅 자원 및 서비스를 제공하는 컴퓨팅 기술 -Samsung SDS-
• IT 리소스를 인터넷을 통해 온디맨드로 제공하고 사용한 만큼만 비용을 지불하는 것 - Amazon Web Service-
• 컴퓨팅 리소스(스토리지 및 인프라)를 인터넷을 통해 서비스로 사용할 수 있는 주문형 서비스 - Google Cloud -
• 인터넷(“클라우드”)을 통해 서버, 스토리지, 데이터베이스, 네트워킹, 소프트웨어, 분석, 인텔리전스 등의 컴퓨팅 서비스를 제공하는 것 - Microsoft Azure - 

장점

• 확장의 유연성

단점

• 획일적인 호스트 사양
• 때때로 멈춤 현상 발생

자체 구축 인프라의 장점

장점

• 서버 하드웨어 구성을 유연하게 구성할 수 있다. 
• 서비스로부터의 요청에 유연하게 대응할 수 있다. 
• 병목현상을 제어할 수 있다.

자체 구축 인프라의 기술 모델

• 수직통합 모델 - 물리적 계층부터 서비스 설계까지 한 기업에서 구축하는 모델 ( Amazon, Google)
• 수평분산 모델 - 각 계층마다 다른 기업이 제공하는 것으로 각각이 모여 전체 시스템이 구축되는 모델

하테나에서 클라우드 서비스 사용 예시

서비스 활용 현황

• 현재 활용 중인 서비스: AWS (Amazon Web Services)
• 주요 서비스: Amazon CloudFront
  • 용도: 미디어 파일 전송을 위한 CDN (Content Delivery Network)
• 자체 구축 인프라 중심 운영: 애플리케이션 및 DB의 클라우드 저장소 본격 도입은 보류

클라우드 컴퓨팅의 적합성

• 적합한 경우: 소규모 서비스, 트라이얼 용도
• 혜택: 비용 효율성, 유연한 확장성
• 한계: 대규모 시스템의 경우 확장성 문제 발생 가능

Amazon EC2의 확장성 이슈

• EC2 확장성: 대규모 시스템 지원에 한계가 존재할 수 있음
  • 대규모 서비스 예시: Facebook, Google 수준의 시스템
• 소규모 서비스에는 EC2가 적합하지만, 대규모 서비스는 자체 구축이 더 유리

목차

• 강의 24 : 전문기술의 응용범위
  • 하테나의 데이터로 검색엔진 만들기
  • 하테나 다이어리의 전문 검색
  • 하테나 북마크의 전문 검색
• 강의 25 : 검색 시스템의 아키텍처
  • 검색 시스템이 완성되기까지
  • 다양한 검색엔진
  • 전문 검색의 종류
• 강의 26 : 검색엔진의 내부구조
  • 역 인덱스의 구조- Dictionary+Postings 
  • Dictionary 만드는 법: 역 인덱스 작성법 #1
  • 지금까지의 내용정리
  • Postings 작성법: 역 인덱스 작성법 #2
  • Scoring에 대한 보증

【 강의 24 】 전문기술의 응용범위

❏  하테나의 데이터로 검색엔진 만들기

검색엔진을 만들 때 중요한 요소 중 하나인 역 인덱스( inverted index)에 대한 설명

역 인덱스의 두 가지 기본요소

• Dictionary
• Postings

❏  하테나 다이어리의 전문 검색 - 검색 서비스 이외에 검색 시스템 이용

‣ RDB 로 처리 -확장성 측면에서 문제

구현 방식

1. 유저가 글을 작성하면 해당 글에 포함되어 있는 키워드를 전부 추출
2. 이 단어들과 블로그의 연관성을 데이터베이스의 레코드로서 저장

>> 단어 "perl" 을 검색하면 해당 단어가 포함된 블로그 목록을 표시

<문제 > 레코드 수가 많아지면서 확장성 측면에서 많은 제한 발생 

‣ 검색기술의 응용

"포함하는 블로그" : 특정 단어를 포함하는 블로그 검색 

• 검색엔진기술을 응용하여 구현 
• 다이어리의 사양에 특화시킨 방법으로 검색속도 향상
  • 불필요한 결과정렬 방식을 제외:  날짜순으로만 정렬
  • 각 글의 id 를 하테나 다이어리의 사양에 특화시킨 방법으로 저장 

❏ 하테나 북마크의 전문 검색 - 세세한 요구를 만족시키는 시스템

"마이 북마크 검색" : 각 개인이 북마크한 개인 데이터로부터 검색하는 시스템

• 각 사용자가 북마크를 하는 타이밍에 각 사용자별로 검색 인덱스 구현 및 갱신
• 직접 구현 함으로써 세세한 요구사항에 대응

【 강의 25 】 검색 시스템의 아키텍처

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

‣ 검색 시스템의 여섯 단계 

1. 크롤링
2. 저장
3. 인덱싱
4. 검색
5. 스코어링
6. 결과표시

각 단계별 과제

1. 대상의 문서를 가져올 플랫폼을 정해서 웹 크롤러를 만들어서 대량의 문서를 가져오는 작업
2. 대량의 문서를 어떻게 저장할 것인가 (하나의 DB에 저장하면 해당 DB에 문제가 생기면 복구 불가 → 분산 DB에 저장해야하는 문제)
3. 가져온 문서로 부터 인덱스(고속으로 검색하기 위한 구조)를 구축
4. 검색 결과를 어떻게 정열할 것인가, 어떤 순서로 보여줄 것인가

❏  다양한 검색엔진

‣ 오픈소스

• grep
• Namazu :  http://www.namazu.org/index.html.en
• Hyper Estraier : https://dbmx.net/hyperestraier/
• Apache Lucene : https://lucene.apache.org/

등 다양한 오픈소스가 있다. 

❏  전문 검색의 종류

‣ grep 형 

• 검색 대상 문서를 처음부터 전부 읽는다 O(mn) text: m, word: n 
  • 계산량을 개선한 방법 : KMP(Knuth-Morris-Pratt, O(m + n)) BM(Boyer-Moore, 최악O(mn), 최선O(n/m)) 
• 즉시성이 좋고, 검색누락이 없으며, 병렬화나 쿼리 확장이 용이(쿼리에 정규표현 사용)
  • UNIX 에서 유용한 명령어
• 대규모 환경에서 구현하기에는 무리가 있는 방식

‣ Suffix 형

• 문서를 검색 가능한 형태로 보유 - 전부 메모리에 올릴 수 있는 형태
• 데이터 구조: Tire, Suffix Array, Suffix Tree
• 이론적으로는 가능
• 정보량이 크고 구현하기 어려움

‣ 역 인덱스형 (주류)

• 실제 시스템에서 많이 채택되는 방식( Google)
• 단어(term)와 문서를 연관짓는 방식
• 즉시성 측면에서 뛰나지 못함 → 검색누락 발생 가능
  • grep 처럼 문서가 변경되면 바로 검색결과도 바뀌는 방식은 어려움

【 강의 26 】 검색엔진의 내부구조

❏  역 인덱스의 구조 - Dictionary + Postings

문서를 인덱스화 한다? → 아래의 그림을 말하는 것

아래의 그림에서 2번을 참고하면 각 단어에 연결되어있는 문서 번호가 있다.

Dictionary? 좌측에 있는 단어(term)의 집합

Postings? 우측에 있는 번호들처럼 각 단어를 포함하고 있는 문서는 몇 번인지를 나타내는 것

(예) Dictionary 내에 있는  term: '하테나' 를 포함하고 있는 Postings 내에는 1, 3, 4 가 있다.

❏  Dictionary 만드는 법

문장에 있는 단어를 term으로 추출한다.

단어를 추출할때 사용가능한 방식들

• 사전 이용( Wikipedia)
• 형태소 분석
• n-gram 기법
• AC (Aho-Corasick) 법 
  *Trie 에서 패턴 매칭으로 매칭이 진행되다가 도중에 실패했을 경우, 되돌아오는 길의 엣지를 다시 Trie에 추가한 데이터 구조를 사용한 방법 (p175, 20강)

‣ 언어의 단어를 term 으로 다루기

• 사전과 AC법을 이용하는 방법
• 형태소 분석을 통하여 단어찾는 법 - 검색 누락 발생 가능 
  • stemming 이나 Lemmatizer 등을 이용하여 부분적 극복가능

‣ n-gram을 term 으로 다루기

• 텍스트를 n 자씩 잘라내는 방식 : "하테나 다이어리" -(2-gram)-> 하테 /테나 /나다 /다이 /이어 /어리 
• 쿼리도 동일한 규칙으로 분할해야한다.
• 원하지 않는 결과가 나올 수도 있다.
  • 東京都 문제 :   
    • 東京都 -(2-gram)->  東京 / 京都 
    • 문서: "東京 타워와 京都타워" 라는 문서를 인덱싱했을때. 이 문서가  東京都로 검색했을때 검색된다.

‣ 검색 시스템 평가와 Recall/Precision

재현률(Recall)/ 적합률(Precision)을 이용하여 검색 시스템에 특정 쿼리를 입력했을 때의 성능을 정량화 가능

• Recall : 검색 결과에 쿼리를 포함한 문서가 얼마만큼 포함되었는지를 의미 ( 올바른 결과의 수 / 적합한 결과 총수)
• Precision : 검색 결과가 얼마나 정확한 결과가 들어 있는지를 의미 ( 올바른 결과의 수 / 반환한 결과 총수)

n-gram 방식은 검색누락은 발생 안하지만 원하지는 않는 결과가 반환 → Recall이 우선

형태소 방식은 검색이 안되는 것도 있지만 원하지는 않는 결과가 반환되지 않음 → Precision 이 우선

팁

타이틀, 코멘트, URL을 대상으로 검색할 때는 n-gram 사용

본문 검색에는 단어기반을 사용

❏  지금까지의 정리

검색엔진 중에 가장 많이 사용되는 방식은 역 인덱스 방식

역 인덱스 방식 : Dictionary + Postings 구조

Dictionary 를 만드는 방식에는 n-gram 과 형태소 분석을 기반으로 하는 방법이 있다.

❏  Postings 작성법

term 이 해당 문서 내에 출현 위치도 저장하는 경우 ( Full Inverted Index)

• 스피닛을 뽑아낼때 이 단어가 문장 내의 어디에 포함되어 있느지 바로 알수 있음
• 스코어링에도 도움
• 필터링에도 용이

문서 ID만을 저장하는 경우

• 정렬(오름차순/내림차순) → VB Code로 압축
• 어느 정도의 데이터의 압축률과 빠른 전개 성능
• 구조  term → 압축된 Postings List 
  • key-value 스토어에 적합

❏  Scoring 에 대한 보충

검색결과를 어떤 순서로 표시할 건지는 상당히 중요한 문제!!

예를 들어 Google은 문서의 중요성을 고려해서 랭킹을 매겨서 검색결과를 표시한다.

주요 알고리즘 : PageRank

PageRank + 검색어의 출현위치 + 이외 다양한 알리고리즘을 이용해여 문서의 중요성을 파악

문서의 중요도를 파악하는데 자주사용되는 알고리즘 TF/IDF 가 있다.

21 강 알고리즘과 평가 하테네 북마크의 기사 분류

기사 분류란?

새로 도착한 기사를 해당 기사의 내용을 기반으로 자동으로 해당 카테고리를 판정하여 분류하는 것

카테고리 판정을 위해 사용한 기술 : 베이지안 필터

- 나이브 베이즈에 근거한 카테고리 추정 : 문서 D 가 카테고리 C 에 속할 확률을 구하는 방식

이 알고리즘이 실용화되기까지 거친 작업

• 분류 엔진을 서버화
• 학습 데이터 정기적인 백업 구현
• 초기 학습 데이터를 수작업으로 준비
• 분류 엔지의 정밀도 추적을 위한 통계구조 작성
• 웹앱 인터페이스
• 등등

위의 과정에서 배울 점

• 기존 방법 익혀두기 : 기본적인 알고리즘을 익혀두어서 문제를 해결하기 위함
  • Tire 나 베이지안 필터 같은 것을 몰랐으면 문서를 자동으로 분류한다는 발상도 하기 힘듬
• 대용량 데이터에 맞서 알고리즘을 선택하고 이를 응용하는 것이 어떤 것인지 그 감각을 익힐 필요가 있음

* 대규모 데이터를 대상으로 한 알고리즘 실용화에 관련된 예

- 키워드 링크

최초 구현 방식

1. 정규표현을 컴파일하는 처리

2. 정규표현에서 패턴을 매칭하는처리

문제점

데이터가 늘어날 수록 키워드의 개수가 증가 -> 키워드 캐수에 비례하는 계산량이 소요

해결방안

Tire(트라이)를 사용한 매칭 구현으로 변경

Tire? 선택

트리구조의 일조인 데이터 구조

• 탐색대상 데이터의 공통 접두사를 모아서 트리구조를 이루는게 그 특징
• 문자열 집합을 트리구조로 해서 효율적으로 저장

AC 법 - Tire에 의한 매칭을 더욱 빠르게하는 방법

Aho-Corasick(AC 법)

• Tire 에서의 패턴매칭으로 매칭이 진행되다가 도중에 실패했을 경우, 되돌아오는 길의 엣지를 다시 Tire에 추가한 데이터 구조를 사용하는 방법
• 계산량이 사전 크기에 의존하지 않는 빠른 방법
• 사전 내에서 패턴 매칭을 수행하는 오토마톤을 구축하고 입력 텍스트에 대해 선형 계산 시간을 실현

Regexp::List  로 변경

Perl 정규표현 라이브러리로 Tire에 의해 최적화된 정규표현으로 변환시키는 라이브러리

• 계산량이 줄어든다.
• 정규표현으로 사용할 수 있다.(유연성)

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

변이: 정규표현 → AC 법 → Refexp::List

고찰

• 심플한 구현이 주효했지만, 데이터가 커지면서 계산량 문제가 발생
• 선택한 알고리즘의 근본적인 문제점을 해결하기 위하여 한 알고리즘 평가를 통해 계산량의 관점에서 문제를 해결

처음부터 최적의 구현을 사용하는 것이 반드시 옳지는 않다.

데이터가 대규모가 될 시기를 대비해서 본질적인 문제의 해결방법을 머릿속에 넣어두어야 한다.

19 강 알고리즘과 평가

알고리즘이란?

Algorithm 은 어떤 값 또는 값의 집합을 입력으로 하고 어떤 값 또는 값의 집합을 출력으로 하는,
명확하게 정의된(well-defined) 계산 절차다.

넓은 의미의 알고리즘

• 특정 문제를 해결하기 위한 일반적인 절차나 규칙의 모음
  (예시: 도메인 로직의 처리의 흐름, DB에서 레코드를 얻ㅇ어서 적절하게 처리한 후 결과를 출력하는 것)

좁은 의미의 알고리즘

• 명확하게 정의된 계산문제에 대해 정의된 계산 절차를 수행하는 것 (주로 책에서 다루는 내용)

알고리즘을 배우는 의의

알고리즘은 엔지니어에게 공통언어 → 커뮤니케이션을 위해서 알아둘 필요가 있음

유한한 컴퓨터 자원을 효과적으로 활용

알고리즘을 이용하여 새로운 문제에 대처가능

알고리즘의 평가

아래로 갈수록 계산량이 많아진다. 

대규모 데이터를 대상으로 할 경우 O(n log n) 까지가 실용적이다.

계산량 개념 적용

• 시간 계산량(실행시간, 단계 횟수)
• 공간계산량 (메모리 사용량)

계산량과 상수항

계산량의 Order 표기에서는 "상수항" 을 무시한다.

상수항?

함수 호출, 함수로 부처 값을 반환하기 위한 처리, 일차변수를 확하는 처리, if 문으로 분기시키는 처리 등이 이에 해당

→ 실질적으로는  복잡해질 수록 상수항이 계산량에 영향을 미친다. 경우에 따라서 상수항을 줄이는 최적화도 필요하다.

최적화시 유의할 점

• 처음부터 상수항을 줄이는 최적화를 하지 않는다.
• 현재 프로그램에 무엇이 문제인지를 정확하게 파악 후 최적화 실행

개선시 문제 해결을 위해 규명해야할 사항

• 알고리즘을 교체해서 개선할 것인가
• 상수항을 줄여서 개선할 것인가
• 물리적으로 리소스가 부족하므로 하드웨어를 교환해서 성능을 개선 할것 인가

알고리즘의 실제 활용 → 예측과 측정이 중요

* 단순한 알고리즘이 더 나은 경우도 있다.

* 고전적인 알고리즘이 좋은 경우도 있다.

써드파티 소스를 잘 활용하자

정평이 난 알고리즘은 제 3자 이용하기 쉽도록 이미 구현된 소스가 공개되어 있는 경우가 많다.

하지만, 이러한 라이브러리를 바로 사용할 수가 없을 수도 있다.

해당 알고리즘이 어떻게 구현이 되어있는지 알아야 한다.

→ 우리가 원하는 사양으로 변경가능

→ 불필요한 구현을 줄여 성능, 유지보수, 테스트, 유연성, 자원 사용 등의 측면에서 다양한 문제를 방지가능