How Google Serves Data from Multiple Datacenters

원제 : How Google Serves Data from Multiple Datacenters

번역 : 구글이 여러 데이터센터로부터 데이터를 서비스하는 방법

Update: Streamy Explains CAP and HBase's Approach to CAP. 우리는 클러스터간 복제를 적용할 계획인데, 각 클러스터는 하나의 데이터센터에 위치합니다. 원격 복제는 시스템으로 최종 일치를 진행하며, 그러나 각 클러스터는 강한 일치가 될 때까지 지속할 것입니다.

구글의 App Engine datastore 를 이끄는 Ryan Barrett은 Google I/O 2009 컨퍼런스에서 Transactions Across Datacenters (and Other Weekend Projects)를 발표하였습니다

발표에서 새로운 기술 경지를 개척할 필요가 없었기 때문에, Ryan은 훌륭한 작업 설명과 여러 데이터센터를 거쳐 작업하는 시스템을 아키텍팅 할 때 여러분이 가진 다른 옵션을 평가하였습니다. multihome이라 부르며, 동시에 여러 데이터센터로부터 작업하는 것입니다..

multihoming은 모든 컴퓨팅분야에서 가장 도전적인 분야이기 때문에, Ryan의 명쾌하고 사려깊은 태도는 편안하게 여러분을 다양한 옵션으로 이끌어줍니다. 이 여행에서 여러분은 다음을 배우게 됩니다:

다양한 multi-homing 옵션 : Backups, Master-Slave, Multi-Master, 2PC, Paxos. 여러분은 또한 이 옵션들이 어떻게 서로 일치성, 트랜잭션, 지연, 처리양, 데이터손실, 장애복구를 위해 지원하는지 배우게 됩니다.

Google App Engine 은 데이터센터간에 마스터/슬래이브 복제를 이용합니다. Google은 다음을 제공하기 위해 이 접근법을 선택하였습니다:
- 적은 지연 쓰기(lowish latency writes)
- 데이터센터 장애 생존(datacenter failure survival)
- 강력한 일치성 보장( strong consistency guarantees).

어떤 솔루션도 이기지 못했기 때문에, 타협책은 여러분이 중요하다고 생각하는데 따라 만들어집니다. 주요한 Google App Engine 목적은 프로그래머를 위해 강한 일치성 모델을 제공하는 것이었습니다. 그들은 또한 데이터센터 장애에도 살아남기를 바랬습니다. 그리고 전형적인 관계형 데이터베이스로 부터 멀리 떨어지지 않았기 때문에 그들은 쓰기 성능을 원했습니다. 이 우선순위가 아키텍처적인 선택을 이끌었습니다.

특정 문제 요구사항을 위해 Paxos, 2PC, 기타 다른 것을 선택할 수 있기 때문에(Yahoo의 PNUTS가 이렇게 동작합니다) 미래에는 선택적인 모델을 제공하기를 희망합니다.

아직 배울게 남아있습니다. 발표에 대한 나의 주석입니다:

일치성 – 읽기가 발생한 다음에 쓰기는 어떤 일이 발생할까?

데이터 읽기/쓰기는 데이터센터를 가로질러 동작하는 데이터의 가장 어려운 종류중 하나 입니다. 사용자는 신뢰성과 일치성의 특정한 단계를 기대합니다.

Weak - 거기에 있을 수도 있고, 없을 수도 있다. 최선의 노력. Memcached 처럼. Voip, live video, 다중사용자 게임 같은 몇몇 응용프로그램에서는 빼먹는 것은 괜찮다. 여러분은 그것들이 어디에 있는가가 아니라 그것들이 현재 어디에 있는지 더 신경써야 한다. 데이터를 위해 이는 좋지 않습니다.

Eventual - 여러분은 결국 여러분이 쓴 것을 보게 되지만, 지금 당장은 아닙니다. 전자우편이 좋은 사례지요. 여러분이 전자우편을 보냈지만, 곧바로 도착하는 것은 아니지만, 그러나 결국에는 거기에 도착하겠지요. DNS 변경 지연 SMTP, Amazone S3, SimpleDB, 검색엔진 색인작업이 모두 이런 종류입니다. 읽기가 쓰여진 것을 보지 않으려고 할 때 지연된 쓰기작업이 있지만, 쓰기는 결국 통과됩니다. 데이터에게는 이상적이지 않죠.

