행운개발자의 기술블로그

데이터의 효율적인 저장과 조회(SSTable, Bloom Filter, LSM Tree)

행운개발자 — Mon, 5 May 2025 22:29:49 +0900

SSTable, Bloom Filter, LSM Tree

rate limiter와 key-value store의 설계 진행하면서 아래의 개념들을 순서대로 확인해보았다

고가용성 rate limiter가 필요함
rate limiter에서 사용하는 알고리즘 확인
- token bucket
- leaky bucket (queue bucket)
- fixed window counter (단위 시간당 고정된 갯수)
- sliding window log (timestamp 기준으로 deprecate)
- sliding window counter (% 기반으로 count 추정)
counter를 저장하기 위해서 고가용성, 분산 환경의 key-value store가 필요함
어떤 Node에 저장될지 결정해야 함 : Consistent Hash
고가용성, 데이터 다중화 : Quorum (N,R,W)
데이터 다중화 과정에서 동기화를 보장해야 함 : Client Side, Versioning, Vector Clock
장애를 탐지해야 함 : 가십 프로토콜
일시적인 장애를 감내해야 함 : Quorum (N,R,M)
영구적인 장애에서 데이터를 복구해야 함 : HashTable

위 과정까지 진행하면 대부분의 문제를 해결해서 데이터가 메모리 상에서 잘 관리됨을 보장할 수 있다. 다음으로는 메모리와 디스크 사이의 동기화 과정에 대해서 알아보아야 한다.

Bloom Filter

거대한 데이터 셋에서 특정 데이터가 존재하는지 아닌지 찾을 떄 사용한다.

bloom filter return false : 데이터 셋에 존재하지 않음
bloom filter return true : 존재할 수도 있고, 존재하지 않을 수도 있음

username을 등록할 때, 이미 해당 username이 이미 존재하는지 확인해야하는 경우가 있다.
이 때 bloom filter가 return false를 한다면, username을 사용할 수 있음이 보장된다.

bloom filter는 확률에 기반한 접근 방법이라서 정확도가 떨어진다고 볼 수도 있지만,
공간의 제약을 개선해준다는 점에서 유의미한 장점을 가진다.

동작 과정

Bloom Filter는 2가지로 구성된다.

Hash Function
a bit array with Length N

ADD

하나의 데이터에 대해서 여러개의 Hash Function을 적용한다.
그리고 각 값을 a bit array의 길이로 moduler를 해서 bit array의 값을 0->1로 변경한다.
이미 1이라면 그대로 둔다.

arr[func_1(x) % N]=1
arr[func_2(x) % N]=1
arr[func_3(x) % N]=1

CHECK

bloom filter에 이미 존재하는지 확인하고 싶은 값 y에 대해서 아래의 값을 확인한다

arr[func_1(y) % N]=1
arr[func_2(y) % N]=1
arr[func_3(y) % N]=1

특징

Collision이 발생할 수 있는 확률이 존재하기 떄문에 존재하지 않음만 보장할 수 있다.
삭제 연산을 지원하지 않는다. 수행하면 다른 key에도 영향이 가기 때문이다.

SSTable

Sorted Strings Table
Apache Cassandra, BigTable에서 사용하는 데이터 저장 포멧
SSTable은 Disk에서 데이터를 File에 효율적으로 저장하기 위한 포멧
1. 데이터 블록(data blocks): 실제 키–값 쌍이 담긴 압축된 블록
2. 인덱스 블록(index blocks): 블록별 최소·최대 키 정보
전체 데이터가 아닌 일부 데이터만 사용해서 Index 검색을 수행한다
특징
- File로 저장되기 때문에 persistent함
- append only를 지원해서 immutable함 (timestamp가 변경되면서 동일한 데이터가 중복해서 저장될 수 있음)
전체 데이터셋에 대한 Bloom Filter를 관리하여, 찾는 데이터의 key가 존재하는지 아닌지 확인한다
key가 존재한다면 데이터 블록의 최소, 최대 값으로 SSTable을 특정하고, 특정된 디스크를 열어서 Value를 확인한다
데이터가 정렬되어 있음을 가정되어 있기 때문에, 어떤 SSTable에 저장되어있는지 확인이 가능하고, 특정된 디스트 내에서도 빠르게 데이터를 찾을 수 있다.
B-Tree는 균형 잡힌 데이터 구조를 지원해서 Sequential, Random Access에서 균형잡힌 성능을 보여주고
SSTable은 LSM Tree와 함께 사용되어 Heavy Write 상황에서 적합하다

LSM Tree

Log-Structured-Merge Tree
SSTable, Bloom Filter를 사용해서 데이터를 효율적으로 저장하는 구조

write에 대한 정보를 먼저 WAL에 저장
Memory에 Write
임계치에 도달하면 Memory에서 Disk에 SSTable 구조로 flush
compression : 작은 파일로 구성된 SSTable을 하나의 큰 SSTable로 합치기 (Read 및 저장 공간 호율 개선)
- SSTable은 immutable이기 때문에 timestamp가 변경되면서 동일한 데이터가 중복해서 저장될 수 있음
- key 정렬
- key에 version이 포함된 경우, 최신 버전만 남기기
- File로 저장하면서 적절한 단계로 SSTable의 Layer를 나누어서 단계적으로 압축해서 저장함
조회 과정
- Memory
- SSTable에 데이터가 존재하는지 확인 (Bloom Filter)
- 존재한다면 리턴
- 존재하지 않으면 다음 SSTable에서 조회

Reference

Memory와 Disk의 동기화 (SSTable, Bloom Filter)

행운개발자 — Mon, 5 May 2025 12:17:04 +0900

SSTable, Bloom Filter

rate limiter와 key-value store의 설계 진행하면서 아래의 개념들을 순서대로 확인해보았다

고가용성 rate limiter가 필요함
rate limiter에서 사용하는 알고리즘 확인
- token bucket
- leaky bucket (queue bucket)
- fixed window counter (단위 시간당 고정된 갯수)
- sliding window log (timestamp 기준으로 deprecate)
- sliding window counter (% 기반으로 count 추정)
counter를 저장하기 위해서 고가용성, 분산 환경의 key-value store가 필요함
어떤 Node에 저장될지 결정해야 함 : Consistent Hash
고가용성, 데이터 다중화 : Quorum (N,R,W)
데이터 다중화 과정에서 동기화를 보장해야 함 : Client Side, Versioning, Vector Clock
장애를 탐지해야 함 : 가십 프로토콜
일시적인 장애를 감내해야 함 : Quorum (N,R,M)
영구적인 장애에서 데이터를 복구해야 함 : HashTable

SSTable

Bloom Filter

키-값 저장소 설계

행운개발자 — Mon, 5 May 2025 12:01:51 +0900

키-값 저장소 설계

키-값 저장소에 저장된 값은 고유한 식별자를 키로 가져야 함
키-값 쌍에서 키는 유일해야함
키는 문자 또는 해시값일 수 있음
성능상의 이유로 키는 짧을수록 좋음

CAP

네트워크 파티션은 불가피하기 때문에, 일관성과 가용성 사이에서 선택을 해야함

데이터 저장

안정 해시를 사용해서 데이터를 어떤 서버에 저장할지 결정

데이터 다중화

안정 해시에서 만나는 여러개의 노드에 모두 데이터를 저장
가상 노드를 사용하는 경우, 실제 서버의 갯수를 카운트가 채워질 때까지 체크해야 함

데이터 일관성

정족수 합의 Quorum Consensus

N : 사본 갯수
W : 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 함
R : 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 함
N,R,W 의 결정 : 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정
- R=1, W=N : 빠른 읽기 연산
- W=1, R=N : 빠른 쓰기 연산
- W+R > N : 강한 일관성이 보장됨 (보통 N=3, W=R=2)

일관성 모델

강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 보장한다
약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다
최종적 일관성 : 약한 일관성의 한 형태. 갱신 결과가 결국에는 모든 사본에 반영되는 모델이다.
강한 일관성을 달성하는 가장 일반적인 방법은, 모든 사본에 대해서 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것이다
이 방법은 고가용성 시스템에서는 적합하지 않다. 새로운 요청의 처리가 중단되기 때문이다.
결과적 일관성 모델을 따르는 경우, 쓰기 연산이 병렬적으로 발생하면서 시스템에 저장된 값의 일관성이 깨질 수 있다.
이 문제는 클라이언트가 해결해야 한다.

비일관성 해소 방법, 데이터 버저닝과 백터 시계

