Paper: Main Memory Database Systems: An Overview

H. Garcia-Molina and K. Salem. 1992. Main Memory Database Systems: An Overview. IEEE Trans. on Knowl. and Data Eng. 4, 6 (December 1992), 509-516. (PDF)

요약

1991-1992년에 쓰여진 이 페이퍼는 당시 인메모리 데이터베이스 시스템에 대한 연구들과 프로토타입 인메모리 데이터베이스들에 대한 서베이 페이퍼라고 할 수 있다.

Introduction

먼저 인메모리 데이터베이스 시스템에 대한 흔한 질문들에 대해서 답하고 있다.

전체 데이터가 메인 메모리에 들어갈 것이라 가정하는 것은 합당한가?

  • 어떤 애플리케이션의 경우에는 데이터의 크기가 메모리 용량의 증가보다 더 느린 속도로 증가할 수도 있고, 어떤 애플리케이션의 경우에는 실시간 제약이 있어서 반드시 메모리 상에 적재되어야 한다.
  • 하지만, 메모리에 적재될 수 있는 애플리케이션도 존재하므로, 이러한 경우, 하나 이상의 데이터베이스 시스템에 저장하고 가장 액세스 빈도가 높은 종류의 데이터를 인메모리 데이터베이스에 저장하는 것을 고려할 수 있고, 실제로도 IMS의 사례에서 이를 보여주고 있다.

인메모리 데이터베이스와 매우 커다란 캐시를 가진 디스크 기반 데이터베이스의 차이점은 무엇인가?

충분히 커다란 캐시를 가지고 있다면 데이터가 항상 메모리 상에 존재하겠지만, 메모리의 장점을 전부 활용하지는 못한다.

  • B-tree와 같이 디스크 액세스를 위해 설계된 인덱스 구조를 가진다.
  • 디스크에 존재할 수 있는 데이터를 액세스하기 위해서, 메모리 상의 데이터를 액세스할 때에도 버퍼 매니저를 사용해야 한다.

특수한 하드웨어를 도입함으로써 메인 메모리가 nonvolatile하다고 가정할 수 있는가?

  • 배터리가 들어간 메모리 보드, UPS 등을 통해서 더 나은 신뢰성을 제공할 수 있지만, 장애의 가능성을 0으로 줄여주지는 못한다.
  • 하지만, 신뢰성이 높아진다면 백업의 빈도 등을 줄여줌으로써 성능 개선에 기여할 수 있다.
  • 배터리가 들어간 메모리 보드나 UPS는, 디스크와 달리 신뢰성을 보장하기 위해 어떤 일을 해야하는 ‘active’한 컴포넌트이므로 장애의 가능성에 기여한다.
  • 백업 메커니즘의 성능이 인메모리 데이터베이스 시스템에 있어서 매우 중요할 것이다.

Impact of Memory Resident Data

Concurrency Control

  • 인메모리 데이터베이스에서 트랜잭션은 디스크 기반 데이터베이스에 비해서 짧아지므로 lock contention도 상대적으로 적을 것이다.
  • 따라서, 인메모리 데이터베이스의 경우 좀 더 큰 lock granularity를 선택할 수 있고, 이를 통해 동시성 관리의 비용이나 CPU cache flush의 비용을 크게 줄일 수 있다.
  • 하지만, 여전히 짧은 트랜잭션과 수명이 긴 트랜잭션이 동시에 수행될 수 있도록 하기 위한 방법이나 멀티프로세서 시스템을 활용하기 위한 방법은 필요하다.
  • 전통적인 데이터베이스에서 lock table 대신, 오브젝트 자체의 1-2 bit를 사용해서 lock을 구현할 수 있다.

Commit Processing

  • 메모리는 volatile하기 때문에 commit 전에 디스크에 로깅을 하는 것이 필요한데, 디스크 액세스는 인메모리 데이터베이스 시스템에서 커다란 성능 bottleneck을 유발할 수 있다.
    • 디스크에 비해 상대적으로 빠르고 작은 stable memory를 도입해서 로그의 일부를 저장할 수 있다. 트랜잭션과 별도로 stable memory에 쓰여진 로그를 디스크에 기록하는 프로세스가 존재할 수 있다.
    • Precommitting – 로그가 디스크에 쓰여지기 전에 트랜잭션의 lock들을 릴리즈하는 방식 – 을 사용해서, lock contention을 줄여 다른 트랜잭션의 응답시간을 개선할 수 있다.
    • Group commit – 복수의 트랜잭션의 로그들을 메모리에 모아뒀다가 한번에 디스크로 flush하는 방식 – 을 사용해서 로깅 bottleneck을 완화할 수 있다.

Access Methods

  • 인메모리 데이터베이스의 인덱스 구조를 위해 여러가지 형태의 해싱과 T-tree와 같은 트리들이 제안되고 있다.
  • 그러한 인덱스 구조들은 공통적으로, 데이터 자체가 아니라 데이터로의 포인터를 저장함으로써 메모리의 이점을 잘 활용하고 있다.

Data Representation

  • 튜플은 데이터로의 포인터 집합으로 표현될 수 있다.
  • 커다란 데이터가 반복적으로 나타난다면 중복 저장하지 않음으로써 공간 효율을 높일 수 있다.
  • 가변 길이 데이터를 포인터로 표현함으로써 데이터구조 디자인을 단순화할 수 있다.

Query Processing

  • 데이터에 대한 포인터 메커니즘을 이용해서 어떤 오퍼레이션을 매우 효율적으로 수행할 수 있다.
    • 예를 들어, 두 테이블을 하나의 attribute를 기준으로 join하려는 경우 그 데이터를 사용하는 튜플로의 포인터를 통해서 엄청나게 효율적으로 join을 수행할 수 있다.
  • 전통적인 데이터베이스에서는 디스크 액세스를 줄이려고 했지만, 인메모리 데이터베이스에서는 CPU 비용을 줄이는 것에 집중해야한다.

Recovery

  • 인메모리 데이터베이스에서는 트랜잭션들은 메모리 상의 데이터만을 이용하므로, 체크포인팅이나 복구가 디스크 상의 데이터를 액세스하는 유일한 이유다.
    • 따라서, 인메모리 데이터베이스에서는 체크포인팅에 최적화해서 매우 커다란 블럭 사이즈를 사용할 수 있다.
  • 복구할 때 많은 양의 데이터를 읽어들여야 하는 문제를 해소하기 위해서 필요한 데이터 블럭부터 로드하거나 여러 개의 디스크로부터 병렬적으로 로드하는 방법을 고려할 수 있다.

Systems

IBM에서 개발한 상용 제품인 Fast Path 이 외에 몇가지의 인메모리 데이터베이스 연구용 프로토타입들에 대해서 간단히 소개하고 있다.

내가 배운 것 & 생각한 것

  • 나도 품어왔던, 인메모리 데이터베이스에 대해서 가장 기본적인 질문들 – 특히, “충분히 많은 메모리 캐시를 가진 디스크 기반 DB를 쓰면 되잖아?” – 에 대해서 명확하게 답하고 있다.
  • 전통적인 데이터베이스 아키텍처 상의 각각의 모듈 또는 기능들에 대해서 인메모리 데이터베이스는 어떻게 다른지, 그리고 어떤 해결책을 고려할 수 있는지를 비교적 짧지만 매우 쉽게 이해할 수 있도록 쓰여져있다.
    • 인메모리 데이터베이스 시스템에서 고려해야할 빅 픽처를 이해하는 데 도움이 된다는 의미에서 도움이 되었다.
    • “OLTP Through the Looking Glass, and What We Found There” 리뷰에서 언급한 것과 마찬가지로, 구체적인 해결책에 대해서는 다양한 문맥에서 더 나은 진척들이 있기 때문에 이 페이퍼에 쓰여진 것만을 고려해서는 안된다.
  • 1992년 이후로 여러가지 변화 – 하드웨어의 발전, OS 및 프로그래밍 시스템의 발전, 인메모리 데이터베이스 분야의 연구 – 가 있었기 때문에, 몇몇은 현재 시점에서는 유효하지 않은 것 같다.
    • Optane DC Memory와 같은 non-volatile memory가 제품화되고 있으므로, 이제 ‘passive’한 메모리 하드웨어가 생겨났다고 할 수 있다.
    • 결국 many-core 시스템의 이점을 잘 활용하기 위해서는 여전히 lock granularity는 중요한 것 같다. 다만, 데이터베이스 lock granularity를 가진 KeyDB가 좋은 성능을 보여주는 것을 보면 완전히 틀린 말은 아니다.
    • optimistic concurrency control에 대해서는 많이 언급하지 않고 있다.
    • 이 페이퍼에서는 CPU 비용을 측정하는 것이 어렵다고 언급되어 있으나, 이후로 CPU 비용에 대해서 측정하는 방법이 많은 발전을 이루었다.

Paper: OLTP Through the Looking Glass, and What We Found There


Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, and Michael Stonebraker. 2008. OLTP through the looking glass, and what we found there. InProceedings of the 2008 ACM SIGMOD international conference on Management of data(SIGMOD ’08). (PDF)

요약

이 페이퍼에서는 인메모리 데이터베이스 시스템에서 Logging, Locking, Latching, Buffer management 등의 기능을 하나씩 제거했을 때 어떠한 성능 변화가 일어나는지를 보여주고 그 결과로부터 미래의 OLTP 데이터베이스에 대해 시사하는 바가 무엇인지에 대해서 논하고 있다.

  • 하드웨어의 변화 그리고 수많은 데이터 중심 애플리케이션들로부터 나타난 다양한 요구 때문에, 표준적인 OLTP 데이터베이스 시스템에서 당연시 되어왔던 logging, concurrency (latching, locking), B-tree, buffer management와 같은 기능들의 일부분만을 가진 데이터베이스들 – Logless/Single-threaded/Transaction-less 데이터베이스들이 나타나고 있다.
  • Shore라는 표준적인 OLTP 데이터베이스 아키텍처를 가진 데이터베이스 시스템에 인메모리 워크로드를 실행하는 실험 셋업을 갖추고, logging, latching, locking, buffer management 등의 기능을 하나씩 제거하면서 instruction의 수가 어떻게 변화하는지를 측정했다.
  • 실험 결과를 통해 logging, latching, locking, buffer management와 같은 기능들이 전체 대비 상당히 높은 CPU 비용을 소비하는 것을 알 수 있었다.

