Actors in Scala

 

Actors in ScalaActors in Scala by Philipp Haller and Frank Sommers

150페이지 남짓의 이 책은 Scala의 Actors 라이브러리에 대한 책이다. 이 책의 저자 중 한명인 Philipp Haller는 Scala Actors 라이브러리의 저자다.

이 책은 Scala Actors를 다루는 것에 대한 기본적인 내용과 Exception/Termination handling, Actor 실행 방법의 customization, Remote Actors를 상세하게 다루고 있다. 원래는 Actor를 사용하는 패턴도 기대하고 있었지만 MapReduce와 같은 몇가지 예시 정도 외에 좀 더 완전한 내용의 것은 찾을 수 없었다. 하지만, 기본적인 Actors 라이브러리의 기본적인 개념을 익히는데에는 좋은 책일 듯 하다.

한가지 문제라면, Scala 2.10 부터는 Actors 라이브러리가 deprecated 되었고, Akka로 대체되었다는 것이다. Scala Actors의 자세한 히스토리는 잘 모르지만, Akka는 Scala Actors와 커다란 차이는 없는 반면 더욱 일관성이 있는 느낌이 든다. Scala Actors와 Akka의 차이에 대한 사항은 Scala Actors Migration Guide를 참고하면 좋을 듯 하다.

Akka는 Java와 Scala 모두 지원하고 있기 때문에, 기존에 Java 위주의 프로젝트를 진행하고 있었지만 Scala 프로젝트도 함께 진행하기 위해 연동해야 하거나 Scala 프로젝트로 전환하는 경우의 통합 수단으로서, 기존의 language-agonostic RPC들, ZeroMQ 등의 대안으로 좋은 선택이 될 수 있지 않을까 생각해보고 있다.

Read More

Hacking Culture

Hacking Culture by Jesse Robins

QCon San Francisco 2012에서 Chef로 유명한 Opscode의 공동창업자인 Jesse Robins가 발표한 내용입니다. Chef나 Opscode에 대한 홍보가 섞여있고, 내용은 어디선가 들어봤을 법한 내용들이었지만, 자신의 이야기를 곁들여서 재미있고 한층 더 마음에 와닿게 설명을 하고 있는 것 같습니다.

Velocity 2009

요즈음 유행하고 있는 DevOps라는 개념이 처음 나온 것은 Velocity 2009에서의 John Allspaw가 발표한 “10 Deploys per Day: Dev and Ops Cooperation at Flicker” (Slides)라는 강연입니다. Jesse Robins의 강연도 이 강연의 일부 내용을 다시 소개하고 있는 것 같군요.

Continuous Delivery

장기간에 걸친 커다란 변경은 위험하기 때문에 작은 양의 코드를 좀 더 자주 배포해야한다는 개념을 Change monster라는 그림을 통해 설명하고 있습니다.

hacking_culture_00

결국 더 빠르게 비즈니스 가치로 이어지고, 버그를 방지할 수 없는 한 버그를 더 빨리 고칠 수 있으며, 개발자들은 자신이 변경한 것을 바로 볼 수 있기 때문에 즐겁게 일할 수 있다는 내용입니다.

DevOps

‘테스트는 통과했으니 이제 운영자의 책임이야’, ‘제가 필요로 하는 권한이 없어’ 같은 전통적인 개발-운영의 문제를 풀기 위해서는 단지 도구가 아니라 서로 신뢰하는 환경이 필요하다고 얘기하고 있습니다.

조직 구조가 제품의 구조를 결정한다는 얘기를 Conway’s law를 빌려 이야기 하고 있습니다.

하나하나 설명하기는 힘들지만, 아래의 그림 한장이 DevOps의 전체 스택을 보여주는 것 같군요.

 

 

hacking_culture_01

Changing Culture

Toyota Production System (이하 TPS)이 한창 유행할 때 모두가 이를 벤치마킹해서 똑같은 시스템을 만들었지만, 가장 핵심적인 요소라고 할 수 있는 누구든지 문제의 해결을 위해서 라인을 정지시킬 수 있는 것은 따라하지 못했다고 얘기하면서 문화의 중요성을 강조합니다.

문화를 바꾸기 위한 다섯가지 조언을 하고 있습니다.

1. Start small, build trust & safety

작은 것은 위협도 되지 않거니와 무시해도 좋다고 생각하기 때문에 거부감을 가지지 않습니다. 사람들에게는 그저 실험이라고 얘기하라고 하고 있습니다.

2. Create champions

자신이 일으키는 변화를 신뢰하고 지원하는 관리자가 있어야 합니다. 그리고, 주변 사람들 모두에게 credit을 주고, 변화와 관련된 사람들에게 특별한 상태 (예를 들어 ‘이달의 직원’)를 주어 그들이 새로운 변화에 대해 더욱 많은 이야기들을 하도록 해야합니다.

3. Use metrics to build confidence

변화를 지지할 수 있는 KPI (예를 들어, MTTR)를 찾아서 그것을 통해 사람들에게 가치를 보여주고, 나중에는 변화하지 않을 경우의 비용을 보여주는 용도로 사용합니다. 사람들에게 변화와 관련한 이야기를 들려줄 때 데이터를 가지고 이야기합니다.

4. Celebrate successes

사람들과 문제를 극복한 사례에 대해 긍정적인 면을 이야기 합니다. 절대로 문제를 만들어낸 사람들에 대해서는 이야기 하지 않습니다.

5. Exploit compelling events

언젠가는 변화를 위한 중요한 기회가 자연스럽게 찾아오게 됩니다. 중요한 것은 이 때 ‘I told you so’가 아니라 ‘What do we do now’라고 이야기할 수 있어야 합니다.