버저닝
- 데이터에 대한 write 연산이 수행되면 (server, version)의 쌍이 생성된다
- 최초로 수정하는 서버에선느 (Server, 1)이 생기고, 이미 기록이 있으면 (Server, old+1)이 저장된다
벡터 시계
- 서로 다른 서버에서 각각의 수정 기록을 가지고 있을 떄,
- 한 서버가 가진 모든 수정 기록이, 다른 서버가 가진 기록보다 모두 같거나 과거의 기록일 때 충돌이 없음을 확인할 수 있다
벡터 시계의 단점
- 백테 시계를 사용해서 충돌을 감지하고 해소하는 방법이 클라이언트에 포함되어야 하여 복잡도 증가
- 서버:버전의 순서쌍 갯수가 굉장히 빨리 늘어남
  - 어떤 임계치를 설정하고 오래된 순서쌍을 제거
  - 업계에서 벡터 시계의 임계치 설정으로 문제가 발생하지 않았음이 보고됨

멀티 노드에서의 장애 대응

장애 감지, 가십 프로토콜

분산 시스템에서는 보통 두 대 이상의 서버가 똑같이 서버 장애를 감지하는 방법을 사용함
모든 노드 사이에서 서로의 상태를 체크하는 방법이 가장 쉬운 방법이지만, 서버가 많을 때에는 비효율적인 접근
가십 프로토콜
- 각 노드는 자신이 관리해야하는 목록을 유지한다
- 이 목록은 각 멤버의 ID와 heartbeat counter를 포함한다
- 각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다
- 각 노드는 무작위로 선정된 노드들에게 주기적으로 자신의 heartbeat counter 목록을 보낸다
- 목록을 받은 노드는 최신의 값으로 갱신한다
- 어떤 멤버의 박동 카운터가 지정된 시간동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주한다

장애 처리, 일시적인 방법 (느슨한 정족수)

quorum에서 W,R를 엄격하게 접근한다면 읽기와 쓰기 연산을 금지해야 한다.
느슨하게 관리한다면 해시 링에서 W,R개의 건강한 서버를 고른다.
해시 링에서 장애 상태로 존재하는 서버에 대한 요청은 다른 서버가 임시적으로 맡아서 처리한다
그 동안 발생한 변경 사항은 복구가 된 뒤에 일괄 반영된다
이를 위해 임시로 쓰기 연산을 처리한 서버에서는 관련된 힌트를 남겨둔다.

장애 처리, 영구 장애 처리 (anti-entropy protocol)

영구적인 장애를 처리하기 위해서는 반-엔트로피 프로토콜을 구현해서 사본을 동기화 해야한다.
사본을 비교해서 최신 버전으로 갱신하는 과정을 포함한다 (사본 간의 일관성이 망가진 상태를 탐지)
전송 데이터의 양을 줄이기 위해서는 Merkle Tree(=Hash Tree)를 사용한다
해시 트리 : 각 노드에는 그 노드의 자식들에 보관된 값의 해시를 라벨로 추가한다
- 트리의 루트만 비교해서 전체가 동일한지 아닌지 알 수 있다
- 차이가 발생하는 부분을 알기 위해서는 루트부터 자신의 라벨을 순서대로 확인하면 된다
- 이를 통해 장애가 영구적으로 발생했을 때, 복구의 필요성을 탐지하고, 탐지가 필요한 경우 최소한의 데이터만 이동해서 복구할 수 있다

Reference

가상 면접 사례로 배우는 대규모 시스템 설계 기초 6장

안정 해시 Consistent Hash

행운개발자 — Sun, 4 May 2025 22:39:32 +0900

안정 해시 설계

수평적인 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 방법

해시 키 재배치(rehash) 문제

serverIndex = hash(key) % N (서버 수)
서버가 추가되면 전체 서버의 갯수가 달라져서, 기존의 hashKey가 달라진다
해시 함수를 통한 해싱 결과가 균등하지 않을 수 있다

안정 해시

해시 테이블의 크기가 변경될 떄 K/N개의 키만 재배치하는 해시 기술
K : 키의 갯수
N : slot 갯수
SHA-1 해시함수의 공간은 0 ~ 2^160-1
해시 함수의 해시 공간을 구부려서 해시 링을 만든다
임의의 위치에 서버를 배치한다
해시 함수 - 해시 키 - 해시 링에서 오른쪽으로 돌면서 가장 가까운 서버에 접근
서버가 추가, 제거되어도 근접한 서버에 저장되었던 키들만 cache miss로 영향받음

안정 해시 문제점 2가지

서버가 추가, 삭제되는 상황에서 해시 링의 partition의 크기를 균등하게 유지하는게 불가능
- 서버개 해시 링에서 담당해야하는 공간 사이에 차이가 있음
해시 키가 해시 공간 안에서 균등하게

안정 해시 문제점 극복 :: 가상 노드

서버는 여러개의 가상 노드를 가짐
해시 링에 가상 노드를 배치
각 서버는 여러개의 가상 노드에 대응되는 부분을 담당
대략적으로 100~200개의 가상 노드를 설정하면 표준 편차가 5%정도 발생함
- 가상 노드 정보를 저장하기 위한 공간을 감안해서 적절한 수준을 선택해야 함

Reference

가상 면접 사례로 배우는 대규모 시스템 설계 기초 5장

처리율 제한 장치, Rate Limiter

행운개발자 — Sun, 4 May 2025 22:27:45 +0900

처리율 제한 장치 설계

네트워크 시스템에서 처리율 제한 장치는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치이다.

역할

Dos 공격에 의한 자원 고갈을 방치
더 많은 서버를 두지 않아도 되어 비용 절감
서버 과부하를 방지

범위 설정

클라이언트 측 제한 장치인지, 서버 측 제한 장치인지
- 서버 측 제한 장치를 설계해야 함
어떤 기준으로 API 호출을 제어해야할지 (IP 주소, 사용자 ID )
- 다양한 제어 규칙을 정의할 수 있도록 해야하는지
시스템 규모는 어느정도를 감안해야 하는지
- 대규모 요청을 처리할 수 있어야 함
시스템이 분산환경에서 동작해야 하는지
- 분산 환경에서 동작해야 함
처리율 제한 장치는 독립된 서비스인지, 애플리케이션 코드에 포함되어야 하는지
사용자의 요청이 처리율 제한 장치에 걸러진 경우, 사용자에게 그 사실을 알려야하는지
- 429 Too Many Request

요구사항

설정된 처리율을 초과하는 요청은 정확하게 제한한다
낮은 응답 시간 : 응답시간에 영향을 주면 안된다
가능한 적은 메모리를 사용해야 한다
분산형 처리율 제한 : 하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야 한다
예외 처리 : 요청이 제한되었을 때 사용자에게 알려야 한다
높은 결함 감내성 : 제한 장치에 장애가 생기더라도, 전체 시스템에 영향을 주면 안된다

접근

일반적으로 rate limiter는 API Gateway라고 불리는 컴포넌트에서 구현됨
rate limiter를 API Gateway에 두어도 되고, 직접 서버에 추가해도 됨
외부 시스템을 사용하는 경우, 어떤 알고리즘을 사용할지 선택지가 제한될 수 있음

알고리즘

token bucket

지정된 용량을 가지는 컨테이너
사전 설정된 양의 토큰이 주기적으로 채워짐
버킷의 최대 용량, 일정한 주기마다 추가되는 일정한 갯수의 토큰
최대 용량을 넘어가는 토큰은 버려짐
각 요청은 하나의 토큰을 사용함
요청이 들어오면, 토큰이 충분한지 확인하고, 하나를 꺼내고, 요청을 시스템에 전달함
토큰이 없는 경우, 해당 요청은 버려짐
인자 2가지
- 최대 토큰 갯수
- 초당 몇 개의 토큰이 추가되는지
적용
- 일반적으로 API Endpoint마다 별도의 토큰을 둔다
- 시스템 전체의 처리율을 10,000개로 제한하고 싶다면, 모든 요청이 하나의 토큰을 공유하도록 처리한다
장점
- 단순하고, 메모리 사용이 호율적이고
- 짧은 시간에 집중되는 트래픽 대응 가능leaky bucket
주로 FIFO Queue로 구현한다
요청이 도착하면 큐가 가득 차 있는지 확인한다
빈 자리가 있는 경우에는 큐에 요청을 추가한다
큐가 가득 차 있는 경우는 새 요청은 버린다
지정된 시간마다 큐에서 요청을 꺼내어 처리한다
인자
- 최대 토큰 갯수 = Queue Size
- 초당 몇 개의 요청을 처리하는지 (고정된 값)
장점
- 제한된 큐의 사이즈로 메모리 사용량이 효율적이다
- 고정된 처리율을 가지고 있어, 안정적으로 출력할 수 있다
단점
- 단시간에 많은 트레픽이 몰리는 경우, 최신 요청들은 모두 버려진다.

fixed window counter

