[SWA] System Design Warmup - 2 (작성중)

Architecture

🏛️

대규모 데이터를 처리하기 위한 시스템을 설계할 때에 고려해야할 사항들이 존재한다. 효율적이고 경제적인 시스템을 구축하기 위해서 이러한 개념을 잘 알고 있어야 한다. 이러한 핵심 구성 요소는 아래와 같다

  • CAP Theorem

  • PACELC Theorem

  • SQL vs NoSQL

  • Load Balancing

  • Caching

  • Data Partitioning

  • Redundancy & Replication

  • Indexing

  • Proxies

  • Long Polling vs WebSocket vs Server-Sent Event

  • Leader & Follower

  • Quorum

  • Heartbeat

  • Bloom Filter

  • Checksum

  • Consistent Hashing

**6. Data Partitioning **

데이터 파티셔닝은 큰 데이터베이스(DB)를 여러 작은 부분으로 나누는 기술로 우리가 흔히 사용하는 RDBMS뿐만 아니라 스키마와 같은 논리적인 구조를 가지는 데이터 저장소에서 사용 가능하다. Application의 관리성, 성능, 가용성 및 LB를 개선하기 위해 여러 서버에 걸쳐 DB / table을 분할한다. 데이터 파티셔닝을 수행하게 되면, 여러 서버에 나눠서 분포가 됨으로 scale-out을 통한 확장이 가능해 진다.

파티셔닝 방법

데이터를 여러개의 작은 단위로 분할하는 다양한 방법이 있다. 다음은 가장 많이 사용되는 세가지 방법이다.

  1. 수평분할 Horizontal Partitioning
    • 행row 단위로 다른 서버에 적재한다. 예를들어 rowId가 0~100의 레코드는 A라는 데이블에 저장되고 101~200의 레코드는 B라는 테이블에 저장되는 구조이다. 이러한 방식을 범위 기반 분할 range based partitioning 또는 데이터 샤딩 Data sharding이라고 부르기도 한다.
    • 이 접근 방식의 주요 문제는 분할에 사용되는 범위 값을 신중하게 선택하지 않으면 서버간 불균형이 발생한다는 것이다.
  2. 수직분할 Vertical Partitioning
    • 칼럼column 단위로 다른 서버에 적재한다. 예를들어 userId, userName, Address 와 같은 신상 정보는 A라는 테이블에 저장하고 friendsList는 B라는 테이블에, photos 는 C라는 테이블에 저장할 수 있다.
    • 이는 구현이 간단하고 application 영향도가 적다. 하지만 app이 증가하는 경우 기능별로 다시 파티셔닝을 해야할 수 있다는 점이다. (일반적으로 RDB는 100억건에 대한 데이터 쿼리를 할 수 없다.)
  3. 디렉토리 기반 분할 Directory Based Partitioning
    • 수평분할과 수직분할의 문제점을 해결하고자 고안된 방법으로, 느슨한 결합으로 파티션 스키마를 찾는 서비스를 별도로 제공함으로써 DB 접근을 추상화 하는 것이다. 특정 데이터의 위치를 찾기 위해 튜플 키와 DB서버간 맵핑 정보를 가지고 있는 디렉토리 서버에 쿼리를 하게 된다.
    • 추가적인 데이터 탐색 레이어가 있기 때문에 구성하는 DB를 확장하더라도 서비스가 접근하는데 무리가 없다.

데이터 분할 기준

  1. 키Key 또는 해시Hash 기반 파티셔닝
    • 저장하고 있는 일부 키 속성에 해시 함수를 적용하여 파티션 번호를 생성함. 이를 통해서 서버간 균일한 데이터 할당을 보장함.
    • 이 방식의 문제점은 맵핑되는 파티션의 번호가 서버 수에 의존됨으로(모듈러 연산을 통해 할당), 서버가 증가하거나 감소하면 데이터 재배포및 해시 맵핑 서비스를 바꿔야 한다는 것이다.
  2. 리스트List 파티셔닝
    • 파티션에 할당 할 수 있는 값의 목록이 할당되어, 새 레코드를 삽입할 때 키 값에 따라 파티션을 확인하여 저장됨.
    • 이 방식도 데이터 불균형을 일으킬 수 있으며, 서버 수 변경에 따라서 목록 값을 갱신해주어야 함
  3. 라운드로빈Round Robin 파티셔닝
    • 데이터를 균등하게 분배하는 가장 간단한 방법. 하지만 데이터 할당에 대한 규칙성이 모호함으로 데이터를 찾을 때 최적화가 이루어질 수 없다.
  4. 복합Composite 파티셔닝
    • 위 파티셔닝 방법 중 다수를 결합하여 새로운 방법을 만듬. 예를들어 먼저 리스트 분할을 수행하고 해시 기반 분할을 적용하여 해시 값들의 범위로 서버에 값들을 할당함.