Hacking Permission

어떤 사람들은 스스로의 시간을 털어서 다른 사람들에게 도움이 되는 옳은 일을 하려고 하지만 보통 권한이 없기 때문에 그렇게 하지 못합니다. 그들에게 “site directors”와 같은 권한을 주라고 얘기합니다.

hacking_culture_02

Don’t Fight Stupid, Make More Awesome

이 강연에서도 언급했다시피 변화를 일으키는 것에는 많은 시간과 인내심이 필요한데, 이 문구를 되새기면 언제든지 다시 힘을 낼 수 있을 것 같은 느낌이군요.

hacking_culture_03

Read More

Programming in Scala

Programming in Scala 2nd EditionProgramming in Scala, Second Edition

2013년이 시작하고 얼마 지나지 않아 트위터에서 개발자 저마다 개인적으로 2012년의 프로그래밍 언어를 꼽는 것이 유행한 적이 있다. 조금 늦었지만, 내게 2012년 한 해의 언어를 꼽으라면 Scala가 될 것 같다.

가장 큰 이유는 두가지로, 첫번째는, (정확히 세어보지는 않아서 모르겠지만 아마도) 2012년 동안 가장 많은 라인을 코딩한 프로그래밍 언어가 Scala라는 것, 두번째는, Programming in Scala를 읽었다는 점이다.

“The Scala Programming Language”

이 책의 주 저자라고 할 수 있는 Martin Odersky는 바로 Scala 언어의 설계자로, 즉 이 책은 흔히 “The XXX Programming Language”에 해당하는 책이라고 할 수 있다. 책의 내용은 Scala의 전반적인 특징들을 예제를 통해서 익히는 튜터리얼 성격의 도입부와 주요한 문법들을 설명하는 부분, 클래스 라이브러리에 관한 부분으로 나누어져 있다고 볼 수 있는데, 지루해 보이는 예제 프로그램을 여러 장에 걸쳐서 계속해서 써먹고 있다는 것을 빼고는 잘 쓰여진 프로그래밍 언어 서적이라고 생각한다. 따라서, Scala 언어를 공부하고자 한다면 이 책을 읽는 것을 추천해도 무리가 없으리라 생각한다.

Scalable Language

이 책을 읽으면서 Scala 언어를 좋아하게 된 가장 큰 이유 중 하나는, 매우 일반적인 문법 토대를 세우고, 다른 문법 요소나 클래스 라이브러리, Java 언어와의 호환성을 그 위에 일구어 냈다는 것이다. 예를 들어, 패턴 매칭(match…case 구문)이 예외 처리나 Actor에서도 사용되는 것이라든지, 기본형이나 컬렉션 클래스들의 Java 호환성을 implicit conversion을 이용해서 해결하는 것과 같은 것들이다. Java 언어를 공부할 때, 특정한 클래스들이 문법의 요소로 사용되는 것이 마음에 들지 않았는데, Scala는 그런 면에서는 오히려 C++ 언어 template을 이용한 확장성 있는 문법을 보는 듯한 느낌이다. 물론 이 언어의 이름인 Scala도 Scalable Language를 의미하는 것이다.

The Throne Threatened

한편, 최근 몇 년간 나의 과제 중 하나는 JVM 환경에서 적절한 glue language를 찾는 것이었다. 그 과정에서 물망에 올랐던 JRuby는 Java와의 호환성 면에서 프로그래머를 괴롭게 만드는 여러가지 문제들이 발견되어 포기했고 (지금은 해결되었을런지도 모르겠다), Groovy는 초기의 기대에 비해 너무나 인기를 끌지 못해서 다른 사람들을 설득하기가 어려웠는데, 반면, Scala 언어는 Java의 기본형이나 시스템 클래스들, 클래스 라이브러리들과의 호환성이 위에서 언급한 것과 마찬가지로 매우 세심하고 우아한 형태로 준비되어 있는 동시에, 어느 정도는 사람들의 이목을 끌었다는 장점이 있다. 오히려 Java의 개선 방향을 제시해주는 것은 아닐까 생각이 들 정도로 JVM 환경의 언어 수준을 한층 더 끌어올린 것 같다.

Closing

이 책을 읽은 것은 몇 달 전의 일이지만, 이제 Pattern matching과 Actor를 쓰기 시작하는 정도에 익숙해진 정도로 대체로 아직은 Java 코드 수준과 크게 다르지 않은 수준의 코드를 쓰고 있기 때문에, Scala 언어로 쓰인 오픈소스 프로젝트의 코드를 통해 좀 더 Scala다운 스타일의 좋은 코드들을 경험해보는 것이 좋을 것 같다.

Further Reads

 

 

 

Read More

The Facebook Release Process

The Facebook Release Process by Chuck Rossi

사용자들이 항상 사용하고 있는 서비스를 하면서 빠르게 변화하는 것은 두마리 토끼를 잡으려는 것과 같이 어려운 일이기 때문에 많은 고민과 노력을 통한 좋은 프랙티스가 필요하다고 생각되지만, 실제로는 그러한 프랙티스는 그다지 널리 알려져 있지는 않는 것 같다.

이 발표는 QCon SF 2012의 발표 중 하나로, Facebook의 Release Engineering을 2008년부터 지금까지 담당해온 Chuck Rossi가 Facebook의 Release Process를 소개하고 있다.

