2017-11-29

Raft - 이해하기 쉬운 consensus algorithm

 분산 시스템을 구축할 때, 모든 노드가 독립적으로 돌아가는 시스템을 설계한 것이 아니라면, 공유된 상태를 합의하기 위한 모종의 방법이 필요하다. 이런 식으로 분산 환경에서 상태를 공유하는 알고리즘을 consensus algorithm이라고 한다.
 consensus algorithm 중에서 가장 유명한 알고리즘은 Paxos다. 하지만 Paxos는 구현은커녕 이해하는 것 자체가 어렵기 때문에, Paxos를 구현한 라이브러리가 거의 없었고, 일부 분산 시스템들이 내부적으로 사용하는 정도였다.
 그래서 분산 시스템을 구축할 때 현실적으로 사용할 수 있는 방법은 Zab algorithm을 사용하는 Zookeeper를 이용하는 것이었다. Zookeeper는 매우 훌륭하다. 사실 지금까지도 분산 환경에서 consensus를 위해 사용할 수 있는 검증 된 거의 유일한 라이브러리라고 말할 수도 있을 정도다. 하지만 Zookeeper는 메시지의 순서가 보장돼야 하기 때문에 반드시 TCP를 사용해야만 한다. 또한, Zab algorithm이 Zookeeper의 구현과 긴밀하게 엮여 있기 때문에 다른 구현을 만들기 힘들어 반드시 JVM을 띄워야 하는 문제가 있다.

 Raft는 구현체를 만들기 어렵다는 기존 consensus algorithm의 문제를 해결하기 위해 이해하기 쉬운 것을 최우선으로 설계된 consensus algorithm이다.
 Raft에서는 노드 간 공유될 state를 append-only state machine으로 본다. 따라서 노드 간에 상태가 합의됐다는 것은 이 state machine을 변경시키는 append command가 같은 순서로 적용됐다는 것을 의미한다. append command를 추가하는 것을 로그를 추가한다고 하고, 모든 노드가 같은 state를 가지게 하는 것을 log replication이라고 한다. 이때 어떤 append command를 추가할 것인지를 모든 노드가 일치한 정보를 가지는 것이 중요한데, Raft는 리더를 선출하여 모든 결정을 리더에게 위임하는 방법을 택했다. 이를 strong leader라고 하는데 덕분에 리더가 결정되고 나면 log replication은 매우 단순하게 진행된다. 이 leader election이 어떻게 되는지 다음 글에서 자세히 다뤄보도록 하겠다.

2017-11-27

