Distributed Hash Table: Chord에 대하여
일단 들어가기에 앞서, DHT (Distributed Hash Table)이란, Distributed System에서 Insert, Find, Delete들을 Key를 통해 가능하게 해주는 Table을 뜻한다.
여러가지 DHT들 중에서 오늘은 Apache Cassandra / AWS DynamoDB와 관련된 Chord에 대해서 이야기를 해보자 한다.
Cassandra에 대해 한번이라도 검색해 본 사람들은 이러한 그림을 본 적이 있을것이다.
이러한 방식을 Chord라고 하며, Chord를 통해서 Distributed System (Cassandra)는 데이터를 어디에 저장해야하는지 혹은 어디에 저장돼 있는지를 알 수 있다.
각 노드에 Key (Id) 할당 하기
Chord를 구성하기 위해서 첫번째로 해야할 일은 바로 각 노드에 Id를 붙여주는 것이다.
여기서 중요한 점은 Id가 몰리는 것이 아니라 골고루 퍼져있어야 하므로 Hash Function을 이용하여 Id를 붙여준다. (골고루 퍼져있어야 하는 이유는 후술 하도록 하겠다)
예를 들어 Address + Port를 SHA-1 Hash Function을 이용하여 string을 만들고,
만들어진 string의 첫 m개만 따와서 (string[:m])
0 ≤ id < 2 ^ m인 Id를 만들 수 있다.
m = 7인 예시: 각 노드의 Id가 0 ≤ id < 2 ^ 7 (128) 인것을 알 수 있다.
Insert
이러한 Chord에 Object(file)을 저장할 때도 유사한 방식을 이용한다. 똑같이 각 파일의 정보(예: 파일 이름)와 Hash Function을 이용하여 Key값을 할당해준다. 그 후 Key보다 같거나 큰 첫번째 노드에 파일을 저장한다.
예를 들어 파일 이름이 “I_love_distributed_systems.txt”이고 여기에 SHA-1을 적용한후 첫 8byte를 잘라 만든 숫자가 42라고 한다면, 파일은 Node 45에 저장이 될 것이다.
이러한 이유로 만약 좋은 Hash Function을 사용하지 않을 경우 한 노드에 object들이 몰릴 수가 있고 그렇게 된다면 Load Balance가 무너지게 된다.
Find
Cassandra에 대해서는 다음 글들에서 좀 더 자세히 다루겠지만, Master가 없는 시스템이라는 사실을 알고있는 사람들도 있을 것이다. 그렇기 때문에 어떠한 Node에 request가 오는지에 상관 없이 처리를 해줄 수 있어야 한다. 그렇기 때문에 각 노드는 다른 노드들의 위치 정보를 갖고 있어야 하는데, Chord에서는 Finger Table과 Successor를 이용해서 다른 노드들의 정보를 보관한다.
Succesor란 자신으로부터 바로 다음 시계방향에 있는 노드를 뜻한다.
Finger Table은 m(Id를 구성하는 Bit개수)개의 노드 ID정보들을 저장하고있다.
각 노드 ID들은 자신의 Id + 2 ^ i (i는 0부터 m -1까지)의 시계방향 노드의 정보를 담고있다.
Node 80의 Finger Table 예시.
모든 노드들의 Finger Table이 만들어졌다면 이제 어떠한 노드에서 시작하더라도 File을 찾을 수 있다.
찾는 알고리즘은 다음과 같다.
어떠한 노드 N이 있고 Key가 k인 파일을 찾고싶을때 자신의 Finger Table 정보중에서 k보단 작거나 같은 ID들 중에서 가장 큰 ID를 갖고있는 노드를 찾는다. 찾지 못 할 경우, Succesor에게 query를 넘긴다.
그림을 보며 다시 이해해 보자.
Node 80에 Key가 42인 파일을 찾아달라고 Request가 왔다고 하자.
- 노드 80은 자신의 Finger Table중 42보다 작으면서 제일 큰 Node 16에게 Request 를 넘겨준다
- 노드 16은 자신의 Finger Table중 42보다 작으면서 제일 큰 Node 32에게 Request를 넘겨준다.
- 노드 32는 자신의 Finger Table중 42보다 작은 Id를 갖고있는 노드의 정보가 없으므로 Succesor인 45에게 넘겨준다.
- 45가 파일을 가지고 있기때문에 끝
Finger Table을 구성하는 특성 때문에 매 Jump마다 거리가 반 좁혀지는 특성을 기대 할 수 있으므로, Search의 Time Complexity는 O(log(n))이라고 할 수 있다.
Fault Tolerance
결국 Chord도 Distributed system이기 때문에 Failure에 대해서 생각 해 보지 않을 수 없다. Fail에 대비하기 위해서 정보를 한 곳에만 저장하는게 아니라 Replication을 만들어 여러 노드에 저장하고 Successor의 개수를 여러개로 늘리는 방식을 가져간다. 자세한 사항은 이 글에서는 다루지 않겠다. 궁금하다면 이 노트에서 더 자세히 알아보기를 추천한다. https://courses.grainger.illinois.edu/cs425/fa2020/L7-8.FA20.pdf
실제 Production Cassandra는 Finger Table을 사용하지 않고 Partitioner를 사용하지만, Chord의 concept에 관한 글이므로 Finger Table을 사용 하였다.