Facebook의 개발자나 코드의 규모는 상당히 큰 편이지만, 릴리즈의 속도는 현재 일하고 있는 서비스의 그것과 거의 유사해서 이 발표를 통해 어떤 면에서는 자신감을 얻을 수 있었고, 반면에 앞으로 개선할 수 있는 많은 영감들을 얻을 수 있었던 것 같다.

이 발표의 주요한 점들을 요약하면 아래와 같다.

Weekly Release & Daily Releases

우선 trunk, lastest, production 3개의 branch로 관리되고 있다. 매주 일요일 오후 6시에 trunk로부터 lastest가 생성되고, 이를 이틀 동안 테스트한 뒤에 production으로 push가 되어 release가 된다. 또한, 매일 300개 가량의 cherrypick을 통해 production으로 릴리즈되고 있다고 한다. 작은 크기의 release를 더욱 자주할 것을 권장하고 있다.

Dogfooding

Facebook의 모든 직원들은 facebook을 사용할 때, www.lastest.facebook.com으로 redirection된다고 한다. 더욱 테스트를 잘하기 위한 이유도 있겠지만, 서비스에 문제를 일으켰을 때, 사용자들이 느낄 고통을 직원들이 느껴보라는 이유도 있다고 한다. 그리고, 이 내부 서비스에 문제가 생기더라도 릴리즈 매니저가 롤백을 하지 않고 고칠 때까지 그대로 둔다고 한다.

Self Service

개발자 개개인이 릴리즈하고자 하는 commit을 추적하기 위해서 릴리즈 매니저에게 메일을 쓴다든가 물어보는 것이 아니고, IRC bot을 통해 자신의 commit이 현재 어떤 상태인지 추적할 수 있다고 한다.

 

Test Automation

Weekly Release는 이틀간의 테스트 기간이 있지만, Daily Release는 그렇지 않은 것 같은데, Daily Release의 테스트는 어떻게 이루어지는가의 의문이 남는데, 자세히 언급하고 있지는 않지만, 일단 자동화된 테스트들이 굉장히 많으며, 이들에 의존하는 것이 아닌가 싶다.

Error Tracking / Perflab

에러의 종류별로 발생 빈도나 API의 응답 속도 등의 트렌드를 그래프로 살펴볼 수 있고, 이를 릴리즈 시기와 비교할 수 있기 때문에, 어떤 릴리즈가 regression을 발생시켰는지를 쉽게 파악할 수 있다. 에러에 직접적으로 관련된 소스 코드를 통해 문제를 일으킨 개발자를 쉽게 찾을 수 있다.

Gatekeeper

어떤 기능을 정해진 조건의 사용자들에게만 릴리즈할 수 있다. 실험적인 기능을 소수의 사용자에게 먼저 릴리즈하고 안정화를 거친 후 전체 사용자에게 릴리즈할 수 있는 bucket test 등의 용도로 사용할 수 있다. Facebook의 다양한 개인 정보들을 가지고 분류할 수 있다.

Push Karma

어떤 commit의 규모 (추가, 변경, 삭제된 라인의 수), 논란이 되는 정도 (review 상의 comment, rejection) 등을 막대 그래프로 시각화 하고 있고, 릴리즈 매니저만 볼 수 있는 개발자에 대한 Like/Dislike 버튼이 있어서 어떤 commit의 위험성을 가늠할 수 있도록 도구를 구성하고 있다.

BitTorrent

수천대에 이르는 서버에 빠른 시간 내에 배포하기 위해서 BitTorrent를 이용하고 있다. 예전에 일했던 팀에서는 비슷한 이유로 Binary Tree 형태로 rsync 구동 플랜을 짜서 배포했던 적이 있었다.

Culture

릴리즈 관리자가 사용할 수 있는 도구는 소프트웨어적인 도구와 문화라고 얘기할만큼 개발 문화의 중요성을 강조하고 있다. 항상 그렇지만, 도구만으로는 성공할 수 없다.

Further Reads

 

 

 

 

Read More

What consistency does your key-value store actually provide?

What consistency does your key-value store actually provide? by Anderson, Eric, et al

Many key-value stores have recently been proposed as platforms for always-on, globally-distributed, Internet scale applications. To meet their needs, these stores often sacrifice consistency for availability. Yet, few tools exist that can verify the consistency actually provided by a key-value store, and quantify the violations if any. How can a user check if a storage system meets its promise of consistency? If a system only promises eventual consistency, how bad is it really? In this paper, we present efficient algorithms that help answer these questions. By analyzing the trace of interactions between the client machines and a key-value store, the algorithms can report whether the trace is safe, regular, or atomic, and if not, how many violations there are in the trace. We run these algorithms on traces of our eventually consistent key value store called Pahoehoe and find few or no violations, thus showing that it often behaves like a strongly consistent system during our tests.

예전에 HP-KVS에 관련해서 자료를 찾다가 발견한 페이퍼인데, 얼마전 한국에 다녀올 때 읽어보게 되었습니다.

1. Perceived consistency rather than worst-case consistency

이 페이퍼는 일반적으로 key-value store들이 보장하는 worst-case consistency가 아니라, 실제로 client에 의해서 관찰되는 consistency의 수준을 측정하는 알고리즘을 제안하고 있다. 우리가 스토리지 기술을 선택할 때는 물론 worst-case consistency가 고려되기는 하지만, 실제로는 ‘실용적인’ 접근을 취하는데, 그것이 의미하는 바는 애플리케이션의 액세스 패턴에 따라 사용자가 느끼는 consistency의 수준이 달라질 수 있음을 고려해서 스토리지 기술을 선택한다는 것이다. 이 페이퍼가 해결하려는 문제 자체가 엄밀하거나 학술적이기 보다는 실용적인 의미를 해석하려는 것이기 때문에 한계는 있겠지만, 어떤 worst-case consistency를 가진 스토리지 – 예를 들어 eventually consistent 스토리지들이 어떤 애플리케이션에 필요한 consistency를 달성하기에 충분한지 충분하지 않은지에 대해서 매우 피상적으로 논의하는 것보다는 체계적인 방법을 제공한다는 점 그리고, 그러한 방법이 존재할 수 있다는 점에서 의미가 있는 것 같다.