이러한 결과로부터 미래의 OLTP 데이터베이스 엔진에 대해 다음과 같은 방향성을 제시하고 있다.

  • 동시성 제어 (Concurrency Control)
    • dynamic locking은 disk-based OLTP 데이터베이스일 때 좋은 선택이었지만, 메모리 기반 워크로드의 경우에는 다시 따져볼 필요가 있고, optimistic concurrency control 방식이 더욱 나은 선택지가 아닌가 하는 의견을 제시하고 있다.
  • 멀티코어 지원 (Multi-core Support)
    • 많은 수의 코어를 가진 컴퓨터가 늘어나고 있고, 동시성이 높은 프로그램들이 성숙하고 있기 때문에, latching과 관련해 더 나은 구현과 멀티쓰레딩의 부담에 대해서 탐색해볼 필요가 있다고 얘기하고 있다.
    • 다른 옵션으로는, 각각의 머신은 하나의 코어를 가진 컴퓨터처럼 볼 수 있는 가상화 환경이 갖춰졌음을 언급하고 있는데, 아마도 각각의 데이터베이스 시스템은 싱글쓰레드 시스템으로 동작할 수 있게 된 것을 함축하고 있는 듯 하다.
    • 이러한 두가지의 접근을 보완해서, 하나의 쿼리를 병렬적으로 처리할 수 있는 시도에 대해서도 언급하고 있다.
  • 복제 관리 (Replication Management)
    • logging을 이용한 active-passive 복제의 경우 여러가지 문제점들을 가지고 있지만 이렇게 밖에 할 수 없었던 이유는 log를 실행하는 것이 복제본에서 트랜잭션을 실행하는 것보다 훨씬 적은 비용이 들었기 때문인데, 인메모리 데이터베이스 시스템에서는 트랜잭션의 비용이 매우 낮으므로, active-active 복제에 대해서 고려할 수 있다고 얘기하고 있다.
    • 이 때, two-phase commit을 이용하는 것은 추가적인 지연이 너무 크기 때문에 timestamp ordering등의 테크닉을 이용해야하리라고 제안하고 있다.
  • Cache-conscious B-trees
    • 데이터 구조를 최적화하기 보다는 이외의 부분 – 동시성 제어나 복구 – 을 최적화하는 것이 더 중요한 것 같다고 얘기하고 있다.
    • 하지만, 그러한 최적화 후에는 B-tree의 캐시 미스가 새로운 bottleneck일 수 있고, 다른 데이터 구조도 살펴봐야 한다고 얘기하고 있다.

내가 배운 것

  • 2008년 시점에 이미 학계에서도 전통적인 OLTP 데이터베이스로부터 다른 접근들이 나타나고 있었고, 인메모리 데이터베이스라는 커다란 트렌드가 이미 시작하고 있었던 것 같다. 그러한 트렌드를 정확히는 알지 못하지만, 적어도 여러 다른 페이퍼나 제품들의 역사를 보면 2000년대 후반부터 2010년에 중반까지 그러한 트렌드가 이어졌고 그 결과 현재와 같이 수많은 상용 인메모리 데이터베이스 제품들이 나오게 된 것 같다.
  • 전통적인 OLTP 데이터베이스 엔진에서 대부분의 logging, latching, locking, buffer management의 CPU 비용이 80% 이상에 이를 정도로 높은지에 대해서는 전혀 알고 있지 못했다. 기존에는 디스크 액세스가 커다란 bottleneck이었겠지만 적어도 인메모리 데이터베이스 시스템을 만든다면 이러한 기능들에 대해서 세심한 주의를 기울여서 디자인 선택을 해야할 것 같다.
  • 이 페이퍼에서 제시하고 있는 방향성에 대해서, 실제로 이 페이퍼에서 수행할 실험결과로부터 직접적으로 도출되는 방향성이라고 보기는 매우 힘들고, 다만 그 당시 시점의 트렌드나 분위기를 설명하고 있는 것으로 이해했다. 각각의 이슈에 대해서 더욱 엄밀하고 자세히 설명하고 있는 페이퍼들이 많으리라고 생각하므로 심각하게 받아들이지는 않아도 될 것 같다.
  • 이 페이퍼를 읽고 역시 2000년대 후반에 시작된 프로젝트인 레디스가 어떤 동기로 시작하게 되었을까 많이 생각을 해보았다. 이 페이퍼에서 얘기하고 있는 디스크 기반 데이터베이스 시스템과 멀티쓰레드 지원, 트랜잭션 지원 등의 오버헤드를 완전히 제거해버린 시스템이니까. 그리고, 인메모리 데이터베이스 시스템을 만든다면 레디스와 대비해 어떤 기능적인 장점을 가져야 하고 그러인한 성능 오버헤드에 대해 어느 부분을 신경을 써야하는 가에 대해서 고민하는 시발점이 되었다.

QCon San Francisco 2015 Day 3

QCon San Francisco 2015 Tracks의 마지막 날. 아직도 Jet lag에 적응이 되지 않았는지 오후가 되면 졸음이 쏟아지는데, 중간 중간 쉬는 시간 (20분)에 호텔에 돌아와서 잠시나마 눈을 붙였더니 그나마 나았다.

The Imitation Game: The New Frontline of Security by Shuman Ghosemajumder

오늘의 키노트. Shuman Ghosemajumder은 전직장인 Google에서 click fraud를 방어하는 것을 담당했다고 한다. Botnet이 IP 기반의 방어를 무력화시켰고, 도구화되어서 click fraud, login form, tax fraud, online banking fraud 등에 활용되고 있다는 상황을 소개하면서 이를 방어하기 위해서는 수작업으로는 불가능하고 ‘robotic defences’를 구축해야한다고 얘기했다. 이러한 공격이 쉬운 이유는 웹사이트 자체가 일종의 API이기 때문이라고 설명. 방어를 위한 주요한 방법 중 하나로 웹 사이트 액세스의 수많은 특성 screen resolution, user agent, time zone 등을 추적해서 어떤 aspect에서의 spike 등이 존재하는 가를 식별하는 것을 들었다. 액세스의 특성이 되는 aspect들이 상대적으로 적은 API액세스 등에 대해서는 어떻게 해야하는지 잘 생각이 안나지만, 이러한 시스템이 방어를 위한 기초적인 시스템임에는 동의한다. 방어를 위한 방법들을 prevention, realtime, near-realtime, batch, reactive defence 등으로 분류하고 여러 관점에서 방법을 구축해야한다고… 하지만 디테일에 대해서는 그다지 다루지는 않았다.

Explorations of the three legged performance stool by Charlie Hunt

Charlie Hunt는 Oracle의 JVM Engineer로 2001년 정도에 출판되었던 Java Performance란 책의 저자라고 한다. 여기서 말하는 3 legs란 throughput, latency, memory footprint를 말하고, 이 중 어느 하나를 개선하려고 하면 나머지 하나 또는 둘을 희생해야한다는 이야기를 Generational GC 상황에 따라 설명을 해주었다. Java GC에 대해 어느 정도 지식을 가지고 있는 엔지니어라면 익숙할만한 이야기.

JDK 9의 feature가 될 Compact strings라는 feature를 개발하기 위한 ‘String density’ 프로젝트에 대해 설명을 해주었는데, 결과만 놓고보면 String의 internal representation에서 char[]를 byte[]로 바꾸고 ISO-8859를 위한 encoding을 추가한 것 뿐이지만, 이를 위해 JVM Engineer들이 어떤 개발 비용을 들이는지 자세하게 설명을 해주었다. 여러 애플리케이션들로부터 heap dump들을 수집해서 footprint를 줄이기 위한 방법을 탐색하고, 각 JVM platform별로 memory layout을 모두 분석하고, performance regression이 없도록 하기 위해 microbenchmark를 각 platform별로 모두 확인하는 과정 등, 프로젝트에는 10명의 엔지니어가 1.5년 정도가 걸렸다고 하니, JVM 엔지니어링은 굉장히 엄밀하게 진행되는 것 같다. Compact strings에 UTF-8을 사용하지 않은 이유는 String의 많은 수의 메서드들은 랜덤 액세스를 사용하는데 UTF-8의 특성 상 랜덤 액세스를 위한 비용이 커지기 때문이라고 한다. 또 하나 재미있었던 것은 기존의 String을 바꾸지 않고 왜 새로운 String 클래스를 만들어서 쓰지 않는가에 대해서는, Hotspot은 55개나 되는 String에 대한 JIT compiler최적화가 들어가있기 때문이라고 설명했다.

JVM Engineer의 GC에 관련한 세션이라서 나름대로 G1 GC의 현재 상황 등 최신의 내부 정보를 얻을 수 있을까 해서 들었는데, Abstract와 조금 다른 방향의 이야기가 나와서 안타까웠다.

애초에는 Confluent의 co-founder들 중 유일한 여성인 Neha Narkhede를 한번 만나보고 싶어서 그녀의 Kafka 세션을 들으려고 했는데, Neha Narkhede가 인기인 것인지 Kafka가 인기인 것인지 룸이 꽉차버려서 안타깝게 발길을 돌려야 했다.

Stream Processing in Uber by Danny Yuan

오늘 들은 토크 중에서는 최고의 토크였다. 풀어야 할 비즈니스 문제들을 명확하게 보여주고, 풀어야할 기술적인 문제들을 정의하고, 후보 솔루션들을 선택하지 않은 이유를 제시한 후, 선택한 솔루션들을 설명했다. 그리고, 그 솔루션들로부터 다시 확장되는 문제들과 다시 솔루션을 제시하는 방식도 꽤 탁월했던 것 같다.