Strong - T구조화된 데이터 시스템을 위한 이상적인 솔루션. 여러분은 넣은 것을 얻을 수 있습니다. 다시 프로그래밍을 최대한 간결하게 하고 생각해보자. 쓰기 후에 어떤 읽기도 쓴 것을 돌려받습니다. AppEngine, file systems, Microsoft Azure, RDBMS는 이 방법으로 동작합니다.

데이터를 데이터센터를 가로질러 옮긴다면 어떤 일치성 보장을 가지고 있을까요? 어떤 보장은 포기하지만, 우리가 얻을 수 있는 것을 알아야 합니다.

트랜잭션 – 여러 작업에서 일관성의 확장된 방식.

트랜잭션 속성 :  정확성, 일관성, enforce variants ACID.

사례: 은행 트랜잭션. A에서 B에게 송금. A의 돈을 인출하여 B에게 더한다. 이 작업은 다른 시간에 발생한다. 이 작업 사이에 A를 위한 또 다른 송금이 발생한다면 어떻게 될까? 송금작업이 실패한다면 ? 여러분은 보장을 원합니다. B에게 돈을 더하는 과정에 크래쉬가 발생해도 여전히 B에게 더해줘야 하는가? A로부터 돈을 받는 것은 여전히 A에게 받은 것일까요? 여러분은 돈을 잃거나 뚝 떨어지기를 바라지 않을 것입니다.

여러분이 데이터센터들에 걸친 작업을 시작할 때 더 많은 것들이 잘못되고 작업들이 많은 지연을 가지므로 트랜잭션을 실시하기 매우 어렵습니다.

여러 데이터센터에서 작업해야 하는 이유는?

장애 발생(Sh*t happens) - 여러가지 이유로 데이터센터가 작동이 안됩니다.

성능(Performance) - 지리기반지역화는 작업을 사용자에게 더 밀접하게 합니다. 빛의 속도 제한은 데이터 전송속도를 제한하며 전세계에 걸친 작업을 할 때 중요합니다. 다중 라우터 홉(hop)을 통과하면 트래픽은 느려집니다. 더 밀접한 것이 더 좋기 때문에 여러분의 데이터가 여러 데이터센터에서 작동을 요구하는 사용자 근처에 있을 때만 더 밀접해집니다. CDN이 이런 작업을 해주지만, 특히 정적인 데이터일 때 그렇습니다. CDN은 어느 곳에나 데이터를 집어넣어줍니.

여러 데이터센터에서 작업하지 못하는 이유?

하나의 데이터센터에서 작업은 쉽습니다: 저렴한 대역폭, 낮은 지연, 높은 대역폭, 간편한 작업, 더 쉬운 코드.

여러 데이터센터에서 작업은 까다롭습니다 : 높은 비용, 높은 지연, 낮은 대역폭, 어려운 작업,  복잡한 코.

한 곳 이상에서 쓰기를 받아들이는 읽기/쓰기 구조화된 데이터 시스템을 가지기란 특별히 어렵습니다. 여러분은 일치성의 문제를 안게 됩니다. 거리라는 문제에서 일치성 관리와 장애는 사소하지 않습니다.

다른 아키텍처 옵션(Your Different Architecture Options)

Single Datacenter. 여러 데이터센터에서 작업하는 것을 신경쓰지 마세요. Don't bother operating in mutiple datacenters. 가장 쉬운 옵션이고 대부분의 사람들이 이렇게 합니다. 데이터센터가 고장나면, 데이터를 잃고, 여러분의 사이트도 다운됩니다.

Bunkerize. 최종 데이터센터를 위한 마지노선을 만드세요. 여러분의 데이터센터가 결코 다운되지 않는다고 확신하세요. SimpleDB 와 Azure는 이 전략을 사용합니다.