2. A eager, eventually consistent protocol often achieves strong consistency

이 알고리즘을 통한 검증을 역시 HP에서 만든 eventually consistent key-value store인 Pahoehoe를 가지고 실험한 결과를 보여주고 있는데, 가장 concurrent한 조건 (128 concurrent processes on 1 key)에서도 consistency violation의 수가 10% 이하로 발생하고 있고, 일반적인 조건 하에서는 1% 수준이다. 그 이유를 우리가 일반적인 웹 애플리케이션에서 예상하고 있는 것과 마찬가지로 concurrent write 하에서의 read가 많지 않기 때문으로 설명하고 있다.

3. Lamport’s consistency assumption on registers: safe, regular, and atomic

이 페이퍼가 검증하려고 하는 consistency 수준의 분류로 Leslie Lamport가 On Interprocess Communication. Part I: Basic Formalism에서 제안한 register의 3가지 consistency semantic을 사용하고 있다. 이는 다음과 같다.

3가지의 consistency 모두 write와 concurrent하지 않은 read는 가장 최근의 write에 의한 값을 return 해야한다. 차이는 write와 concurrent한 read에서 발생한다.

  • safe: write와 concurrent한 read는 임의의 값을 return
  • regular: write와 concurrent한 read는 가장 최근의 write에 의한 값과 concurrent한 write들에 의한 값들 중 하나를 return
  • atomic: write와 concurrent한 read도 가장 최근의 write에 의한 값을 return

worst-case consistency를 가지고 예를 든다면, 최근 유행하는 eventual consistent storage들은 concurrent하지 않은 read에 대해서 가장 최근의 write에 의한 값을 return하는 것을 보장하지 않으므로 가장 느슨한 수준인 safe 조차 만족하지 못한다. 반면에 일반적인 ACID 데이터베이스는 atomic 수준에 해당한다.

4. Methods

이 페이퍼가 제안하고 있는 알고리즘은 대략 다음과 같다.

  1. 어떤 key-value store에 대한 클라이언트의 모든 액세스에 대해 시작 시각과 종료 시각, 그리고 저장하거나 읽어온 값의 로그를 기록한다.
  2. 이 로그를 바탕으로 오퍼레이션이 vertex이고, should-happen-before 관계가 edge인 directed graph를 구성한다. 이 때 이 관계는 검증하려는 consistency 종류에 따라서 달라지는데, 대체로 시간의 관계, 값의 인과 관계를 의미한다고 보면 된다.
  3. 구성된 graph에서 cycle이 발견되지 않으면 consistent, 발견되면 inconsistent하다고 판단한다.

straight-forward하기 때문에 쉽게 이해할 수 있다. 시각의 정확성이나 값의 인과관계를 찾는 부분 등에서 보완이 필요한 것 같긴 하지만 중요한 문제는 아닌 것 같다.

5. Measuring Consistability

여러 eventually consistent 스토리지들은 failure가 발생했을 때 consistency를 희생하게 되어있는데 이 때의 consistency 희생이 어느 정도인지 측정하는 작업이 필요하다.

6. Further Reads

  • J. Misra, Axioms for memory access in asynchronous hardware systems, 1986.
  • L. Lamport, On interprocessing communication, Part I: Basic formalism and Part II: Algorithms, 1986
  • W. Vogels, Eventually consistent, 2009
  • A. Aiyer, et al., On the availability of non -strict quorum systems, 2005
  • E. Anderson, et al., Efficient eventual consistency in Pahoehoe, an erasure-coded key-blob archive, 2010

Read More

Paxos Made Simple

Paxos Made Simple by Leslie Lamport

Paxos Made Simple이라는 글의 저자인 Leslie Lamport는 분산 컴퓨팅 분야에서는 너무나 유명한 분이기 때문에 따로 설명할 필요가 없을 정도입니다. 예를 들어, 1978년에 출판된 “Time, Clocks, and the Ordering of Events in a Distributed System”과 같은 페이퍼는 인용 회수로 볼 수 있는 그 영향력 뿐만 아니라 OS 수업의 읽기 과제로도 빠질 수 없는 그야말로 seminal work입니다. 그의 주요한 업적 중 하나가 바로 Paxos 알고리즘인데, 최근에는 Chubby나 Zookeeper 등의 제품으로 구현되어 분산 시스템의 중요성이 점점 떠오르고 있는 요즈음 더욱 더 일상적으로 쓰이게 되어가고 있습니다.

The Paxos algorithm, when presented in plain English, is very simple.

Abstract에서 보다시피 이 글은 Paxos 알고리즘을 쉬운 말로 설명하고자 하는 시도인데, 합의 문제로부터 정의되는 조건을 충족하기 위한 자연스러운 해결책이 바로 Paxos 알고리즘임을 보이려 하고  있습니다.

하지만, 논리적인 단계들을 정확하기 이해하기 위해서는 쉬운 말로 쓰여진 용어들을 정확하게 해석해야 하기 때문에, 프로그래머 입장에서 볼 때는, 오히려 의사 코드 수준으로 설명하는 다른 글 (예를 들어, Paxos Made Moderately Complex)들이 훨씬 더 이해하기 쉽다는 생각이 들었습니다.

