개발자 노트

오늘 글 에서는 합의(consensus) 알고리즘 중 하나인 Raft 알고리즘(이하 Raft)에 대해서 설명한다. Raft에 대해서 조사를 하게 된 이유는 Kafka에서 Zookeeper을 제외하는 대신 Controller의 역할 수행을 위해 Raft의 일부 개념을 가져와서 구현했기 때문이다. Kafka에서 사용하는 Raft는 정확히 같은 동작방식을 사용하는 것은 아니다. 크게 차이가 나는 부분은 로그 복제 부분이다. 대표적으로 Raft는 push 방식으로 controller가 데이터를 각 follower에 보내지만 Kafka에서는 pull 방식으로 follower들이 데이터를 가지고 온다. 이 글에서는 그 차이점에 대해 설명하기 보다 Raft 논문에서 설명하는 leader 선정 과정 및 로그 복제 방법..

AVL Tree의 노드를 삭제한 이후에도 재배열 과정을 거쳐야 한다. 재배열 과정에서 지켜야할 규칙은 이전 블로그에서 기록한 내용과 동일하다. T1, T2, T3는 루트노드 y 또는 x의 자식트리이다. (y는 왼쪽, x는 오른쪽 트리) y x / \ Right Rotation / \ x T3 – – – – – – – > T1 y / \ < - - - - - - - / \ T1 T2 Left Rotation T2 T3 두 트리에서 지켜야 할 데이터 크기의 순서는 아래와 같다. keys(T1) < key(x) < keys(T2) < key(y) < keys(T3) 삭제의 순서 노드 w를 삭제한다고 할 때, 순서는 아래와 같다. BST의 삭제 방법과 동일하게 노드 w를 삭제한다. w 노드로부터 불균형한 첫번째..

AVL Tree는 스스로 균형을 맞추는 이진탐색트리(BST)이다. 여기서 균형을 맞춘다는 것은 왼쪽/ 오른쪽 자식트리의 깊이 차이가 1을 넘지 않는다는 의미이다. [그림1] AVL Tree [그림 2] AVL Tree가 아님 위 [그림1, 2]는 AVL Tree의 성립 조건을 비교하는 예시이다. [그림 1]의 경우는 모든 노드에서 자식노드들(왼쪽, 오른쪽)의 깊이 차이가 1을 넘지 않는다. 그런데 [그림 2]의 트리는 8과 18을 가진 노드에서 자식노드들의 깊이 차이가 1을 넘기 때문에 AVL Tree 조건을 성립하지 않는다. 왜 AVL Tree를 사용할까?이진탐색트리의 작업들(검색, 삽입, 삭제 등)을 수행할 때 O(logN)의 시간이 소요된다. 하지만 한쪽으로 노드들이 쏠린 트리의 경우 수행시간이 O..

두 n자리 수의 곱셉은 n2 의 연산이 필요하다. 1의 자리부터 n자리까지 연속에서 곱을해서 더했던 방법이 우리들에게 익숙하다. 왼쪽과 같이 2자리수의 곱을 계산했을 때 22의 곱의 합으로 이루어짐을 볼수 있다. 카라츠바 알고리즘은 두 수 x,y의 곱을 x,y의 절반인 수들의 곱 3번과 덧셈으로 계산하는 방식이다.큰 문제를 반으로 분할해 가며 해결하는 방법으로 분할정복의 대표 알고리즘이다. 아래는 wikipedia에 나온 알고리즘 단계의 내용이다.http://en.wikipedia.org/wiki/Karatsuba_algorithm [카라츠바 알고리즘 정리]x와 y를 B진법의 n자리수라고 했을 때, n보다 작은 양수 m에 대해 x,y를 쪼갤 수 있다. x = x1Bm + x0y = y1Bm + y0(단,..

분할정복 2개 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 즉, 해를 구할 수 있을 만큼 충분히 나누어서 해결하는 방법이다. 하향식 접근법 (top-down) [세가지 구성요소] 문제를 더 작은 문제로 분할하는 과정(divide) 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case) 분할의 의미로 전체 n을 반으로 나누어 생각할 수 있다(n/2). 병합을 의미하는 n번의 작업(b는 임의 상수). [분할정복의 대표 알고리즘] 병합정렬, 퀵 정렬 [분할정복의 예] 아래 그림은 병합정렬의 진행 과정을 도식화 한..