우버에서는 승객과 드라이버들을 더욱 잘 매치해주기 위해 수요와 공급을 분석, 예측해야하고, 이로부터 요금도 동적으로 결정해야하는 요구사항이 있다. 또한 서비스의 문제로 인한 비효율적이거나 이상한 패턴들을 찾아내거나 fraud 등을 탐지해야하는 문제도 가지고 있다. 토크의 시작은 지도 상의 수요 공급을 나타내는 히트맵과 여러 metric들의 trend가 그 오른쪽에 함께 보여지는 아름다운 대시보드를 보여주는 것으로 시작했다. 그리고, 쿼리 입력 필드에서 특정 승객이나 특정 드라이버의 상태 변화를 상태를 node로하는 그래프로 보여주는 뷰도 보여주었다.

이러한 비즈니스적인 요구사항을 만족시키기 위해서는 애플리케이션을로부터 수집된 이벤트들이 소실되지 않도록 저장하고 쉽게 확장 가능한 스토리지가 필요하고 이를 위해 Kafka를 이용한다고 설명했다.

또한 승객과 드라이버가 가진 수많은 필드 – 차원들에 따른 쿼리가 가능하고, 여러가지 형태의 aggregation을 지원하는 스토리지도 필요한데, 우선 Redis나 HBase 등과 같은 KV store 계열은 모든 키의 조합을 미리 계산해야하기 때문에 사용이 불가능하고 (‘불가능’이라는 단어에 대해서 항상 조심스러울 수 밖에 없다는 이야기도 함께 함.) RDB의 경우 여러 인덱스를 관리하는 것이 고통스럽고 스캐닝이 충분히 빠르지 않기 때문이라는 이유로 솔루션이 될 수 없다고 했다. 결론은 이쯤에서 예상했지만 Elastic Search였고, 장점으로 제시한 것은 매우 효율적인 역인덱스들과 자동적으로 여러 노드에 쿼리가 분산되고 다시 통합되는 분산쿼리 기능이었다.

여기에 더해서 이벤트의 데이터들은 여러가지 normalization이나 precalculation, 여러 스트림의 join, sessionization, state 관리 등이 필요하기 때문에 이를 처리하기 위한 layer로 Apache Samza를 선택했다고 한다. Samza는 YARN 위에서 동작하고, Kafka와의 integration이 매우 뛰어나고, built-in checkpointing이나 state management를 가지고 있는 것을 장점으로 제시했다.

여기에 더해서 Storage가 down되거나 프로세싱이 오래 걸리는 경우를 위한 배치 프레임워크로는 Spark를 선택했다고 한다. 결과적으로는 Kafka – Samza/Spark – Elastic Search로 구성되는 전형적인 Lambda architecture를 구성했다고 한다.

지역들을 헥사곤으로 쪼개서 수요 공급을 보여주기 위해서는 주위 hexagon의 데이터들과의 smoothing이 필요하고 이를 위해서 쿼리 결과의 Post processing도 필요하다고 한다. 이러한 처리는 순서한 function과 combinator로 이루어지는데, 이를 paralleize하고 pipelining하는 layer를 가지고 있는 듯하다.

Elastic search는 cardinality가 높은 쿼리를 하면 오랫동안 실행하다가 그대로 죽어버리는 문제를 가지고 있기 때문에, Pipelining, Validation, Throttling 등을 수행하는 query layer도 따로 구현하고 있다고 한다. 지금의 아키텍쳐는 상당히 타이트한 스케줄 내에 만들어냈어야 했기 때문에 외부의 도구들을 가져다 썼지만, 지금으로서는 Elastic Search 대신 자신들의 요구사항에 맞는 것을 만드는 것도 가능할 것 같다고 얘기했다.

One more thing으로 어떤 쿼리를 지정해두면 이에 해당하는 이벤트들이 특정 채널 (이를테면 Hipchat)로 전달되는 CEP를 가지고 있는 것도 보여주었다.

토크 중에 ‘사람은 기다릴 수 있지만 기계는 기다릴 수 없다’라는 말을 했는데, 사람과 기계에게 모두 analytic data를 제공하는 아키텍쳐를 가지고 있고, 단순히 외부의 프로덕트들을 가져다 조립한 것이 아니라 요구사항에 필요한 부분들을 채워넣고, 훌륭한 비주얼라이제이션과 응답시간을 가진 도구를 개발한 것도 타이트한 일정에 쫓기는 서비스 회사로서는 정말 굉장하다고 느꼈다.

Life of a Twitter JVM engineer by Tony Printezis

Twitter에서는 수천개의 머신에서 JVM을 사용하고 있다고 한다. (생각보다 규모가 크지 않다는 인상을 받았다.)
주요한 stack은 Finagle, Netty, TwitterJDK, Mesos, CentOS이고, 서버 사이드의 언어는 Scala가 메이저에 해당하고 Java, Ruby, Python 등이라고 한다.

Twitter의 VM Team은 TwitterJDK를 개발하는 것을 담당하고 있는데, OracleJDK와는 달리 OpenJDK에 패치를 더한 형태라고 한다. 소스 리파지터리의 구성도 OpenJDK의 리파지터리로부터 hg-git을 해오고 TwitterJDK를 릴리즈할 때마다 최신의 OpenJDK 릴리즈로 업데이트한다고 한다. 릴리즈는 1달에 1번 정도씩 이루어지고, 2주간의 Canary 기간을 걸친다고 한다. Deployment는 Packer를 이용하고 Mesos 상의 서비스에 적용된다고 한다. (VM 이미지 안에 JVM이 함께 배포되고, Mesos 클러스터를 구성하게 된다는 이야기?)

주요한 개선은 Heap profiling, Binary logging framework (for GC logs), Intermediate generation for G1 등이라고 한다. GC log를 시스템화 함으로써 여러가지 GC에 관련된 문제들도 찾아내고 해결할 수 있었는데, Neopotism (Old gen의 dead object로부터 참조된 young gen의 object가 collection되지 않는 현상을 가리키는 듯), TLAB이 full이 되었을 때 object allocation이 느려지는 문제 (새로운 TLAB의 pre-allocation으로 해결?), DirectBuffer cache가 계속 자라나서 leak처럼 되는 문제 (최대 크기를 제한해서 해결) 등을 해결했다고 한다. 이것들에 대한 자세한 내용은 완벽하게 이해하지 못해서 비디오가 나오면 다시 한번 봐야할 것 같다.

Netty @Apple: Large Scale Deployment/ Connectivity by Norman Maurer

희승님과 함께 Netty의 주요 개발자 중 하나라고 할 수 있고 Netty in Action의 저자이기도 한 Norman Maurer의 토크.

Apple에서는 무려 40만개나 되는 Netty 인스턴스들이 동작하고 있고, 초당 수천만개의 리퀘스트를 처리하고 있다고 한다. 직접적으로 언급하지는 않았지만 많은 주요한 Apple 서비스들에 사용되고 있는 것 같고… 이러한 배경으로 인해 Apple 엔지니어들이 Netty에 contribution할만한 요구사항들과 가치들도 생겨나는 것 같다.

우선 JDK NIO의 비효율적인 인터페이스 (Selector.selectedKeyes()가 항상 새로운 collection을 만들어서 리턴하는 것), NIO 구현 내에 concurrency에 대한 충분한 고려가 없이 synchronized 키워드가 너무 많이 사용된 점, 주요한 플랫폼이라고 할 수 있는 리눅스에 대한 최적화가 불가능한 것, copy가 많이 일어나는 점을 들면서, 이러한 문제들을 해결하기 위해 도입한 Native transports에 대해 설명했다. Linux의 epoll을 이용하고 있고, 여러가지 유용한 TCP 옵션들 (TCP_CORK, TCP_NOTSENT_LOWAT, TCP_FASTOPEN, …)을 지원하며, sync를 줄이는 등의 개선들을 활용할 수 있다고 한다. 이 정도가 되면 여타의 JVM기반 네트워크 프레임워크의 수준을 넘어서는 것이 아닐까 생각이 들었다.

DirectBuffer의 allocation 비용이 Heap buffer에 비해 높은 것은 잘 알려져있는데, 이러한 이유 중 하나로 allocation/deallocation 내부 코드에 heap usage를 체크하기 위한 코드 등에 syncronization들이 들어가 있기 때문이라고 한다. PooledByteBufAllocator를 이용해서 DirectBuffer를 pooling하는데 jmalloc과 유사하게 thread-local cache를 이용하고 arena별로 sync를 하는 approach를 취해서 성능을 개선하고 있다고 한다.

이 외에도 JDK SSL, Optimization, Thread model, Backpressure, Connection pooling 등의 내용들을 언급했는데, 자세한 내용은 나중에 슬라이드와 관련된 이슈를 읽어보아야 할 것 같다.

Netty는 나름대로 성숙한 프레임워크였지만 지금도 굉장히 많은 개선들이 지속적으로 이루어지고 있는 점은 정말 대단한 것 같다. 한편, 이 토크 자체는 Netty 4.0이나 그 주변의 개선들을 언급하고 있는 것 같고, Apple에 직접적으로 관련된 내용은 처음의 숫자들 밖에 없었는데, 토크의 제목이 왜 Netty @ Apple인지는 조금 의문이 들었다.

Stylus, Facebook’s new stream processing platform by Jerry Chen

Facebook의 stream processing이라고 해서 나름대로 기대하고 들었는데, 토크 자체는 현재 시점에서는 보편적인 프로세싱 모델을 다루는 데에 시간을 많이 할애한 것 같아서 실망스러웠다.

잘 알려진 Scribe가 Kafka와 같은 Event Stream이라면, Stylus는 Imperative processing을 담당하고 있고, Puma라는 프로덕트는 SQL-like 인터페이스를 제공하고 있다고 한다. Stream processor로서 일반적인 keyed tuple을 처리하는 모델이라고 할 수 있는데, 특이한 점은 key에 대한 State가 외부의 DB로부터 관리된다는 점이다. 이 state는 local DB로 관리되기도 하는데 성능을 위해서 remote DB로도 제공되는 것 같다.