아래는 요약이라고 하기에는 너무 길고, 그렇다고 번역이라고 할 수도 없지만, 개인적으로 중요하다고 생각한 점들을 기록한 메모라고 보시면 좋을 것 같습니다.

(more…)

Read More

Consistency Tradeoffs in Modern Distributed Database System Design

지난 번에 소개했던 IEEE Computer 2012년 2월호의 CAP Theorem 특집 중 세번째 글입니다. CAP Theorem 특집을 읽게된 계기도 바로 이 글의 저자인 Abadi의 블로그 글이었습니다.

Consistency Tradeoffs in Modern Distributed Database System Design by Daniel J. Abadi

Critique

현대의 DDBS에서 CAP의 consistency/availability tradeoff 보다 consistency/latency tradeoff가 중요한 설계상의 결정임을 주장하고 PACELC라는 모델을 제안하고 있습니다.

CAP 만으로 설명하기 어려웠던 설계 결정들에 대해 의문이 있었다면 PACELC가 완벽하지는 않지만 CAP에 비해서 더 좋은 모델임에 동의할 수 있을 것 같습니다. 주변 분들에게도 PACELC에 대해서 설명해주면 당연하게 받아들이는 눈치였습니다. 한편, 이 글은 매우 간결하면서도 문제로부터 결론을 도출하기 까지 논리의 흐름이 부드럽게 이어지기 때문에 이해가 잘 되고 그리 무겁지 않게 읽을 수 있습니다.

PACELC의 개념이 직관적으로는 이해하기 쉬운 반면, 현재 존재하는 시스템을 분류할 때 저자도 언급하고 있는 애매한 점들이 등장하는 것을 보면 엄밀한 도구라고 보기에는 약간 무리입니다. tradeoff 의 모든 측면을 모델로 표현하는 것은 매우 어렵기 때문에 베이스라인이라는 표현과 이로부터 상대적인 tradeoff의 유무를 기준으로 사용한 것 같습니다.

역시 완벽하지는 않겠지만 현대의 DDBS에서 활용하고 있는 설계 결정들을 모두 정리해서 스펙트럼 또는 이에 상응하는 모델로 정리할 수 있다면 앞으로의 DDBS 프레임워크의 발전에서 중요한 기초가 될 수 있지 않을까 생각합니다.

아래는 이 글의 요약입니다.

CAP is for Failure

CAP에서 consistency와 availability 사이의 tradeoff를 발생시키는 요소는 단지 partition tolerance 만이 아니라, partition tolerance와 network partition의 존재, 두 가지 요소의 조합이기 때문에, network partition이 존재하지 않을 때, CAP 자체는 consistency와 availability를 동시에 만족시키는 시스템을 허용하고 있다.

Consistency/Latency Tradeoff

network partition이 존재하지 않는다고 하더라도 consistency, availability, latency 사이의 tradeoff는 존재한다. 이러한 tradeoff가 존재하는 이유는 high availability 요구사항으로 인해 시스템은 데이터를 복제해야하기 때문이다.

Data Replication

시스템이 데이터를 복제하는 순간부터 consistency와 latency 사이의 tradeoff가 발생한다. 데이터 복제를 구현하는 데에는 아래와 같이 3개의 방법이 존재하지만, 각각은 모두 latency의 요소가 존재한다.

(1) 데이터의 업데이트를 동시에 모든 복제본으로 보내기

선처리 레이어(preprocessing protocol)를 통과하지 않거나 합의 프로토콜 (agreement protocol)이 없다면 오퍼레이션의 적용 순서의 차이로 인해 복제본들 사이의 차이가 발생한다. 선처리 레이어나 합의 프로토콜을 사용한다면 모든 복제본들이 합의된 순서대로 업데이트를 적용하는 것을 보장할 수 있지만, 선처리 레이어를 위한 추가적인 시스템 컴포넌트, 모든 복제본에 대한 업데이트, 합의 프로토콜 자체 등 latency가 발생하는 여러가지 원인들이 된다.

(2) 데이터의 업데이트를 합의된 마스터 노드에 먼저 보내기

마스터 노드는 모든 업데이트 요청을 처리하고 마스터 노드가 처리한 순서는 마스터 노드가 모든 리플리카에 복제하면서 다른 복제본들에도 그대로 적용된다.

마스터로부터 다른 복제본으로의 복제 방법은 아래와 같은 3가지가 존재한다.

a. 동기적인 복제: 복제본들로의 업데이트가 일어날 때까지 마스터 노드는 대기한다. 복제본들이 consistent하지만, 모든 복제본들의 업데이트로 인해 latency가 증가한다.

b. 비동기적인 복제: 복제본들이 업데이트 되었다는 보장이 없으므로, consistency/latency tradeoff는 시스템이 읽기를 어떻게 다루느냐에 달려있다.

i. 시스템이 모든 읽기를 마스터 노드에서 수행한다면 consistency의 감소가 없지만, 마스터 노드가 다른 복제본에 비해서 가까운 곳에 있지 않을 때, 또는 마스터 노드가 과부하 상태이거나 동작 불능 상태일 때는 latency가 발생한다.

ii. 어떤 노드에서도 읽기를 수행하도록 한다면 읽기의 latency는 좋아지지만, 동일한 데이터의 inconsistent한 읽기가 발생한다. update sequence number의 추적을 통해 sequential/timeline consistency 또는 read-your-writes consistency를 구현해 consistency의 감소를 줄일 수 있다.

