개발자 노트

오늘 글 에서는 합의(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..

기본 자료구조 중 하나인 연결리스트를 정리하기 위해 알고리즘 문제를 풀어보았다. algospot의 조세푸스 문제이다. (링크) 문제를 간략히 요약하면 원으로 둘러싸인 병사들이 하나씩 죽는데, k번의 간격을 두고 순차적으로 죽으며 나머지 2명을 찾아내는 문제이다. 원으로 모여있다고 가정하기 때문에 연결리스트의 마지막 다음이 첫번째 연결리스트 노드로 인식하고 풀어나가면 된다. Java에서는 연결리스트의 표준 라이브러리로 LinkedList를 구현해 놓았다. LinkedList의 iterator(링크)로 노드들을 순차적으로 탐색할 수 있다. 문제를 풀면서 LinkedList에 대해서 정리를 추가로 한 부분.iterator()로 얻은 첫 노드는 LinkedList의 첫 노드가 아니라 첫 노드를 가르키는 head..

python 공부를 할 때, 실제로 코딩을 하면서 공부하는 방법이 익숙해 지는데 빨라서 간단한 알고리즘을 풀기로 했다.그래서 활용한 방법이 http://projecteuler.net에서 수학 관련 알고리즘 문제를 푸는 것이었다. 첫번째로 풀 문제는Problem 12. Highly divisible triangular number 간단히 설명하면 아래와 같이 연속적인 숫자들의 합으로 구해진 triangle number 중에서 처음으로 소수의 개수가 500개가 넘는 수를 구하는 문제이다. 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 (연속적인 숫자의 합)1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... (triangle number) triangle number에 대한 소수..

두 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는 임의 상수). [분할정복의 대표 알고리즘] 병합정렬, 퀵 정렬 [분할정복의 예] 아래 그림은 병합정렬의 진행 과정을 도식화 한..