Fault tolerance를 위해서 state의 저장은 checkpointing을 사용하고 있으며 guarantee에 따라서 checkpointing과 state의 저장 순서가 바뀌는 방식이다. (at-most-once라면 checkpointing을 먼저, at-least-once라면 checkpointing을 나중에)

Backfill이라고 해서 오래된 데이터를 다시 읽어오는 방법도 제공하고 있는 것 같고, 중복된 코딩을 막기 위해 Stylus processor의 logic을 그대로 Batch로 실행하는 방법도 제공하는 것 같다. Mobile 클라이언트 이벤트 로그들을 처리해서 in-memory query storage인 Scuba에 집어넣는 역할, 페이지의 trend를 계산하기 위해서 scoring이나 ranking을 하는 사례를 설명했다.

Flying faster with Heron by Karthik Ramasamy

Twitter의 stream processor로서 Storm을 대체한 Heron에 대해서 설명하는 토크였는데, Storm의 여러가지 문제점들을 설명하고 이를 Heron에서 어떻게 해결했는지 설명했다.

Storm의 아키텍쳐는 마스터에 해당하는 Nimbus, ZooKeeper 클러스터, Supervisor와 Worker들로 이루어진다. Nimbus는 Worker가 실행할 작업들을 scheduling하고 monitoring하는 역할을 하는데, 그 자체가 SPOF일 뿐만 아니라, resource의 reservation이나 isolation 개념이 없기 때문에 작업의 성격에 따라서 예측불가능한 성능 이슈가 자주 발생한다고 한다. ZooKeeper 클러스터는 Kafka spout의 offset/parition의 체크포인팅과 Storm Worker들의 heatbeat으로 인해 contention이 발생하기 쉽다고 한다. 실제로 작업을 수행하는 Worker들은 하나의 JVM 내에 여러 Worker들이 실행되기 때문에 디버깅이 어렵고 튜닝하기도 어렵다고 한다. 또한 데이터들이 거치게 되는 input queue와 output queue가 공유되기 때문에 여기서 발생하는 contention 문제도 언급하고 있다. 한편 Storm 자체는 Clojure로 쓰여져있지만 작업을 개발하는 개발자들은 Java 등을 사용하고, Storm의 커뮤니케이션 layer라고 할 수 있는 ZeroMQ는 C++를 사용하고 있기 때문에 이로 인한 유지보수의 어려움도 문제라고 이야기 하고 있다. 이 외에도 Backpressure 개념의 부재나 Efficiency에 관련된 문제들도 언급하고 있다.

Heron의 아키텍쳐를 설명하며 Heron은 Storm의 이러한 문제들을 해결하고 있다고 하고 성능도 몇 배 이상 좋아졌다고 얘기하고 있는데, 자세한 내용은 Heron paper를 읽어보는 편이 좋을 듯 하다.

QCon San Francisco 2015 Day 2

2번째 날 어제보다는 약간 일찍 일어나서 호텔 조식도 먹고 출근했다. 오늘은 샌프란시스코에서 일하는 강문식 군과 점심을 먹느라 세션 2개 정도를 건너뛰었다. 나중에 비디오로 보기로…

Building Highly-resilient Systems at Pinterest by Yongsheng Wu

Yongsheng Wu는 Storage & caching team의 lead. 수만개의 AWS instance를 사용하고 있고, 100개 정도의 서비스를 가지고 있다고 한다. 서비스 수십개 관리하기도 어려운데 수백개라니… 마이크로서비스가 업계 대세인 것인가 하는 생각이 들었다. 서비스가 나뉘어져있다보니 사용하는 언어도 Java, Scala, Go, C++로 다양한 것 같다.

토픽에 해당하는 Highly Resilient한 시스템을 위해서 5가지를 내세웠는데 다음과 같다.

  • Dynamic service discovery
  • Realtime configuration
  • Caching
  • Persistent storage
  • Async processing

Dynamic service discovery에 대해서는 상식적으로 생각할 수 있는 수준인 ZooKeeper의 ZNode들이 서버들을 나타내도록 하고 클라이언트는 상위 노드의 변화를 subscribe하는 형태를 기본으로 하고 있다. 이러한 시스템은 누구나 쉽게 상상할 수 있는 것이지만, 문제는 ZooKeeper에 장애가 발생했을 때 서비스의 가용성이 0가 될 수가 있다는 점인데, Pinterest에서는 Zum이라는 local daemon을 도입해서 ZooKeeper의 로드를 줄이고, 로컬 카피를 애플리케이션에게 제공하는 것으로 이 문제를 해결하고 있다. 단순하면서도 실용적인 해결책이라고 생각한다.

Realtime configuration에 대해서도 역시 Zum을 이용해 로컬 카피를 제공하는 비슷한 접근을 활용하고 있는데, 설정이 ZooKeeper에 있는 것이 아니라 Amazon S3에 두고 ZooKeeper는 단지 versioning과 변경 통지를 위한 용도로만 사용하고 있다.

Caching은 memcached의 consistent hash ring을 관리하기 위해 Facebook의 Mcrouter를 사용하고 있다고 한다. 재미있는 것은 일시적인 실패로 인해 cache inconsistency가 발생하는 문제를 해소하기 위해 Mcrouter의 로그를 Kafka에 보내고 이를 다시 플레이하는 시스템을 가지고 있는 점이었다.

MySQL Shard의 설정 관리도 위에서 설명한 Zum을 이용해 관리되는 것 같다.

Async processing을 위해서는 PinLater라는 서버를 가지고 있는데, 비동기적인 작업을 queue로서 관리하고 일정 회수 만큼 재시도해주는 서버다. Dashboard로 각 작업의 현황을 쉽게 볼 수 있는 점은 편리해 보였다.

발표에서 소개된 것들을 발표 이후에 곧 오픈소스화할 예정이라고 하니, 조금 더 살펴볼 여지는 있을 것 같다. 문제 자체도 LINE이 가지고 있는 문제들과 비슷하고, 해결책도 (엄밀한 해결책이라기보다는) 굉장히 실용적인 스타일이라 공감이 되는 면이 있었다.

Beyond ad-hoc automation: to structured platforms by Bridget Kromhout

수많은 meme들을 이용해서 토크를 이어나갔는데, 나름대로 흥미로운 이야기들을 많이 한 것 같지만, 이건 나중에 슬라이드와 비디오가 나온 후에야 정리를 할 수 있을 듯 하다. 그 중에서도 생각나는 것들을 들자면, 회사나 조직의 환경에 한정되는 ad hoc 도구들을 만드는 것에 대해서 비판적인 논조를 유지한 것 같고, 항상 200 OK를 뱉는 healthcheck를 예를 들며 도구보다는 원리에 집중하라는 이야기, 자동화는 플랫폼이고, 이 플랫폼에서 무엇을 하려는 것인지 constraint를 정의하라는 이야기 등이 생각이 난다. 단순히 몇가지 도구를 추가해서 자동화하는 것이 아니라 전체적인 관점에서의 플랫폼을 만들어나가야 한다는 조언으로 되새기게 된 것 같다.

A Brief History of Chain Replication by Christopher Meiklejohn

Chain Replication은 그동안 공부해보고 싶은 토픽 중의 하나였는데, 대략적으로 어떠한 문제들을 다루는지 조금은 알게 된 것 같다. Chain Replication에 관련된 연구들을 하나하나 요약해서 설명해주었는데, 사실 굉장히 엄밀하게 생각해보지 않으면 안되는 것들이라 짧은 시간 내에 이해하기는 쉽지 않았다.

Datastructures in and on IPFS by Juan Batiz-Benet

IPFS는 구글과 같이 하나의 서비스에 종속된 서비스를 가질 것이 아니라 인터넷이라는 분산된 네트워크를 활용해서 정보들을 안전하게 저장해보자는 동기로부터 출발해, Merkle tree의 아이디어를 차용한 내용 기반의 addressing을 기초로 여러 인터넷 프로토콜, 인터넷 포맷들을 조합해서 파일시스템을 만들어보자는 아이디어 그리고 구현이다. 하나의 연구분야일거라고 생각하고 있었는데, 한 사람의 아이디어로부터 출발한다는 것이 놀라웠다.

내일은 프로그램의 마지막인 3일차. 내일도 흥미로운 발표들이 많으니 기대가 된다. 더불어 1일차 비디오들이 차근차근 업로드되고 있어서 이것들도 소화해보기 시작해야할 것 같다.

QCon San Francisco 2015 Day 1

어쩌다보니 지금까지 미국이나 유럽 등지를 한번도 여행한 적이 없어서, 올해 초 다짐한 것이 미국 여행. 페이퍼를 읽는 것이나 토크를 보는 것도 좋아하기 때문에 무겁지 않은 QCon에도 가보자라고 해서 올해 봄 무렵에 QCon SF 2015를 예약해두었다. 여러가지 위기는 있었지만, 가족여행을 겸해서 QCon SF에 참석하는 계획을 잡았고, 지난 토요일에 San Francisco에 도착했다. 이로서 목표 달성!

오늘부터 3일에 걸쳐 QCon SF 2015의 본 프로그램이 진행되고 이후 이틀동안은 Workshop이 진행된다. 오늘만 하더라도 듣고 싶었던 토크는 꽤 많았지만, 그래도 고심 끝에 골라서 들어간 토크들이니 내 입장에서 듣고 느낀 것들을 적어본다.

Avoiding the Big Crash by Bill Buxton (Slides)

Xerox PARC 출신으로 35년간 컴퓨터 사이언티스트와 디자이너로서 종사하고 현재는 MSR의 Principal Researcher. 스마트 왓치와 같은 초소형 디스플레이를 가진 제품과 벽면을 가득 채울 정도로 커다란 디스플레이를 가진 제품은 완전히 다른 설계를 가져야 함을 설명하면서, 또한 기존의 경험들을 활용하기 위해 common denominator도 찾아야 한다면서 그 예로 Bimanual In-Place Commands를 든다.