c. 데이터의 업데이트를 복제본의 일부에 대해서는 동기적으로 복제하고, 나머지는 비동기적으로 복제한다. 이 경우에도 consistency/latency tradeoff는 시스템이 읽기를 다루는 방식에 달려있다.

i. 동기적으로 복제가 된 적어도 1개 이상의 노드로부터 읽기를 수행한다. (R + W > N)

ii. 동기적으로 업데이트 되지 않은 노드들에서 읽기를 수행하도록 허용한다. (R + W <= N)

(3) 데이터의 업데이트를 임의의 노드에 먼저 보내기

하나의 데이터 항목에 대한 두개의 업데이트가 서로 다른 노드로 보내질 수 있다. 동기적인 복제인가, 비동기적인 복제인가에 따라서 (1), (2)에서와 같은 latency 문제나 consistency 문제가 발생한다.

Tradeoff Examples

PNUTS의 경우, 마스터 노드로부터 비동기적으로 데이터를 복제하고, 아무 노드에서나 읽기를 수행하므로 (즉, 2-b-ii의 경우), latency를 위해 consistency를 tradeoff 하고 있다. 반면, CAP의 관점에서는 network partition이 발생했을 때, 소수 (minority) 파티션에 존재하는 마스터 노드는 사용 불가능하므로 consistency를 위해 availability를 trade-off하는 CP 시스템에 해당한다.

PNUTS는 일반적인 상황 (baseline case)에서 consistency를 희생하는 선택은 CAP에서의 consistency/availability tradeoff 라기보다는 consistency/latency tradeoff 때문이라고 할 수 있고, 일반적인 시스템에서 consistency를 희생하는 주된 이유가 CAP이 아니라는 증거를 보여주고 있다.

PACELC

DDBS에서의 consistency tradeoff는 CAP 대신 다음과 같은 PACELC로 좀 더 완전한 설명이 가능하다.

  • if there is a partition (P), how does the system trade off availability and consistency (A and C);
  • else (E), how does the system trade off latency and consistency (L and C)?

예를 들어, partition이 발생했을 때 availability를 위해 consistency를 포기하고, 보통의 상황에서는 낮은 latency를 위해 consistency를 포기하는 Dynamo, Cassandra, Riak과 같은 시스템들은 PA/EL 시스템이다. VoltDB/H-Store, Megastore와 같은 ACID 시스템들, BigTable과 이에 관련된 시스템들 (e.g. HBase) 은 PC/EC 시스템이다. MongoDB는 partition이 발생했을 때 master에서 복제되지 않은 데이터가 있더라도 새로운 master를 선출해서 서비스를 하기 때문에 PA/EC 시스템이다. PNUTS는 위에서 설명한대로 PC/EL 시스템이다. (이 때, PC는 CAP에서의 consistency가 아니라 일반적인 상황에 대비해서 consistency를 희생하지 않는다는 의미이다.)

Read More

Jolt Awards 2012

2012년에도 어김없이 Jolt Awards가 발표되었었는데, 최근에야 생각이 나서 찾아보았습니다. 모두 흥미로운 책들로 보입니다만, Google의 개발 환경을 어느 정도 엿볼 수 있는 How Google Tests Software를 Kindle로 사서 읽고 있습니다.

The Best Books

http://www.drdobbs.com/joltawards/jolt-awards-the-best-books/240007480

Jolt Award

Jolt Productivity Award

Jolt Finalist

Read More

CAP Twelve Years Later: How the “Rules” Have Changed

지난 2012년 2월, IEEE Computer에 CAP Theorem에 대한 특집이 실렸습니다. 특집의 첫번째 아티클을 쓴 저자는 지난 2000년 PODC (Symposium on Principles of Distributed Computing)에서 CAP Theorem을 conjecture의 형태로 발표했던 바로 Eric Brewer입니다.

CAP Twelve Years Later: How the “Rules” Have Changed by Eric Brewer

1. CAP Theorem

소위 NoSQL 운동에 대해서 조금이나마 관심이 있었던 분들은 CAP Theorem에 대해 들은 바가 있을 것입니다.

CAP Theorem은 네트워크를 통해 데이터를 공유하는 시스템은 아래의 3가지 특성 중 2개만을 가질 수 있다고 얘기하고 있습니다.

  • Consistency (C)
  • High Availability (A)
  • Tolerance to Network Partitions (P)

네트워크로 연결된 2개의 노드로 구성된 시스템이 있다고 가정해봅시다. 그리고 네트워크 파티션에 의해 2개의 노드는 통신할 수 없는 상황이 벌어졌다고 생각해봅시다.

Availability를 위해 하나 이상의 노드가 상태를 업데이트할 수 있도록 한다면 2개의 노드가 가지고 있는 데이터는 inconsistent해지므로 Consistency를 포기하는 것이 됩니다. Consistency를 보존하려고 한다면, 2개의 노드 중 한 쪽은 unavailable한 것처럼 행동해야 하므로, Availability를 포기하는 것이 됩니다. 노드들이 서로 통신할 때만, Consistency와 Availability를 동시에 보존할 수 있으므로 이는 Partition Tolerance를 포기하는 것이 됩니다.

2. Why 2 of 3 is misleading

“Partition Tolerence를 포기할 수 없으므로, Consistency와 Availability 중 하나를 선택해야 하고, Availability를 희생할 수 없으므로, Consistency를 희생해야한다” 정도가 NoSQL 운동의 초기에 등장했던 AP 시스템들의 공통된 주장이었습니다.

그러나, Eric Brewer는 이런 식으로 3개의 특성 중 2개만을 선택해야 한다는 관점이 많은 오해를 불러왔다고 얘기하고 있습니다.