Single Master. 쓰기를 하고 다른 사이트가 복제하는 마스터 데이터센터를 선택하세요. 복제는 읽기 전용 서비스로 사용합니다.
- 좋기는 하지만 훌륭하지 않습니다.
- 데이터는 보통 비동기로 복제되기 때문에 손실에 대한 취약점이 있습니다.
- 다른 데이터센터의 데이터는 장애시에 일치하지 않을 수 있습니다.
- 금융기관에서 많이 사용합니다.
- 읽기 위한  지리기반지역화를 해야합니다. 일치성은 기술에 의존합니다. 쓰기는 여전히 한 데이터센터로 제한됩니다.

Multi-Master. 진정한 multihoming. 신성한 성배. 모든 데이터센터가 읽기와 쓰기를 합니다. 모든 데이터가 일치합니다. 트랜잭션도 역시 동작합니다. 이건 정말로 어렵지요.
- 그래서 몇몇은 단지 두 데이터센터만을 선택합니다. NASDAQ 은 가까운 곳에 두 데이턴 센터를 (낮은 지연) 가지고 있고 모든 트랜잭션에 2단계 커밋을 수행하지만, 그러나 매우 엄격한 지연 요구사항을 적용하고 있습니다.
- 개 이상의 데이터센터 이용은 근본적으로 더 어렵습니다. 여러분은 이를 위해 큐 지연, 라우팅 지연, 빛이 속도에 비용을 지불해야 합니다. 단지 작은 파이프를 이용하여 기본적으로 더 느립니다. 용량과 처리량에 지불할 수 있지만, 여러분은 지연에는 무한대로 지불해야 합니다.

실제 방법은 무엇이 있을까요?

어떤 기술이 있으며 다른 접근방법들의 tradeoffs 는 무엇입니까? 평가표가 아래에 있습니다:

	Backups	M/S	MM	2PC	Paxos
Consistency	Weak	Eventual	Eventual	Strong	Strong
Transactions	No	Full	Local	Full	Full
Latency	Low	Low	Low	High	High
Throughput	High	High	High	Low	Medium
Data loss	Lots	Some	Some	None	None
Failover	Down	Read-only	Read/Write	Read/Write	Read/Write

- M/S = master/slave, MM - multi-master, 2PC - 2 Phase Commit
- 특정한 접근법을 위해 어떤 종류의 일치성, 트랜잭션, 지연, 처리량을 선택하시겠습니까? 장애시에 데이터를 잃어도 될까요? 얼마나 많이 잃을까요? 우리가 유지보수로 장애극복을 하거나 뭔가를 옮기려 할 때, 데이터센터를 퇴역시키려 할 때, 얼마나 잘 할 수 있을까요, 얼마나 기술적으로 지원할 수 있을까요?

Backups - 데이터의 복제본을 은밀하고 안전하게 만듭니다. 일반적으로 약한 일치성, 보통 트랙잭션을 지원하지 않습니다. 초기의 내부 데이터저장을 위해 사용되었습니다. 상용제품 시스템에 충분하지 않습니다. 마지막 백업 이후 데이터를 잃어버립니다. 다른 데이터센터로 백업을 복원할 때 다운됩니다.

Master/Slave Replication - 마스터에 쓰기는 또한 하나 이상의 슬래이브에 쓰기를 합니다.
- 복제가 비동기이기므로 지연과 처리량에 좋습니다.
- 매우 주의하지 않으면 약한/최종 일치.
- 데이터센터들에 여러 개의 복사를 가지므로, 장애가 발생하면 매우 적은 데이터를 잃으며, 많지는 않습니다. 마스터가 다른 데이터센터를 옮기기 전까지 장애극복은 읽기전용으로 지속됩니다.
- Datastore는 현재 이 메커니즘을 사용합니다. 진정한 multihoming은 데이터센터간의 특별한 hop을 가지고 있기 때문에 지연을 추가합니다. App Engine은 여전히 쓰기에서 느려서 이 특별한 hit는 괴롭습니다. 더 낮은 지연 쓰기를 여전히 제공하기 때문에 M/S는 가장 좋은 형태의 혜택을 제공합니다.