[CppCoreGuidelines] const_cast는 언제 써야 하는가

 C++의 const_cast는 레퍼런싱하는 object의 cv-qualifier를 제거하는 캐스팅이다. cv-qualifier는 타입에 constness와 volatility를 더해주는 한정자이므로 const_cast는 constness뿐 아니라 volatility도 제거할 수 있다. constness를 제거하면 수정할 수 없었던 object를 수정할 수 있게 해주고, volatility를 제거하면 해당 object에 접근하는 코드가 최적화되어 사라질 수 있게 해준다. 따라서 const_cast는 실제 존재하는 object가 별도로 있고, 그것에 접근하는 방법을 변경한다.
 문제는 volatile object의 레퍼런스를 const_cast로 volatility를 없앤 뒤 이 object에 접근하는 것이나, const object의 레퍼런스를 const_cast로 constness를 없앤 뒤 이 object를 수정할 경우 이 코드가 어떻게 동작할지는 undefined behavior라는 것이다. 즉 아래와 같은 코드들은 전부 undefined behavior이다.

 그렇다면 const_cast는 언제 사용하는 것일까? 사실 const_cast를 사용해야만 하는 경우는 없다. 무언가를 하기 위해 반드시 const_cast가 필요하다고 느껴진다면 디자인에 무언가 문제가 있는 것이다. 그래서 C++ Core Guidelines에서는 const_cast를 사용하지 않는 것을 권장한다. 흔히 const_cast를 사용하는 패턴을 정리하면 아래의 3가지 패턴으로 분류할 수 있다. 이제부터 그 3가지 패턴이 왜 사용하면 안 되는지 설명할 것이다.

  첫 번째 용례는 어떤 object의 cv-qualifier를 cv1이고, 이 object를 레퍼런싱하는 cv1보다 더 cv-qualified 된 cv2를 가지는 변수를 가지고 있을 때, cv1보다 높고, cv2보다는 낮은 레벨의 cv-qualifier를 갖도록 하는 것이다. 즉, int i1이 선언돼 있고 이 i1를 지칭하는 const int& i2가 있을 때, i2를 int&로 캐스팅하는 용도다.
 하지만 잘 설계됐다면 undefined behavior를 감수하고 중간에 cv-qualified 된 레퍼런스로 들고 다닐 이유가 없다.

 두 번째는 non-const method를 가지는 클래스의 const instance가 있을 때, 이 instance를 통해 non-const method를 호출하는 것이다.
 하지만 어떤 메소드가 non-const method인 이유는 그 함수 안에서 mutable이 아닌 subobject를 수정하기 때문이다. 이를 const_cast를 통해서 강제로 호출할 경우 subobject를 수정하는 동작이 undefined behavior가 될 수 있으므로 안전하지 않다.

 마지막 사용 방법은 어떤 클래스의 const 메소드와 non-const 메소드 두 개를 정의할 때 코드의 중복을 없애기 위해서다.  이는 Scott Meyers의 Effective C++에서 추천하는 방법이기도 하고 실제로 매우 많이 보게 되는 코드다. 일반적으로 이 경우 const*로 캐스팅한 this가 반드시 non-const object를 레퍼런싱하는 것을 보장하기 때문에 안전하다. 하지만 이는 f 함수가 리턴하는 레퍼런스가 S의 멤버라는 가정하에서만이다. 예를 들어 f가 리턴하는 reference_to_r이 static storage를 가지는 const R이었다면 위의 코드는 정상적으로 컴파일되지만, non-const인 S의 instance를 통해 f를 호출할 경우 그 결과값은 const object를 지칭하는 non-const 레퍼런스이기 때문에 안전하지 않다.
 그래서 C++ Core Guidelines에서는 const_cast의 사용을 금지하고, C++11에서 추가된 decltype을 이용해서 아래와 같이 해결하는 것을 권장한다.  위의 코드에서는 f_impl의 리턴 타입이 템플릿 파라미터인 T에 의존하고, f의 결과값은 f_impl의 결과값이기 때문에, reference_to_r이 const-object의 레퍼런스라면 R& f를 컴파일할 때 에러가 발생하기 때문에 안전하게 선언할 수 있다.

 이상으로 const_cast를 사용하는 코드가 어째서 위험한지 알아보았다. 사실 C++11 이전에도 const_cast가 위험하다는 것은 널리 알려져 있었다. 하지만 코드의 중복을 제거하기 위해 const_cast를 사용하는 것을 대체할 방법이 없었기 때문에, 일반적으로 const_cast를 사용하지 말라고 할 수 없었다. 하지만 C++11에 들어간 decltypeconst_cast 없이도 코드의 중복을 없앨 방법을 제공한다. 따라서 C++11 이후로는 undefined behavior가 되기 쉬운 const_cast를 더는 쓸 이유가 없다.

2017-11-26

[C++] as-if rule - 소스에 적힌 순서대로 실행되지 않는 이유

 as-if rule이란, 프로그램의 실행 결과가 변하지 않는다면 소스에 적혀있는 것이 아닌 다른 방법으로 실행하는 것을 허용하는 규칙을 말한다. 이러한 규칙을 as-if rule이라는 이름으로 부르는 것은 C++에서만 찾을 수 있지만, C를 비롯한 다른 언어에서도 이러한 부류의 최적화를 허용한다.

 as-if rule을 허용하는 이유는 크게 두 가지로 보인다. 우선 컴파일러의 최적화를 방해하지 않기 위함이다. 만약, 표준 문서에서 적용할 수 있는 최적화 방법을 화이트 리스트로 관리한다면, 새로운 최적화 기법이 나왔을 때, 컴파일러가 이를 적용하기 위해서는 표준을 수정해야 한다. 하지만 표준에서 허용하지 않는 동작만 기술해두면 컴파일러 구현체에서 새로운 최적화를 구현하는데 조금 더 자유로울 수 있다.
 두 번째 이유는 C++이 가정하는 abstract machine이 엄밀하게 정의되지 않았기 때문이다. 일반적으로 C++의 실행 타깃은 native processor다. 이 프로세서는 제조사에 따라서, 혹은 칩 아키텍처에 따라서 다른 특성을 가질 수 있는데, C++ 표준은 이때 실행할 프로세서의 종류나 특성을 한정 짓지 않는다. CPU 별로 메모리 오더, 레지스터 크기, 레지스터 개수 등이 전부 다르기 때문에 가능한 최적화도 전부 다르다. 따라서 표준에서 어떤 최적화를 허용할지 명시할 수 없고 as-if rule이라는 이름으로 코드의 실행결과를 바꾸지 않는 최적화를 전부 허용하도록 명시한 것이다.

