graph db

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.