11월, 2017의 게시물 표시

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는 리

[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를 cv 1 이고, 이 object를 레퍼런싱하는 cv 1 보다 더 cv-qualified 된 cv 2 를 가지는 변수를 가지고 있을 때, cv 1 보다 높고, cv 2 보다는 낮은 레벨의 cv-qualifier를 갖도록 하는 것이다.

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

as-if rule 이란, 프로그램의 실행 결과가 변하지 않는다면 소스에 적혀있는 것이 아닌 다른 방법으로 실행하는 것을 허용하는 규칙을 말한다. 이러한 규칙을 as-if rule이라는 이름으로 부르는 것은 C++에서만 찾을 수 있지만, C를 비롯한 다른 언어에서도 이러한 부류의 최적화를 허용한다. as-if rule을 허용하는 이유는 크게 두 가지로 보인다. 우선 컴파일러의 최적화를 방해하지 않기 위함이다. 만약, 표준 문서에서 적용할 수 있는 최적화 방법을 화이트 리스트로 관리한다면, 새로운 최적화 기법이 나왔을 때, 컴파일러가 이를 적용하기 위해서는 표준을 수정해야 한다. 하지만 표준에서 허용하지 않는 동작만 기술해두면 컴파일러 구현체에서 새로운 최적화를 구현하는데 조금 더 자유로울 수 있다. 두 번째 이유는 C++이 가정하는 abstract machine이 엄밀하게 정의되지 않았기 때문이다. 일반적으로 C++의 실행 타깃은 native processor다. 이 프로세서는 제조사에 따라서, 혹은 칩 아키텍처에 따라서 다른 특성을 가질 수 있는데, C++ 표준은 이때 실행할 프로세서의 종류나 특성을 한정 짓지 않는다. 두 번째 이유는 C++이 가정하는 abstract machine이 실행 타깃에 의존하는 형태로 정의되었기 때문이다. 이를 parameterized nondeterministic abstract machine이라고 한다. 구현체는 이 parameter를 정해 실제 abstract machine을 완성한다. C++이 abstract machine을 이렇게 복잡한 방식으로 정의하는 이유는 C++의 실행 타깃이 가상 머신이 아닌 native processor이기 때문이다. 이 프로세서는 아키텍처에 따라서 다른 특성을 가질 수 있다. 다양한 아키텍처를 지원하기 위해 C++ 표준은 실행할 프로세서의 특성을 한정 짓지 않는다. CPU 별로 메모리 오더, 레지스터 크기, 레지스터 개수 등이 전부 다르므로 가능한 최적화도 전부 다르다. 따라서 표준에

[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에서 테스트 된 코드를 그대로 사용할 수 있다.

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

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

[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로 선언돼 있을 때 이 두 변수 사이에 읽기/쓰기는 다른