데이터 파티셔닝의 문제점

데이터 파티셔닝이 적용된 DB에는 데이터 처리에 대한 제약이 존재한다. 이러한 제약의 대부분은 여러 테이블/동일 테이블에 여러 행에 대한 작업이 단일 서버에서 이루어지지 않기 때문에 발생한다.

  1. 조인 및 비정규화 : 한 서버에서 join 연산을 수행하는 것은 간단하지만 여러 서버에서 join 을 수행하는 것은 불가능한 경우가 많다. 따라서 이 경우 join 에 필요한 데이터에 대해 DB를 비정규화 처리하는 것이다. 하지만 또 이로 인해 데이터 불일치와 같은 부작용이 발생할 수 있다.
  2. 참조 무결성 : 파티션 된 DB에서 외래키foreign key와 같은 데이터 무결성 제약조건을 적용하는 것은 매우 어렵다. 만약 이를 제공하기 위해서는 application 레벨에서 이를 제공해줘야 한다.
  3. 리밸런싱 : 데이터 분포가 균등하지 않은 경우 데이터에 대한 리밸런싱을 수행해야 한다.

7. 인덱스 Index

DB의 성능을 향상시키기 위해서 인덱스는 가장 먼저 고려되야 하는 사항 중 하나이다. 특정 테이블에 대해 인덱스를 설정하는 것은 새로운 조건에 대한 임의접근Random access를 가능하게 하는 것이다. 인덱스를 설정하는 것은 하나 이상의 열column을 설정할 수 있으며, 내부적으로 설정한 열로 정렬되어 빠른 조회가 가능하다.

예시 . 도서관 데이터 베이스

도서관의 도서 정보를 저장하는 DB를 설계한다고 가정하자. 도서에 대한 스키마 정보는 일반적으로 책 제목, 작가, 주제 및 발행일 등 4개의 열로 구성된다. 가장 일반적인 도서 검색은 책 제목으로 검색하는 것과 작가 이름으로 검색하는 것일 것이다. 이러한 액세스 패턴은 구성해야 하는 인덱스 설정과 동일하다. 테이블에 있는 도서 정보의 레코드를 책 제목으로 정렬된 인덱스와, 작가로 정렬된 인덱스를 생성하게 된다.

인덱스의 개념은 대용량 저장소에서도 유사하게 고려된다. 인덱스를 사용한다는 것은 결국 더 적은 페이로드payload를 찾는 방식이다. 대용량 저장소는 일반적으로 데이터를 분산해 저장하고 있기 때문에, 데이터의 올바른 물리적 위치를 찾을 방법이 필요하게 된다. 인덱스는 이를 위해 필요하다.

인덱스로 인한 성능 저하

인덱스는 데이터 검색 속도를 높일 수 있지만 추가 적으로 관리해야 하는 키가 존재하기 때문에 데이터 write/update 속도가 느려지게 된다. 사용하고 있는 인덱스에 테이블을 추가하거나 기존 행을 업데이트 할 때 원본 테이블에 데이터를 저장하는 것 뿐만 아니라, 해당 테이블에 설정된 모든 인덱스에도 write/update가 이루어져야 하기 때문이다.

따라서 반드시 테이블에 불필요한 인덱스를 추가하는 것은 피해야 하며, 사용하지 않는 인덱스는 제거해야 한다.