모든 새로운 제품은 물론 그 자체로도 가치와 좋은 경험을 제공해야하지만, 전체적인 복잡도를 줄이고 다른 제품들의 가치를 더 높일 수 있어야 한다는 룰을 제시하고, 여러가지 inspiration이 될만한 설명들을 제공해주었다. 단지 돈을 벌기 위한 수단, 다른 제품들과의 경쟁 우위에 있어야만 하는 것으로서만 제품을 생각하는 것이 아니라 우리 주변에 있는 다른 사람들에게 더 좋은 경험을 제공해주기 위한 고민을 우리 스스로가 해야한다는 메시지로 받아들였다. 글로만 이러한 내용을 설명하기는 어렵지만 내가 했던 일들과 하고 있는 일, 그리고 해야하는 일들을 모두 돌아보게 만드는 굉장히 인상 깊은 토크였다.

Scaling Uber by Matt Ranney

5년동안 PHP+MySQL로부터 시작해서 빠르게 개발하기 위해서 technical debt도 많이 쌓였다는 이야기를 하면서 저런 성장하는 회사의 모습은 한국의 비슷한 상황의 회사와도 크게 다르지 않구나라고 느꼈다. 한편으로는 저런 이야기라면 LINE의 이야기도 충분히 재미있는 토크감이 될 수 있다고 생각했다. (물론 영어가 문제…)

Microservices 아키텍쳐로 2개의 서비스로 시작했던 서비스의 개수가 무려 700개 이상으로 늘어났다는 것이 굉장히 놀라웠다. PHP로 시작했지만 지금은 node.js, Python, Go, Java로 언어들이 늘어났다고 한다. 이러한 환경의 어려움을 극복하기 위한 도구로서, 서비스 간의 분산 및 failover를 위해서 ringpop-node, 통신 프로토콜로서 TChannel (+ tcurl, tcap, thriftrw), 서비스 디스커버리로서 Hyperbahn 등을 소개했는데, 다른 오픈소스를 가져다 쓰기 보다는 자체적으로 개발하고 이를 오픈소스화 했다는 점이 조금 신기했다.

How Netflix Directs 1/3rd of Internet Traffic by Haley Tucker & Mohit Vora

No comment.

Beyond the Hype: 4 years of Go in Production by Travis Reeder

Go가 그리 유명하지 않던 시절 Ruby의 CPU 소비를 줄이기 위해서 Go로 이동했다고 한다. Python, Javascript, Java, Ruby등과의 성능 비교 그래프를 보여주었다. 언어를 바꾸고 나서 30대 서버 (…)에서 2대 서버로 바꿀 수 있었다고 한다. 언어의 변경에 따르는 여러가지 문제들에 대해서 논리적인 대답을 가지고 있는 것은 아니라서 좀 아쉬웠다. 토크 자체는 20분 남짓 만에 일찍 끝나고 수많은 질문들이 이어졌는데, 대답하기 쉬운 질문들은 물론 아니었지만 대부분 문제된 적이 없거나 잘 모르겠다는 답변이 돌아와서 ‘4년’의 경험에서 기대한 것보다는 많이 모자랐다. Go언어의 초보라고 할 수 있는 내가 알고 있는 수준에서 크게 다르지 않다라는 느낌.

다만 질문들은 나름대로 Go언어 생태계에서 정답을 내놓을 필요가 있는 것들이라서 나열해본다.

  • Dependency management: vendoring, submodule (Golang은 패키지에 version이라는 개념이 없다.)
  • Compile time: 의존성이 있는 C 라이브러리들이 문제가 되었지 Go가 문제된 적이 없었음. (충분히 큰 소스의 프로젝트라면?)
  • DB들을 위한 라이브러리들의 제공: 아직 불충분.
  • Testing: go test로 충분. rspec과 같은 것이 있는가란 질문에 대해 잘 모르겠지만 Go언어의 특성상 그런 것이 존재할 수 있는지는 의문이라고 코멘트.
  • IDE: sublime, intelliJ, … (Atom은 왜 언급안해…)
  • GC 문제: 지금까지 경험한 적이 없다고. (없는 것 같다고 대답했다가 concurrent GC 언급한 다른 질문자에게 따끔하게 지적받음.)
  • Debugging: 처음에 로그를 사용한다고 대답. godebug 등 오픈소스 도구들도 나타나고 있기 때문에 점차 개선되고 있다고 함. gdb등도 가능. (디버깅에 대한 IDE 지원은 절실하긴 한 듯.)
  • Monitoring: JMX 등의 퍼실러티가 있느냐란 질문이었는데, 그런 건 없고 자기네들은 statsd을 사용.
  • Java 아키텍쳐로부터의 마이그레이션 방법: 마이크로서비스별로.
  • GUI: 서버 위주이고 별로 없는 것 같다고 대답. (아닌데…)
  • Refactoring: 별로 본질적인 것은 아닌 것 같다고 대답.
  • RoR scaffolding: 잘 모르겠다고 대답.
  • Onboard engineer를 위해 특별히 하고 있는 것: 특별히 없음. Go가 variable의 type notation 등의 일부를 제외하면 다른 언어와 크게 다르지 않다고 대답.
  • 언어 개선 표준 프로세스가 있는지: 오픈소스이니 디스커션이 가능하지 않겠냐는 대답.
  • Profiling: pprof. production에 사용하기에는 어렵도 metric을 남기는 쪽이 좋을 듯 하다고 대답.
  • interface가 있는지: 있음.
  • Shared libary로 빌드할 수 있는지: 잘 모르겠다고 대답.
  • Maven 같은 의존성 관리 도구가 있는지: 모르겠다고 대답.
  • 사용하고 있는 design pattern이 있는지: 잘 모르겠다고 대답.

Personalization in the Pinterest Homefeed by Dmitry Chechik

Jet lag 때문인지 너무 졸려서 무슨 이야기를 했는지 잘 모르겠음. 🙁

Rust: unlocking systems programming by Aaron Turon

어느 한 쪽을 희생한 언어들과 달리 Rust는 Control과 Safe라는 특성을 둘다 달성하는 곳을 목표로 하는 언어이고, ownership의 이전 메커니즘에 따른 Memory safety에 대해서 설명함.

Spark: A Coding Joyride by Doug Bateman

Sponsored track인데도 Spark의 명성을 인정하듯 룸이 가득찼다.

Spark의 개요에 대해 설명. Spark, GraphX, MLlib의 코딩을 보여준다고 한 것 같은데, 실제로는 RDD와 필터링 정도만 코드를 보여주었다. 결과적으로는 내가 Spark에 대해서 아는 부분 이상을 얻지는 못한 듯. 스피커가 전문 Trainer라서 그런지 설명을 듣기에는 편했고, Databrics라는 Spark hosting 서비스는 Spark를 시험해보기에 굉장히 편리해보였다. (30일 trial 가능.)

So We Hear You Like Papers by Ines Sombra and Caitie McCaffrey Slides

Caitie McCaffrey는 Distributed system에 대해, Ines Sombra는 Verification 분야에 대해 몇몇 페이퍼들을 소개했다. 둘다 다른 컨퍼런스 등에서도 활약하는 듯 하고, Ines Sombra는 Papers we love meetup의 SF chapter에서 활동하는 듯하다.

둘다 설명하는 속도가 굉장히 빨라서 정확성을 차치하더라도 정말 대단하다고 생각. Exhibiter reception 직후 키노트라 다들 맥주 한두잔 한 후라서 그런지 조금은 덜 진지한 분위기였던 것 같기도 하고… Ines Sombra는 아예 맥주 한병을 들고 마시면서 진행했다. 어쨌든 스마트함을 마음껏 뽐내는 분위기 같아서 재미있었다. 중간중간에 관심을 가져볼만한 페이퍼들도 보였던 것 같아서 나중에 슬라이드를 확인해봐야 할 것 같다.

내일과 모레도 재미있는 토크들은 많은 듯 하니, 게으름 피지 않고 여기에 적어보려고 노력해보겠다. 🙂

Paper: TAO: Facebook’s Distributed Data Store for the Social Graph (Part 1)

Bronson, Nathan, et al. “TAO: Facebook’s Distributed Data Store for the Social Graph.” USENIX Annual Technical Conference. 2013.

Facebook은 사용자들 사이의 관계, 사용자들의 포스팅, 이에 대한 코멘트 등을 MySQL에 저장하고 memcache에 캐싱하고 있었는데, 이를 개선한 TAO라는 시스템에 관한 페이퍼. geographically 분산된 단일한 인스턴스라는 점이 놀라운 점. 이후에도 설명되겠지만 graph abstraction만으로 Facebook의 주요한 데이터들을 표현한다는 것도 매우 흥미로운 점.

Before TAO, Facebook’s web servers directly accessed MySQL to read or write the social graph, aggressively using memcache [21] as a lookaside cache. TAO implements a graph abstraction directly, allowing it to avoid some of the fundamental shortcomings of a lookaside cache architecture. TAO continues to use MySQL for persistent storage, but mediates access to the database and uses its own graph-aware cache.
TAO is deployed at Facebook as a single geographically distributed instance. It has a minimal API and explicitly favors availability and per-machine efficiency over strong consistency; its novelty is its scale: TAO can sustain a billion reads per second on a changing data set of many petabytes.

Background

Facebook의 타임라인과 같은 데이터를 구축할 때 흔히 컨텐트가 생성될 때 타임라인 데이터를 업데이트하는 방식과 타임라인을 읽을 때 타임라인 데이터를 업데이트하는 두가지 방식이 고려되는데, 이 페이퍼에서는 Facebook에서는 모든 항목에 대해 privacy check가 동적으로 이루어져야 하기 때문에 전자의 접근을 불가능하다고 얘기한다. 즉, 실시간으로 aggregation과 filtering이 이루어져야 한다는 것.