Multi-Master Replication - 동시에 여러 데이터센터에서 쓰기를 지원합니다.
- 데이터가 충돌할 때 여러분은 나중에 모든 쓰기를 합치는 방법을 계산해야 합니다.  마치 비동기 복제와 같지만, 여러분은 여러 지역으로부터 쓰기를 제공하고 있습니다.
- 할수 있는 최선은 최종 일치입니다. 쓰기는 즉시 모든 곳으로 가지 않습니다. 이점이 패러다임 전환입니다. 백업을 하고 어떤 것도 변하지 않는 M/S 같은 강력하게 일치하는 시스템을 가정했습니다. 이들은 우리가 multihome을 만들게 도와주는 기술일 뿐입니다. 다중 쓰기가 합쳐지기 때문에 문자 그대로 시스템이 동작하는 방법을 변화시킵니다.
- 합치기 위해서 여러분은 직렬화 방법과, 모든 여러분의 쓰기에 순서를 부여하는 방법을 찾아야 합니다. 전세계적인 시계는 없습니다. 일은 병렬로 발생합니다. 여러분은 맨처음 일어날 일을 알 수 없습니다. 따라서  timestamps, local timetamps + skew, local version numbers, distributed consensus protocol 을 이용하여 만들어야 합니다. 이것은 마법이며 달성하는 몇 가지 방법이 있습니다.
- 전세계적 범위의 트랜잭션을 하는 방법은 없습니다. 다중 동시 쓰기를 하면 여러분은 트랜잭션을 보장할 수 없습니다.  따라서 여러분은 다음에 무엇을 할지 알아야 합니다.
- AppEngine 은 응용프로그램을 쉽게 만들기 위해서 강력한 일치성을 원했고, 따라서 이 옵션을 고려하지 않았습니.
- 데이터센터들이 쓰기를 처리하면 되기 때문에 장애극복은 쉽습니다.

Two Phase Commit (2PC) - 분산 시스템간의 트랜잭션 설정을 위한 프로토콜.
- 주어진 2PC 트랜잭션을 위한 주조정자가 있기 때문에 반 분산(Semi-distributed )입니다.  적은 데이터센터만 있기 때문에 주조정자의 같은 집합을 통하려는 경향이 있습니다.
- 동기방식입니다. 모든 트랜잭션은 처리량을 줄이고 지연을 증가시키는 마스터를 통해 직렬화됩니다.
- AppEngine 에게는 쓰기 처리량이 중요하기 때문에 이 옵션을 심각하게 검토하지 않았습니다.  어떤 단일지점 또는 직렬화 장애는 제대로 동작하지 않을 것입니다.  추가적인 조정이 필요하기 때문에 지연은 높습니다. 쓰기 200ms 범위에서만 가능합니다.
- 이 옵션은 동작은 합니다. 여러분은 모든 데이터센터에 쓰기를 하거나 아무것도 쓰지 않을 수 있습니다. 여러분은 강력한 일치성과 트랜잭션을 얻습니다.
- N+1 데이터센터가 필요,  여러분이 하나를 다운시키면, 로드를 처리할 N개를 가지게 됩니다.

