Twitter Gizzard

Gizzard는, Twitter에서 개발한 분산 자료저장소를 위한 framework이다.

• Distributed system 위에서 정보를 효율적으로 저장 및 조회하기 위한 middleware; 보다 구체적으로 본다면, 여러 개의 mysql 에 sharding을 적용하기 위해 개발한 network 기반 middleware다.
• Forwarding table과 replication tree을 이용하여 분할/분산 관리한다.
• 쓰기 동작에 대한 항등성(idempotent)과 가환성(commutative)을 강제하여 자료의 일관성을 보장한다.
• 무한으로 확장되는 follow 개념을 mysql에 분산 저장하기 위하여 개발을 시작하였다.

[참고] "shard" 란 한 대의 computer에 정보를 저장하는 대신, 여러 대의 computer에 걸쳐서 저장하는 것을 말한다.

배경
Twitter는 자체 제작한 분산 환경의 자료 저장 공간을 갖고 있다. 자체 제작한 방법들은 이전 보다 쉽게 자료를 관리할 수 있도록 해 준다. Twitter team은 Gizzard - 장애 발생에 대하여 대응이 빠르고 , 분산 환경 구조 database를 쉽게 생성하고 관리할 수 있도록 도와주는 기능을 가진 Scala 기반 framework - 를 개발하였고, 공개하였다.
Gizzard는 모든 요구를 완벽하게 충족해 주는 완벽한 기술은 아니지만 대부분의 다양한 문제들에 대해서 충분히 유용하게 활용할 수 있다. Gizzard를 바라볼 때, 고수준(사용자 입장에 가까운 단계) 관점에서 보면, 밑단에 있는 임의의 저장 공간들(SQL databases, Lucene 등)에 대하여 분할 기능을 제공하고 이를 관리해 주는 networking service로 생각할 수 있다. Gizzard의 분할 방식은 forwarding table을 이용하여 자료를 나누어 저장하는 방식이다. 여기서 Forwarding table이란 key를 분할 영역들에 연결한 map을 말한다. 그리고 각 partition은 replication tree를 이용하여 자신이 (소유한) 복사본을 관리한다.
Gizzard 는 “migration” (예를 들면, clustering system에 새로운 machine - 여기서는 computer를 의미한다 - 을 유연하게 추가하는 것)을 지원한다. 그리고 장애 상황을 매우 잘 관리한다. 이것은 쓰기 동작이 항등성(idempotent)과 가환성(commutative)을 만족하도록 요구하기 때문인데, 만약 쓰기 동작 실행 중 실패가 발생하면 - network partition 등과 같은 이유로 인하여 - 나중에 해당 명령을 다시 수행하도록 한다. 이 때, 항등성과 가환성을 만족하면 해당 정보가 최신 상태를 유지할 수 있다.  정리하자면, Twitter는 gizzard를 만들어서 종종 까다로운 sharding 처리 과정으로부터 오는 고충을 제거하였다. 그래서 분산 자료 저장 및 관리를 쉽게 해주었고, twitter system에서 엄청나게 많은 양의 요청들을 빠트리지 않고 잘 다룰 수 있게 해 주었다.

동작원리 상세

1) Gizzard is middleware network service
Gizzard는 networking service의 middleware로 동작한다. 여기서 "middle”은 client 들과 매우 많은 수의 partitions, replicas 들 사이에 위치한다. Gizzard가 가운데 (middle)에 놓인다는 것은 자료에 대한 모든 요청과 조작, 관리가 gizzard를 통해야 한다는 것이다. Gizzard의 instance들은 상태 정보를 기록하지 않으므로, 따라서 산출물의 양이나 또는 TCP 연결 수 제한 등의 조건 등을 고려하여 필요에 따라 여러 개의 gizzard instance들을 실행할 수 있다. Gizzard는 Java virtual machine에서 동작하기 때문에, 꽤 효율적이다. Twitter에서 활용하고 있는 gizzard application인 FlockDB에서 초당 10,000건의 요청을 처리하고 있다.

2) Gizzard supports any data-storage back-end
Gizzard는 network를 통해 접근할 수 있는 data storage service들 사이에서는 자료의 복사본을 생성할 수 있도록 설계하였다. 따라서 gizzard를 기존의 관계형 database, Lucene, Redis, 또는 그 외의 어떠한 것에도 적용할 수 있다. 보통, gizzard의 모든 쓰기 실행은 항등성과 가환성을 동시에 만족한다 (5. Gizzard is fault-tolerance와 6. Winged migrations 부분에서 다시 다룬다). 그래서 두 조건을 만족하기 위하여 back-end store를 사용하는 것에 몇 가지 제약 사항이 있다. 구체적으로 보면, gizzard는 쓰기 실행이 적용되는 순서를 보장하지 않는다. 항등성 조건은 같은 쓰기 실행을 반복하여 시도하여도 결과가 누적되지 않고 유지되어야 하며, 가환성 조건은 쓰기 실행 순서를 바꾸어도 결과가 바뀌지 않아야 하기 때문에 실행 순서에 상관없이 동일한 동작을 해야 한다. 이것은 쓰기 실행에 대하여 적용 순서 보다 자료의 일관성을 유지하고자 하는 목적이 더 강하기 때문이다.