타임라인을 고정된 간격의 윈도우로 나누고, 각 윈도우마다 counter를 붙인다
요청이 접수되면 이 카운터의 값은 1씩 증가한다
카운터의 값이 임계치에 도달하면 새로운 요청은 임계치가 열릴 때까지 버려진다
단점
- 타임라인 윈도우의 경계부근에서는, 각 윈도우의 counter * 2에 가까운 요청이 몰린다

sliding window log

새 요청이 들어오면 timestamp를 추적함
timestamp는 redis의 sorted set으로 저장함
새 요청이 들어오면 만료된 타임스템프를 제거함
만료의 기준 : 현재의 타임 윈도우보다 오래된 시간에 들어온 요청
장점
- 어느 순간도 허용된 크기 이상의 요청을 처리하지 않음
단점
- timestamp를 저장해서 메모리 사용량이 증가함

sliding window counter

fixed window counter + sliding window log
fixed에서 단위 시간당 처리량을 비율로 계산함
- 현재 단위 시간의 요청 수 + 직전 1분간 요청수 * 직전 1분과 겹치는 비율
장점
- timestamp를 기준으로 저장하지 않아서 메모리 사용량이 좋고
- timestamp 기준 시간이 바뀌는 구간에서도 처리율이 안정된다
단점
- 비율에 기반한 다소 느슨한 처리방식

구현

IP 주소 별 또는 API Endpoint 별로 처리율을 제한해야 함
counter 정보를 DB가 아닌 메모리에 저장해야 빠르며, 보통 Redis를 사용해서 구현함
Redis는 2가지 명령어를 제공함
- increase : 메모리에 저장된 카운터 1 증가
- expire : counter에 timeout 설정. timeout이 지나면 자동으로 삭제.
클라이언트 - Rate Limiter(Redis) - My Service

429 Too Many Request

요청이 거절된 경우, 헤더에 정보 추가
- x-rate-limit-remaining : 남은 요청 수
- x-rate-limit-limit : 매 윈도우마다 클라이언트가 처리할 수 있는 수
- x-rate-limit-retry-after : 몇 초 뒤에 다시 요청을 보내야 하는지

경쟁 조건

동시성 문제가 발생할 수 있음
락으로 해결할 수 있지만, 락을 걸면 시스템 성능이 상당히 나빠짐
대안 2가지
- 루아 스크립트
- redis : sorted set 사용

동기화

여러 대의 처리율 제한 장치 사이의 동기화
쉬운 방법 : sticky session
- 규모에서 확장가능하지 않고, 유연하지 않음
적절한 대안 : 여러개의 처리율 제한 장치에서 중앙 집중된 redis를 사용하기

TODO

rate limiter의 알고리즘은 파악함
동시성과 동기화의 문제를 모두 redis에 위임함

Reference

가상 면접 사례로 배우는 대규모 시스템 설계 기초 4장

Google File System 뜯어보기 - Memory Mapped I/O

행운개발자 — Thu, 24 Apr 2025 18:00:46 +0900

GFS에는 아래와 같은 문장이 나온다.

The checkpoint is in a compact B-tree like form that can be directly mapped into memory and used for namespace lookup without ex-tra parsing. This further speeds up recovery and improves availability.

전체적인 느낌은 이해가 되었지만 directly mapped into memory 라는 내용이 어떻게 동작하는지 잘 이해되지 않았다. 그래서 이번 글은 MemoryMapedFile에 대한 내용을 정리해본다.

What is checkpoint in GFS

GFS에서 Master는 3가지 Metadata를 저장한다.

the file and chunk namespaces
the mapping from files to chunks
the locations of each chunk’s replicas

처음 두 가지의 메타 정보는 operation log를 사용해서 disk에 저장이 되는 것을 보장하게 된다. GFS의 2.6.3 Operation Log에서는 여러개의 Operation Log를 주기적으로 checkpoint로 merge해서 저장한다는 내용이 나온다. 장애가 발생한 상황에서 가장 마지막 checkpoint + 아직 checkpoint로 저장되지 않은 Operation Log만 빠르게 로딩해서 recovery를 빠르게 하고 availability를 개선한다는 내용이다.

The checkpoint is in a compact B-tree like form that can be directly mapped into memory and used for namespace lookup without ex-tra parsing. This further speeds up recovery and improves availability.

MemoryMappedFile이 무엇이길래 recovery가 빨라지고 availability가 개선된다는걸까? 이 부분을 이해하기 위해 우선 CS 개념을 다시 리마인드해보았다.

CPU, Memory, Disk의 동작 과정

기초 개념부터 다시 훑어봤지만 여기서는 간단하게 정리해보려고 한다.

CPU - Register - L1/L2/L3 Cache - Memory - Disk 순서대로 데이터가 접근된다
Memory는 Logical Memory, Physical Memory로 구분된다
CPU가 처리하는 연산자 + 데이터 는 16 bit이다.
Memory의 주소 공간은 1 Byte 단위이고, 연산자 + 데이터는 2개의 메모리 주소 공간에 나누어서 저장된다.
32 Bit CPU에서는 최대 4GB의 메모리를 사용할 수 이었고, 64 Bit CPU는 64개 bit로 구성된 주소를 처리할 수 있게 되었다.
Memory는 Logical Address Physical Address로 나뉘어진다.
Process는 각자 독립적인 Logical Address를 가지고 Access할 때 Physical Address로 변환되어서 사용된다.
Page는 Virtual Memory를 고정 크기로 나눈 것이고 Frame은 Physical Memory를 구정 크기로 나눈 것이다.
메모리에서 Page, Frame은 동일한 사이즈를 가지고, Disk에서도 메모리에 로딩하기 위해 동일한 크기만큼 Page가 로딩된다.
Memory와 Disk 사이에는 Page Cache가 존재한다. 불필요한 Disk IO를 OS 레벨에서 제어하는 역할을 한다.
Page Cache가 점유하고 있는 메모리 크기는 free -h로 확인 가능하다.

Read, Write의 동작 과정

Application에서 일반적인 File I/O를 하는 과정에서는 2가지 Buffer가 사용된다. Application Level에서 선언한 Byte Buffer (User Buffer), Page Cache라고 불리는 Kernel Buffer이다. 일반적인 Write에서는 Application User Buffer -> Kernel Buffer 로의 copy가 1번 일어나고, Kernerl Buffer에서 Disk로 write-back하면서 한 번 더 copy가 일어난다. Read에서도 Disk -> Kernel Buffer -> User Buffer로 copy가 2번 일어난다. (Disk에서 Kernel Buffer로의 이동도 Hardware에서 Kernel Buffer로의 이동이기 때문에 copy의 종류라고 생각했다.)

MemoryMappedFile에서는 UserBuffer를 사용하지 않는다. Application에서 MemoryMappedFile을 선언하면 Virual Memory 영역에 Disk에 저장된 File에 대한 참조가 생성된다. 그리고 처음으로 접근할 떄 Page Fault가 발생하고 Disk -> Kernel Buffer로의 Page 이동이 일어난다. 그리고 그 이후에는 OS의 Page 정책에 따라서 File의 필요한 부분만 Kernel Buffe로 로딩된다.

Memory Mapped I/O를 사용하는 이유

UserBuffer를 사용하지 않기 떄문에 COPY가 1번이라서 I/O가 더 빠르다.
GFS에서는 without ex-tra parsing 라고 표현했는데, Application Memory에서 객체로 관리하기 위한 Binary -> Object로의 변환 과정도 없이 바로 필요한 값에 접근할 수 있다. 이렇게 binary에서 필요한 값을 바로 찾기 위해서는 byte 단위로 데이터가 어떻게 저장되어 있는지를 다루는 specification이 내부적으로 정의되어 있을듯하다.
File 사이즈가 1GB라도 OS의 Page 전략에 따라 File 전체가 Kernel Buffer에 로딩되지 않고도 사용될 수 있다. Application에서 RandomAccess나 Stream을 통해서 File 전체를 User Buffer에 로딩하지 않고 사용할 수 있다면, Kernel Buffer에서는 Paging을 사용해서 File에서 필요한 부분만 로딩해서 사용한다.

Native Memory vs Direct Memory

JVM 기준으로 생각해보면 MemoryMappedFile은 Heap을 사용하지 않는다. Native memory라고도 하고 Off-heap이라고도 한다. 중요한 점은 GC의 영향 범위를 벗어난 영역이라는 점이다. Direct Memory는 Native Memory랑 동일하게 Heap을 사용하지 않는다. Direct Memory는 Disk와 같은 H/W와의 상호작용을 암시하는 의미를 가진다. JVM에서 Heap 밖의 영역을 사용할 때 Application에서 직접 메모리 관리를 컨트롤하기 위한 목적으로 사용한다면 Native Memory를 사용한다고 할 수 있다. 반면 SSD, Network와 같이 하트웨어 장비에 mapping해서 사용하기 위한 목적이라면 똑같이 Off-Heap을 사용하지만 Direct Memory를 사용한다고 표현하는 것이 더 적합하다.

