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.
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.
페이스북에서 사용자가 포스트를 올리면 데이터베이스의 쓰기가 발생하게 되는데, 이러한 쓰기 오퍼레이션은 다른 사용자의 뉴스 피드를 갱신한다거나, 캐시 무효화, 인덱스 등의 내부 시스템에 사용할 필요가 있다. 이를 위한 한가지 접근은 데이터베이스의 쓰기 오퍼레이션을 전부 메시지 큐로 전달하고 이를 여러 consumer에게 전달하는 방식인데, 페이스북 웜홀은 페이스북의 기존의 스토리지 (MySQL, RocksDB, HDFS)의 데이터가 엄청나기 때문에, 이를 별도의 메시지큐에 복제하는 것을 피하고 접근을 선택해야만 했다.
Wormhole의 전체적인 구조는 Producer, Datastore, Publisher, Subscriber로 이루어지며, Facebook의 서비스에 해당하는 Producer가 역시 서비스를 위한 Datastore (MySQL, RocksDB, HDFS)를 업데이트하면, 일반적으로 Datastore와 동일한 서버에서 동작하는 Publisher가 Datastore의 WAL을 읽어서 이를 ‘Wormhole update’라는 공통적인 포맷 (키-밸류로 이루어진 해시 + 메타데이터)으로 만들고, 이를 Subscriber들에 전달하는 방식이다.
Datastore가 sharding 되어있기 때문에, Wormhole update에는 shard에 대한 정보가 추가되어 전달된다. 아마도 이를 이용해서 Replication 등에 활용할 수 있으리라 생각된다. 하나의 Subscriber 애플리케이션도 당연히 여러 Subscriber로 sharding될 수 있는데, 하나의 Datastore shard로부터의 Flow는 하나의 Subscriber로만 전달된다. (Replication 등을 위해) 하나의 shard로부터의 순서를 보장하기 위해서는 이 요건은 필수적인 것으로 보인다. 이러한 방식 때문에 Subscriber들 사이의 조율에 대한 필요성이 줄어들기도 할텐데, 이러한 부분에서는 Kafka가 떠오르기도 한다.
Publisher는 ZooKeeper를 이용해서 Subscriber들을 관리하며, Subscriber가 마지막으로 읽고나서 acknowledgement를 보낸 로그상의 위치를 기록한다. Subscriber는 읽고 있는 위치를 특별히 상태로서 관리하지 않아도 된다. 이러한 면에서, Kafka의 경우 Consumer가 읽어야 하는 위치를 상태로서 유지하고 broker로부터 pull하는 방식 임에 반해, Wormhole은 Publisher가 Subscriber로 push하는 정반대의 방식이라고 볼 수 있다.
Kafka와 같은 시스템에서는 일정 기간 동안의 버퍼를 가지고 있기 때문에 하나의 Consumer가 지연되더라도 단순히 이전의 offset으로 pull하는 방식으로 해결하는데, Wormhole은 내부적으로 이러한 버퍼에 해당하는 스토리지를 따로 가지고 있는 것이 아니기 때문에, Publisher는 각 Subscriber의 Flow를 별도로 관리해서 서로 다른 WAL의 위치를 읽어들일 수 있는 기능을 제공한다. 이러한 기능 덕분에 하나의 Subscriber가 느려진다고 해서 다른 Subscriber가 반드시 느려지지 않을 수 있게 된다. 여기서 문제는 서로 다른 n개의 Subscriber가 Datastore의 서로 다른 위치를 읽어들이고 있다면 Datastore의 랜덤 디스크 I/O가 증가해서 Producer 즉, 서비스의 성능에도 영향을 주게 된다. Wormhole은 이러한 문제를 피하기 위해 서로 다른 속도를 가진 Subscriber들에 대해 항상 별도의 Flow가 할당되는 것이 아니라, Subscriber가 읽고 있는 위치나 속도에 따라서 Flow들을 적당히 묶어서 Caravan이라는 개념을 도입하고 있다. 이러한 수준의 최적화까지 갖추고 있는 것은 물론 페이스북의 실제적인 필요에 의한 것이겠지만, Wormhole이 상당히 성숙된 시스템임을 느끼게 한다.
Wormhole은 간단한 필터링 메커니즘을 가지고 있어서, 각각의 Subscriber 애플리케이션이 제공한 필터에 따라서 Publisher는 필터링된 업데이트만을 Subscriber에 전달한다. 필터링은 키-밸류들의 집합에 해당하는 Wormhole update에 대한 오퍼레이션들에 대한 AND, OR로 표현된다. 이 오퍼레이션들에는 키가 존재하는지, 어떤 키의 값이 특정 값인지, 어떤 키의 값이 특정 집합에 포함되는지, 이러한 오퍼레이션들의 역들이 있다. 이러한 간단한 필터링이 존재할 수 있는 것은 불투명한 데이터를 전달하는 것이 아니라 공통적인 데이터 포맷이 정의되어 때문이다. 또한, Subscriber 애플리케이션에 따라서 모든 데이터가 필요하지 않은 경우는 매우 쉽게 상상할 수 있으므로, 이러한 기능 역시 페이스북의 매우 실제적인 요구사항에 근거한 것으로 보인다.
쉽게 상상할 수 있듯이 Datastore는 보통 복제본을 가지고 있고, 어떤 Datastore 샤드가 실패했을 때, 해당 샤드에 대한 Wormhole의 설정을 직접 바꾸거나 마스터가 복구될 때까지 기다리는 것이 아니라, 자동적으로 복제본을 이용해 Subscriber로 데이터를 계속 전달할 수 있도록 하기 위한 메커니즘을 가지고 있는데, Wormhole 논문에서는 이를 Multiple-Copy Reliable Delivery (MCRD)라고 부르고 있다. 각 Publisher는 Zookeeper의 ephemeral node를 이용해서 fail-over에 대한 coordination을 한다.
Wormhole에서 MCRD가 매우 독특한 점은 복제본들 사이에서 WAL내의 동일한 레코드의 물리적인 위치는 서로 다르기 때문에, MCRD가 아닌 경우와 달리 물리적인 위치 정보를 기록해두어도 fail-over 시에는 아무런 의미가 없다는 점이다. 따라서, MCRD 모드에서는 논리적인 위치 – 단조증가하는 sequence number나 timestamp를 ZooKeeper에 저장해둔다. 여기서 어려운 이슈는 실제로 DataStore의 종류에 따라 이러한 논리적인 위치를 정의하고, 이러한 논리적인 위치가 주어졌을 때, 이를 물리적인 위치로 변환하는 일인데, 이를 위해 DataStore에 따라 logical positions mapper가 제공된다.
Wormhole의 운영적인 측면에서 재미있는 사실 하나를 언급하고 있는데, 1%의 Datastore에 장애가 발생해서 Wormhole publisher들이 제대로 동작하지 않게 되면, 1%의 데이터가 제대로 전달되지 않아 1%의 stale한 캐시가 발생하게 될텐데, 좀 더 자세히 들여다보면 100% 사용자의 1% 데이터가 stale하게 되는 것이 아니고, 1% 사용자의 100% 데이터가 stale하게 되는 것이기 때문에, Publisher의 신뢰성이 중요하다라고 강조를 하고 있다. 이러한 설명으로 미루어볼 때 Facebook의 대부분의 Datastore는 사용자별로 sharding이 되어있는 것을 알 수 있다. :)
또 하나 재미있는 점은 분산된 deployment 시스템을 이용한다는 점이다. Datastore는 장비가 추가되거나 빠지는 경우가 흔하기 때문에, Wormhole Publisher도 이에 따른 관리를 해주기 위해서 초기에는 중앙 집중적인 관리 시스템을 사용했다고 한다. 하지만, 이러한 시스템 하에서는 아주 많은 장비들에 대해 관리를 할 때 실수가 발생할 가능성이 높았기 때문에, Wormhole monitor라는 가벼운 프로그램을 동작시키고, 이 프로그램이 주기적으로 설정을 검사해서 Publisher를 실행할지 말지, 그리고 어떤 설정으로 Publisher를 실행할지 등을 정하는 분산 관리 시스템으로 바꾸었고, 훨씬 더 신뢰성있고 사용하기 쉬워졌다고 한다.
Wormhole은 페이스북과 같은 대규모 인터넷 서비스를 위한 아키텍쳐에서 스토리지에 대한 요구사항을 특별히 늘리지 않으면서도 스토리지에 저장되는 데이터를 소비해야하는 다양한 애플리케이션들에게 매우 효율적이고 신뢰성 있게 데이터를 전달해주는 시스템으로 보인다. 보다 다양한 Datastore에 대한 지원 등이 쉽지는 않을 수도 있다고 생각하지만, 페이스북 내에서는 충분한 수준이고, Wormhole의 디자인에서 엿볼 수 있는 여러가지 실용적인 선택들은 다른 시스템에도 여러가지로 적용해볼만 하다고 생각한다.
AJOUX, Phillipe, et al. Challenges to Adopting Stronger Consistency at Scale. In: 15th Workshop on Hot Topics in Operating Systems (HotOS XV). USENIX Association. (pdf, slides)
최근 geo-replicated data store에서 높은 consistency를 제공하기 위한 연구들이 많이 있다고 한다. – 이 논문에서 나열하고 있는 그런 논문들의 목록도 흥미로운데 이는 마지막에 한번 정리해보자. – Facebook에서도 사용자들에게 – 특히, 읽기에 대한 – end-to-end consistency를 제공하기 위해서 이러한 연구 결과들을 도입하고 싶으나, 여러가지 이유로 이것이 쉽지가 않은데, 그 이유가 무엇인지 일단 알아보자…라는 것이 이 논문의 취지.
There have been many recent advances in distributed systems that provide stronger semantics for geo-replicated data stores like those underlying Facebook. These research systems provide a range of consistency models and transactional abilities while demonstrating good performance and scalability on experimental workloads. At Facebook we are excited by these lines of research, but fundamental and operational challenges currently make it infeasible to incorporate these advances into deployed systems. This paper describes some of these challenges with the hope that future advances will address them.
Facebook은 확장성과 효율을 위해서 샤딩, 복제, 캐싱 등을 아주 많이 활용하고 있는 것으로 보인다. Sodcial graph 시스템을 예로 들고 있는데, 하나의 node나 edge가 MySQL(!)에 쓰여지면, 이것이 비동기적으로 다른 데이터 센터로 복제되고, 여러 계층의 캐시들을 업데이트하고, pub-sub 시스템에 의해 검색이나 뉴스피드를 위한 다른 시스템으로 전달된다. 당연한 이야기지만, Facebook 내의 여러 기능에 해당하는 시스템들은 효율을 위해 각자 특별한 샤딩 방식이나 캐시, 인덱스들을 유지해야한다. Twitter (http://blog.lastmind.net/archives/664)나 LinkedIn (http://blog.lastmind.net/archives/657)의 시스템과 같이 Primary Data Store (DB)로부터 비동기적인 복제를 통해 Secondary Index를 생성하거나 다른 서비스로 이벤트를 전달하는 방식은 현재의 대규모 인터넷 서비스에서는 매우 공통적인 부분으로 보인다.
Facebook relies on sharding, data replication, and caching to efficiently operate at scale. When a node or edge is added to the social graph, it is first written to a single MySQL instance. From there it is asynchronously replicated to all of our data centers, updated or invalidated in multiple layers of cache, and delivered through a scalable publisher-subscriber system to other services such as Search and News Feed. No single data placement strategy can efficiently serve all workloads in a heavily sharded system, so many of these services choose a specialized sharding function and maintain their own data store, caches, and indexes.
Fundamental Challenges
Integrating Across Stateful Services
Facebook의 Social graph는 여러 서비스들을 위한 시스템에 각 서비스를 위한 형태로 복제되고 있다고 한다. 문제는, 대부분의 연구 결과들에서 나타나는 설계들은 단일한 서비스를 상정하고 있다는 것이다. Facebook는 그러한 여러한 서비스가 따로 사용자에게 제공되기 보다는 하나의 서비스처럼 제공되므로 여러가지 문제들이 발생하게 된다.
Facebook’s architecture of cooperating heterogeneous services is different from the monolithic service that most research designs assume. This difference alone is not fundamental—Facebook can be externally viewed as a single service even though internally it is comprised of many services.
Storing Data Consistently Across Services
Facebook의 각 서비스들은 Social graph의 일부에 대한 캐시, 인덱스, 복제본 등을 가지고 있다. Wormhole이라는 Facebook의 pub-sub 시스템은 업데이트를 비동기적으로 여러서비스들에 전달해주고 있다.
In a sharded and scaled environment like Facebook’s, services may maintain their own optimized cache, index, or copy of a portion of the social graph. Wormhole [40] is our scalable pub-sub system that asynchronously delivers update notifications to all of the services that manage state.
이 때, 만약 높은 consistency를 제공하기 위해서는 동기적으로 업데이트 통지를 전달할텐데, availability와 latency를 떨어뜨리는 요인이 된다. 인과성을 위한 시스템을 사용하더라도 여러 서비스들 사이의 의존관계를 표현하는 것은 굉장한 복잡도를 가져오게 된다.
To provide strong consistency across our services, we would need to propagate update notifications synchronously impacting availability and latency. A causal system could avoid atomic updates, but would still need to be integrated into every service and threaded through every communication channel greatly increasing the complexity of the dependency graph.
Decentralized Access to Services
클라이언트는 한 화면에서 표시되는 여러 컨텐츠를 별도의 리퀘스트를 통해 가져와서 클라이언트에서 통합한다. 이 때문에 클라이언트는 일관되지 않은 결과들을 가지고 session-based guarantee를 보장함으로써 사용자에게 일관된 상태를 보여주어야 한다.
The Facebook web site and its mobile applications use parallelism and pipelining to reduce latency. The notification bar and the central content are fetched by separate requests, for example, and then merged at the client. Mobile applications also aggressively cache results using local storage, and then merge query results with previously seen values. […] but it leaves the user’s device as the only safe location to define session-based guarantees or demarcate isolation boundaries.
단일한 사용자는 보통 동일한 지역의 동일한 클러스터로 라우팅 되므로 이러한 성질은 사용자가 inconsistency를 경험할 확률을 낮추어준다. 하지만, 그러한 성질이 보장되는 것은 아니므로 역시 문제는 있다.
Requests for a single user are usually routed to the same cluster in the same region. This routing stability assists in reducing the number of user-visible inconsistencies, because most of the variance in asynchronous update propagation is inter-region.
Composing Results
조금 설명이 애매하기는 한데, 여러 서비스로부터의 결과를 조합해야할 경우, 그 사이의 의존관계를 다루어야 하는데, 각 서비스는 각자의 서비스를 위한 일부의 결과를 가지고 있기 때문에, 이를 일반적으로 처리하기가 쉽지 않다는 의미인 듯 하다.
Each service can be thought of as implementing its own limited query language, so it is not clear that the dependencies can be captured in a way that is both sufficiently generic and sufficiently precise.
Query Amplification
사용자 입장에서는 하나의 쿼리지만, 내부적으로는 여러 서비스들에 대한 수천개의 쿼리로 실행될 수 있다는 이야기.
For example, a user’s home page queries News Feed to get a list of stories, which depends on a separate service to ensure story order of previously seen content. These stories are then fetched from TAO to get the content, list of comments, likes, etc. In practice, this behavior produces fork/join query patterns that have fan-out degrees in the hundreds and critical paths dozens deep.
Slowdown Cascades
동일한 데이터가 각각의 서비스에서는 서로 다른 샤딩 방식과 인덱싱을 통해 저장되므로, 서로 다른 서비스들의 샤드 사이에 all-to-all ordering 의존 관계가 발생하고, 높은 consistency를 요구하는 시스템에서는 하나의 서비스에서 하나의 샤드만 실패 또는 지연되더라도 이에 의존하는 모든 다른 서비스의 모든 샤드에 영향을 줄 수 있다는 이야기.
Different services use different sharding and indexing schemes for the same data. For instance, TAO shards data based on a 64-bit integer id, News Feed shards based on a user id, and the secondary index system shards based on values. The use of different sharding schemes creates all-to-all ordering dependencies between shards in different services. This connectedness accelerates slowdown propagation in strongly consistent systems. A failure in one shard of one service would propagate to all shards of a downstream service.
Latency Outliers
여러 쿼리들을 조합해야하는 경우, 하나의 쿼리만 느리더라도 최종적인 응답에 영향을 미칠 수 있음. 이것이 strong consistency와 직접적인 연관성이 있는지는 명확하게 이해하기 어려우나, strongly consistent system의 응답속도나 outlier들이 그렇지 않은 시스템들에 비해 더 높기 때문에 언급되는 것 같음.
Parallel subqueries amplify the impact of latency outliers. A user request does not return until it has joined the results of all of its queries, and thus must wait for the slowest of its internal requests.
Linchpin Objects
데이터의 개수도 많고 매우 자주 읽히는데다 쓰기도 많은 무언가를 Linchpin Object라고 부르고 있다. 흔히 Facebook의 연예인 페이지나 유명 대기업의 페이지를 상상하면 될 것 같다. 역시 좋은 성능을 제공하는 것이 strongly consistent system에서는 중요하다고 얘기하고 있다.
The most frequently read objects are often also frequently written to and highly connected. Examples of these linchpin objects include popular users like celebrities, popular pages like major brands, and popular locations like tourist attractions. […] A system that provides stronger consistency must provide good performance for these linchpin objects.
Net Benefit to Users
stronger consistency는 프로그래머가 프로그램의 정확성에 대해 생각하기 편리하고, 사용자에게 일관성을 제공한다는 측면에서 이점을 가지고 있지만, 이를 정량적으로 측정하기는 어려울 뿐만 아니라, 그러한 이점들이 단점들 – 커뮤니케이션 오버헤드, 무거운 상태관리, 응답속도의 증가 – 을 넘어서지 않을지도 모름.
Systems with strong consistency are easier for programmers to reason about and build on top of [6, 12] and they provide a better experience for users because they avoid some anomalous application behavior. However, these benefits are hard to quantify precisely, and they do not appear in isolation. When all aspects of user experience are considered it might even be the case that the benefit does not outweigh the detriment. […] Stronger properties are provided through added communication and heavier-weight state management mechanisms, increasing latency. Although optimizations may minimize these overheads during failure-free execution, failures are frequent at scale. Higher latency may lead to a worse user experience, potentially resulting in a net detriment.
Operational Challenges
Fully Characterizing Worst-Case Throughput
여러 서비스가 얽혀있는 복잡한 시스템에서 실패나 복구 방법에 대해 미리 예측하거나 관찰하기 쉽지 않을 뿐더러 이를 정형화하기도 쉽지 않다는 얘기.
While there is no theoretical impediment to preserving worst-case throughput despite strengthening Facebook’s consistency guarantees, our experience is that failure and recovery behavior of a complex system is very difficult to characterize fully. Emergent behavior in cross-service interactions is difficult to find ahead of time, and may even be difficult to identify when it is occurring
Polyglot Environment
(아마도 백엔드) 서비스 내에서 C++이 가장 보편적으로 사용되는 언어인 것은 매우 신기함.
While C++ is the predominant language for standalone services at Facebook, Python, Java, Haskell, D, Ruby and Go are also supported by Thrift, our inter-service serialization format. The application code coordinating service invocations is generally written in Hack and PHP, and final composition of query results may be performed by JavaScript in the browser, Objective C/C++ on IOS, or Java on Android.
여러 언어를 사용하고 있기 때문에 인터페이스나 쓰레딩 모델 등에 대해 가정하는 것이 어렵다는 이야기.
Ports or foreign function interfaces must be provided to give all of these codebases access to an end-to-end consistency platform. Perhaps the trickiest part of this multi-language support is the wide variety of threading models that are idiomatic for different languages and runtimes, because it is likely the underlying consistency system will need to initiate or delay communication.
Varying Deployment Schedules
낮은 레벨의 서비스들은 매우 보수적인 deployment 프로세스를 가지고 있으므로, 이에 관련한 시스템을 빠르게 개발하는 것은 쉽지 않을거라는 이야기.
Facebook has an extremely aggressive deployment process for the stateless application logic, but we are necessarily more conservative with stateful and mature low level services. An inter-service coordination mechanism that is used by or interposes on these low-level services will have a deployment velocity that is constrained by the release engineering requirements of the most conservative component.
Reduced Incremental Benefit in a Mature System
consistency에 관해 이미 적용된 workaround들이 있으므로, 이를 일반적으로 개선하는 시스템의 이득이 떨어진다는 이야기.
While these workarounds would not exist in a newly built system, their presence in Facebook reduces the incremental benefits of deploying a generic system for stronger consistency guarantees.
Related Work
Prior Facebook Publications
memcache cache
B. Atikoglu, et al. Workload analysis of a large-scale keyvalue store. In SIGMETRICS, 2012.
R. Nishtala, et al. Scaling memcache at facebook. In NSDI, 2013.
TAO graph store
N. Bronson, et al. Tao: Facebook’s distributed data store for the social graph. In USENIX ATC, 2013.
Wormhole pub-sub system
Y. Sharma, et al. Wormhole: Reliable pub-sub to support geo-replicated internet services. In NSDI, May 2015
a characterization of load imbalance in the caches
Q. Huang, et al. Characterizing load imbalance in real-world networked caches. In HotNets, 2014.
an analysis of the messages use case
T. Harter, et al. Analysis of hdfs under hbase: A facebook messages case study. In FAST, 2014.
understanding and improving photo/BLOB storage and delivery
D. Beaver, et al. Finding a needle in haystack: Facebook’s photo storage. In OSDI, 2010. Q. Huang, et al. An Analysis of Facebook Photo Caching. In SOSP. ACM, 2013.
S. Muralidhar, et al. f4: Facebook’s warm blob storage system. In OSDI, 2014.
L. Tang, et al. RIPQ: Advanced Photo Caching on Flash For Facebook. In FAST, Feb. 2015.
Systems with Stronger Semantics
replicated state machines
L. Lamport. Time, clocks, and the ordering of events in a distributed system. Comm. ACM, 21(7), 1978.
F. B. Schneider. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Computer Surveys, 22(4), Dec. 1990.
causal and atomic broadcasts
K. P. Birman and R. V. Renesse. Reliable Distributed Computing with the ISIS Toolkit. IEEE Comp. Soc. Press, 1994.
systems designed for high availability and stronger consistency
K. Petersen, et al. Flexible update propagation for weakly consistent replication. In SOSP, Oct. 1997.
scalable causal consistency for datacenter-scale and/or geo-replicated services
S. Almeida, et al. Chainreaction: a causal+ consistent datastore based on chain replication. In EuroSys, 2013.
P. Bailis, et al. Bolton causal consistency. In SIGMOD, 2013.
J. Du, et al. Orbe: Scalable causal consistency using dependency matrices and physical clocks. In SOCC, 2013.
J. Du, et al. Gentlerain: Cheap and scalable causal consistency with physical clocks. In SOCC, 2014.
W. Lloyd, et al. Don’t settle for eventual: Scalable causal consistency for wide-area storage with COPS. In SOSP, Oct. 2011.
W. Lloyd, et al. Stronger semantics for low-latency geo-replicated storage. In NSDI, Apr. 2013.
strong consistency for datacenter-scale and/or geo-replicated services
J. C. Corbett, et al. Spanner: Google’s globally distributed database. In OSDI, Oct. 2012.
R. Escriva, et al. HyperKV: A distributed, searchable key-value store for cloud computing. In SIGCOMM, 2012.
L. Glendenning, et al. Scalable consistency in Scatter. In SOSP, Oct. 2011.
C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguic¸a, and R. Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. In OSDI, Oct. 2012.
J. Ousterhout, P. Agrawal, D. Erickson, C. Kozyrakis, J. Leverich, D. Mazi`eres, S. Mitra, A. Narayanan, M. Rosenblum, S. M. Rumble, E. Stratmann, and R. Stutsman. The case for ramcloud. ACM SIGOPS Operating Systems Review, 43(4), 2010.
D. B. Terry, V. Prabhakaran, R. Kotla, M. Balakrishnan, M. K. Aguilera, and H. Abu-Libdeh. Consistency-based service level agreements for cloud storage. In SOSP, 2013.
transactions for datacenter-scale and/or geo-replicated services
P. Bailis, et al. Scalable atomic visibility with ramp transactions. In SIGMOD, 2014.
J. Baker, et al. Megastore: Providing scalable, highly available storage for interactive services. In CIDR, Jan. 2011.
J. C. Corbett, et al. Spanner: Google’s globally distributed database. In OSDI, Oct. 2012.
T. Kraska, et al. Mdcc: Multi-data center consistency. In EuroSys, 2013.
W. Lloyd, et al. Stronger semantics for low-latency geo-replicated storage. In NSDI, Apr. 2013.
S. Mu, et al. Extracting more concurrency from distributed transactions. In OSDI, 2014.
Y. Sovran, et al. Transactional storage for geo-replicated systems. In SOSP, Oct. 2011.
A. Thomson, et al. Calvin: fast distributed transactions for partitioned database systems. In SIGMOD, May 2012.
C. Xie, et al. Salt: combining acid and base in a distributed database. In OSDI, 2014.
Y. Zhang, et al. Transaction chains: achieving serializability with low latency in geo-distributed storage systems. In SOSP, pages 276–291. ACM, 2013.
Discussions of Challenges to Stronger Consistency
criticism of enforcing an order in a communication substrate instead of end to end
D. R. Cheriton, et al. Understanding the limitations of causally and totally ordered communication. In SOSP, Dec. 1993.
slowdown cascades to motivate enforcing only an explicit subset of causal consistency
P. Bailis, et al. The potential dangers of causal consistency and an explicit solution. In SOCC, 2012.
detail the importance and challenges for tail latency in high-scale services at Google
J. Dean, et al. The tail at scale. Comm. ACM, 56(2), 2013.
My Opinion
Strongly consistent system의 연구자들에게 방향을 제시하기 위해 Facebook의 시스템이라는 도메인 내에서 발생하는 숙제들을 정의하고 있는 논문이라고 볼 수 있는데, 마치 Facebook에서 strongly consistent system을 일반적으로 도입해서는 안되는 이유들을 정리해놓은 듯한 느낌이 들었다. 오히려 나의 관심은 Facebook에서 데이터의 복제에 관한 시스템과 복제본 사이의 consistency 문제를 어떻게 다루고 있는가 였는데, 우리가 고심하고 있는 문제들이나 해결 방향이 상당히 닮아 있다는 인상을 받았다. 여러 서비스에 걸친 업데이트 통지를 위해 인프라로서 pub-sub을 적극적으로 활용하고 있는 점이나, 서비스별로 소셜 그래프의 별도 인덱스나 캐시 등을 잘 구축해서 활용하고 있는 점은 잘하고 있다고 생각했다. Facebook의 graph storage인 TAO, pub-sub 시스템인 Wormhole 등에 대해 관심이 생겼다.
Facebook의 VP of Engineering인 Jay Parikh와의 자동화에 관한 인터뷰.
하드웨어의 실패에 따른 자동화된 진단과 복구를 위한 FBAR라는 자동화 시스템에 대해 이야기하고 있다. FBAR에 대해서는 조금 오래된 글 (2011년)이지만, 다음 글에서 조금 더 자세한 내용을 볼 수 있다. https://www.facebook.com/notes/facebook-engineering/making-facebook-self-healing/10150275248698920
We built a system we call FBAR, for Facebook Auto Remediation, to do a very basic set of hardware remediation tasks. Before, if a server had a hard drive failure or some hardware error, an alarm would go off and some human would have to log in, or walk to the computer, and try to debug or fix it. You’d do some things to try to fix it in software, you’d reboot the machine, you might try to reimage it. A lot of that software remediation and debugging is all automated now. No person has to be involved with that. The system will detect the error– it could be a disk drive, it could be a CPU, it could be a networking card or power failure—and can go ahead and do a bunch of things that it knows how to do.
당연한 이야기이지만, 자동화의 이점 중 하나는 휴먼 에러를 방지하는 것이다.
You don’t have to worry about that with automation, because work consistently gets done in the same way every time. And cluster turn-ups which used to take three or four months now can be done in the course of a week – sometimes in just a couple of days.
자동화를 통한 효율에 관한 이야기인데, 일반적인 IT 회사에서 200~500대의 서버당 1명이 일하고 있다면, Facebook에서는 25,000대당 1명의 효율을 가지고 있다고… 예전에도 들은 바가 있는 것 같지만, 2000대를 1명이 담당하는 정도가 되니 불안함을 느꼈던 것을 생각하면 대단한 것 같기는 하다.
So we have done a lot of work on the software automation side of this, to the point that we only need one technician in the data center for every 25,000 servers. That is a ratio that is basically unheard of. Most IT shops have ratios of one to 200, or one to 500.
이 인터뷰에서 자동화의 이점으로 가장 강조하고 있다고 느끼는 점인데, 상당히 단순한 부분들을 자동화하고 나면, 똑독한 사람들이 더욱 높은 수준의 일을 할 수 있고 미래에 대해서 생각할 수 있도록 한다는 것이다. 그리고, 그런 똑똑한 사람들이 오랜 시간에 걸쳐 평범한 일을 하게 된다면 결국 번아웃과 불행함으로 이어지고, 결국 이직을 하게 마련인데, 업무가 지루하고 반복적인 단순 업무가 되지 않도록 지속적으로 자동화를 하고 아키텍쳐를 바꿔나가야한다고 얘기하고 있다.
I think one of the major ways you do this is by continuing to keep them out of their comfort zone. If they end up doing “humdrum” work for a long time, they’re not learning anything, yet they’re spending a lot of time doing it. That leads to burnout and unhappiness, and then they’re going to go somewhere else. So, I think, if growing your company depends on keeping these brilliant technologists engaged, the necessity is that you have to keep automating and rearchitecting your systems so that things don’t become boring, monotonous, and repetitive. Automation serves your talent objectives.
변화를 위한 조직 구조에 대해 – 변화를 위한 팀과, 안정적이고 효율적인 운영을 위한 팀을 분리하는 것이 전통적인 접근.
Otherwise, you put them in a position where one team, in order to hit its goals, always wants to make changes, and another team only wants to make everything stable and cost-effective. Those two are completely opposed to each other. […] When I showed up at Facebook in 2009, this is what I saw and I thought is was perfectly reasonable. It was this way when I was at Akamai, it was this way when I got to Ning.
문제는 단기적인 비용에 기반해 의사결정을 하기 때문에, 미래를 위한 투자를 하지 않게 되고, 자동화는 작은 팀의 임무로 맡겨지기 때문에, 수많은 엔지니어들의 요구에 따라가지 못하게 되는 것.
Sometimes we were making decisions that were short-term cost based, when we should have been basing them on what we would need to be ready for a year from now. In other places, the focus on automation wasn’t there, because it wasn’t a team’s own responsibility. Questions about automation were being tossed to a small team of people who just weren’t going to keep up with this swarm of engineers that we were hiring.
Facebook에서는 이를 같은 팀에 묶고 변화와 운영을 동시에 하도록 하고 있다. 이 또한 쉬운 일은 아닌데, 인터럽트들이 장기적인 목표에서 벗어나도록 하기 때문. 데드라인에 대해서 조금 유연하게 대처할 필요가 있다고 얘기하고 있다.
No, we come up with what we call big bets as a team, planning the investments in technology that will take one or two or three years to build. For example, we built a new compiler that runs the front end of our site. It took us a couple of years to build and that R&D effort was done in parallel, in the same team that was maintaining the existing run time that was running the live Facebook.
이러한 방식의 장점에 대해서, 혁신을 위한 팀은 변화에 대한 성과에 대해서 걱정하고, 전선에서 뛰는 비즈니스 팀은 언제쯤 재미있는 일을 할 수 있는지에 대한 불만을 표하는 상황 등을 방지할 수 있다고 얘기하고 있다.
But meanwhile there are so many benefits — starting with the fact that it’s done in a much more open way. No one likes it when there’s a team working in some secure undisclosed location “doing something really cool that is going to replace what you’ve got.” It’s a tough thing to manage on both ends. The innovation team worries: “We’re not making any impact now – they’ve just stuffed us in a corner and told us go deliver something great.” And the core business team you’re depending on to deal with problems and customer support issues and all the urgent things that come up, is saying, “When do we get to work on something cool? Are we second-class citizens or something?”
의견
자동화의 이점에 대해서는 100% 동감하고 적어도 IT 업계의 일정 규모 이상의 회사라면 어떤 조직이라도 항상 중요한 목표가 되어야 한다고 생각한다. 변화팀과 운영팀을 통합하는 조직 구조에 대해서는 전반적으로는 동의하나, 아마도 VP 레벨의 입장에서는 통합된 조직일지는 몰라도 실무 수준에서는 이 글에서도 제시하듯이 인터럽트와 단기적인 비용에 기반한 요구들은 장기적인 관점에서의 업무에 매우 해롭기 때문에, 일정 규모 이상의 조직이라면, 정도의 차이는 있더라도 팀 내에서라도 어느 정도의 분리는 필요하지 않는가라고 생각한다. 다만, 변화팀과 운영팀이 서로 얼굴을 맞대고 이야기할 수 없을 정도로 서로 다른 조직의 바운더리로 분리되어 있다면, 이 글에서 지적된 것과 같은 부정적인 효과는 항상 발생할 것이다.
사용자들이 항상 사용하고 있는 서비스를 하면서 빠르게 변화하는 것은 두마리 토끼를 잡으려는 것과 같이 어려운 일이기 때문에 많은 고민과 노력을 통한 좋은 프랙티스가 필요하다고 생각되지만, 실제로는 그러한 프랙티스는 그다지 널리 알려져 있지는 않는 것 같다.
이 발표는 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
릴리즈 관리자가 사용할 수 있는 도구는 소프트웨어적인 도구와 문화라고 얘기할만큼 개발 문화의 중요성을 강조하고 있다. 항상 그렇지만, 도구만으로는 성공할 수 없다.