3) Gizzard handles partitioning through a forwarding table
Gizzard는 개별 shard들의 정보를 범위(ranges)에 연결하는 방법으로 분할 - 여러 장치들에 퍼져 있는 자료들을 상호배타적인 범위로 나눈다 - 기능을 다룬다. 여기서 연결이란 forwarding table을 이용한 것으로 좁은 경계를 가진 수치 범위와 해당 범위에 속하는 자료들을 구분 짓는 것이다. 보다 세밀하게 보면, 사용자는 자신의 직접 정의한 “hashing” 함수 - 사용자의 자료와 application에 따라 적절한 key를 제공하면 forwarding table에 속한 범위들 중 하나에 몇 개의 (자료)를 속하게 할 지 생성하는 함수 - 를 직접 정의하여 사용할 수 있다. 이러한 함수들은 program으로 작성할 수 있으므로 사용자의 요구조건이나 상황에 맞게 최적화 해서 사용하는 것이 가능하다. Table 기반의 접근방식은 많은 수의 분산 환경 system에서 활용하고 있는 기술인 consistent hashing과 다르다. 이러한 접근 방식은 이질적인 크기의 분할 공간들을 허용하기 때문에, 보다 쉽게 병목지점을 관리할 수 있다. - 극단적으로 자주 사용하는 자료를 분리한다. 사실, Gizzard는 사용자가 forwarding 전략을 직접 작성하여 적용하는 것을 지원하기 때문에, 분할 관리 정책으로 consistent hashing을 이용하는 것이 가능하지만, 추천하지는 않는다.

4) Gizzard handles replication through a replication tree
Forwarding table에서 참조하는 개별 shard는 물리적인 shard 또는 논리적인 shard이다. 물리적인 shard는 특정한 back-end 저장 공간을 참조하고 있는 것으로 보통 SQL database 종류이다. 반대로 논리적인 shard는 단지 다른 여러 shard들의 tree 이다. 이 tree의 개별 branch는 자료의 몇몇 논리적인 변환을 표현하고, 개별 node는 back-end 저장 공간을 표현한다. Branch에서 일어나는 이러한 논리적 변환은 해당 branch의 자식들에게 읽기/쓰기 동작들을 어떻게 전달할 지 결정한다. 논리적인 shard의 예를 들어 두 단계 replication tree가 있다고 하면, (forwarding table에서 참조할 때 ) 단 한 개의 분할 공간인 것처럼 인식하게 된다. 아래 그림에서 “Replicate” branch는 쓰기 동작을 모든 자식들에게 반복하고, 상태와 가중치 함수를 따라 읽기 균형을 맞추도록 하는 간단한 전략이다. 사용자는 각자의 필요에 맞춰 branch를 연결하는 방법/논리적 shard를 사용자 정의할 수 있다. 이를테면, 추가적인 transaction/coordination primitives 또는 quorum 전략들 같은 것을 말한다. 그러나 gizzard는 Replicating, Write-Only, Read-Only, 그리고 Blocked(읽기와 쓰기 모두 불가능한 것)와 같이 널리 사용할 수 있는 몇몇 개의 기본적인 전략들을 함께 배포한다. 보다 이해하기 쉽지 않은 형태들을 위한 utility는 Migration 에서 다룬다. 물리적 또는 논리적으로 배치한 복사본들의 원형을 추출하는 방식은 각 분할 공간 별로 달라질 수 있다. 이것이 의미하는 것은 사용자가 “hotter” - 연산이 집중되는 곳 - 에서는 높은 복사 수준을 정하고, “cooler” - 연산이 비교적 적은 곳 - 에서는 낮은 복사 수준을 정할 수 있다. 이것은 system을 매우 유연하게 설정 가능하도록 해준다. For instance, Alternatively, 보다 나은 고장 허용 범위를 위해서는 - 그러나 복잡도는 증가한다 - 여러 장치들에 걸쳐서 “stripe” 를 적용할 수 있다. 이 경우 다른 것들의 mirror가 되는 장치는 없다.

