행운개발자의 기술블로그

SSTable, Bloom Filter, LSM Treerate limiter와 key-value store의 설계 진행하면서 아래의 개념들을 순서대로 확인해보았다고가용성 rate limiter가 필요함rate limiter에서 사용하는 알고리즘 확인token bucketleaky bucket (queue bucket)fixed window counter (단위 시간당 고정된 갯수)sliding window log (timestamp 기준으로 deprecate)sliding window counter (% 기반으로 count 추정)counter를 저장하기 위해서 고가용성, 분산 환경의 key-value store가 필요함어떤 Node에 저장될지 결정해야 함 : Consistent Hash고가용성, 데이터..

SSTable, Bloom Filterrate limiter와 key-value store의 설계 진행하면서 아래의 개념들을 순서대로 확인해보았다고가용성 rate limiter가 필요함rate limiter에서 사용하는 알고리즘 확인token bucketleaky bucket (queue bucket)fixed window counter (단위 시간당 고정된 갯수)sliding window log (timestamp 기준으로 deprecate)sliding window counter (% 기반으로 count 추정)counter를 저장하기 위해서 고가용성, 분산 환경의 key-value store가 필요함어떤 Node에 저장될지 결정해야 함 : Consistent Hash고가용성, 데이터 다중화 : Quo..

키-값 저장소 설계키-값 저장소에 저장된 값은 고유한 식별자를 키로 가져야 함키-값 쌍에서 키는 유일해야함키는 문자 또는 해시값일 수 있음성능상의 이유로 키는 짧을수록 좋음CAP네트워크 파티션은 불가피하기 때문에, 일관성과 가용성 사이에서 선택을 해야함데이터 저장안정 해시를 사용해서 데이터를 어떤 서버에 저장할지 결정데이터 다중화안정 해시에서 만나는 여러개의 노드에 모두 데이터를 저장가상 노드를 사용하는 경우, 실제 서버의 갯수를 카운트가 채워질 때까지 체크해야 함데이터 일관성정족수 합의 Quorum ConsensusN : 사본 갯수W : 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 함R : 읽기 연산에 대한 정족수. 읽기..

안정 해시 설계수평적인 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 방법해시 키 재배치(rehash) 문제serverIndex = hash(key) % N (서버 수)서버가 추가되면 전체 서버의 갯수가 달라져서, 기존의 hashKey가 달라진다해시 함수를 통한 해싱 결과가 균등하지 않을 수 있다안정 해시해시 테이블의 크기가 변경될 떄 K/N개의 키만 재배치하는 해시 기술K : 키의 갯수N : slot 갯수SHA-1 해시함수의 공간은 0 ~ 2^160-1해시 함수의 해시 공간을 구부려서 해시 링을 만든다임의의 위치에 서버를 배치한다해시 함수 - 해시 키 - 해시 링에서 오른쪽으로 돌면서 가장 가까운 서버에 접근서버가 추가, 제거되어도 근접한 서버에 저장되었던 키들만 cache m..

처리율 제한 장치 설계네트워크 시스템에서 처리율 제한 장치는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치이다.역할Dos 공격에 의한 자원 고갈을 방치더 많은 서버를 두지 않아도 되어 비용 절감서버 과부하를 방지범위 설정클라이언트 측 제한 장치인지, 서버 측 제한 장치인지서버 측 제한 장치를 설계해야 함어떤 기준으로 API 호출을 제어해야할지 (IP 주소, 사용자 ID )다양한 제어 규칙을 정의할 수 있도록 해야하는지시스템 규모는 어느정도를 감안해야 하는지대규모 요청을 처리할 수 있어야 함시스템이 분산환경에서 동작해야 하는지분산 환경에서 동작해야 함처리율 제한 장치는 독립된 서비스인지, 애플리케이션 코드에 포함되어야 하는지사용자의 요청이 처리율 제한 장치에 걸러진 경우, 사용자에게..

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 GFSGFS에서 Master는 3가지 Metadata를 저장한다.the..

요즘 GFS 논문을 읽어보고 있다. 흥미롭지만 어려워서 여러번 반복해서 읽으면서 정리를 해보고 있다. 아직 이해 제대로 못한 부분이 많지만 부족하게라도 일단 글을 발행해야겠다. 현재 시점에서 가장 인상 깊은 점은 두가지이다. 대부분의 'Operation이 Master의 오버헤드를 줄이는 방향으로 설계되었다'Relaxed Consistency Model에서 Consistency/InConsistency와 Defined/Undefined의 개념을 구분했다.이 외에도 Single Master에서 모든 Metadata를 메모리로 관리하는 점, GFS를 사용하는 Application Level에서 Write를 하고 Rename을 하도록 권장하고 있는데 알고보니 일반적인 파일 다운로드에서도 수행되고 있는 연산인 ..

개략적인 규모 추정구글 엔지니어 Jeff Dean에 따르면 개략적인 규모 추정이란 보편적으로 통용되는 성능 수치상에서 사고 실험을 행하여 추정치를 계산하는 행위로서, 어떤 설계가 요구사항에 부합할 것인지 확인해보는 과정을 이야기합니다.2의 제곱수분산 시스템에서 사용하는 데이터의 양은 크게 커질 수 있으나, 데이터 볼륨의 단위를 2의 제곱수로 어떻게 표현하는지 알아야 합니다.위와 같은 제곱수에 대한 어느정도의 감을 머릿속에 집어넣어두는 것은 꽤 중요합니다.예를 들어, 이전 포스팅에서 GFS에서 가정한 Individual STREAMING READ operation size는 대략 수백 KB ~ 1MB라고 했습니다."넉넉 잡아 1MB라고 생각하고 2^20정도이구나" 정도의 숫자에 대한 감을 기억해두면 개력적..

IntroductionGFS에서는 시스템 디자인을 할 때 기존의 방식을 재검토했던 4가지를 소개합니다.First, component failures are the norm rather than the exception.File System은 비싸지 않은 수많은 머신에서 수많은 Client의 요청을 받기 때문에 시스템 결함은 일반적인 현상이다.Second, files are huge by traditional standards. Multi-GB files are common.여러개의 객체를 다루어야할 때, 작은 여러개의 파일로 나누어서 관리하기보다, 일반적으로 하나의 큰 파일을 생성해서 관리한다.Third, most files are mutated by appending new data rather tha..

What is CAP Theorem분산 시스템을 설계할 때에는 CAP 정리를 이해하고 있어야 한다. CAP 정리는 일관성(Consistency), 가용성(Availability), 파티션 감내(Partition Tolerance)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것을 불가능하다는 정리다. 우선 각 요구사항의 의미부터 명확히 정리하고 넘어가자.일관성 Consistency : 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다.가용성 Availability : 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.파티션 감내 Partion Tolerance : 파티션은..