2017-11-20

[C++] Visual C++의 volatile

 지난번 글에서 말했듯이 C++ 11 이전에는 메모리 접근의 순서를 보장할 수 있는 표준 방법이 없었다. 따라서 플랫폼에 따라 다른 코드를 사용해야 했다. x86은 mfence, ARM이라면 DMB 인스트럭션을 인라인 어셈블리를 사용하여 집어넣거나, gcc의 __sync_synchronize 나 Visual C++의 MemoryBarrier 매크로를 사용하는 방법이 일반적이다. 여기에 Visual C++은 volatile에 추가적인 제약을 거는 방법으로 메모리 접근 순서를 보장하는 방법을 마련하였다.

 Visual C++의 컴파일 옵션에서는 volatile의 동작을 2가지 중 하나로 선택할 수 있다. /volatile:iso로 컴파일하면, iso 표준대로 메모리 접근 순서와 상관없이 as-if rule에 의해 코드가 최적화되어 사라지는 것만을 방지한다. 하지만 /volatile:ms로 컴파일하면 iso 표준에서 규정하는 제약에 추가적으로 volatile object에 접근하는 것이 load-acquire, store-release semantic을 따른다. 즉, 간략히 말하면 store는 뒤에 있는 load가 실행된 다음에 실행될 수 있지만, 다른 메모리 접근의 순서는 순서대로 실행되는 게 보장된다.

 컴파일 때 아무 옵션을 안 주면 x86에서는 /volatile:ms가 기본값이다. 사실 x86 CPU는 load-acquire, store-release semantic을 따르기 때문에 volatile object에 접근하는 코드는 컴파일 타임에 순서를 바꾸지 않겠다는 것이다.
  ARM에서는 /volatile:iso가 기본값이다. 따라서 /volatile:ms를 이용하여 컴파일하면 DMB 인스트럭션을 이용하여 CPU가 순서를 바꿔 실행하는 것을 막기 때문에 성능이 떨어진다. 하지만 x86에서 테스트 된 코드를 그대로 사용할 수 있다.

2017-11-19

[C++] memory barrier - 메모리 접근의 순서 보장하기

 지난번 글에서 말했듯이 C++의 volatile object에 대해서 메모리 접근 순서를 보장하지 않지만, 메모리 접근 순서를 보장한다고 잘못 아는 사람이 많이 있다. 이는 지난번에 글에서 말했듯이 Java나 C#으로 멀티 스레드 프로그래밍을 배운 사람들이 잘못 알기 때문이기도 하지만 C와 C++로 멀티 스레드 프로그래밍을 배운 사람들도 잘못 아는 경우가 많다. 그런 경우는 보통 아래와 같은 착각을 하기 때문이다.

Access to volatile objects are evaluated strictly according to the rules of the abstract machine. - C++14 intro.execution 1.9.8.1
 C++ 표준에 적혀있는 위의 문장에 따르면 volatile object에 접근이 엄격하게 실행된다고 적혀있다. 이 문장을 잘못 이해해서 엄격한 순서로 실행된다고 받아들이는 사람들이 있다. 하지만 이는 그저 volatile object에 접근하는 코드는 as-if rule에 의해 최적화되지 못한다는 것으로 메모리에 접근해야 할 코드를 최적화해서 없애거나, 레지스터 등을 이용해서 최적화하지 못한다는 것이다. 그보다 중요한 것은 abstract machine의 규칙을 따른다는 것이다.

 여기서 말하는 abstract machine은 다른 구현체에서 같은 동작을 보장하기 위해 C++ 표준이 기술한 가상의 기계를 의미한다. 근데 이 abstract machine은 의존성이 없는 다른 메모리 영역에 접근하는 것에 대해 순서를 보장하지 않는다. 이는 컴파일러가 as-if rule에 따라 최적화할 여지를 남겨두기 위해 서기도 하지만, 실제로 CPU가 실행 시간에 메모리 접근을 재배치할 수 있기 때문이다. 그래서 실제로 어셈블리의 순서대로 실행될지 알 수 없다.
 물론 모든 인스트럭션이 재배치되는 것은 아니고 CPU마다 자신이 재배치하여 실행할 수 있는 조합이 있다. 예를 들어 가장 많이 사용되는 X86의 경우 메모리에 저장하는 인스트럭션이 메모리에서 값을 읽는 인스트럭션 뒤로 가는 것만 허용하고, 저장-저장, 읽기-읽기의 순서와 메모리를 읽는 인스트럭션이 뒤에 오는 저장 인스트럭션보다 먼저 실행될 것은 보장해준다. 하지만 이 동작에 의존하면 ARM이나 PowerPC 같이 모든 메모리 접근 순서가 보장되지 않는 CPU에서는 의도하지 않은 동작을 할 수 있다.
 그렇다면 순서를 보장하기 위해서는 어떻게 해야 할까? C++11이 들어오기 전에는 표준에 스레드와 관련된 내용이 없었다. 이 말은 다른 말로 C++의 abstract machine은 싱글 스레드로 가정하였다는 것이고, 당시에는 의존성 없는 메모리에 접근하는 순서가 중요하지 않았다. 그래서 당시 표준에서는 메모리 접근 순서를 보장하는 방법도 존재하지 않았고, 자신이 실행할 플랫폼에서 지원하는 방법을 사용해야 했다. 하지만 C++11에서는 멀티 스레드를 지원하도록 변하면서 fence를 칠 방법이 표준에 들어왔다.
 C++11에서 지원하는 std::atomic_thread_fence는 x86의 경우 mfence 계열의 인스트럭션으로 번역되고, ARM의 경우 DMB 같은 인스트럭션으로 번역된다. 이런 메모리 순서를 보장하는 특별한 instruction을 memory barrier 혹은 memory fence라고 한다.