5) Gizzard is fault-tolerant
고장 허용 범위에 대한 내용은 분산 환경에서 매우 관심을 갖고 있는 분야 중 하나이다. 이유는 이러한 system들은 여러 computer들이 관계하고 있고, 어떠한 순간에 하나 또는 그 이상이 오작동을 일으킬 가능성이 있기 때문이다. 그래서 gizzard는 어떠한 single-points of failure라도 회피하도록 설계하였다. 어떤 특정한 복사본이 망가지면, gizzard는 아직 살아있는 복사본들에게 요청을 보내서 가중치 함수를 유지하도록 한다. 만약 한 분할 공간 안에 있는 모든 복사본을 접근 할 수 없는 상태라면, gizzard는 그 shard로 향하는 읽기 요청을 수행할 수 없게 된다. 그러나 다른 shard 들은 영향을 받지 않는다. 접근이 불가능한 shard로의 쓰기 기능은 shard가 다시 접근 가능해 질 때 까지 buffer에 대기한다. 사실, 어떠한 수의 복사본이 접근 불가능하게 되더라도, gizzard는 살아있는 복사본들에게는 가능한 빠른 시간 안에 쓰기 동작을 시도한다. 그리고 접근 불가능한 shard에 대해서는 쓰기 동작(의 자료)을 buffer에 대기하고 있다가 추후에 다시 시도하는데, 이것은 shard가 정상으로 돌아오기를 기다리는 것이다. 기본적인 전략은 모든 쓰기 동작들이 내구성을 가지도록 하는 것이다. 그 때 쓰기 동작들은 비동기(그러나 매우 낮은 지연 시간을 갖도록 관리하는)로 shard 내의 모든 복사본에 적용된다. 만약 shard를 사용할 수 없는 상황이라면, 쓰기 동작은 오류 queue에 쌓이게 되고, 추후 순서대로 재시도를 한다. Eventual consistency (일관성 정책)을 달성하기 위해서는 앞에서 언급한 재시도에 대한 정책이 필요하다. 정책은 사용자가 작성한 쓰기 동작들이 항등성과 가환성을 동시에 만족해야 한다. 이유는 이러한 재시도 정책이 기존 순서를 벗어나기 때문이다. 예를 들면, 새로운 작업이 이전에 실패해서 재시도를 하는 작업보다 먼저 적용될 수 있기 때문이다. 항등성과 가환성의 예시를 확인하고 싶다면 gizzard 시연용 application인 Rowz를 참고하면 된다.

6) Winged migrations
신속한 migration은 한 computer에서 다른 computer로 shard의 자료를 복사하거나 이동하는 것을 편리하게 해줄 때가 종종있다. 그리고 사용자는 많은 혹은 소수의 장치들에게 가해지는 부하를 조절하거나, 또는 hardware의 장애를 처리하기 위해서 이 기능을 사용할 수 있다. 아래 그림은 조금 더 모호한 형태를 띄는 논리적 shard에 대하여 어떻게 migration이 동작하는 지를 설명한다. 저장소 A에서 저장소 A’으로의 migration을 수행하면, 두 저장소 사이이며 동시에 저장소 A’의 앞인 위치에 WriteOnly shard가 오도록 설정한다. 그리고 이전 shard에서 새 shard로 자료를 복사한다. WriteOnly shard는 새 shard가 기동하는 동안 어떠한 자료도 읽을 수 없도록 보장한다. 이유는 쓰기 동작이 순서에 상관없이 일어나기 때문이며, 모든 쓰기 동작은 항등성을 갖고 있음으로써 자료의 일관성을 유지해야 하기 때문이다.

7) How does gizzard handle the write conflicts?
쓰기 충돌이라는 것은 같은 record에 두 개의 조작이 서로 다른 방법으로 값을 변경하려고 시도하는 것이다. 쓰기 동작들은 실제 적용할 때 gizzard에서는 순서를 보장하지 않기 때문에, 사용자들이 자료를 modeling할 때, 쓰기 충돌에 대해서 고려해야 하는 것이 매우 중요하다. 다른 곳에서 설명한 바와 같이, 쓰기 동작은 충돌을 피하기 위해서 항등성과 가환성을 반드시 충족해야 한다. 사실상 다양한 경우들을 통해 보더라도 이 방법은 느슨하고, 까다롭지 않은 요구사항이다. 오히려 경계가 정해져 있는 대기시간과 고수준의 가용성을 이용하여 message 전달 순서를 보장하려는 노력보다 쉽다. 위에서 언급한 것과 같이, Rowz는 “newer” - 반복적으로 쓰기를 시도할 때 이전에 쓰기 작업이 성공하지 않았을 경우 새로 시동하는 작업을 지칭한다 - 만 적용할 수 있도록 하는 time-stamp 기술을 설명하고 있다. 자세한 사항에 대한 문서는 곧 나올 예정이다.

---

• An Unorthodox Approach To Database Design : The Coming Of The Shard
• How to Use Gizzard
• Twitter gizzard: a framework for sharding