정리하면 인덱스를 생성하는 것은 빠른 read를 위해서 데이터를 중복으로 관리하는 것이기 때문에 write/update작업에 대한 추가적인 연산이 필요하게 된다. 그러므로 적절한 trade-off로 각 서비스에 최적화를 해야 한다.

8. Proxy

프록시 서버는 client와 back-end 서버 사이의 중간 서버이다. client 는 웹 페이지, 파일, 연결 등과 같은 서비스를 요청하기 위해 proxy 서버를 사용한다. 간단히 말해서 proxy 서버는 다른 서버의 리소스를 요청하는 client 요청에 대한 중개자 역할을 하는 SW 또는 HW의 일부이다.

일반적으로 proxy 서버는 다음과 같은 기능을 수행 한다.

  • client 요청에 대한 필터링 (유효한 요청만 backend로 전달)
  • client 요청에 대한 변환 (header 추가/제거, 리소스 암호화/복호화, 리소스 압축 등)
  • backend 서버의 리소스 캐시로 부하 전파 방지

Proxy Server 타입

  1. Open Proxy (Forward Proxy)
    • Open Proxy는 인터넷 사용자가 접근가능한 프록시 서버
    • 일반적으로 같은 네트워크 그룹(ex. 폐쇄망)의 사용자에 대해서 인터넷 서비스를 수행하기 위해 사용된다.
    • 외부 접근에 대한 차단을 수행할 수 있음
    • Open proxy는 다음과 같이 두 가지 종류로 나뉨
      • Anonymouse Proxy - 초기에 요청한 client에 대한 정보는 나타내지 않는다.
      • Transparent Proxy - 프록시 서버 자체적으로 http 헤더를 지원하여 client IP를 확인할 수 있다. 이러한 방법의 장점은 서버들에 대해서 캐시를 저장할 수 있다는 것이다.
  2. Reverse Proxy
    • 하나 이상의 서버에서 client를 대신하여 리소스를 검색한다. 그 다음 그 결과는 client로 반환되어 마치 proxy server 자체에서 발생한 것처럼 보여준다.
    • 내부망 접근에 대한 보안을 위해서 사용됨

9. Redundancy and Replication

중복성Redundancy는 백업 형태로 시스템의 안정성을 높이거나 실제 시스템 성능을 향상 시키기 위해 시스템의 중요한 구성 요소/기능 요소를 복제하는 것. 중복성Redundancy는 SPoF를 제거하기 위해서 사용한다.

복제Replication는 정보(데이터)를 공유하여 중복 리소스에 대한 일관성을 보장하는 것이다. 이러한 SW/HW레벨의 복제를 통해서 신뢰성, 내결함성, 접근성 등을 향상시킬 수 있다. 복제는 많은 DB에서 사용되며 일반적으로 primary-replica 관계를 통해서 사용한다.

primary 서버는 모든 업데이트를 replica로 복제한다. 각 replica들은 업데이트가 성공적으로 반영되었는지 전달하고 primary는 계속해서 후속 업데이트를 전송할 수 있는 것이다.

정리

  • Redundancy (중복성) —> 단순 백업, 일반적으로 데이터 일관성 보장 어려움
  • Replication (복제) —> replica 설정, 데이터가 동기화 되어 있음

10. Quorum

분산 시스템에서 데이터는 내결함성 및 고가용성을 위해 여러 서버에 복제된다. 시스템이 데이터를 여러 사본으로 유지하기로 결정하면 모든 복제본에 대한 일관성을 유지하는 방법을 고민해야 한다. 분산 시스템에서의 쿼럼quorum은 성공적으로 분산 처리를 수행하기 위해서 필요한 최소 서버의 수를 의미한다.

예시

분산 시스템에서 7대의 노드에 데이터가 복제되어 있다고 가정하자. 이 경우 쿼럼은 트랜잭션에 대해 동일 작업을 수행해야 한느 최소 시스템의 수를 의미한다. 7대의 서버 중 4대의 컴퓨터가 과반수 쿼럼을 구성하게 되고, 각 노드가 동의하는 경우 해당 작업을 반영commit한다. 쿼럼은 분산 작업에 필요한 일관성 요구사항을 적용한다.