Reference

https://www.youtube.com/watch?v=K9L9YZhEjC0

Google File System 리뷰

행운개발자 — Sun, 20 Apr 2025 22:46:02 +0900

요즘 GFS 논문을 읽어보고 있다. 흥미롭지만 어려워서 여러번 반복해서 읽으면서 정리를 해보고 있다. 아직 이해 제대로 못한 부분이 많지만 부족하게라도 일단 글을 발행해야겠다.

현재 시점에서 가장 인상 깊은 점은 두가지이다.

대부분의 'Operation이 Master의 오버헤드를 줄이는 방향으로 설계되었다'
Relaxed Consistency Model에서 Consistency/InConsistency와 Defined/Undefined의 개념을 구분했다.

이 외에도 Single Master에서 모든 Metadata를 메모리로 관리하는 점, GFS를 사용하는 Application Level에서 Write를 하고 Rename을 하도록 권장하고 있는데 알고보니 일반적인 파일 다운로드에서도 수행되고 있는 연산인 점, Distributed Lock Manager 없이 Lease의 개념을 도입해서 Consistency Model을 달성한 점이 재미있다.

아래는 아직 해결하지 못한, 애매하게 알고 있는 개념들이다. 그리고 더 아래에는 GFS를 읽으면서 정리한 내용이 아직 draft 상태로 정리되어 있다.

내일 출근길에 마저 읽고 정리해봐야겠다. 후

Question

동일 chunk에 대한 추가 read는 캐시 유효 기간이 지나거나 파일이 다시 열릴 때까지 master와의 상호작용 없이 수행됩니다.

파일이 다시 열릴 때는 왜 Client Side의 Chunk Index Cache가 만료될까?

master는 64 MB chunk당 64 bytes 미만의 metadata만 유지하며, 파일 이름은 prefix compression으로 저장되어 파일당 64 bytes 미만의 메모리를 차지합니다.

prefix compression이 뭐지?

client가 캐시된 replica 위치로 stale replica에 접근할 수 있는 창이 있으나, cache 만료 또는 파일 재오픈 시 새 위치를 받아 consistency가 회복됩니다. append-only 파일은 stale replica가 premature end-of-chunk만 반환해 outdated data를 거의 노출하지 않습니다.

부족한 데이터를 반환하는게 왜 문제가 안되지? 그리고 lease에 의해서 ordered replica로 동작하면 stale replica는 어떻게 발생하고 대응되는거지? write 연산은 어떻게 되는거지?

record append의 at-least-once semantics는 각 writer의 출력을 보존합니다

master는 때때로 lease가 만료되기 전에 취소를 시도할 수 있다(예: 파일이 rename되는 동안 mutation을 중단하고 싶을 때).

가정

친숙한 파일 시스템 인터페이스를 제공함
- create, delete, open, close, read, write
POSIX 같은 표준 API는 구현하지 않음
snapshot : 낮은 비용으로 디렉터리 트리를 복사함
mutation = write or record append
record append : 여러 클라이언트가 동시에 같은 파일에 데이터를 Append 할 때, 각 클라이언트의 Append를 Atomic하게 보장함
- 추가적인 locking 없이 여러 클라이언트가 동시에 Append를 할 수 있음

Architecture

GFS 클러스터는 Single Mater와 Multi Chunk Server로 구성됨
여러개의 Client가 GFS 클러스터에 접근할 수 있음
Client
- 각 애플리케이션에서 파일 시스템 API를 구현함
- master와 chunkserver에 메타데이터 및 데이터 작업을 요청함
- POSIX API를 제공하지 않아서 Linux vnode 레이어와 연동할 필요가 없음
- Metadata 연산은 Mater와 수행함
- Data 연산은 Chunk Server와 수행함
- Metadat는 캐싱하지만, Chunk 데이터는 캐싱하지 않음
Master
- 하나의 File이 여러개의 Chunk로 나누어지고, 각 Chunk마다 64bit의 Chunk Handle로 식별할 수 있음
- 모든 파일 시스템의 Metadata를 메모리에 관리함
Metadata
- File Namesapce
  - File Namespace 별로 다른 Replication Level을 지정할 수 있음
- Access Control
- File To Chunk Mapping
- Chunk Location 관리
- Chunk Lease 관리
- Orphan Chunk GC
- Chunk Migration
- HeartBeat : 모든 ChunkServer와 통신하여 상태를 수집하고 명령을 전달함
Chunk Server
- Chunk를 Linux File로 저장함
- Chunk Handle + Byte Range를 전달받아서 데이터를 Read, Write를 수행함
- 데이터를 Linux File에 저장하므로 Linux Buffer Cache가 자주 접근되는 데이터를 메모리에 유지함
  - Assumption에서 동일한 파일에 대한 Heavy Operation이 가정됨
Chunk
- 각 File은 Fixed Size Chunk로 분할됨
- 각 Chunk는 여러개의 Chunk Server에 Replication 되어 저장됨 (default replica size 3)

Single Master

단 하나의 Master만 존재함
모든 Metadata 정보를 메모리에 관리하여 빠른 연산을 수행함
Read/Write의 과정에서 개입을 최소화하여 병목이 되지 않아야 함
Client로부터 FileName, Chunk Index를 전달받아서 Chunk Handle, Chunk Replica의 위치를 응답함
- Chunk Index : Fixed Chunk Size를 사용해서 Client가 직접 계산함
Client로부터 여러개의 Chunk에 대한 정보를 요청받아서 Client와 Master 사이의 연산을 최소화할 수 있음

Client : FileSize, Fixed Chunk Size로 ChunkIndex를 계산
Client -> Master : FileSize, Chunk Index 전달
Master -> Client : Chunk Handle, Chunk Replica Location 반환
Client : 전달받은 정보를 Caching (캐시 유효 기간이 끝나거나, 파일이 다시 열릴 때까지)
Client -> Chunk Server : 가장 가까운* Chunk Server에게 Chunk Handle, Byte Ranage를 전달해서 Read/Write
- 가장 가까운 : TODO

Chunk Size

64MB의 고정된 사이즈 : 전통적인 파일 시스템의 사이즈보다 배우 큰 사이즈
장점
- 동일한 Chunk에 대한 Read/Write를 수행할 때 최초 한번만 Master와의 상호작용을 하게 됨. 대부분의 요청이 대용량 파일에 대한 순사 처리이기 때문에 특히 효율적임
- 같은 Chunk에서 다수의 연산이 수행될 가능성이 높아서, ChunkServer와 TCP 연결을 장시간 유지함으로써 네트워크 오버헤드를 줄일 수 있음
- Master에서 관리해야하는 Metadata의 갯수가 줄어들어서 Master에서 사용해야하는 메모리의 사이즈가 감소하는 영향이 있음
단점
- 작은 파일은 하나의 Chunk로 구성될 수 있음. 이때 이 Chunk를 가지고 있는 Chunk Server가 HotSpot이 될 수 있음.
사례
- GFS가 Batch Queue System으로 사용되는 경우, 동일한 Executable에 대해서 수백개의 Client가 Read 요청을 할 때 하나의 Chunk Server로 요청이 몰리는 현상이 발생함
대응
- 해당 Executable에 대한 Replication의 갯수를 늘리고, Batch 시작 시간은 Stagger하도록 변경

Metadata

주요 Metadata 3가지
1. File 및 Chunk Namespace
2. File - Chunk Mapping
3. 각 Chunk Replica Location
모든 Metadata를 Memory에서 관리함
처음 2가지는 Local Disk + Operation Log에 저장되고 원격 머신에 복제되어 영속성 및 일관성을 보장함
- 원격 머신에 복제 : Single Master라고 했지만, Metadata 연산에 참여하는 것은 Single Master이고 가용성을 위해서 Master도 Replica로 존재하는 듯함
Chunk Replica Location은 Chunk Server에게 질의해서 최신 정보를 조회함 (Master가 시작할 때, Chunk Server가 추가/삭제될 때)
In-Memory Data Structure
- 모든 Metadata를 메모리에 관리하므로 master의 작업이 빠름
- 주기적으로 Chunk의 상태를 스캔해서 Chunk GC를 수행할 수 있음
- Chunk Server의 장애시, Chunk Re-Replication을 수행할 수 있음
- Load, Disk의 균형을 위해서 Chunk Migration을 수행할 수 있음
- 단점
  - 메모리 사용량이 시스템 용량을 제한할 수 있음
  - 하지만 Chunk Size 64 MB 당 Metadata는 64 Bit미만이고, FileName은 Prefix Compression으로 저장되어 파일당 64 Bytes 미만의 메모리를 차지함
  - 필요하다면 Master 메모리를 추가하는 비용은 단순함, 신뢰성, 성능, 유연성을 고려할 때 합당한 대가로 판단됨
