[데이터베이스] 16. 분산 데이터베이스

Constant Hash

지금 공부하고 있는 데이터베이스는 하나의 컴퓨터에 모든 데이터를 저장하는 것을 가정하고 있다.

하지만 규모가 큰 서비스를 운영하다보면 매우 많은 데이터를 다루므로 하나의 컴퓨터에 저장할 수 없다.

따라서 규모가 큰 데이터는 결국 여러 컴퓨터에 쪼개서 저장할 수 밖에 없다.

 

 

 

데이터를 나누어서 저장한다면 우선 그림과 같이 같은 스키마를 갖는 테이블을 여러 개 만들어야 한다.

이때 어떤 데이터가 어떤 테이블에 저장될 지 결정하기 위해 각각의 테이블에 0번부터 i 번까지 인덱스를 매긴다.

그리고 데이터를 저장할 테이블을 결정할 때는 데이터의 PK를 해싱한 값으로 결정한다.

이때 해시 값은 0부터 i 사이의 값이 나올 것이다.

해시함수는 단순하게 고려한다면, PK 값이 숫자일 때 이 수를 (i+1) 로 나눈 나머지를 반환하는 함수를 사용할 수 있다.

그리고 특정 데이터를 조회한다면, 이 데이터의 PK 값을 해싱한 (위 예시에서는 i+1 로 나눈) 값을 가지고 테이블을 찾아서 조회한다.

 

 

 

 

이렇게 테이블을 나누어 운영을 하는 상황에서 갑자기 0번 테이블에 장애가 발생해서 사용할 수 없게 되었다고 해보자.

그러면 0번 데이터를 다시 1부터 i 번 테이블 안에 적절히 나누어서 담아야 한다.

이때도 해싱을 사용하여 데이터를 옮길 수 있다.

 

 

 

 

제일 간단한 방법은 0번 테이블을 포기하고 나머지 i-1 개 테이블에 대해 다시 0부터 i-1 까지 번호를 매기는 것이다.

그러면 모든 데이터에 대해 다시 해시함수를 사용하여 저장될 테이블을 결정하고 위치를 재조정 해주어야 한다.

애초에 분산 데이터베이스를 사용한다는 것 자체가 데이터가 너무 많기 때문이었는데, 이렇게 하나에 장애가 발생할 때마다 수많은 데이터의 위치를 매번 재조정해야 한다면 리소스가 많이 들 것이다.

 

또한 장애가 발생할 때마다, 특정 데이터를 찾기 위한 기준과 해시함수가 계속 바뀌므로, 데이터베이스를 사용하는 입장에서도 매우 불편하다. (즉, 데이터 조회의 기준이 일관되지 않는다.)

 

그래서 이런 문제를 해결하고자, 장애가 발생해도 데이터베이스를 일관되게 사용할 수 있는 방법을 고안하였다.

그것이 바로 consistent hash 이다. consistent hash 는 hash ring 이라는 개념을 사용한다.

 

 

 

 

우선 그림과 같이 어떤 데이터의 PK 값을 해싱했을 때 나오는 범위가 0 ~ i 라고 해보자.

그리고 데이터를 저장하는 서버의 개수가 3개가 있다고 하면, 0부터 i 라는 범위를 3개로 쪼개 각각의 서버가 담당하도록 만든다.

서버가 담당하는 영역의 기준 역시 해싱을 통해 결정한다.

그리고 각 서버가 담당하는 역할은 자신의 해시값에서부터 시계 반대방향으로 돌면서 그 영역의 해시값에 대해서 자신이 관리하는 것이다.

 

예를 들어 그 서버의 IP 주소와 같은 값을 해싱했다고 해보자. 첫번째 서버의 해시 결과가 2, 두번째 서버의 해시 결과가 19, 세번째 해시 결과가 i 라면 0부터 2까지는 파란색 노드(서버)가 담당하고, 3 ~ 19 는 빨간색 노드, 20 ~ i 까지는 보라색 노드가 담당하도록 설정할 수 있다. (만약 서버가 1개라면 1개의 서버가 0 ~ i 범위를 모두 커버할 것이다.)

 

분산 데이터베이스 상황에서는 노드(서버)는 상황에 따라 사라질 수도 있고, 추가될 수도 있다.

만약 장애가 나서 노드가 사라진 상황을 생각해보자.

만약 2번 노드가 장애로 인해 사라지면 어떻게 변할까?