We present each user with content tailored to them, and we filter every item with privacy checks that take into account the current viewer. This extreme customization makes it infeasible to perform most aggregation and filtering when content is created; instead we resolve data dependencies and check privacy each time the content is viewed.

MySQL과 memcache를 이용한 원래의 아키텍쳐 대신 TAO를 만들어야 했던 이유로, PHP API에서의 encapsulation 실패 – 자세히는 설명되어있지 않지만, graph abstraction이 아니어서 발생하는 데이터 모델상의 여러가지 문제들을 말하는 것이 아닐까 싶다. – 그리고, PHP가 아닌 언어로부터의 접근 – 역시 이러한 요구사항은 흔히 아키텍쳐의 변화를 이끄는 동력이 되는 듯 – 그리고 lookaside 캐시 아키텍쳐의 여러가지 문제들을 들고 있다. 캐시 아키텍쳐의 문제들로는 다음과 같은 문제들을 들고 있다.

우선 edge들의 리스트를 표현하는 데에 있어서 특정 키에 해당하는 모든 edge 리스트를 가져와야 하는 key-value 캐시는 비효율적임을 들고 있다. 캐시에서 리스트를 직접 지원한다면 이러한 문제를 해결할 수 있으나 동시적인 업데이트에 따른 문제들을 언급하고 있다.

Inefficient edge lists: A key-value cache is not a good semantic fit for lists of edges; queries must always fetch the entire edge list and changes to a single edge require the entire list to be reloaded. Basic list support in a lookaside cache would only address the first problem; something much more complicated is required to coordinate concurrent incremental updates to cached lists.

액세스의 제어를 위한 로직들이 클라이언트에 있으므로 thundering herds와 같은 문제들이 발생하는 것을 언급하고 있다. 이를 캐시에 내장함으로써 더욱 효율적으로 문제를 해결할 수 있다고 얘기하고 있다.

Distributed control logic: In a lookaside cache architecture the control logic is run on clients that don’t communicate with each other. This increases the number of failure modes, and makes it difficult to avoid thundering herds. Nishtala et al. provide an in-depth discussion of the problems and present leases, a general solution [21]. For objects and associations the fixed API allows us to move the control logic into the cache itself, where the problem can be solved more efficiently.

Facebook은 MySQL의 비동기 master/slave 리플리케이션을 사용하고 있기 때문에 슬레이브를 사용하는 데이터센터의 캐시들에는 consistency 문제가 있다. 이 페이퍼에서는 가능한 한 복제본의 캐시의 consistency를 유지하기 위한 방법들을 제시하고 있다.

Expensive read-after-write consistency: Facebook uses asynchronous master/slave replication for MySQL, which poses a problem for caches in data centers using a replica. Writes are forwarded to the master, but some time will elapse before they are reflected in the local replica. Nishtala et al.’s remote markers [21] track keys that are known to be stale, forwarding reads for those keys to the master region. By restricting the data model to objects and associations we can update the replica’s cache at write time, then use graph semantics to interpret cache maintenance messages from concurrent updates. This provides (in the absence of multiple failures) read-after-write consistency for all clients that share a cache, without requiring inter-regional communication.

TAO Data Model and API

TAO의 Object는 64-bit integer로 식별되며, object type (otype)을 가지고 있다. Association은 source object (id1), association 타입 (atype), destination object (id2)로 식별된다. 임의의 두 object들 사이에서 특정 타입의 association은 최대 1개만 존재할 수 있다는 제약이 존재한다. Object와 association은 모두 key-value attribute들을 가지고 있으며 가능한 key들과 value들의 type, 그리고 default value는 type별 schema에 따라 정해진다. per-type schema라는 이 개념은 대단히 새로운 것은 아니지만 일반적인 모델의 attribute 정의에 대해 고민하던 내게 도움이 되었다.

TAO objects are typed nodes, and TAO associations are typed directed edges between objects. Objects are identified by a 64-bit integer (id) that is unique across all objects, regardless of object type (otype). Associations are identified by the source object (id1), association type (atype) and destination object (id2). At most one association of a given type can exist between any two objects. Both objects and associations may contain data as key→value pairs. A per-type schema lists the possible keys, the value type, and a default value. Each association has a 32-bit time field, which plays a central
role in queries1.

Object: (id) → (otype, (key  value)∗)
Assoc.: (id1, atype, id2) → (time, (key  value)∗)

TAO의 Object API는 Object에 대한 기본적인 CRUD에 더해서 field들의 subset을 업데이트할 수 있는 API를 지원하고 있다.

Association API도 association의 CRUD를 위한 API를 제공하고 있다. 매우 흥미로운 점은 친구 관계와 같이 양방향을 가지는 association의 경우, 그 association type을 inverse type으로 설정을 해주면 TAO association API에서 알아서 inverse association에 대해서도 operation을 실행해준다는 점이다. Graph DB에서 당연한 기능인지는 잘 모르겠지만, 이를 application layer에서 직접 구현하고자 한다면 boilerplate 코드가 되기 쉬운 부분들이 일반적으로 해소되고 있다고 생각한다. 한편, inverse type의 association을 추가할 때 가장 걱정이 되는 점은 두 association의 write가 atomic하게 반영될 수 있는가 일텐데, 이에 대해서는 페이퍼에서 명시적으로 언급하고 있지는 않은 듯 하다.

  • assoc add(id1, atype, id2, time, (k→v)*) – Adds or overwrites the association (id1, atype,id2), and its inverse (id1, inv(atype), id2) if defined.
  • assoc delete(id1, atype, id2) – Deletes the association (id1, atype, id2) and the inverse if it exists.
  • assoc change type(id1, atype, id2, newtype) – Changes the association (id1, atype, id2) to (id1,
    newtype, id2), if (id1, atype, id2) exists.

Facebook과 같은 서비스에서는 대부분의 데이터는 오래된 것이고 자주 액세스되어야 할 데이터는 최근 생성된 일부의 데이터라는 점을 creation-time locality라는 말로 표현하고 있다. TAO의 Association Query API들은 creation-time locality에 따른 cache 가능성을 높이기 위해 time range 쿼리가 가능한 점을 엿볼 수 있다. 역시 흥미로운 점은 Association Query API로부터 리턴되는 Association List의 association type별 제약이 정해져있다는 점이다. 잘은 모르지만 이러한 점들은 일반적인 Graph DB에서는 가할 수 없는 제약이 아닐까 싶다.

  • assoc get(id1, atype, id2set, high?, low?) – returns all of the associations (id1, atype, id2) and their time and data, where id2 ∈ id2set and high ≥ time ≥ low (if specified). The optional time
    bounds are to improve cacheability for large association lists (see § 5).
  • assoc count(id1, atype) – returns the size of the association list for (id1, atype), which is the number of edges of type atype that originate at id1.
  • assoc range(id1, atype, pos, limit) – returns elements of the (id1, atype) association list with index i ∈ [pos,pos+limit).
  • assoc time range(id1, atype, high, low, limit) – returns elements from the (id1, atype) association list, starting with the first association where time ≤ high, returning only edges where time ≥ low.

Paper: Immutability Changes Everything

Helland, Pat, and One Market Street. “Immutability changes everything.” (2012).

Abstract

There is an inexorable trend towards storing and sending immutable data. We need immutability to coordinate at a distance and we can afford immutability, as storage gets cheaper.
This paper is simply an amuse-bouche on the repeated patterns of computing that leverage immutability. Climbing up and down the compute stack really does yield a sense of déjà vu all over again.

Thoughts

저장 장치의 가격이 싸지면서 immutability에 기반한 컴퓨팅이 필요해지고 가능해지고 있다고 주장하며, 컴퓨팅의 여러 layer 걸쳐서 그러한 예들을 보이고 있다. immutability가 컴퓨팅에서 중요한 도구임에는 분명하지만 그렇다고 mutability가 컴퓨팅의 역사에서 사라질 것은 아니므로 선택편향이 의심된다. 차라리 로그가 중요하다는 주장이 나아보인다.

이 페이퍼에서 언급하는 Immutability를 활용하는 예들은 다음과 같다.

  • Transaction logs of DBMSs
    • The truth is the log. The database is a cache of a subset of the log.
  • Accounting: “Accountants don’t use erasers.”
  • Append-only distributed single master
  • Forms with many layers
  • Data on the outside: messages, files, documents
  • MapReduce, Dryad
    • Immutable inputs, idempotent functional computation over immutable inputs
  • Versions
    • A linear version history, DAG of version history
  • Multi-version concurrency control
  • Log structured merge trees
  • Copy-on-write
  • Log structured file systems
  • GFS, HDFS
  • Consistent hashing
  • Wear leveling of SSDs
  • Shingled disk systems

Talk: “When “Worst” is Best (in Distributed Systems)” by Peter Bailis

“When “Worst” is Best (in Distributed Systems)” by Peter Bailis at Strange Loop 2015 (Video)

UC Berkeley의 Ph.D. candidate인 Peter Bailis의 Strange Loop 2015에서의 발표.

Worst case를 유리하게 만드는 최적화는 일반적으로 average case를 불리하게 만들지만, 이 Talk에서는 Worst case를 위한 디자인을 통해서 average case도 개선되는 경우들을 예를 들어 보여주고 있다. Worst case에 대한 고려를 하는 것은 매우 강력한 디자인 도구가 될 수 있다는 점을 강조하고 있다.

Worst case를 위한 디자인이 average case도 개선하는 경우들의 예로는 다음과 같은 것들을 들고 있다.

  • Coordination-free/avoding distributed system: CRDTs, I-confluence, RAMP, HAT, Bloom^L, …
  • Replication
  • Failover
  • Tail Latency
  • Universal Design
  • Accessibility

Paper: A simple totally ordered broadcast protocol

Reed, Benjamin, and Flavio P. Junqueira. “A simple totally ordered broadcast protocol.” proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware. ACM, 2008.