Chunk Location
- Master는 어떤 Chunk Server가 특정 Chunk Replica를 가지고 있는지 저장하지 않음 (Metadata의 3번째 항목)
- Master의 시작, Chunk Server의 추가/삭제에서 HeartBeat 메시지로 Chunk Placement를 제어하여 최신 정보를 유지함
- 실제로 Chunk Server가 갖고 있는 최종 정보는 해당 서버만 알기 때문에, Master가 이를 일관되게 유지하려는 시도는 불필요함

Operation Log

Metadata의 영속적인 기록이고, 동시 작업의 순서를 정의하는 Logical Time의 역할을 수행함
- Logical Time
  - 작업의 선후순서만을 보장하는 Time, 각 Operation과 그 사이의 시간을 측정하지 않음
  - File, Chunk, Version에 따라서 unique하게 부여됨
Operation Log가 특히 중요하기 때문에 Local Disk, 원격 Disk에 모두 Flush한 뒤, Client의 요청을 처리함
여러개의 Record를 묶어서 Flush하여 성능 영향을 최소화 함
Checkpoint
- 복구의 과정은 checkpoint와 이후의 log 파일 상태만 재생해서 빠르게 복구할 수 있음
- 별도의 쓰레드에서 여러개의 Record를 묶어서 Checkpoint를 생성하여 incoming mutation을 지연시키지 않음.
- 수백만 파일 규모에서도 수 분 이내에 완료됨
- 불완전한 checkpoint는 복구 과정에서 자동으로 무시됨

Consistency Model

Relaxed Consistency Model

Gurantees by GFS

- File Namespace 변경 (파일 생성) : Atomic, Master가 Namespace Locking으로 일관성을 보장함. Operation Log가 global하게 순서를 정의함
- Data Mutation : mutation 유형, 성공 여부, 동시성 상황에 따라서 달라짐
    - A file region is consistent if all clients will always see the same data, regardless of which replicas they read from. 
    - A region is defined after a file data mutation if it is consistent and clients will see what the mutation writes in its entirety
    - Defined : 모든 클라이언트가 동일한 데이터를 읽음
    - 여러개의 Mutation이 동시에 성공하면 undefined  but consistent 상태가 됨
    - 실패한 Mutation은 inconsistent 상태로 만듦
- Write : 지정한 offset에 데이터를 저장함
- Append : Client가 아닌 GFS가 선택한 offset에 데이터를 Atomic하게 Append하고 Offset을 반환함
    - Record가 Chunk의 끝을 넘는 경우 Padding이 추가될 수 있음
    - 일부 Replica에 대해서 append가 실패하는 경우, 동일한 Record가 중복되어서 저장될 수 있음
- Defined = Consistency가 2가지 요소로 만족됨 
    - 모든 Replica에 대해서 동일한 순서대로 Mutation을 적용함
    - Chunk Version Number로 오래된Stale Replica를 배제함

Stale Replica // TODO

- Client의 요청에서 제외되고, Chunk GC에서 제거됨
- Client에 캐싱된 Chunk Handle에 Stale Replica가 포함된 경우, Cache 만료 또는 File 재오픈할 때 consistency가 회복됨
- Stale Replica가 가지고 있는 Chunk Version Number는 정상 Replica보다 작아서 Master에서 반환하는 Replica에서 제외됨
- Stale Replica의 경우 오래된 Offset을 가지고 있어서 premature end-of-chunk만을 반환하고, 오래된 데이터를 잘못 제공하지는 않음

Lease and Mutation Order

mutation은 write, append operation과 같이 chunk의 내용 또는 metadata의 내용을 변경하는 연산
각 mutation은 해당 chunk의 모든 replica엑서 수행됨
replica 사이의 일관된 mutation 순서를 보장하기 위해 lease의 개념을 사용함
master는 replica 중 하나를 chunk lease로 지정하고 primary 라고 부름
primary는 chunk에 대한 모든 mutation에 대한 순서를 지정하고, 모든 replica는 이 순서에 따라서 mutation이 수행됨
따라서 global mutation의 순서는 MAster가 부여한 Lease의 순서에 따라서 수행되고, 각 Mutation에 대한 순서는 primary가 할당한 순서에 따라서 결정됨

Lease 메커니즘

master의 관리 오버헤드를 최소화하기 위해서 설계됨
lease의 초기 timeout = 60초. 단, chunk가 계속해서 변형되는 한 primary는 master로부터 lease를 연장해서 계속 사용할 수 있음. 이 과정은 Master, Chunk Server 사이의 Heart Beat를 통해서 처리됨
master와 primary가 통신이 끊어져도 lease가 안료된 이후에 안전하게 다른 replica에 새 lease를 부여할 수 있음

Client -> Master : Lease를 보유한 Chunk Server와 다른 Replica의 위치 정보를 조회
Master -> Client : Master는 Lease가 없을 때 생성해서 응답함. Primary ID, Secondary Replica의 위치를 응답
Client : 이 정보를 캐싱하여 primary가 unreachable하거나 더이상 lease를 보유하지 않는다고 응답할 때까지 master와 다시 통신하지 않음
Client -> Chunk Server : 모든 Replica에 데이터에 ID를 부여하고 Push. Primary가 정의한 순서와는 무관하게 데이터를 전송
Chunk Server -> Client : LRU Buffer Cache에 데이터를 보관. 데이터를 수신함을 ACK
Client -> Primary : 모든 Replica가 ACK을 보내면 Primary에게 데이터 ID와 함께 Write 요청을 전송
Primary -> Secondary : 모든 Write 요청을 정의한 순서에 따라서 Secondary에게 전달
Secondary -> Primary : ACK
Primary -> Client : 최종 응답을 전송

에러가 발생하는 경우 4~8의 과정을 retry하고 필요하면 전체 과정을 retry
만약 어플리케이션의 Write 연산이 대용량이거나 Chunk 사이즈를 넘는 경우, 여러개의 Write로 분할됨.
여러개의 Client들의 동시성 연산에 의해서 섞이거나 덮어써질 수 있음.
하지만 모든 Replica에는 동일한 연산이 적용되어서 undefined이지만 consistency가 보장될 수 있음

Data Flow

data flow가 control flow와 분리되어 네트워크를 효율적으로 사용할 수 있음
목표 : 머신 전체의 네트워크 대역폭을 활용하고, 병목 및 높은 대기 구간을 피하고, 모든 데이터를 전달하는게 걸리는 지연 시간을 최소화하는 것
각 머신의 full outbount 대역폭을 활용하기 위해서 데이터는 tree가 아닌 chain 형태로 전달됨
네트워크 병목과 높은 대기 구간을 피하기 위해서 각 머신은 가직 데이터를 수신하지 않은 가장 가까운 머신에 데이터를 전달함
- client가 serve 1~4에 데이터를 보낼 때 client -> s1 -> s2 -> s3 -> s4 순서대로 전달함
- IP 주소로부터 토폴로지 상의 거리를 추정할 수 있음
TCP 연결을 파이프라이닝하여 latency를 낮춤. chunk sever는 데이터를 받으면 곧바로 다음 머신으로 전달을 시작함
- B 바이트를 R개의 Replica에 대해서 전송할 때 B 바이트 / T 네트워크 처리량 + R 리플리카 수 * L 머신 간 대기 전송 시간만큼이 걸림

Atomic Record Append

GFS는 Record Append라는 Atomic Append를 제공함
Write에서는 Offset을 Client가 지정하지만, concurrent write에서는 간섭이 발생해서 offset 사이에 영역이 섞일 수 있음
Record Append에서는 Client가 데이터를 작성하면 GFS가 자차적으로 선택한 Offset에 Atomic하게 최소 한 번 이상 Append하고, 그 offset을 반환함
분산 환경에서 여러 Client가 동일한 파일에 Append를 하는 경우, 분산 락 Manager가 필요하지만, Record Appender에서는 primary에서 약간의 로직만 추가해서 이를 해결한다
Client가 Chunk에 대한 Append를 Primary에게 요청할 때, Primary는 현재 Chunk가 최대 크기를 넘지 않는지 확인한다
넘는다면 현재 chunk를 padding하고 secondary에게도 padding을 지시한다. 그리고 그 다음 append를 실행한다.
Record의 크기를 Chunk의 최대 1/4 사이즈로 제안하여 디스크 fragmentation을 최소화한다.
Record가 MAX를 넘지 않으면 Secondary에게까지 Append하고 Offset을 전달한다