다수의 복제본이 있는 경우 사용자가 일관성 없는 데이터를 읽을 가능성이 있다. 예를들어 R1, R2, R3 세개의 복제본 중에 값 v1이 R1에 쓰여졌다고 가정하자. 이런 경우 R2, R3는 아직 데이터가 갱신되지 않았기 때문에 v1은 읽을 수 없게 된다.

쿼럼에서 어떠한 값이 선택되어야 할까? 쿼럼의 과반수가 가지고 있는 값을 가져야 한다. 예를들어 7과 6의 과반수는 4가 되고, 5와 4의 과반수는 3이된다. 7노드가 견딜 수 있는 장애는 3대가 되고 4노드가 견딜 수 있는 노드는 1대가 된다.

쿼럼은 R + W > N 일때 달성된다. (R - 읽기 최소 노드, W-쓰기 최소 노드, N-쿼럼그룹노드)

예를들어 N =3 이라고 할 때 각 설정 값에 따라서 다음과 같은 성격을 갖느다.

  • (N = 3, W = 1, R = 3) : 빠른 쓰기, 느린 읽기, 내구성이 떨어짐
  • (N = 3, W = 3, R = 1) : 느린 쓰기, 빠른 읽기, 내구성 – 쓰기가 완료 보장되어야 읽기가 가능함.

대부분은 read가 write 보다 많이 발생하기 때문에 1 < R < W < N 일 때 최고의 성능 (처리량 / 가용성) 이 나타난다.

11. Leader & Follower

쿼럼Quorum의 문제점

분산 시스템은 내결함성fault-tolerance 및 고가용성High Availability을 위해서 여러 데이터 사본을 보관한다. 이전에 알아본 것과 같이 시스템은 쿼럼Quorum을 사용해 복제본 간의 데이터 일관성을 보장할 수 있다. 이때 과반수의 노드에 데이터가 write/read되지 않으면 작업이 성공한 것으로 간주되지 않는다. 그렇기 때문에 쿼럼에는 가용성Availability 저하라는 단점이 존재한다. 그리고 쿼럼에서 일부 작업이 실패하는 경우 일관된 데이터를 확인할 수 없기 때문에 특정 시나리오에서는 쿼럼이 적절하지 않을 수 있다.

해결방안 - Leader & Follower

위에 설명한 문제의 해결방안으로 단일서버(leader)에서만 데이터 복제를 담당하고 작업을 조정하도록 한다. 다수의 노드 중 한 서버가 리더로 선출된다. 이 리더는 데이터 복제를 담당하고 모든 조정coordination의 중심적인 역할을 수행하게 된다. Leader 외의 서버들을 Follower라고 하는데, 이 서버들은 leader의 write 작업만을 수락하고 백업을 수행하게 된다. leader가 실패하는 경우 follower 중 한 서버가 leader가 될 수 있다. 구성에 따라서 follower가 부하 분산을 위한 read replica 역할을 수행할 수도 있다.

2_DL_simple_arch

12. Heartbeat

분산 환경에서 작업 및 데이터는 서버들에 분산된다. 이러한 설정에서 요청을 효율적으로 분배routing하려면 서버들이 다른 서버들의 상태를 알아야 한다. 분산 시스템에서 요청이 서버에 도착할 때마다 서버는 해당 요청을 처리할 서벌르 경정할 수 있는 충분한 정보를 가져야 한다. 따라서 서버 장애를 적시에 감지하는 것이 중요한 작업이 되며, 시스템이 수정 조치를 취하고 데이터/작업을 다른 정상 서버로 이동하고 환경이 더 악화되는 것을 막을 수 있다(circuit break) .

이를 위해서 각 서버는 중앙 모니터링 서버 또는 시스템의 다른 서버에 주기적으로 heartbeat을 전송하여 자신의 프로세스가 살아있으며 동작중인 것을 표시할 수 있다. heartbeat은 분산 시스템에서 오류를 감지하는 메커니즘 중 하나이다. 중앙 서버(일반적으로 master server)가 있는 경우 모든 서버(slave,worker)들은 중앙 서버에게 주기적으로 메세지를 보낸다. 중앙에서 관리하는 서버가 없으면 모든 서버가 서버 집합을 선택하고 무작위로 heartbeat을 보내게 된다.