2017-11-18

[C++] volatile

 volatile은 C++에서 가장 오해받고 있는 키워드 중 하나일 것이다. 오해받는 이유는 크게 2개라고 생각한다. 첫 번째로 C++의 volatile이 Java나 C# 등 다른 언어에서 말하는 volatile과 다르기 때문이고, 두 번째로 C++의 volatile은 CPU와 컴파일러가 어떻게 동작하는지 알지 않으면 이해하기 어려운 비직관적인 기능이기 때문이라고 생각한다.

 Java나 C# 등 다른 언어에서 volatile은 다른 스레드에서 visibility를 보장해주기 위해 사용된다. 따라서 변수의 접근이 리오더링 되는 것을 막고, 언제나 최신 값을 유지하는 것을 보장해준다. 특히나 멀티 스레드 프로그래밍을 한다면 누구나 한 번쯤 읽어본다는 고전 명작 The Art of Multiprocessor Programming에서 그 예제 코드가 Java로 돼 있기 때문에 C++에서도 volatile 키워드가 같은 의미를 가진다고 생각하는 사람이 많다.

 하지만 C++에서 volatile은 멀티 스레드와 아무런 관련이 없다. 이는 과거 C 표준에 스레드와 관련된 내용이 없던 시절에 추가된 이후로 지금까지 스펙이 변경되지 않았기 때문이다. 그래서 C++의 volatile은 싱글 스레드 코드에서 변수의 접근이 최적화되어 사라지는 것을 막을 뿐이다. 예를 들어 int a가 있을 때 a += 1을 반복하는 코드가 3회 반복될 때, 이 중간에 a에 접근하는 코드가 없으면, 이 코드는 a += 3으로 최적화될 수 있다. 만약 중간에 a에 접근하는 코드가 있어도, 매번 a를 메모리에서 접근하지 않고, a를 레지스터에 집어넣어 최적화할 수 있다. 하지만 a의 타입이 volatile int였다면, 이와 같은 최적화는 할 수 없고 a를 메모리에서 읽어 1을 더하여 메모리에 쓰는 코드가 3번 들어가야 한다.
 하지만 리오더링 되는 것을 막지 않는다. 따라서 의존성이 없는 두 변수가 volatile로 선언돼 있을 때 이 두 변수 사이에 읽기/쓰기는 다른 순서로 실행될 수 있다. 아래의 코드가 volatile이 리오더링되는 것을 막지 않기 때문에 C++이 volatile을 사용했을 때 다른 언어와 다르게 동작하는 대표적인 예제다.
 위의 코드에서 thread1_mainthread2_main이 다른 스레드에서 동시에 실행될 때 코드가 쓰여 있는 순서대로 실행된다면 b가 1이고 a가 0인 순간이 올 수 없기 때문에, 절대로 assert에 걸리지 않는다. 하지만 앞에서 말했듯이 C++의 volatile은 리오더링을 막지 않기 때문에 thread1_mainb = 1a = 1보다 먼저 실행될 수 있어서 b는 1이지만 a는 0인 순간이 올 수 있고 assert에 걸릴 수 있다.