Primary가 모든 Replica에 대해서 동일한 Offset을 보장함으로서 Atomic한 연산을 보장하게 된다.
중복된 레코드가 남아서 inconsistency한 영역이 생기거나 offset이 record의 길이만큼 늘어나지 않을 수는 있다.
하지만 이 부분은 Application 레벨에서 Checksum, UniqueID를 사용해서 검증할 수 있으므로 Defined Region의 개념에는 어긋나지 않는다.

Implications for Applications

Checkpoint : 지금까지 성공적으로 파일에 데이터를 Write한 Offset
애플리케이션이 중간에 실패해도 Checkpoint 이후부터 다시 쓰면 됨
Checkpoint까지만 읽으면 됨
CheckSum : CheckPoint 별로 현재까지 데이터로 만든 CheckSum을 저장해둔다
Atomic Rename : 멀티파트 Write를 할 때 mv /tmp/data.part /data/finalname 처럼 atomic rename
대부분 애플리케이션은 overwrite 대신 append 방식으로 파일을 생성·수정합니다. writer는 처음부터 끝까지 파일을 작성한 뒤, atomic rename으로 영구 이름을 부여하거나 주기적으로 checkpoint를 기록합니다. checkpoint에는 애플리케이션 수준 checksum도 포함될 수 있습니다. reader는 정의된 상태가 보장된 마지막 checkpoint까지의 데이터만 처리합니다. 이 방식은 append가 random write보다 효율적이고, 실패에 더 강건하다는 장점이 있습니다. checkpoint는 writer 재시작을 용이하게 하고, reader가 incomplete 데이터를 읽지 않도록 합니다.
또 다른 전형적 사용은 다수의 writer가 병렬로 append해 merge 결과나 queue를 구성하는 경우입니다. record append의 at-least-once semantics는 각 writer의 출력을 보존합니다. reader는 checksums 기반으로 padding과 중복 record를 식별·제거하며, idempotency가 필요한 경우 record 내부의 unique identifier로 필터링할 수 있습니다. 이러한 record I/O 기능은 Google 내부 라이브러리 코드로 제공되어, 다른 파일 인터페이스 구현에서도 활용됩니다. 이로써 희소한 중복을 제외하면 동일한 record 시퀀스가 항상 전달됩니다

Keep Alive를 사용한 Connection Closed 대응 과정

행운개발자 — Sat, 19 Apr 2025 13:57:46 +0900

어느날 아래와 같은 오류가 발생했습니다. 결론적으로는 Keep Alive 설정에 문제가 있었습니다.
앞으로는 비슷한 오류가 발생하지 않도록 대응했던 과정을 정리해보겠습니다.

2025-04-16T01:58:49.626Z
[ERROR][2.0.1][tp-epoll-2] .s.i.h.a.o.g.XXXXXXClient : invoke Sending mutation failed: error=org.springframework.web.reactive.function.client.WebClientRequestException: recvAddress(..) failed: Connection reset by peer

2025-04-16T02:13:42.896Z
[ERROR][2.0.1][tp-epoll-1] s.i.h.a.s.XXXXXXXService : uploadXXXXXX$lambda$28 Connection has been closed BEFORE response, while sending request body

2025-04-16T02:14:21.254Z
[ERROR][2.0.1][tp-epoll-3] s.i.h.a.s.XXXXXXXService : invoke Failed to complete analysis: analysisJobId=XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX XXXXXServerId=XXXXX errorMessage=Retries exhausted: 2/2 metric=
{
    "type": "XXXXXXXXXMetric",
    "eventType": "FAILED",
    "instanceId": "i-XXXXXXXXXXXXXXX",
    "autoScalingGroup": "XXX-XXXX-XXXX-XXXX"
}

상황

먼저 대략적인 서버의 구조는 아래와 같은 상황이었습니다. 에러 로그가 발생한 곳은 Server A입니다.

Client - Server A - Server B

Client는 Server A에게 요청을 보냅니다. Server A는 요청을 받으면 S3로부터 Image를 다운로드 받아서 Server B로 Upload 합니다.
S3로부터 Image를 Streaming 방식으로 다운로드 받은 뒤에 바로 Server B에게 MultiPart Upload를 하는 형태입니다.

분석

에러 로그는 두 가지 종류가 있습니다.

Connection reset by peer
Connection has been closed BEFORE response, while sending request body

첫 번째 로그는 'Server A가 사용하고 있는 연결을 Server B가 끊었다'는 뜻입니다. 두 번째 로그는 'Server A가 File Upload를 하고 있는 도중에 연결이 끊어졌다'는 뜻입니다. 두 에러는 사실 같은 원인으로 발생하고 있었습니다. 바로 KeepAlive 설정입니다.

Checking for dead peers를 보면 KeepAlive가 필요한 상황이 잘 나와있습니다. 요역해보면 다음과 같습니다.

Server A와 Server B가 연결을 맺음
Server A는 연결된 커넥션을 커넥션 풀에 넣어서 사용함
일정 시간이 지난 뒤에 Server B는 연결되었지만 데이터 전송이 없는 커넥션을 종료함
Server B는 연결을 종료했지만 Server A는 이를 알지 못하는 상황이 발생
Server A에서 커넥션 풀에서 커넥션을 조회해서 Server B로 데이터 전송을 시도
Server B는 종료된 연결로부터 데이터가 수신되었기 때문에 RST 패킷을 전송
Server A는 커넥션 풀에서 커넥션을 조회해서 사용했음에도 RST 패킷을 받아서 연결 종료 (에러 로그 1번)
또는 Server A가 데이터를 전송하고 있는 도중에 Server B에서 일정 시간이 지난 뒤에 연결을 종료함 (에러 로그 2번)

_____                                                     _____
|     |                                                   |     |
|  A  |                                                   |  B  |
|_____|                                                   |_____|
    ^                                                         ^
    |--->--->--->-------------- SYN -------------->--->--->---|
    |---<---<---<------------ SYN/ACK ------------<---<---<---|
    |--->--->--->-------------- ACK -------------->--->--->---|
    |                                                         |
    |                                       system crash ---> X
    |
    |                                     system restart ---> ^
    |                                                         |
    |--->--->--->-------------- PSH -------------->--->--->---|
    |---<---<---<-------------- RST --------------<---<---<---|
    |                                                         |

원인

위와 같은 문제가 발생한 워인은 Server A에서 TCP KeepAlive 설정을 지정하지 않았기 때문에 발생했습니다. KeepAlive 설정을 지정하지 않으면 KeepAlive가 자동으로 활성화되고 아래와 같은 기본값이 사용됩니다.

$ cat /proc/sys/net/ipv4/tcp_keepalive_time
7200
$ cat /proc/sys/net/ipv4/tcp_keepalive_probes
9
$ cat /proc/sys/net/ipv4/tcp_keepalive_intvl
75

위 설정은 커넥션이 연결되고 tcp_keepalive_time 시간이 지난 뒤부터, tcp_keepalive_intvl의 간격으로 tcp_keepalive_probes번 duplicated ACK을 전송하겠다는 뜻입니다. linux의 tcp_keepalive_time의 기본값이 2시간(7200)으로 설정되어 있기 때문에 한 번 연결된 커넥션은 커넥션 풀에 (2시간 + 75초 * 9)동안 살아있습니다.

Server A에서는 2시간이 넘는 시간동안 동일한 커넥션을 유지하고 사용하려고 하는데, 이미 Server B로에는 종료된 커넥션이기 때문에 RST 패킷을 받고 연결이 끊어지는 현상이 발생한 것입니다. (에러 로그 1번) 그리고 이 타이밍이 데이터를 전송하고 있는 순간(markSentBody)이었다면 에러로그 2번이 발생한 것입니다.

