무상태(stateless) 웹 계층에서 비정규화(de-normalization)까지

The Shard

무상태(stateless) 웹 계층 → 수평적 확장(scale out) → DB의 scale out(sharding) → 안정해시(consistent hash) → join, 비정규화(de-normalization)

무상태(stateless) 웹 계층

• 웹 계층에서는 상태를 갖지 않는 것이 좋다.
• 상태 정보를 보관하는 서버는 클라이언트 정보(상태)를 유지하여 요청들 사이에 공유되어야 한다.
• 이유는 수평적 확장(scale out)에 불리하기 때문
• 해결하기 위해서는 상태정보(사용자 세션 데이터 등..)를 웹 계층에서 제거 -> DB로 관리
• 무상태(stateless) 웹 계층이라 부름

stateful web layer

• 사용자 A의 세션정보, 프로파일 이미지 같은 상태정보가 서버 1에 저장되면, 사용자 A를 인증하기 위해 HTTP요청이 반드시 서버 1로 전송
• 문제는 같은 클라이언트로부터의 요청은 항상 같은 서버로 전송되어야 한다.
• 대부분의 LB가 이를 지원하기 위해 고정 세션(sticky session)이라는 기능을 제공
  - https://itnext.io/sticky-sessions-and-canary-releases-in-kubernetes-8c45de2b0a2e
• 하지만 LB에 부담 -> LB 뒷단에 서버를 추가, 제거하기도 까다로워짐 -> scale in/out 어려워진다.

무상태 아키텍처

stateless web layer

• 웹 서버는 상태 정보가 필요한 경우 공유 저장소로부터 데이터를 가져옴
• 상태정보와 웹 서버를 물리적으로 분리
• 구조가 단순하고, 안정적, 규모 확장이 쉽다.

 

무상테 웹 레이어 전체구조

그럼 웹서버는 상태정보를 DB로 넘기면서 scale out이 쉬워졌지만,
DB는 어떤 식으로 scale out을 하는 거지?

• 데이터베이스의 수평적 확장(scale out) = 샤딩(sharding)
  - 서버를 추가하면서 성능 향상

샤딩(sharding)

• 대규모 데이터베이스를 샤드(shard)라고 부르는 작은 단위로 분할하는 기술

sharding

샤딩(Sharding)과 레플리케이션(Replication)의 차이

 레플리케이션 

• 여러 개의 DB를 master-slave 형태로 구축하고, master에 DML(Write-only)을 하고 slave에 복제(Read-only)하는 방식

샤딩

• 테이블을 특정 기준으로 나눠서 저장하고 검색

샤딩 전략 구현 시 고려해야 할 가장 중요한 것

• 샤딩 키(sharding key)
• 위 그림에서 샤딩 키 = user_id
• 데이터를 각 샤드에 고르게 분할(read, write) 할 수 있도록 샤딩 키를 정하는 것이 중요

샤딩을 적용했을 때 생기는 문제점

• 데이터 재샤딩(resharding)
  - 샤드 간 데이터 분포가 균등하지 못해서 특정 샤드에 할당된 공간 소모가 부족해지면, 샤드 키를 계산하는 함수를 변경
•  데이터 재배치 이슈 → '안정 해시'를 통해 해결

안정 해시(consistent hash)

• scale out을 위해 요청, 데이터를 서버에 균등하게 나누는 것이 중요한데, 이 목표를 위해 보편적으로 사용하는 기술
• 서버가 추가되거나 삭제될 때 재배치되는 키의 수를 최소화
• 데이터가 비교적 균등하게 분포 → scale out의 확장성 달성하기 쉽다.

샤딩 유형

범위 기반 샤딩

• usrId 1~1000 = shard0, userId 1001~2000 = shard1, userId 2001 ~ 3000 = shard2
• userId의 범위를 기준으로 샤딩

범위 기반 샤딩

해시 기반 샤딩

• shard N = hash(key) % N(shard 개수)

해시 기반 샤딩

해시 키 재배치(refresh) 문제

재배치 전

• 서버 풀(server pool)이 고정되어 있거나 데이터 분포가 균등할 경우 잘 동작
• 서버가 추가되거나 기존서버가 삭제될 경우 문제가 발생

재배치 후 1개 서버 삭제되었을 경우

• 해시 값은 변하지 않지만 함수가 변경되어 분포가 균일하지 않고 대부분의 데이터가 재배치
  - 8개 중 5개의 데이터가 재배치됨(key0, 5, 7, 4, 3)
• 이 문제를 해결 → 안정 해시 전략