그 이유는 다음과 같이 설명하고 있습니다.

  • 파티션은 흔히 일어나지 않으므로, 파티션이 일어난 상황이 아닐 때에도 Consistency나 Availability를 포기할 타당성은 적다.
  • Consistency-Availability 사이의 선택은 하나의 시스템에서 단 한번 이루어지는 것이 아니라, 세부적인 단위로에서 여러번 일어날 수 있다.
  • 3개의 특성들은 연속적이다. Availability는 0% – 100%, 여러 레벨의 Consistency, Partition에 대한 시스템 내의 Disagreement 등이 이를 나타낸다.

3. Cap-Latency connection

또한 Eric Brewer는, 전통적인 관점에서 네트워크의 파티션은 커뮤니케이션의 단절을 의미하는 것이지만, 제한된 시간 내에 커뮤니케이션을 하지 못하는 것을 네트워크 파티션으로 보는 관점을 제시하고 있습니다. 즉, 어떤 오퍼레이션의 타임아웃이 발생한 시점에 시스템이 해당 오퍼레이션의 재시도를 시도한다면 Consistency를 선택하는 것이고, 그렇지 않는다면 Availability를 위해서 파티션을 허용하는 것입니다.

이러한 관점에서 시스템의 설계자가 목표로 하는 response time에 따라 타임아웃을 설정하면, 타임아웃이 발생하는 것을 파티션으로 감지하고, 파티션 모드로 진입할 수 있게 됩니다.

한편, 지연 (Latency)을 피하기 위해 강한 Consistency를 포기하는 시스템의 예로 Yahoo의 PNUTS를 들고 있고, 업데이트와 업데이트 이후 일정 시간동안의 읽기에 대해서는 지연을 허용하는 Facebook의 시스템을 그 반대의 사례로 들고 있습니다.

4. Managing partitions

Eric Brewer는 파티션을 다루는 전략을 다음과 같이 제안하고 있습니다.

우선 파티션은 흔하지 않기 때문에, CAP은 대부분의 시간 동안 완벽한 C와 A를 허용해야합니다. 하지만, 파티션이 발생했을 경우에는, 파티션을 매우 명시적으로 관리해야한다고 언급하고 있습니다. 이를 아래의 3단계와 그림으로 표현하고 있습니다.

  1. 파티션의 시작을 감지
  2. 특정 오퍼레이션을 제한할 수 있는 명시적인 파티션 모드에 진입
  3. 커뮤니케이션이 회복된 후, Consistency를 복구하고 파티션 모드 동안의 실수를 만회하기 위한 파티션 복구 프로세스를 시작

Managing Partition

4.1. Which operations should proceed?

기본적으로 어떤 오퍼레이션을 제한할지는 시스템이 유지해야하는 불변조건 (invariants)에 달려있습니다. 파티션 동안 유지되지 않아도 되고, 파티션 복구 시 쉽게 복구할 수 있는 경우 (예를 들어, 중복된 키들의 병합)에는 오퍼레이션을 허용할 수 있고, 파티션 동안 유지되어야만 하는 불변조건에 해당하는 경우에는 오퍼레이션을 금지하거나 지연하거나 수정해야 한다고 얘기하고 있습니다.

실제로 오퍼레이션에 대해 어떤 조치를 취할지는 시스템에 대한 모든 원자적인 (atomic) 오퍼레이션과 불변조건들의 테이블을 만들고 각각의 항목별로 오퍼레이션이 불변조건을 위반할 수 있는지 여부를 검토해야 합니다.

중요한 것은 실제로 시스템을 사용하는 사용자에게는 이러한 조치가 보이지 않는 것입니다. 신용카드 결제의 경우 통신이 불가능한 상황에서 의도를 기록한 후 나중에 실행하는 것이나, Bayou의 캘린더 애플리케이션에서 잠재적으로 inconsistent한 항목들을 다른 색상으로 표시하는 등 흔히 오프라인 모드라고 불리는 사용자 인터페이스에서의 처리를 언급하고 있습니다. 본질적으로 이러한 오프라인 모드는 장시간 동안의 파티션과 다름없다는 것입니다.

파티션이 끝난 후 복구를 위해 파티션의 양단에서 일어난 오퍼레이션의 이력을 추적하는 가장 좋은 방법으로 오퍼레이션들 사이의 인과적인 의존성을 보존하는 버전 벡터 (version vector)를 사용하는 것이라고 얘기하고 있고, 이러한 시스템의 좋은 예로 Dynamo를 들고 있습니다.

4.2. Partition recovery

파티션 복구 동안, 파티션 양단의 상태를 일관되게 (consistent) 만들고, 잘못된 응답이나 시스템 외부로의 영향 등 파티션 모드 동안에 이루어진 실수를 만회하는 두가지 문제를 해결해야 합니다.

우선 일관성의 문제는 파티션 상태로부터 시작해서 양단의 오퍼레이션들을 재실행 (roll-forward) 하면서 계속 일관된 상태를 유지하는 방식을 가장 쉬운 방식으로 언급하고 있습니다.

한편, 양단의 오퍼레이션을 병합할 때 발생하는 충돌에 대해서는, 일반적인 충돌 해결의 문제는 해결 불가능하지만, 현실적으로는 설계자는 파티션 동안의 오퍼레이션 제한을 통해 복구 동안의 자동 병합에서 문제가 생기지 않도록 합니다. (예를 들어, Google Docs는 텍스트의 추가, 삭제, 스타일의 적용으로 오퍼레이션을 제한)