만약 일정 시간 이상 서버에서 heartbeat이 수신되지 않으면 시스템은 해당 서버에 문제가 생겼다고 생각해서 해당 서버에 대해 요청 전송을 중지하고 교체 작업을 시작할 수 있다.

13. Checksum

분산 시스템에서 구성 요소간에 작업을 위해 데이터를 이동하게 되는데, 전송 과정에서의 이슈(storage, N/W, S/W 등)로 인해 수신한 메세지가 손상되었을 수도 있다. 분산 시스템은 데이터 무결성을 보장하기 위해서 데이터의 checksum을 계산하고 데이터와 함께 저장한다.

Checksum을 계산하기 위해 MD5, SHA-1, SHA-256 또는 SHA-512 같은 암호화 해시 함수가 사용된다. 해시 함수는 입력 데이터를 받아 고정 길이의 문자열(문자와 숫자)을 생성한다. 이러한 문자열을 checksum이라 한다.

시스템이 일부 데이털르 저장할 때 데이터의 checksum을 계산하고 데이터와 함께 checksum을 저장한다. 클라이언트가 데이터를 검색할 때 서버에서 받은 데이터가 저장된 checksum과 일치하는지 확인한다. 그렇지 않은 경우 클라이언트는 다른 복제본에서 요청한 데이터를 검색하도록 설정할 수 있다. 이는 분산 파일 시스템인 Hadoop(HDFS)에서 데이터노드의 data-block을 가져올 때 수행하는 방식이다.

14. Consistent Hashing

확장 가능한 시스템 설계에서 가장 중요한 것은 데이터가 서버간에 분할되고 복제되는 방식을 정의하는 것이다. 데이터 파티셔닝과 복제 전략은 모든 분산 시스템의 핵심이다.

  • Data Partitioning : 서버 세트에 데이터를 분배하는 프로세스. 시스템의 확장성Scalability와 성능을 향상시킨다.
  • Data Replication : 데이터의 여러 복사본을 만들어 다른 서버에 저장하는 프로세스로 데이터의 가용성Availability와 내구성Durability를 향상시킨다.

Consistent Hashing은 이러한 데이터 파티셔닝 및 복제를 효율적으로 처리하기 위한 캐싱cacheing 방법이다.

데이터 분배의 문제점

일반적으로 터를 여러 노드에 배포할 때 다음과 같은 이슈가 발생할 수 있다.

  • 특정 데이터가 어떤 노드에 저장되는지 어떻게 알아낼 것인가?
  • 노드를 추가하거나 제거 할 때 기존 노드에서 새 노드로 이동할 데이터를 어떻게 결정할 것인가?
  • 노드를 추가하거나 제거 할 때 데이터 이동을 최소화 할 수 있는 방법은 무엇인가?

단순한 접근 방식은 적절한 해시 함수를 사용하여 데이터의 수를 총 서버 수의 모듈러 연산하여 서버를 찾게된다. 이 경우 노드가 추가/제거되는 경우 기존의 모든 맵핑이 손상된다. 따라서 작업을 다시 시작하려면 모든 키를 다시 맵핑하고 서버 수에 따라 데이터를 이동해야 한다. 이 경우 엄청난 리밸런싱 부하가 발생할 것이다.

Consistent Hashing을 통한 해결방안

Consistent Hashing은 데이터를 물리적 노드에 맵핑하고 서버가 추가되거나 제거될 때 작은 키 집합만 이동하도록 한다. 이 방법은 분산 시스템에서 관리하는 데이터를 ring과 같은 원형의 형태로 저장한다. 그리고 ring의 각 노드에는 데이터 범위가 할당된다. 이러한 범위의 시작을 토큰이라고 하는데 이는 각 노드에 하나의 토큰이 할당되는 것을 의미한다. 각 노드에 할당된 범위는 다음과 같이 계산된다.

범위의 시작 : 토큰 값

범위의 끝 : 다음 토큰 값 -1

시스템이 데이터를 읽거나 써야할 때 가장 처음에 수행하는 것은 MD5 해싱 알고리즘을 키에 적용하는 것이다. 이 해싱 알고리즘의 결과는 데이터가 어느 범위 내에 있는지 찾아내는 것으로 읽거나 저장할 노드가 어디인지를 결정한다.