안정 해시(consistent hash) 재배치 

해시테이블의 크기가 변할 때, 평균적으로 K/n의 키만 재매핑되면 된다. 즉 노드나 슬롯의 개수가 바뀔 때, 노드의 추가나 삭제를 할 때, 오직 K/n의 아이템만 다시 섞이면 되는 것이다. (n은 전체 노드의 개수, K는 item의 개수)
- wikipedia

해시 공간(hash space), 해시 링(hash ring)

• 데이터 키에 해시함수 SHA-1을 사용한다고 가정
• 함수 SHA-1의 해시 공간 범위 → 0 ~  2^160-1 

hash space

• 해시 공간(hash space)의 양쪽을 모으면 해시 링(hash ring)이 만들어진다.

hash ring

해시 서버

• 서버 IP, host 등을 해시함수(SHA-1)에 사용해 해시 값에 맞는 위치에 대응

해시 서버 배치

해시 키

• 데이터 키 또한 해시함수(SHA-1)에 적용해 맞는 곳에 위치

해시 키 배치

서버 조회

• 해당 키의 위치로부터 시계방향으로 링을 탐색하여 만나는 첫 번째 서버에 해당 데이터가 위치

서버 조회 = 시계방향으로 링 탐색

서버 추가

• 서버 4가 추가될 경우, key 0만 재배치됨

서버4 추가 = key0만 재배치

재배치 시 2가지 문제점

1. 서버 추가, 삭제 시 파티션의 크기가 균등하지 않다.
- s1이 삭제되어 s2의 해시 공간이 2배로 커짐

파티션 크기 불균등

2. 키의 균등 분포를 달성하기 어렵다.
- 아래 그림과 같이 서버가 분포되어 있을 때, s1, s3은 데이터가 없고 대부분의 키가 s2에 보관됨
- 해시 함수가 적절히 분배를 해주지 못하는 이슈

키 불균등 분포

해결방법 → 가상 노드

• 실제 노드 또는 서버를 가리키는 노드
• 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다

가상 노드

• 마찬가지로 키(key 0)의 위치에서 시계방향으로 탐색하다 만나는 최초의 가상노드(서버 1_1)가 나타내는 서버 → 서버 1

서버 조회

• 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해짐
• 표준 편차가 작아 저서 데이터가 더 고르게 분포
• 100~200개의 가상노드를 사용했을 경우 표준 편차 값은 평균의 5%(가상노드 200개)~10%(가상노드 100개) 사이
• 가상 노드를 더 늘리면 표준편차의 값은 더 줄어들지만, 가상 노드 데이터를 저장할 공간이 더 필요하기 때문에 타협적 결정(trade off)이 필요
• 시스템 요구사항에 맞게 적절히 노드 수를 조정

재배치할 키 결정

• 재배치 과정은 이전과 같음.

안정 해시 목적

• 서버 추가, 삭제 시 재배치되는 키의 수 최소화
• 데이터가 보다 균등하게 분포 → scale out에 유리

적용처

• 아마존 다이나모 데이터베이스(DynamoDB)
• 아파치 카산드라(Apache Cassandra)
• 디스코드 채팅 애플리케이션

ES에서는 샤딩시 안정해시를 사용하는가 궁금해짐?

• https://www.elastic.co/guide/en/elasticsearch/reference/current/indices-split-index.html#incremental-resharding
• Lucene indices 이슈로 비용이 크기 때문에 기존 index의 샤드를 분리한(split) 새로운 인덱스를 생성 가능한 api를 사용하라.

POST /my_source_index/_split/my_target_index
{
  "settings": {
    "index.number_of_shards": 2
  }
}

 

조인(join)과 비정규화(de-normalization)

• 하나의 데이터베이스를 여러 샤드로 쪼개고 나면, 여러 샤드에 걸친 데이터를 조인하기가 힘들어 짐
• 이를 해결하기 위한 한 가지 방법은 데이터 베이스를 비정규화하여 하나의 테이블에서 질의가 수행되도록 하는 것

Fin.

• 무상태(stateless) 웹 계층 → 수평적 확장(scale out) → DB의 scale out (sharding) → 안정해시(consistent hash)
  → join, 비정규화(de-normalization)로 이어진 의식의 흐름 정리

Ref

• https://jjingho.tistory.com/150
• https://jjingho.tistory.com/156
• https://donghyeon.dev/%EC%9D%B8%ED%94%84%EB%9D%BC/2022/03/20/%EC%95%88%EC%A0%95-%ED%95%B4%EC%8B%9C-%EC%84%A4%EA%B3%84/