RedisRaft에 대한 Jepsen 리포트가 나왔다. https://jepsen.io/analyses/redis-raft-1b3fbf6 RedisRaft는 Redis Labs에서 개발하고 있는, Raft를 이용해 replication을 구현한 Redis module이다. 약 2018년 초에 PoC 프로젝트로 시작되었고, 2019년 중반부터 본격적으로 개발하기 시작했다고 한다. 실제로 RedisRaft의 GitHub repository를 확인해보아도 Yossi Gottlieb라는 개발자가 약 1년 전부터 commit을 하기 시작한 것을 알 수 있다. 현재는 개발 중이고 2021년에 GA로 내놓을 예정이라고 한다. …
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의 주요한 데이터들을 표현한다는 것도 …
Paper: TAO: Facebook’s Distributed Data Store for the Social Graph (Part 1) 더 보기 »
Reed, Benjamin, and Flavio P. Junqueira. “A simple totally ordered broadcast protocol.” proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware. ACM, 2008. 이 페이퍼는 Zab라는 ZooKeeper의 내부에 구현되어있는 ordered broadcast 프로토콜을 소개하고 있다. 이 페이퍼는 informal한 형태로 Zab에 대한 요구사항과 동기, 그리고 프로토콜 자체에 대해서 설명하고 있으므로 이를 파악하기에 좋은 것 같다. …
Shapiro, Marc, et al. “Conflict-free replicated data types.” Stabilization, Safety, and Security of Distributed Systems. Springer Berlin Heidelberg, 2011. 386-400. Distributed system에서 replica 사이의 consistency를 유지하는 것은 매우 어려운 문제지만, CRDT라고 불리는 특별한 데이터구조들은 semilattice나 commutativity와 같은 그 자체의 성질을 이용하여 consistency의 문제를 훨씬 단순한 문제로 만들어준다. CRDT에 해당하는 데이터구조나 수학적인 성질들은 오래전부터 알려져있었고 활용되어왔지만, …
Sharma, Yogeshwer, et al. “Wormhole: Reliable pub-sub to support geo-replicated internet services.” NSDI, May. 2015. Challenges to Adopting Stronger Consistency at Scale 논문을 소개할 때도 언급한 바가 있는 이 논문은 Wormhole이라는 페이스북의 스토리지 업데이트를 여러 애플리케이션에 전달하기 위한 pub-sub 시스템을 소개하고 있다. 페이스북에서 사용자가 포스트를 올리면 데이터베이스의 쓰기가 발생하게 되는데, 이러한 쓰기 오퍼레이션은 다른 사용자의 뉴스 …
Chandra, Tushar D., Robert Griesemer, and Joshua Redstone. “Paxos made live: an engineering perspective.” Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. ACM, 2007. 이 논문은 Paxos를 실제로 구현하고자 할 때 고려해야할 현실적인 문제들과 해결방식을 설명하고 있다. Google은 Chubby에서 필요로하는 분산 로그 스토리지를 위해 기존의 상용 솔루션을 대체하는 Paxos를 구현하게 되었다고 …
Paper: Dotted version vectors: Logical clocks for optimistic replication (Part 1) A Kernel for Eventual Consistency 인과성을 이용하는 분산 스토리지의 동작에 있어서 논리적 시계 집합에 대한 sync 와 update 2개의 오퍼레이션이 핵심을 이루고 있다고 주장하고 있다. 먼저 sync 오퍼레이션의 경우에는 두 개의 시계 집합을 취해서 두 집합의 원소들인 논리적 시계들 사이에 인과성의 관계가 있다면 이전에 해당하는 …
Paper: Dotted version vectors: Logical clocks for optimistic replication (Part 2) 더 보기 »
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에서도 사용자들에게 – …
Paper: Challenges to Adopting Stronger Consistency at Scale 더 보기 »
PREGUIÇA, Nuno, et al. Dotted version vectors: Logical clocks for optimistic replication. arXiv preprint arXiv:1011.5808, 2010. Dynamo, Cassandra, Riak, Voldemort와 같은 시스템들은 쓰기 가용성 (write availability)을 보장하기 위해, 어떤 하나의 데이터 항목의 여러 복제본이 동일한 데이터 항목의 복제본이 서로 다른 값으로 갈라질 (diverge) 수 있고, 이를 나중에 수리(repair)하는 방법을 고안하고 있다. 이 때, 복제본 버전들을 비교해서 …
Paper: Dotted version vectors: Logical clocks for optimistic replication (Part 1) 더 보기 »
Kafka: A distributed messaging system for log processing In Proceedings of 6th International Workshop on Networking Meets Databases (NetDB), Athens, Greece (2011) by J. Kreps, N. Narkhede, J. Rao Kafka는 기존의 메시징 시스템에서 당연하다고 가정하고 있었지만, 로그 처리 시스템에서는 필요없는 보장들을 과감하게 버리고, 성능 위주의 설계를 함으로써, 실제로 링크 속도에 육박하는 성능을 보여주고 있고, 상당히 …
Kafka: a Distributed Messaging System for Log Processing 더 보기 »