상태의 자동적인 수렴을 위한 일반적인 프레임워크 중 하나는 상호적인 (commutative) 오퍼레이션입니다. 하지만, 실제로는 상호적인 오퍼레이션만 사용하는 것은 매우 어렵기 때문에, CRDT (Commutative Replicated Data Type)이란 개념을 소개하고 있습니다. CRDT는

  • 파티션 동안 모든 오퍼레이션들은 상호적임을 보장하거나,
  • 상태를 기록한 후, 파티션 동안에 일어나는 모든 오퍼레이션은 그 상태에 대해 단조적임을 보장합니다.

예를 들어, 집합에 대한 추가와 삭제 오퍼레이션에 대한 CRDT 구현은, 추가된 항목들과 삭제된 항목들에 대한 집합을 각각 유지하는 것입니다. 파티션 복구 시점에서 시스템은 양단의 집합으로부터 정리 작업을 수행할 수 있습니다. 정리 작업은 파티션 동안에는 불가능하기 때문에 파티션 이후로 지연시켜야 하는 오퍼레이션이지만, 인지되는 가용성을 제약하지 않습니다. 따라서, CRDT를 통해 상태를 구현할 수 있다면, 설계자는 Availability를 선택하더라도 파티션 이후에 자동적으로 상태가 수렴될 수 있도록 보장할 수 있습니다.

4.3. Compensating for mistakes

시스템 외부에 가해진 실수를 복구하는 것은 시스템 외부로의 영향에 대한 이력을 필요로 합니다. 어떤 사람이 전날 밤 술에 취해 전화를 걸었다면, 그 전화들은 외부로의 영향에 해당하고, 그 사람이 다음 날 아침 정상 상태가 되었을 때, 잘못 건 전화들에 대해 만회를 하기 위해서는 어젯밤 걸었던 전화들에 대한 기록을 필요로 합니다.

다른 예로, 파티션 동안에 시스템이 동일한 주문을 두 번 수행했다고 가정해봅시다. 시스템이 주문의 이력으로부터 중복된 주문을 식별할 수 있다면, 중복된 주문 중 하나를 취소하고 고객에게 적절하게 사과하는 메일을 보낼 수 있지만, 그러한 이력이 없다면, 그러한 실수를 파악하는 것은 고객의 부담이 됩니다.

Brewer는 여기서 보상 트랜잭션 (Compensating Transaction)의 개념을 소개하고 있습니다. 예를 들어, 하나의 트랜잭션으로 모든 직원들의 레코드들을 업데이트 하려고 한다면 모든 레코드를 lock하게 됩니다. 보상 트랜잭션은 커다란 트랜잭션을 다수의 작은 트랜잭션으로 쪼개어 각각 따로 commit하는 방식을 취합니다. 따라서, 원래의 커다란 트랜잭션을 취소하려고 할 때 이미 commit된 작은 트랜잭션의 영향을 수정하는 새로운 트랜잭션 -보상 트랜잭션을 실시합니다. 보상 트랜잭션의 접근은 전통적인 데이터베이스의 접근과 같이 직렬성 (Serializability)이나 격리성 (Isolation)에 의존하기 보다는 트랜잭션의 전체적인 영향에 의존합니다. 그리고 외부에 미친 영향까지도 고려가 되어야 합니다. 예를 들어, 중복된 지불을 환불하는 것은 애초에 고객에게 청구하지 않는 것과 같다고는 할 수 없지만, 거의 동등하다는 것이고, 이러한 생각 – 실수를 인정하고 보상을 통해 동등한 결과를 얻는 방식이 파티션 복구에서도 성립한다고 얘기하고 있습니다.

5. Closing

Eric Brewer가 마지막에서 강조하고 있는 것은 시스템 설계자는 파티션이 존재할 때, 무턱대고 consistency나 availability를 희생하려고 해서는 안되고, 이 글에서 언급하고 있는 방식을 통해 양쪽 모두를 최적화하려고 해야한다는 것입니다. 이를 위한 버전 벡터 (version vector)나 CRDT 등의 기술들이 프레임워크화되고 좀 더 보편화될 것이라고 얘기하고 있습니다.

제가 이 글을 읽고 느낀 점들은 아래와 같습니다.

  • CAP Theorem에 대해서 이 글을 읽기 전까지만 해도 단순화된 관점 – 2 of 3을 가지고 있었으나, 이 글을 읽고나서 CAP Theorem에 대한 이해도가 좀 더 높아졌고, 단순한 AP 또는 CP 시스템 이외의 시스템 설계의 많은 가능성에 대해서 생각해보게 되었습니다.
  • 상태의 수렴을 위한 데이터와 오퍼레이션의 재설계가 필요하다는 것은 깨닫고 있었지만, CRDT와 같은 좋은 사고 도구가 될 수 있는 정식화 (formalization)가 있는지는 몰랐습니다.
  • 결국 현재로서는 분산 저장 시스템은 매우 복잡한 설계가 필요할 뿐만 아니라, 전통적인 DB와는 다르게 보편화된 프레임워크가 있기 보다는 개별 시스템 별로 따로 설계를 해야하는 수준이기 때문에, 아직 더 많은 연구와 개발이 필요한 분야인 반면, 그만큼 비용이 많이 들어가는 부문인 것 같습니다.
  • CAP Theorem 특집의 글들을 읽고 있습니다만, 이를 요약할 수 있을 정도로 완벽하게 이해하고 정리하는 것은 매우 시간이 걸리는 일이네요. 여력이 된다면 다섯개의 글 모두 정리해보고 싶습니다.

 

 

Read More