Paxos - 독립 노드 그룹이 결정에 따라 주요한 합의에 도달하는 합의 프로토콜 (참조 : http://en.wikipedia.org/wiki/Paxos_algorithm).
- 프로토콜 : 제안 단계와 다음에 동의 단계가 있다. 여러분은 지속되는 것으로 간주되어야 하는 것을 위해 무엇인가 지속되어야 한다고 말하기 위해 동의하는 오직 하나의 주 노드가 필요합니다.
- 2PC와 다르게 완전 분산입니다. 단일 주조정자가 없습니다.
- 다중 트랜잭션은 병렬적으로 수행됩니다. 덜 직렬화됩니다.
- 이 프로토콜에서는 2개의 추가적인 순회 조정 여행이 필요하기 때문에 쓰기는 높은 지연시간을 갖습니다.
- 이렇게 하기를 원했지만, 쓰기에 150ms 지연을 지불하지 않았는데,  RDBMS의 경우 5ms 쓰기와 비교되었기 때문입니다.
- 그들은 물리적으로 폐쇄된 데이터센터에서 사용하려 했지만, 내장 멀티-데이터센터 오버헤드(라우터등)이 너무 높았습니다. 같은 데이터센터 안에서도 너무 느렸습니다.
- Paxos는 여전히 구글에서 많이(ton) 사용됩니다. 특별히 Lock 서버를 위해 사용됩니다. 데이터센터를 가로질러 하려는 것을 조정하기 위해. 특별히 상태가 데이터센터간에 이동될 때. App 가 하나의 데이터센터에서 데이터를 제공하고 있고 다른 데이터센터로 이동해야 한다면 조정은 Paxos를 통해 이뤄집니다. Memcache 관리와 오프라인 프로세싱에 사용됩니다.

다양한 읽을거리

Entity Groups 은 AppEngine에서 일치의 단위입니다. 동작은 Entity Group에서 직렬화됩니다. Entity group으로 모든 커밋 로그는 복제됩니다. 이는 일치성을 유지하고 트랜잭션을 제공합니다. Entity Goups 은 본질적으로 조각들입니다. 조각이 많은 쓰기를 처리하기 때문에 조각은 확장을 가능케 합니다. Entity Goup에서 데이터 저장 조각은 덩어리(chunks) 크기입니다.BuddyPoke는 4천만 사용자를 가지고 있는데, 상요자는 entity group을 가지고 있습니다. 4천만개 다른 조각입니다.

내 개에게 음식주기는 Google에서 사용하는 전략입니다. 반복하고 내부적으로 새로운 기능을 사용하도록 합니다. 많은 것을 이용하는 것은 매우 이릅니다. 여러분은 매우 많이 반복할 수 있고 따라서 런칭을 준비하기 전에 향상됩니다.

TAzure와 SimpleDB 같은 경재자로써 데이터센터에서 관계형 데이터베이스를 살펴보았습니다. RDMBS로 삽입은 적은 ms 입니다. AppEngine에 쓰기는 30-40ms 입니다. 읽기는 빠릅니다. 웹에서 읽기가 쓰기보다 광범위하게 많기 때문에 이 trade-off를 좋아합니다.

토론

발표에서 저도 몇가지 궁금한 것이 있습니다. Google 은 분산 MVCC 접근법을 고려했을까요? 분산 MVCC는 흥미롭지만 옵션으로 발표하지 않았습니다. 확실히 Google 규모에서 in-memory 데이터 그리드는 아직 적절하지 않습니다.

프로그래머의 작업을 쉽게 만들기 때문에 강력한 일치 모델을 위한 설정은 주요한 설계 목적으로써 반복해서 구체화시켜야 합니다. A counter to this is that the programming model for Google App Engine is already very difficult. The limits and the lack of traditional relational database programming features put a lot of responsibility back on the programmer to write a scalable app. I wonder if giving up strong consistency would have been such a big deal in comparison?

나는 평가표와 왜 Google App Engine이 이런 선택을 했는가에 대한 토론에 진심으로 감사드립니다. 쓰기가 이미 Google App Engine에서 느리기 때문에 그들은 더 많은 조정 레이어를 흡수하는 많은 공간(headroom)을 가지지 않았습니다. 이것들은 설계 회의에서 개발자들이 나누는 종류이지만, 그들은 보통 사무실이나 회의실 바깥에서 만들지 않았습니다. “왜 우리가 다 가질 수 없는거야 ”라고 큰 소리로 말하는 Ryan의 말을 들었습니다. 우리는 결코 모든 것을 가질 수 없습니다. 공유를 해 준 Rayn에 많이 감사드립니다.

Related Articles

Slides for the Talk

ZooKeeper - A Reliable, Scalable Distributed Coordination System

Yahoo!'s PNUTS Database: Too Hot, Too Cold or Just Right?

Paper: Consensus Protocols: Paxos by Henry Robinson

Paper: Consensus Protocols: Two-Phase Commit by Henry Robinson

Paper: Dynamo: Amazon’s Highly Available Key-value Store

Are Cloud Based Memory Architectures the Next Big Thing?