이 페이퍼는 Zab라는 ZooKeeper의 내부에 구현되어있는 ordered broadcast 프로토콜을 소개하고 있다. 이 페이퍼는 informal한 형태로 Zab에 대한 요구사항과 동기, 그리고 프로토콜 자체에 대해서 설명하고 있으므로 이를 파악하기에 좋은 것 같다. Zookeeper에 대한 페이퍼Zab에 대한 좀 더 formal한 페이퍼도 따로 있으므로 앞으로 읽어볼 것.

The logical components of the ZooKeeper service

Zab는 Zookeeper Atomic Broadcast라는 이름대로 Zookeeper의 노드들 사이에 동일한 오퍼레이션들의 순서를 유지하고 결과적으로 노드들의 상태를 동일하게 유지되기 위해 사용된다. (Atomic Broadcast 참고.)

Zookeeper는 클라이언트로부터의 request들을 그대로 Zab로 보내는 것이 아니라 conditional operation이나 version increment를 포함하고 있어서 본질적으로 idempotent하지 않은 request를 idempotent한 transaction으로 변환하는 과정을 가지고 있다. 이 변환은 leader 노드에서만 발생할 수 있으며, 그 이유는 leader 노드만이 오퍼레이션으로 인해 변할 미래의 상태에 대한 완벽한 정보를 가지고, 새로운 값을 정할 수 있기 때문이다.

Requirements

Zookeeper는 다음과 같은 요구사항을 가지고 있다.

  • Reliable delivery
    • If a message, m, is delivered by one server, then it will be eventually delivered by all correct servers.
  • Total order
    • If message a is delivered before message b by one server, then every server that delivers a and b delivers a before b.
  • Causal order
    • If message a causally precedes message b and both messages delivered, then a must be ordered before b.
  • Prefix property
    • If m is the last message delivered for a leader L, any message proposed before m by L must also be delivered.

우리가 알고 있는 Zookeeper의 특성 상 다른 것들은 쉽게 추론할 수 있으나, 클라이언트 입장에서의 correctness를 표현한 Causal order requirement는 이러한 말로 표현하는 것을 아직 자주 본 것은 아니라서 눈여겨보게 되었다.

Zookeeper의 어떤 노드가 실패했을 때 snapshot을 읽어들인 다음 snapshot 이후에 배달된 transaction들을 리플레이하게 되는데, 위에서 설명했던 idempotent한 transaction 덕에 이러한 복구 과정에서 atomic broadcast는 at most once delivery를 보장하지 않아도 된다. 이는 또한 복구 과정에서는 total order requirement가 완화되는 것을 의미하기도 한다.

Motivation

이 부분에서는 왜 이미 존재하는 프로토콜을 사용하지 않고 Zab를 고안해서 사용하게 되었는가를 각 프로토콜을 들어 설명하고 있다. 굉장히 많은 페이퍼들을 인용하며 설명을 하고 있는데, 가장 중요한 것은 역시 Paxos와의 비교라고 할 수 있다. 이 페이퍼는 현실의 조건에 따른 가정을 토대로 Paxos를 단순화시킬 수 있다고 이야기 하고 있다.

Paxos는 메시지의 손실과 순서가 바뀌는 것 조차도 허용하고 있지만, TCP를 사용한다면 메시지가 FIFO 순서로 전달되는 것을 가정할 수 있고, Zab는 이에 따라 per-proposer causality를 보장할 수 있다. Paxos는 FIFO channel을 가정하지 않기 때문에 이러한 보장을 할 수 없다.

두번째로 Paxos에서는 복수의 leader로부터 하나의 인스턴스에 대한 proposal이 가능하므로, proposal이 서로 충돌하거나 어떤 값이 commit 되었는지 알아내기 힘든 문제가 있다. Paxos에서는 어떤 노드라도 높은 투표만 얻으면 리더가 될 수 있는 반면, Zab에서는 다수의 노드가 기존의 리더를 버리지 않는 이상 새로운 리더가 될 수 없다. 이로 인해 Zab에서는 주어진 인스턴스에 대해서 단 하나의 proposal을 보장할 수 있고, 이는 프로토콜을 여러 면에서 단순화 시킨다.

Protocol

Zab protocol은 recovery와 broadcast 두 개의 모드로 이루어져있다. Zookeeper를 처음으로 실행했을 때나 leader 실패가 발생했을 때는 recovery 모드가 되고, leader가 성립되고 quorum이 leader와 동기화를 완료하게 되면 broadcast 모드가 된다.

Zookeeper는 broadcast의 leader를 (request를 transaction으로 변환하기 위한) write request의 leader로도 사용하기 때문에, 만약 분리되었을 경우 발생할 둘 사이의 latency를 제거한다.

Broadcast

단순화된 two-phase commit과 유사하다고 얘기하고 있다. two-phase commit과는 달리 Zab에는 abort가 없기 때문에 follower는 leader의 proposal을 수용하거나 leader를 포기하는 두가지의 선택지 밖에는 없으며, 또한 leader는 quorum을 이룬 follower들로부터 ack을 받는다면 commit을 진행할 수 있다.

broadcast 프로토콜은 모든 커뮤니케이션에 대해 FIFO 채널을 이용하므로 순서를 보증하는 것이 매우 쉽다.

leader가 proposal을 보낼 때는 zxid라고 불리는 단조증가하는 ID를 부여한다. Zab는 causal ordering을 보존하기 때문에 전달된 메시지는 zxid들에 의해서도 정렬된다. 이 후에 proposal은 follower별로 존재하는 queue에 넣어지고, 이는 FIFO 채널을 통해 follower로 전달된다. follower는 받은 proposal을 디스크에 쓰고 leader에게 ack을 보낸다. leader가 다수의 follower로부터 ack을 받으면 commit을 broadcast하고 leader 자신에게 메시지를 배달(deliver)한다. follower들은 commit을 받았을 때 메시지를 배달한다.

Recovery

Recovery에서 중요한 것은 commit된 모든 메시지를 제대로 보존하는 것과 commit되지 않은 – skip된 메시지를 보존하지 않는 것이다.

commit된 모든 메시지를 보존하는 문제는 leader election 과정에서 quorum 서버 중에서 가장 높은 proposal number를 가지고 있는 노드를 leader로 선택하는 것이다. 새로 선출된 leader는 새로운 proposal을 처리하기 전에 트랜잭션 로그에 있는 모든 메시지들이 propose되고 quorum에 의해 commit되도록 한다.

새로운 follower 노드가 추가되었을 때는 leader는 우선 follower가 보지 못한 proposal을 모두 queueing하고 그 다음 마지막으로 commit된 proposal까지 commit들을 queueing한 후에 새로운 follower노드를 broadcast 리스트에 등록한다.

skip된 메시지를 보존하지 않는 것은 epoch을 이용한다. Zookeeper의 zxid는 64bit 숫자인데, lower 32bit은새로운 proposal을 생성할 때마다 증가하는 counter이고, high order 32bit은 epoch에 해당한다. 새로운 leader가 선출될 때마다 로그 상에 가지고 있는 가장 높은 zxid의 epoch에 1을 더하고, counter를 0으로 리셋한 zxid를 이후의 proposal을 위해 사용한다.

epoch을 통해서 여러 리더들이 동일한 zxid를 사용하는 것을 방지할 수 있을 뿐만 아니라, 더욱 중요하게는, 한번 실패했던 리더가 되살아나더라도 zxid가 낮기 때문에 리더가 될 수 없고, 이 노드가 follower가 되었을 때 leader는 기존 epoch의 proposal을 truncate하도록 해주기 때문에, recovery 과정이 단순해지고 빨라지는 장점을 가지고 있다.

Closing

Raft 등에서도 채용된 여러가지 개념들을 볼 수 있었다는 점이 재미있었다. two-phase commit-like 프로토콜이나 quorum이 유지되는 한 leadership의 유지, epoch (term)의 개념 등. 또한 다른 consensus 프로토콜들을 통해 어렴풋이 추측하고 있던 Zookeeper의 프로토콜에 대해 조금 더 정확하게 이해할 수 있게된 것 같다. 사실 Zab 이외에도 여러가지 알고리즘이나 최적화 등이 Zookeeper에 활용되었으리라 추측하는데, 위에서 언급한 Zookeeper에 관련한 다른 페이퍼들이나 Zookeeper의 코드를 읽어보아도 재미있을 것 같다.

Paper: Conflict-free Replicated Data Types

Shapiro, Marc, et al. “Conflict-free replicated data types.” Stabilization, Safety, and Security of Distributed Systems. Springer Berlin Heidelberg, 2011. 386-400.

Distributed system에서 replica 사이의 consistency를 유지하는 것은 매우 어려운 문제지만, CRDT라고 불리는 특별한 데이터구조들은 semilattice나 commutativity와 같은 그 자체의 성질을 이용하여 consistency의 문제를 훨씬 단순한 문제로 만들어준다. CRDT에 해당하는 데이터구조나 수학적인 성질들은 오래전부터 알려져있었고 활용되어왔지만, 이 페이퍼의 저자들이 2007년에 처음으로 CRDT라는 이름을 붙였다. 2009년에는 Treedoc이라는 온라인 협업 에디팅을 위한 데이터구조를 제안하면서 역시 CRDT의 한가지 예로서 제시한다. 하지만 이 때까지도 CRDT의 정의는 commutativity를 이용한다 정도로 매우 모호한 상태였지만, 2011년에 출판된 이 페이퍼는 CRDT의 성질을 수학적으로 정의하고 증명한 것에 큰 의미가 있는 것으로 보인다. 이 페이퍼와 같은 해에 출판된 “A comprehensive study of convergent and commutative replicated data types.”란 페이퍼에서는 이 페이퍼의 개념들을 더욱 자세하게 설명할 뿐만 아니라 알려진 CRDT들의 카탈로그를 제시하고 자세하게 설명하고 있다. 이 페이퍼는 오히려 그 페이퍼의 정수만을 간추려놓은 논문으로 보인다.