이러한 구성은 노드가 추가/삭제 될 때 데이터의 이동을 최소한으로 한다. 예를들어 노드가 제거되면 다음 다음 노드가 제거된 노드가 서비스 하던 키 범위를 이어받게 된다. 하지만 이런 방식은 데이터가 균일하지 않고 부하가 분산된다는 문제점이 있다.

  • 노드 추가/제거 : 노드를 추가하거나 제거하면 토큰이 다시 계산되어 대규모 클러스터에서 큰 오버헤드가 발생(Consistent Hasing으로 해결)

  • 핫스팟hot-spot : 특정 노드에 하나의 큰 범위가 할당됨으로 데이터가 균등하게 분할되지 않으면, 일부 노드가 핫스팟이 될 수 있다.

  • 노드 재구축 : 각 노드의 데이터는 고정된 수의 다른 노드에 복제됨으로, 특정 노드를 재구축해야 할 때 같은 해시 범위값을 갖는 그것의 복제 노드만 데이터를 제공할 수 있다. 이것은 복제본 노드에 많은 부하를 발생하고 서비스 저하로 이어진다.

Virtual Node

Consistent Hashing에서 발생하는 문제점을 해결하기 위해서 가상노드Virtual Node 방식을 사용할 수 있다. 기존과 같이 노드에 단일 토큰을 할당하는 대신 해시 범위를 여러개의 작은 범위로 나누고 각 물리노드에 이러한 작은 범위를 여러개 할당한다. 이러한 각 하위 범위는 VNode(virtual node)로 간주한다. Vnode에서는 노드가 하나의 토큰만 담당하는 대신 많은 토큰을 담당한다.

실제로 VNode는 클러스터 전체에 무작위로 분산되며 일반적으로 두 개의 인접한 VNode가 동일한 물리적 노드 똔느 랙에 할당되지 않는다. 또한 노드는 내결함성을 위해 다른 노드의 복제본을 전달한다. 만약 클러스터가 이기종 노드를 사용해 구성되어 있다고 한다면 일부 서버는 다른 서버보다 더 많은 VNode를 보유할 수 있게된다.

Virtual Node 장점

VNode는 해시 범위를 더 작은 범위로 나누어 클러스터의 물리적 노드에 부하를 보다 균등하게 분산하는데 도움을 준다. 또한 노드를 추가하거나 제거한 후 재조정 프로세스의 속도가 빨라지게 된다. 노드가 추가되면 기존 노드에서 많은 Vnode를 수신하여 균형잡힌 클러스터를 유지한다. 노드를 다시 빌드해야 하는 경우도 다수의 노드로 부터 데이터를 가져올 수 있음으로 좀 더 빠르게 처리가 가능하다. 그리고 VNode를 사용하면 이기종 시스템이 포함된 클러스터를 보다 쉽게 유지할 수 있다. 즉 높은 사양의 노드에는 많은 수의 vnode를 할당하고 낮은 사양의 노드에는 더 작은 수의 vnode를 할당할 수 있다.

데이터 복제에서의 Consistent Hashing

고가용성 및 내구성을 보장하기 위해 Consistent Hashing은 서로 다른 N개의 노드에 N개만큼의 복제본을 생성한다. (N는 replica factor). 각 키는 coordinator node에 할당되고 이 노드는 먼저 데이터를 로컬에 저장한 다음 링의 N-1 시계방향 후속노드에 복제한다. 결과적으로 각 노드는 자신과 N번째 후속노드의 링 영역을 갖게 된다.

Eventually consistency가 보장되는 시스템에서는 항상 모든 복제본이 일관성을 가질 필요는 없다. 분산 시스템에서 고가용성을 당성하기 위해 eventual consistency가 사용된다.

정리

위에서 살펴본 것 처럼 consistent Hashing은 데이터를 효율적으로 분할하고 복제하는데 도움을 준다. 따라서 확장/축소가 필요하거나 데이터 복제를 통해 고가용성을 달성하려고 하는 분산 시스템에서 사용할 수 있다.