// reactor.netty.http.client.HttpClientOperations#onInboundClose
    @Override
    protected void onInboundClose() {
        ...
            else if (markSentBody()) {
                exception = new PrematureCloseException("Connection has been closed BEFORE response, while sending request body");
        ...
    }

대응

projectreactor http-client document에는 keep alive 설정을 하는 방법이 나와있습니다. NIO transport와 Epoll transport 중 어떤 것을 사용하는지에 따라서 설정값이 달라진다고 되어있습니다. 저는 에러 로그에 [ERROR][2.0.1][tp-epoll-2] 이라고 나와있어서 epoll을 사용하는 것을 바로 알 수 있었습니다.

public class Application {

public static void main(String[] args) {
    HttpClient client =
        HttpClient.create()
            .bindAddress(() -> new InetSocketAddress("host", 1234))
            .option(ChannelOption.CONNECT_TIMEOUT_MILLIS, 10000) 
            .option(ChannelOption.SO_KEEPALIVE, true)            
            // The options below are available only when NIO transport (Java 11) is used
            // on Mac or Linux (Java does not currently support these extended options on Windows)
            // https://bugs.openjdk.java.net/browse/JDK-8194298
            //.option(NioChannelOption.of(ExtendedSocketOptions.TCP_KEEPIDLE), 300)
            //.option(NioChannelOption.of(ExtendedSocketOptions.TCP_KEEPINTERVAL), 60)
            //.option(NioChannelOption.of(ExtendedSocketOptions.TCP_KEEPCOUNT), 8);
            // The options below are available only when Epoll transport is used
            .option(EpollChannelOption.TCP_KEEPIDLE, 300)        
            .option(EpollChannelOption.TCP_KEEPINTVL, 60)        
            .option(EpollChannelOption.TCP_KEEPCNT, 8);

keepalive 설정을 지정하는 방법은 알았으니, 어떤 값으로 지정할지를 결정해야합니다. 그런데 Serer B의 시스템은 외부 시스템이라서 정확한 Timeout을 알 수 없는 상황입니다. 그래서 좀 reference를 찾아보니 IBM TCP/IP settings에서 두 가지 기준을 발견했습니다.

firewall의 connection timeout보다 작은 값으로 지정해야 한다
정확한 값을 모르는 경우 2분으로 지정하고 검증하라

The parameters that control the keep alive frequency vary with each operating system. You must set the keep alive interval value lesser than the connection timeout value of the firewall. If you do not know the value of the firewall setting, set keep alive interval value to 2 minutes and verify.

firewall의 connection timeout보다 작은 값으로 지정해야한다는 점은 Serer B에서 주기적으로 연결을 끊는 시간보다 짧은 시간을 설정해야함을 의미합니다. Server B가 이미 연결을 끊은 뒤에 keepAlive를 체크한다면 매번 RST를 받고 의미가 없게 된다는 뜻입니다. 결론적으로 (2분은 너무 짧은 것 같아서) keepalive의 값은 위 코드에서 제사힌 300, 60, 8 의 값을 그대로 사용해보기로 결정했습니다.

고려사항

keepalive의 값을 지정할 때 다양한 timeout의 시간을 고려해야하는지 따져봤습니다.

client의 connection timeout : keepavlie는 connection이 연결된 이후에 동작하기 때문에 client의 connection timeout과는 무관합니다.
HttpClient의 ReadTimeout, WriteTimeout : Server A와 Server B가 주고 받는 데이터가 커서 ReadTimeout, WriteTimeout을 좀 크게 지정한 상황입니다. 하지만 KeepAlive Timeout에는 영향을 주지 않습니다. KeepAlive는 TCP 레벨에서, ReadTimeout/WriteTimeout은 HTTP 레벨에서 동작합니다. 두 Timeout이 겹치더라도 KeepAlive를 ACK만 보내기 때문에 Read/Time 트레픽에 큰 영향을 주지 않을 것입니다.

좀 더 깊게 알아보기

Preventing disconnection due to network inactivity에는 NAT Proxy를 사용하는 환경에서 네트워크 끊김을 방지하기 위한 노하우를 소개합니다. 당장 필요한 상황은 아니지만 한 번 정리해봤습니다.

|     |         |     |                                   |     |
|  A  |         | NAT |                                   |  B  |
|_____|         |_____|                                   |_____|
    ^               ^                                         ^
    |--->--->--->---|----------- SYN ------------->--->--->---|
    |---<---<---<---|--------- SYN/ACK -----------<---<---<---|
    |--->--->--->---|----------- ACK ------------->--->--->---|
    |               |                                         |
    |               | <--- connection deleted from table      |
    |               |                                         |
    |--->- PSH ->---| <--- invalid connection                 |
    |               |                                         |

위와 같은 상황에서 Server A에서 가지고 있는 연결은 아무 이유도 없이 끊어질 수 있습니다. 이러한 원인은 NAT에서 '모든 연결을 모두 메모리에 관리할 수는 없다'는 현실적인 이유에서 발생합니다. NAT 입장에서 가장 일반적이고 현실적인 접근은 오래된 커넥션은 끊고 가장 최신의 연결만 유지하는 것입니다. 이러한 상황에서 Server A와 Server B 사이에 TCP 연결을 계속 유지해야하는 경우에도 NAT의 정책에 따라서 우선순위가 밀려서 연결이 끊어질 수 있습니다. 이러한 경우에는 A와 B 사이에 일정 간격으로 의미없는 데이터를 지속적으로 주고 받는 방법이 있습니다. 이렇게 되면 지속적으로 커네션이 최신화되고 NAT에서 제외될 가능성이 줄어드는 효과를 가지게 됩니다.

이러한 Heartbeat는 IdleStateHandler를 사용해서 구현할 수 있습니다. IdleStateHandler는 일정 시간동안 데이터가 없으면 IDLE 이벤트를 발생시켜줍니다.

readerIdleTime 동안 inbound 데이터가 없으면 READER_IDLE 이벤트
writerIdleTime 동안 outbound 데이터가 없으면 WRITER_IDLE 이벤트
allIdleTime 동안 어느 쪽도 이벤트가 없으면 ALL_IDLE 이벤트

connection
    .addHandlerLast(IdleStateHandler(0, 30, 0, TimeUnit.SECONDS))
    .addHandlerLast(object : ChannelDuplexHandler() {
        override fun userEventTriggered(ctx: ChannelHandlerContext, evt: Any) {
            if (evt is IdleStateEvent && evt.state() == IdleState.WRITER_IDLE) {
            // 30초 동안 쓸 데이터가 없으면 의미없는 데이터 전송
            ctx.writeAndFlush(Unpooled.wrappedBuffer("\r\n".toByteArray()))
            }
        }
    })

Block/File/Object Storage 그리고 Goofys(Fuse)

행운개발자 — Mon, 14 Apr 2025 22:40:51 +0900

저장소 시스템 종류

저장소 시스템 종류에는 크게 3가지가 있다.

block storage
file storage
object storage

세 가지 종류의 storage의 차이점을 이해해보자. 그리고 Fuse가 무엇이고 어떤 경우에 사용되는 것인지까지 이해해보자. 먼저 각 Storage에 대한 개념적인 설명이다.

block storage

HDD나 SSD처럼 서버에 물리적으로 연결되는 형태의 드라이브는 블록 저장소의 가장 흔한 형태이다. 블록 저장소는 raw block을 서버에 volume의 형태로 제공한다. 가장 유연하고 융통성이 놓은 저장소다. 서버는 raw block을 포맷한 다음 파일 시스템으로 이용하거나 애플리케이션에 블록 제어권을 넘겨버릴 수도 있다. 데이터베이스나 가상 머신 엔진 같은 애플리케이션은 raw block을 직접 제어하여 최대한의 성능을 끌어낸다.

블록 저장소는 서버에 물리적으로 직접 연결되는 저장소에 국한되지 않는다. 고속 네트워크를 통해 연결될 수도 있고, 업계 표준 연결 프로토콜인 FC(Fiber Channel)이나 iSCSI를 통해 연결될 수도 있다. 개념적으로 보자면 네트워크를 통해 연결되는 블록 저장소도 원시 블록을 제공한다는 점에서 다르지 않다. 서버 입장에서 보면 물리적으로 연결된 블록 저장소와 마찬가지로 동작한다.
네트워크를 통해서 연결되는 저장소라고 하면 NFS가 먼저 떠오르는데, NFS는 block storage가 아니가 file storage의 한 종류이다.

가상 머신, 데이터 베이스 같은 높은 성능이 필요한 애플리케이션에 사용된다.

file storage

파일 저장소는 블록 저장소 위에 구현된다. 파일과 디렉토리를 쉽게 다루는 데 필요한 더 높은 수준의 추상화를 제공한다. 데이터는 데이터의 계층으로 표현하는 디렉토리 안에 보관된다. 파일 저장소는 가장 널리 사용되는 범용 저장소 솔루션이다. SMB/CIFS나 NFS와 같은 파일 수준 네트워크 프로토콜을 사용하면 하나의 저장소를 여러 서버에 동시에 붙일 수도 있다. 파일 저장소를 사용하는 서버를 블록을 직접 제어하고, 볼륨을 포맷하는 등의 까다로운 작업을 신경 쓸 필요가 없다. 파일 저장소는 단순하기 때문에 폴더나 파일을 같은 조직 구성원에 공유하는 솔류션으로 사용하기 좋다.

범용적 파일 시스템 접근이 필요한 곳에 사용된다.

object storage

객체 저장소는 새로운 형태의 저장소다. 데이터 영속성을 높이고 대규모 애플리케이션을 지원하며 비용을 낮추기 위해 의도적으로 성능을 희생한다. 실시간으로 갱신할 필요가 없는 상대적으로 cold 데이터 보관에 초점을 맞추며 데이터 아카이브나 백업에 주로 쓰인다. 모든 데이터를 수평적 구조 내에 객체로 보관한다. 계층적 디렉터리 구조는 제공하지 않는다. 데이터 접근은 보통 RESTful API를 통한다. 다른 유형의 저장소에 비해 상대적으로 느리다.

바이너리 데이터, 구조화되지 않은 데이터의 저장에 사용된다.

Goofys

Goofys allows you to mount an S3 bucket as a filey system.

Goofys Github에 소개된 내용이다. file storage가 block storage 위에 구현되는 것은 이해할 수 있다. 그런데 object storage를 file system으로 mount할 수 있게 한다는 것은 무슨 뜻일까?

일단 아래와 같이 goofys를 실행하고 실행하면 아래와 같이 bucket에서 목록 조회하는 명령을 ls 로 할 수 있게 된다. 신기하다.

- goofys build
- go.mod 확인
- ~~go 1.14 다운로드 https://go.dev/dl/~~
    - 설치 후 cd {goofys} & go build 하면 go 1.17 필요하다고 나옴
- go 1.17 다운로드
- git clone
- go build
- go install
- ./goofys {bucketName} /Users/hwanseok/study/study-goofys

Goofys를 이해하기 위해서는 먼저 Fuse를 이해해야한다.

FUSE (Filesystem in Userspace) is an interface for userspace programs to export a filesystem to the Linux kernel

FUSE Github에 소개된 내용이다. 이해가 잘 되지 않는다. 우선 간단하게 알아보자.

Fuse

FileSysem은 일반적으로 Kernel mode에서 동작한다. 일반적으로 개발자들을 user mode에서 개발을 하고 File I/O가 필요한 경우 kernel mode의 기능을 사용한다. 그런데 FUSE는 filesystem이 usermode에서 동작하도록 도와주는 역할을 한다. 이제 FUSE에 대한 아래의 설명을 좀 더 이해가 잘 된다.

FUSE (Filesystem in Userspace) is an interface for userspace programs to export a filesystem to the Linux kernel. The FUSE project consists of two components: the fuse kernel module (maintained in the regular kernel repositories) and the libfuse userspace library (maintained in this repository). libfuse provides the reference implementation for communicating with the FUSE kernel module.

FUSE가 user mode에서 filesystem을 사용할 수 있는 역할을 하고, libfuse를 통해서 FUSE의 기능을 사용할 수 있다.

A FUSE file system is typically implemented as a standalone application that links with libfuse. libfuse provides functions to mount the file system, unmount it, read requests from the kernel, and send responses back. libfuse offers two APIs: a "high-level", synchronous API, and a "low-level" asynchronous API.

libfuse를 사용하면 kernel 모드의 read request를 읽을 수 있다는 부분이 인상깊다.

In both cases, incoming requests from the kernel are passed to the main program using callbacks. When using the high-level API, the callbacks may work with file names and paths instead of inodes, and processing of a request finishes when the callback function returns. When using the low-level API, the callbacks must work with inodes and responses must be sent explicitly using a separate set of API functions.

위 설명에는 좀 더 구체적으로 콜백을 사용해서 incoming request가 처리됨을 알려주고 있다. file name과 path를 사용해서 처리될 수도 있고, inode를 사용해서 처리될 수도 있다.

Goofys 다시보기

이제 대략적으로나마 Goofys의 동작 과정을 이해할 수 있다.

User Mode의 Application에서 File List 명령어 호출
Kernel mode에서 File List에 대한 이벤트 감지
libfuse를 통해 Goofys에 정의된 Callback을 실행
Goofys에서는 mount된 bucket에 대해서 AWS S3 list API 호출
AWS S3 list API 호출의 결과를 libfuse에게 응답으로 전달

좀 더 깊게

여기서부터 좀 더 깊게 이해하려면 File System에 대한 개념을 다시 정리해보아야겠다.

HDD는 왜 IOPS 기준으로 provisioning이 제공되지 않을까?

행운개발자 — Mon, 14 Apr 2025 22:07:01 +0900

File Storage, Block Storage, Object Storage의 차이점을 알아보기 이전에 HDD와 SSD 등의 기본 개념을 되짚어보고 AWS와 같은 클라우드 서비스에서 어떤 차이를 보이는지 알아본다.

HDD와 SSD 개념

HDD

HDD의 기본적인 구조는 넘어가고 중요한 요소한 다뤄보려고 한다. HDD는 기계적인 구조를 갖춘 저장 장치이다. 디스크 I/O 시간은 다음 세 가지 요소로 구성된다.

Seek Time: 헤더가 해당 트랙으로 이동하는 시간
Rotational Latency: 디스크가 회전하여 데이터가 헤더에 도달할 때까지 기다리는 시간
Data Transfer Time: 데이터를 실제로 전송하는 시간

주의사항은 디스크에 표기된 transfer rate는 디스크 내부 속도이며, OS나 애플리케이션에 전달되는 속도와 다를 수 있다는 점이다.

SSD (Nonvolatile Memory Devices)

SSD는 반도체 기반 저장장치로, 기계적 지연이 없고 빠른 응답성이 특징이다. 주로 Flash NAND와 컨트롤러로 구성되어 있다. 3가지 operation을 지원하는데 READ > WRITE > ERASE 속도를 가진다. 특이사항은 데이터를 쓰려면 먼저 ERASE가 필요하다. NAND cell은 일반적으로 10만 회 erase 후 수명이 다한다. 그래서 영구적으로 사용할 수 없다.

DWPD (Drive Writes Per Day): 예를 들어 1TB SSD가 5 DWPD이면, 하루에 5TB까지 쓰는 것이 가능

SSD는 GC를 통해서 invalid한 데이터를 지워야 새로운 데이터를 쓸 수 있다. Garbage Collection 로직이 invalid한 data의 location을 옮기고 erase가 되어 write를 할 수 있는 준비를 한다. 전체 용량 중 20%는 over-provisioning의 영역으로 지정되어서 invalid한 데이터가 지워진 뒤에 over-provisioning으로 지정된다. over-provisioning을 통해서 GC의 효율적인 동작이 가능해진다

SSD는 수 많은 NAND Cell로 구성되는데, NAND Cell은 가장 작은 저장 단위이다. 전자의 존재 유무로 1비트를 저장한다. Die는 Cell 들의 집합으로 병렬처리를 수행하는 하드웨어의 최소 단위이다. Die가 많으면 병렬처리 연산 능력이 커진다.

AWS EBS 설정 둘러보기

AWS EBS의 과금 모델은 아래와 같다.

볼륨 유형	요금 구조
Provisioned IOPS SSD (io2) - Storage	$0.125/GB-month
Provisioned IOPS SSD (io2) - IOPS	$0.065/provisioned IOPS-month up to 32,000 IOPS
Throughput Optimized HDD (st1) Volumes	$0.045 per GB-month of provisioned storage

위 표는 SSD와 HDD의 차이를 보여준다. SSD는 과금의 기준이 Storage와 IOPS이고 HDD는 Throughput 이다. (SSD 중에서 gp3는 Throughput 기준의 과금도 있긴 하다.) HDD는 왜 IOPS를 기준으로 과금되지 않을까? HDD의 전체 데이터 속도를 구성하는 요소들을 보면 상대적으로 개선의 여지가 더 적다. 구조적으로 높은 IOPS를 제공할 수 없다. 하드웨어적으로 부품이 움직어야하기 때문이다. 반면에 SSD는 Die가 추가됨에 따라서 (크기가 커짐에 따라서) 병렬 연산을 수행할 수 있는 연산 처리량을 확보할 수 있다.

$ lsblk
NAME          MAJ:MIN RM SIZE RO TYPE MOUNTPOINT
nvme0n1       259:0    0   8G  0 disk
├─nvme0n1p1   259:1    0   8G  0 part /
└─nvme0n1p128 259:2    0   1M  0 part

기타

Volatile Memory

DRAM은 휘발성 메모리로, 임지 파일이나 빠른 캐시 용도로 사용된다. 프로그램에서 DRAM 영역에 데이터를 쓰면 다른 프로세스에서도 사용할 수 있다. linux booting 과정에서도 storage devices가 loading되기 전까지 temporary file을 DRAM 영역에 저장한다.

linux : /dev/ram
macOs : diskutil command create them

Secondary Storage Connection Methods

저장 장치는 system bus or I/O bus를 통해서 연결된다. 연결 방식에는 ATA, SATA 등의 여러가지가 있고 SATA 방식이 많이 사용되곤 한다. 좀 더 빠른 연결을 위해서 특별한 interface가 개발되었는데 바로 NVMe이다. NVMe는 device를 system PCI bus에 바로 연결해서 increse throughput, decresing latency를 지원한다.

Reference

OS 공룡책