그러면 기존의 정의대로, 빈 영역은 시계 반대방향을 따라 돌면서 인접 노드가 해당 영역을 커버한다.

 

 

 

그러면 위 그림과 같이 Node 3 이 Node 2 가 커버하던 영역을 함께 커버하게 되고, Node2 에 저장된 데이터만 Node3 에 옮길 수 있다면  데이터에 접근하는 사용자는 같은 해시값을 사용하여 접근해도 분산 DBMS 가 알아서 해당 해시값을 커버하는 Node 로 요청을 전달하여 쿼리를 처리할 것이다. (이렇게 Node 정보를 찾아주는 서비스를 directory service, DS 라고 한다.)

갑작스러운 장애가 나서 Node 2 에 접근할 수 없는 상황이라면 Node 2 데이터를 Node3 에 옮기지 못한 것아니냐는 생각이 들 수 있다.

물론 이런 장애를 예방하려면 당연히 데이터를 다른 곳에 복사해서 저장해놓는 백업 정책도 필요하다.

 

 

DHT

지금은 간단하게 표현해서 3개의 노드만 표현했지만, 실제로는 이런 노드가 수천개가 존재한다.

그러면 수많은 사용자가 DS 에게 Node의 위치를 물어보기 위해 접근하면 DS 역시 버거워 할 것이고,

이 DS가 죽으면 전체 서비스가 죽는, Single Failure (중단점) 문제가 발생할 수 있다.

그래서 등장한 것이 Distribute Hash Table (DHT) 이며, 이를 충실하게 구현한 데이터베이스가 바로 카산드라이다.

 

DHT의 동장원리는 다음과 같다.

우선 위 그림에서는 데이터의 해시값과 그 데이터를 저장하고 있는 서버의 해시값을 함께 그렸기 때문에 헷갈린다.

그래서 아래와 같이 다시 표현해보겠다.

 

 

 

빨간색 동그라미가 서버이고, 각 서버는 IP 주소같은 대표값을 해싱한 값을 갖는다.

각 컴퓨터는 데이터를 해싱한 값의 범위가 자신의 값 이하인 것을 담당한다.

(이거는 구현하기 따라 다른 것 같다. 다른 블로그 글에서는 자신 이상의 값을 포함한다고 하기도 한다.)

 

예를 들어서 해시값이 36인 호스트에게 해시값이 15인 데이터를 찾아달라는 요청이 들어왔다고 해보자.

그러면 36인 호스트는 자신이 커버하는 범위에 15가 없으므로 시계방향으로 인접한 노드에게 15가 있는지 물어본다.

(각 호스트는 시계방향으로 인접한 호스트의 주소를 알고 있다.)

 

하지만 인접한 호스트도 15를 관리하지 않으므로 역시 인접한 노드에게 물어보고, 결국 19번 호스트에게 가서야 위치를 알게 된다.

즉, 결국엔 모든 호스트에게 다 질의를 해봐야 찾을 수 있는 것이다.

그래서 이때 사용하는 것이 finger table (라우팅 테이블) 이다.

 

핑거 테이블은 각 노드가 갖고 있는 테이블로서, 자신의 해시값에 2^i 을 더한 데이터를 포함하는 가장 가까운 호스트의 번호값이 저장된 테이블이다.

 

예를 들어 현재 노드 값이 80 이라면, 80 + 1, 80 + 2, 80 + 4, ...., 각각에 대해 어떤 번호의 노드로 가야 이와 관련된 값이 있는지 저장해두고, 예를 들어 83 이라는 값의 조회를 요청한다면, 우선 83은 자신이 담당하는 번호가 아니므로 핑거 테이블에서 이 값보다 큰 값 중 제일 작은 84번 정보를 보고 해당 노드에 질의를 보내는 것이다.

 

그래서 이 핑거 테이블 역시 전 지구적인 서비스라면 수천개의 노드가 있을 텐데, 그 노드 정보를 다 갖고 있는 중앙화된 요소를 두지 말고, 각각의 노드가 협력해서 데이터를 찾자는 방향에서 등장한 개념이다.

또한 이 개념이 바로 NoSQL의 근간이 되는 개념이다.

 

 

참고자료

https://binux.tistory.com/119

 

https://ddongwon.tistory.com/76

 

 

https://medium.com/@heonjang.lee96/distributed-hash-table-chord%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC-dd950afc9b3d