Amazon DynamoDB 나 Apache Cassandra에서 consistent hasing을 통해 노드간 데이터를 배포하고 복제한다.

15. Long-Polling vs WebSockets vs Server-Sent Events

Long-Polling, WebSocket 및 Server-Sent Events는 웹 브라우저와 같은 client와 web server간 널리 사용되는 프로토콜이다. 이것들에 대해서 비교하기 전에 먼저 표준 HTTP web request가 어떻게 생겼는지 이해하는 것 부터 시작해야 한다. 다음은 일반적인 HTTP 요청에 대한 일련의 이벤트이다.

<15-1>

  1. client는 연결을 열고 server에서 데이터를 요청한다.
  2. server는 응답을 계산한다.
  3. server는 열린 요청에 대해 클라이언트에 응답을 다시 보낸다.

Ajax Polling 의 문제점

Polling은 대부분의 AJAX 애플리케이션에서 사용하는 표준 기술이다. 기본 아이디어는 client가 데이터를 위해 서버를 반복적으로 polling(요청)한다는 것이다. client는 요청을 하고 서버가 데이터로 응답할 때까지 기다린다. 사용가능한 데이터가 없으면 빈 응답이 반환된다.

<15-2>

  1. Client는 연결을 열고 일반 HTTP를 사용하여 서버에서 데이터를 요청한다.
  2. 요청된 웹 페이지는 일정한 간격(e.g 0.5초)로 서버에 요청을 보낸다.
  3. 서버는 일반 HTTP 트래픽과 마찬가지로 요청을 계산하고 client에게 응답response을 보낸다.

클라이언트는 서버에서 업데이트를 받기 위해 위 세 단계를 주기적으로 반복한다. polling의 문제점은 client가 새로운 데이터를 계속해서 요청해야 한다는 것이다. 결과적으로 많은 응답이 비어있어 HTTP 오버헤드가 발생하게 된다.

HTTP Long-Polling

이 방식은 데이터를 사용할 수 있을 때 마다 서버가 클라이언트에 정보를 push 할 수 있도록 변경한 polling 기술의 변형이다. Long-polling을 사용하면 client는 정상적인 polling에서와 똑같이 서버에서 정보를 요청하지만, 서버가 즉시 응답하지 않을 수 있다. 그렇기 때문에 이 기술을 Hanging GET이라고도 한다.

서버에서 client에 전달할 데이터가 없는 경우, 데이터가 빈 응답을 보내는 대신 서버는 요청을 보류하고 보내줄 데이터가 있을 때까지 기다립니다. 그리고 데이터가 사용할 수 있게 되면 전체 응답이 client로 전송된다. client가 데이터를 받은 후에 client는 곧바로 서버에 다시 데이터를 요청함으로 서버는 거의 항상 데이터를 보내줄 수 있는 client의 요청을 가지고 있는 상태가 된다. 기본적인 HTTP Long-polling 애플리케이션의 수명주기는 다음과 같다.

<15-3>

  1. client는 일반 HTTP를 사용하여 초기 요청을 한 다음 응답을 기다린다.
  2. 서버는 업데이트를 사용할 수 있거나 시간 초과가 발생할 때까지 응답을 지연한다.
  3. 업데이트를 사용할 수 있는 경우 서버는 client에 전체 응답을 보낸다.
  4. client는 일반적으로 응답을 수신하는 즉시, 허용가능한 대기 시한 뒤 새로운 long-poll을 보내게 된다.
  5. 각 long-poll 요청에는 시간제한이 있다. client는 시간 초과로 인해 연결이 닫히 후 주기적으로 다시 연결해야 한다.

WebSockets

웹 소켓은 단일 TCP연결을 통해 전 이중 통신(full-duplex communication)채널을 제공한다. client와 서버간 영구적인 연결을 제공하여 양측이 언제든지 데이터 전송을 시작할 수 있다.