Strong Eventual Consistency

Eventual consistent 시스템의 경우 필연적으로 conflict resolution이 필요하게 되는데, 이러한 conflict resolution의 부담을 덜어주는 메커니즘으로서 Version vector나 Dotted version vector 등을 사용한다. CRDT는 근본적으로 conflict가 발생하지 않는 데이터 구조이며, 따라서 causality tracking을 필요로 하지 않을 뿐더러 conflict resolution을 위한 coordination 등을 필요로 하지 않는다. 이러한 특성을 Strong Eventual Consistency라고 이야기 하고 있다.

We propose a simple, theoretically-sound approach to eventual consistency. Our system model, Strong Eventual Consistency or SEC, avoids the complexity of conflict resolution and of roll-back. Conflict-freedom ensures safety and liveness despite any number of failures. It leverages simple mathematical properties that ensure absence of conflict, i.e., monotonicity in a semi-lattice and/or commutativity. […] In our conflict-free replicated data types (CRDTs), an update does not require synchronisation, and CRDT replicas provably converge to a correct common state. CRDTs remain responsive, available and scalable despite high network latency, faults, or disconnection.

우선, Eventual Consistency를 어떤 replica의 causal history에 포함된 method는 결국에는 (eventually) 다른 replica의 causal history에 포함되는 것으로 정의하고 있다. 그리고 Convergence의 특성을 추가적으로 실행되는 method가 없어서 서로 다른 replica의 causal history가 동일하게 유지되는 상황에서는 결국에는 두 replica의 상태가 동등해지는 것으로 정의하고 있다. □(Globally)나 ◊(Finally)와 같은 notation은 처음으로 본 것인데 Temporal Logic에서 사용되는 notation인 것 같다.

Definition 2.2 (Eventual Consistency (EC)). Eventual delivery: An update delivered at
some correct replica is eventually delivered to all correct replicas: ∀i, j : fci ⇒ ◊f
cj .
Convergence: Correct replicas that have delivered the same updates eventually reach equivalent
state: ∀i, j : □ci = cj ⇒ ◊□sisj .
Termination: All method executions terminate.

Strong Eventual Consistency는 여기에 더해서 서로 다른 replica의 causal history가 동일하다면 동등한 상태를 가지는 특성으로 정의하고 있다. 이 paper에서는 한 replica의 causal history를 실행된 method들의 집합으로 정의하고 있으므로 – 그 method들에 대한 순서나 인과성 등의 정보는 포함하지 않고 있으므로 causal history라고 부르는 것은 조금 이상한 것 같다 – 정확히는 실행된 method들의 집합이 동일할 경우라고 보면 될 것 같다.

Definition 2.3 (Strong eventual consistency (SEC)). An object is Strongly Eventually Consistent if it is Eventually Consistent and:
Strong Convergence: Correct replicas that have delivered the same updates have equivalent state: ∀i, j : ci = cj ⇒ si ≡ sj .

State-based CRDT (CvRDT) and Operation-based CRDT (CmRDT)

CRDT를 2가지로 분류하고 있다. 첫번째는 상태들을 merge하는 method를 기반으로 정의하는, Replica들의 상태가 converge할 수 있는 형태의 CRDT인 Convergent Replicated Data Type (CvRDT)이고, 두번째는 operation들이 commutative한 성질을 기반으로 정의하는 CRDT인 Commutative Replicated Data Type (CmRDT)이다. Paper에서는 두 가지의 CRDT는 서로를 emulation할 수 있으므로 equivalent하다고 이야기 하고 있다.

우선 CvRDT의 정의를 이해하기 위해서는 lattice와 semilattice라는 수학 개념에 대해서 이해를 해야한다. Lattice란 기본적으로 어떤 ordering에 대해 정의되는 부분순서집합이며, 임의의 두 원소에 대해서 유일한 join과 meet가 그 집합 내에 존재해야한다. 여기서, join과 meet는 least upper bound와 greatest lower bound라고도 불리며, 우리에게 익숙한 개념으로 보자면, 최소공배수와 최소공약수에 해당하는 개념이다. 이 때, 최소공배수와 최소공약수가 각각 join과 meet가 되는 lattice는 배수를 ordering으로하는 정수집합에 해당한다. 정수집합의 모든 두 원소가 서로 배수관계가 있는 것은 아니지만 – 즉 부분순서집합 – 모든 두원소는 최소공배수와 최소공약수를 가진다. Semilattice란 join 또는 meet 중 하나를 가지는 부분순서집합이고, 어느 쪽이냐에 따라서 join-semilattice와 meet-semilattice로 불린다.

CvRDT에서 정의되는 객체는 객체들의 상태 집합에 대한 join-semilattice이고, merge method는 join 즉 least upper bound로 정의된다. 다시 말하면, 서로 다른 두 replica의 어떤 두 상태가 주어지더라도 이 상태를 merge한 상태가 정의되어있다고 할 수 있다. 이러한 객체가 SEC를 만족하는 것에 대한 증명은 어느 한쪽의…

Definition 2.4 (Monotonic semilattice object). A state-based object, equipped with partial order ≤, noted (S,≤, s0, q, u,m), that has the following properties, is called a monotonic semi-lattice: (i) Set S of payload values forms a semilattice ordered by ≤. (ii) Merging states with remote state s′ computes the LUB of the two states, i.e., s •m(s′) = s⊔s′. (iii) State is monotonically non-decreasing across updates, i.e., s ≤ s • u.
Theorem 2.1 (Convergent Replicated Data Type (CvRDT)). Assuming eventual delivery and termination, any state-based object that satisfies the monotonic semilattice property is SEC.

CmRDT는 말그대로 update method의 commutativity에 기초해서 상대적으로 단순하게 정의되고 있는데, 중요한 것은 concurrent update에 대해서만 commutativity 특성을 요구하고 다른 모든 update는 causal하게 전달되는 것을 가정하고 있다. 현실적으로는 어떤 경우에 어떤 update가 commutative하게 일어나고 어떤 경우에는 그렇지 않은 것은 쉽지 않기 때문에 이러한 제약을 주는 이유에 대해서 조금 의문이 들고, 특히 엄밀하게 정의되어있지 않은 CvRDT와 CmRDT의 equivalence에 대해서도 의문이 들게 만드는 부분이다.

Definition 2.6 (Commutativity). Updates (t, u) and (t′, u′) commute, iff for any reachable replica state s where both u and u′ are enabled, u (resp. u′) remains enabled in state s • u′ (resp. s • u), and s • u • u′ ≡ s • u′ • u.
Theorem 2.2 (Commutative Replicated Data Type (CmRDT)). Assuming causal delivery of updates and method termination, any op-based object that satisfies the commutativity property for all concurrent updates, and whose delivery precondition is satisfied by causal delivery, is SEC.

Example CRDTs

먼저 increment-only integer counter (G-Counter)를 위한 CRDT를 제시하고 있는데, 여러 replica는 integer vector의 각 replica에 해당하는 component를 increment하고, 두 vector의 merge operation은 각 component의 max를 취한 vector를 돌려주는 것으로 정의하고 있다. value method는 모든 component의 합에 해당하는 값을 돌려주게 된다.

increment와 decrement 둘다 가능한 integer counter (PN-Counter)를 위해서는 위에서 정의한 increment-only counter 2개를 결합하여, 하나는 increment를 기록하고 다른 하나는 decrement를 기록해서 실제 value method는 둘 사이의 차에 해당하는 값을 돌려주는 CRDT를 제시하고 있다.

여기서 설명한 G-Counter, PN-Counter를 포함해 G-Set, 2P-Set 등으로 이름지어진 여러 CRDT, 그리고 Directed Graph의 operation-based CRDT 구현 등에 대해 간략하게 설명하고 있는데, 위에서 언급한 “A comprehensive study of convergent and commutative replicated data types.”에서 훨씬 자세한 설명을 하고 있으므로 이 글에서는 생략하도록 한다. 이에 대해서 알고자 한다면 다음 페이지를 참고하면 좋을 것이라고 생각한다.

  • https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
  • https://vaughnvernon.co/?p=1012
  • http://blog.plasmaconduit.com/crdts-distributed-semilattices/
  • https://github.com/aphyr/meangirls

Closing

  • CRDT가 distributed system의 여러가지 도구들 – vector clock, log, … – 과 commutativity라는 관점에서 유사성을 공유하고 있는 것을 고려하면, CRDT의 정식화나 실제 CRDT들에 대해서 생각해보는 것은 좋은 도구가 되며 distributed system을 다루기 위한 사고 훈련이 되는 것 같다.
  • CRDT가 모든 문제를 해결해줄 수는 없으나 이미 알려진 CRDT들을 이용해서도 애플리케이션 관점에서 의미있는 이익을 얻을 수 있는 것으로 보인다. Garbage collection과 같은 실제적인 이슈들이 있으나 해결이 불가능한 것은 아니고, Riak 2.0 등에서 CRDT를 도입한 것을 볼 때 실제적인 응용을 시도해 볼 가치가 있다고 생각한다.
  • 이 논문의 저자들의 2007년, 2009년에 출판한 논문들은 CRDT라는 이름만 붙어있을 뿐이지 수학적인 정식화 등은 전혀들어있지 않다. 하지만, 이름을 붙이고 수년동안 연구를 하면서 완벽하지는 않지만 어느 정도의 엄밀함을 가진 모델을 성립시키고 하나의 분야로서 다루어질 수 있게 된 것 같다. 물론 이것만 하더라도 대단한 것이지만, A급 컨퍼런스의 A급 논문들만 보다보면 처음부터 거추장스러운 것은 하나도 없고, 논리적으로 완벽하며 또한 해당 분야에서도 중요한 의미를 지니고 있는 세상에 없을만한 것으로 보이곤 한다. 이 둘을 보면서, 평범한 과학자나 엔지니어들의 현실은 오히려 이러한 A급 논문보다 이들 논문들과 더 가깝지 않을까라는 생각이 조금 들었다.