Client는 웹소켓 핸드쉐이크hand-shake라는 프로세스를 통해 웹소켓을 연결한다. 프로세스가 성공하면 언제든지 양방향으로 데이터를 교환할 수 있다. 웹소켓 프로토콜은 낮은 오버헤드로 클라이언트와 서버간 통신을 가능하게하여 서버와의 실시간 데이터 전송을 용이하게 한다. 이는 서버가 client의 요청없이 브라우저에 콘텐츠를 보낼 수 있는 표준화된 방법을 제공하고, 브라우저에 콘텐츠를 보낼 수 있는 표준화된 방법을 제공한다. 이러한 방식으로 client와 서버간 양방향 진행중인 대화가 발생할 수 있다.

<15-4>

Server-Sent Events (SSEs)

이 방식에서는 client는 서버와 지속적이고 장기적인 연결을 설정한다. 서버는 이 연결을 이용해 데이터를 client에보낸다. client가 데이터를 서버로 보내려면 다른 기술/프로토콜을 사용해야 한다.

  1. Client는 일반 HTTP를 사용하여 서버에서 데이터를 요청한다. (초기 설정)
  2. 요청 된 웹 페이지는 서버에 대한 연결을 한다.
  3. 서버는 새로운 정보가있을 때 마다 client에 데이터를 보낸다.

SSE는 서버에서 client로의 실시간 트래픽이 필요하거나 서버가 루프에서 데이터를 생성하고 여러 이벤트를 Client로 보낼 때 가장 좋다. 이 방식에서는 client는 초기 서버 연결 후 서버에 데이터를 polling 하지 않는다

<15-5>

16. Bloom Filter

만약 구조화된 대용량의 구조화된 데이터(레코드 ID로 식별될 수 있는)가 여러개의 파일에 저장되어 있는 경우, 하나의 파일에 필요한 데이터를 가장 많이 효과적으로 저장하는 방법은 무엇인가?

필요한 데이터를 찾기 위해서 파일의 내용을 하나씩 읽는 방법은 효율적이지 못하다. 이에 대한 한가지 해결방법은 각 데이터 파일에 대한 인덱스를 생성하여 별도의 인덱스 파일에 저장하는 것이다. 이 인덱스는 각 레코드ID를 데이터 파일의 offset에 맵핑할 수 있다. 그리고 각 인덱스 파일은 레코드ID를 기준으로 정렬된다. 이 상태에서 인덱스 내의 레코드ID를 찾기 위해서는 이진 탐색이 최선이다. 과연 이 방법이 최선일까?

블룸필터Bloom Filter는 이러한 데이터 파일들에 원하는 값이 있는지 찾는 효율적인 알고리즘이다. 블룸필터 데이터 구조는 원하는 데이터가 집합에 있는지 여부를 알려준다. 유일하게 발생할 수 있는 오류는 잘못 찾는 것이다. 즉, 존재하지 않는 값을 찾을 때 잘못된 파일 안에서 찾을 수 있다.(없는 값이기 때문에 성능에 대한 저하는 발생하지만 잘못된 결과를 출력하지는 않는다)

필터에 더 많은 요소가 있으면 오류율이 증가한다. 비어있는 블룸 필터는 모두 0으로 설정된 m 개의 비트 배열입니다. k 개의 서로 다른 해시 함수를 사용하여, 각 해시 함수를 통해 세트 요소를 m 비트 위치 중 하나에 매핑한다.

  • 요소(element)를 추가하려면 해시 함수에 입력하여 k 비트 위치를 얻고 이 위치의 비트를 1로 설정한다. 요소가 세트에 있는지 테스트하려면 해시 함수에 입력하여 k 번째 비트 위치를 가져온다.
  • 이 위치의 비트 중 하나가 0이면 요소는 확실히 세트에 없다. 모두 1이면 요소가 세트에있을 수 있다. (반드시 있는 것은 아니다)

다음은 P, Q, R의 세 가지 요소가있는 Bloom 필터에 대한 예시이다. 20 비트로 구성되며 세 가지 해시 함수를 사용한다. 컬러 화살표는 집합의 요소가 매핑되는 비트를 가리킨다.

<16-1>

요소 X는 0을 포함하는 비트 위치로 해시되기 때문에 확실히 세트에 없다. 고정 오류율의 경우 새 요소 추가와 멤버십 테스트는 모두 일정한 시간 작업이며 ‘n’요소를위한 공간이있는 필터에는 O (n) 공간이 필요합니다.