databute / databute

[D2 CAMPUS FEST mini 최우수상 수상작] Distributed In-memory Key-value Store

Databuter

Databuter는 제 7회 D2 CAMPUS FEST mini의 최우수상 수상작입니다.

Databuter는 분산 인 메모리 키 - 값 스토어 Databute의 서버 구현체입니다.

Databuter의 목표는 메모리에 키 - 값 엔트리를 저장하여, 기존의 데이터베이스 시스템 보다 더 빨리 엔트리를 조회할 수 있도록 하는 것입니다. 또한, 하나 이상의 Databuter 노드가 클러스터를 형성한 뒤 엔트리를 분산시켜 저장하여 용량 및 처리량을 확장하거나, 축소할 수 있도록 하는 것입니다.

사용자는 엔트리를 조회 (GET), 저장 (SET, UPDATE) 및 삭제 (DELETE) 하거나 유효 기간을 설정 (EXPIRE) 할 수 있습니다. 엔트리는 숫자 (Integer, Long), 문자열 (String), 리스트 (List), 셋 (Set) 및 딕셔너리 (Map) 타입을 지원합니다.

엔트리들은 버킷이라 하는 논리적 엔트리 블록에 저장됩니다. Databuter에는 다수의 논리적 버킷이 존재하며, 키를 총 버킷 수에 대해 일관적 해싱을 취한 값과 같은 인자를 가지는 버킷에 엔트리를 저장합니다.

버킷들은 Databuter 클러스터의 노드들이 유지합니다. 한 버킷은 서로 다른 두 노드가 똑같이 유지하고 있어 한 노드에 장애가 발생하더라도 즉시 극복할 수 있습니다.

사용법

gradlew jar
java -jar build/libs/databuter-{version}.jar

라이센스

MIT License

Copyright (c) 2019 - 2021 databute

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

databute's Issues

ShutdownHook 등록

시스템을 시작할 때 ShutdownHook를 등록하여 시스템이 종료될 때 관련된 리소스를 정리할 수 있어야 한다.

Active Bucket이 삭제 되었을 경우, Standby Bucket을 승격.

Active Bucket이 삭제 되었을 경우, Standby Bucket을 승격시켜주어야 한다.

추상화된 네트워크 모듈 설계

네트워크 모듈로 사용하는 Netty 라이브러리를 추상화하여 본 프로젝트에 맞는 구조로 설계.

본 프로젝트에서는 외부 사용자와 통신을 위한 서버와, 내부 노드 간 통신을 위한 서버, 다른 노드에 접속하기 위한 클라이언트 모듈이 필요하다. 따라서, 이들을 추상화하여 최소한의 코드로 작성할 수 있어야 한다.

버킷 타입을 액티브 버킷과 스탠바이 버킷으로 변경

현재 버킷 타입은 마스터 버킷과 백업 버킷으로 되어있는데 이 보다 일반적으로 많이 쓰이는 단어인 액티브, 스탠바이로 변경한다.

버킷 notification message에 factor를 남겨야 함.

버킷 notification message에 factor를 남겨야 함.

Session 클래스에 메시지 전송을 위한 메서드 추가

현재 Session 클래스의 channel().writeAndFlust() 메서드, 혹은 ctx.writeAndFlust() 메서드로 메시지를 전송하고 있다.
이를 Object 클래스가 아닌 Message 클래스만 파라미터로 받는 메서드를 추가하여 사용할 수 있도록 해야한다.

Shared Bucket Factor 생성.

ActiveBucket의 개수를 세어주는 Shared Bucket Factor가 필요.
/databuter/bucketFactor 에 SharedCount로 생성해야함.

Bucket에 Node가 연결되어있지 않은 경우 Bucket을 삭제시켜주어야 함.

Bucket에 Node가 연결되어있지 않은 경우

• Factor를 재배치하고,
• zookeeper에서 Bucket을 삭제시켜주어야 함.

Cluster와 ClusterCoordinator 병합

Cluster와 ClusterCoordinator가 거의 같은 일을 수행하지만 따른 객체로 되어있어 한 객체로 병합해야 한다.

클러스터 노드들을 관리하는 별도의 모듈 필요

클러스터 노드들을 Cluster 모듈에서 관리하지 않고 별도의 모듈에서 관리하도록 하여 Cluster 모듈에 너무 많은 책임이 주어지지 않도록 해야 한다.

ZooKeeper를 버킷 관리에 사용하기 위해 클러스터 모듈 밖으로 이동

현재 Curator Framework를 ClusterCoordinator 안에서 생성하고 있으나, ZooKeeper의 버킷 관리 등에도 사용하기 위해 별도의 모듈로 이동한 후 생성자를 통해 주입받도록 수정해야 한다.

ZooKeeper 기반 노드 디스커버리 구현

자동으로 분산 환경을 구성하기 위한 ZooKeeper 기반 노드 디스커버리 구현.

프로그램이 시작하면, 먼저 ZooKeeper에 등록된 기존 노드 정보를 동기화한다.
기존 노드 정보 동기화가 끝난 뒤, 자신의 정보를 ZooKeeper에 등록하여 다른 노드들이 자신과 동기화할 수 있도록 한다.

클러스터가 연결 해제된 경우 Standbybucket 제거

클러스터가 연결 해제된 경우,
각 클러스터들은 각자 관리하는 bucket 중
standbybucket이 연결 해제된 해당 클러스터인 bucket의 standby 정보를 제거 해주어야 한다.

ZooKeeper 연산 비동기로 변경.

현재 동기식으로 사용중인 ZooKeeper 연산 비동기로 변경.

버킷 그룹 통일.

localBucketGroup과 remoteBucketGroup으로 나뉜 버킷 그룹을 통일해주어야 함.
하나의 BucketGroup 내에서 관리할 수 있도록 수정.

클라이언트 세션과 연결이 끊어지면 클라이언트 세션 그룹에서 해당 세션 제거

클라이언트 세션과 연결이 끊어지면 해당 세션을 완전히 제거해야 이미 닫힌 채널에 패킷을 보내는 일이 발생하지 않는다.

버킷 추상화

버킷은 마스터 버킷과 백업 버킷으로 나뉜다.
이 두 버킷을 추상화하여 해당 버킷의 타입이 무엇인지 모르더라도 같은 동작을 수행할 수 있어야 한다.

버킷 리팩토링

버킷 관련된 클래스들을 리팩토링 한다.

버킷에 Factor 할당

각 버킷은 Key값에 modular 연산을 취할 Factor 값을 갖고있어야 한다.

버킷 정보 모니터링을 등록한 클라이언트 유지

클라이언트가 버킷 정보 모니터링 요청을 보내면, 시스템에 해당 클라이언트들을 등록한다.
이슈 #54 에서 클러스터의 모든 노드가 모든 클라이언트에 버킷 변경 정보를 전송하면 플러딩 문제가 발생하므로 버킷 정보 모니터링을 등록한 클라이언트에만 전송할 수 있도록 해당 클라이언트들을 유지해야 한다.

클러스터 노드 세션과 연결이 끊어지면 클러스터 노드 세션 그룹에서 해당 세션 제거

클러스터 노드 세션과 연결이 끊어지면 해당 세션을 완전히 제거해야 이미 닫힌 채널에 패킷을 보내는 일이 발생하지 않는다.

버킷에 할당된 노드 정보를 nodeId로 변경

현재 clusterId로 사용 중이나 이는 의미 상 올바르지 않으며, nodeId로 변경하는 것이 더 낫다.

다른 노드와 handshake 프로토콜 구현

다른 노드와 아웃바운드 채널이 연결된 후 정보 교환을 위한 handshake 프로토콜 구현.

아웃바운드 채널이 연결된 후 정보 교환을 위해 handshake 메시지를 전송한다. handshake 요청을 받은 노드는 자신의 노드 아이디 정보를 응답한다. 응답을 받은 노드는 알맞은 노드인지 확인한 뒤, 올바른 노드가 확인되면 클러스터 그룹에 해당 노드를 등록한다.

클라이언트와 기본적인 프로토콜 구현

클라이언트의 데이터 조작 요청을 처리하기 위한 기본적인 프로토콜을 구현해야 한다.

기본 프로토콜은 다음과 같다.

• get: 키에 해당하는 값을 리턴한다. 키가 없는 경우 NOT_FOUND 코드를 리턴한다.
• set: 키에 해당하는 값을 설정한다.
• update: 키에 해당하는 값을 변경한다. 키가 없는 경우 NOT_FOUND 코드를 리턴한다.
• delete: 키에 해당하는 값을 제거한다. 키가 없는 경우 NOT_FOUND 코드를 리턴한다.

백업이 설정되어있지 않은 버킷에 자동으로 백업 설정

프로그램을 시작할 때 조회하는 버킷 목록에서 백업이 설정되어있지 않는 버킷을 발견할 경우 그 버킷의 백업으로 동작하도록 한다.

더 이상 백업이 필요한 버킷이 없을 경우 새 버킷을 생성한다.

ZooKeeper의 버킷 정보 모니터링

클러스터의 모든 노드는 네임 서버의 역할을 수행하기 때문에 버킷에 대한 같은 정보를 유지해야 한다.
따라서 각 노드는 ZooKeeper의 버킷 디렉토리를 모니터링하여 버킷 정보의 변화를 감지하고 업데이트해야 한다.

최대 버킷 수 만큼 버킷 관리

최대 버킷 수 (availableBucketCount)는 시스템의 전체 메모리 크기에서 시스템이 사용할 메모리 크기 (guardMemorySize)를 제외한 후 버킷 메모리 크기 (bucketMemorySize)로 나눈 값 이다. 메모리 크기의 단위는 항상 메가바이트이다.

시스템이 시작하면, ZooKeeper에 등록된 버킷의 정보를 받아와서 백업이 설정되어있지 않는 버킷에 먼저 백업 버킷으로 설정한다. 이 때 버킷의 수가 최대 버킷 수 보다 작아야 한다.
더 이상 백업이 필요한 버킷이 없으면서, 최대 버킷 수 보다 적은 수의 버킷이 생성되어 아직 여유가 있는 상황이라면, 그 수의 차이 만큼 마스터 버킷을 생성한다.

클라이언트 통신을 위한 서버 모듈 구현

클라이언트와 통신할 수 있는 서버 모듈 구현이 필요하다.

ZooKeeper에 데이터를 변경 해야할 경우 Lock을 걸어주어야 함.

ZooKeeper에 데이터를 변경 해야할 경우 Lock을 걸어주어야 함.

메시지 핸들러가 channelRead0를 직접 override 하지 않도록 수정

현재 메시지 핸들러는 SimpleChannelInboundHandler를 추상화 해서 사용 중이다.
메시지 핸들러가 실행되는 channelRead0 메서드를 직접 override 하지 않는게 좋을 듯 보이는데, ChannelHandlerContext ctx에 직접 접근할 수 없도록 하는 것이 좋아보이기 때문이다.
따라서 메시지 객체만 파라미터로 가지는 중간 인터페이스가 필요하다.

추상화된 클러스터 모듈 구현

클러스터를 구성하기 위한 추상화된 모듈 구현.

현재 클러스터를 구성하기 위한 코디네이터로 ZooKeeper를 사용하고 있으나, 다른 코디네이터를 적용할 수 있도록 클러스터 기능을 추상화하는 모듈 구현이 필요하다.

주기적인 heartbeat 메시지 전송

각 노드는 다른 노드의 가용 상태를 확인하기 위한 주기적인 heartbeat 메시지 전송 구현.

클러스터 그룹에 등록된 노드들에게 주기적 (기본값 2초)으로 heartbeat 메시지를 전송한다.
만약 일정 시간 이상 (기본 값 8초) heartbeat 메시지가 수신되지 않는다면 해당 노드에 문제가 생긴 것이라 판단하고 요청을 보내지 않는다.

logback 설정

클러스터에 속한 노드와 양방향 연결

클러스터에 속한 노드와 통신하기 위한 양방향 채널 연결 구현.

각 노드는 다른 노드와 통신을 위해 양방향 채널을 연결한다.
아웃바운드 채널은 다른 노드에 요청하기 위해, 인바운드 채널은 다른 노드의 요청에 응답하기 위해 사용한다.

ZooKeeper 기반 클러스터 모듈 설계

ZooKeeper 기반 클러스터링 자동화를 위한 모듈 설계.

클라이언트의 클러스터 정보 요청에 대한 응답 구현

클라이언트가 처음 시스템에 접속하면 클러스터에 속한 다른 노드들의 정보와, 버킷의 정보를 요청할 것이다.
따라서, 이 요청에 대해 올바른 응답을 구현해야 한다.

버킷이 추가될 때 스탠바이 버킷으로 설정

현재 ZooKeeper에 등록된 버킷에 대해서만 스탠바이 버킷으로 설정하고 그 뒤에 추가되는 버킷들에 대해서는 설정하지 않는다.
좀 더 일반적으로 동작하는 상황을 만들기 위해서는 버킷이 추가될 때 스탠바이 버킷으로 설정하는 것이 낫다.

프로그램 시작할 때 버킷 생성

프로그램을 시작할 때 버킷을 생성해야 한다.

버킷은 다음 용도로 사용될 수 있다.

• 노드의 데이터를 저장할 수 있는 마스터 버킷
• 다른 노드의 데이터를 백업할 수 있는 백업 버킷

각 노드가 마스터 버킷을 생성하면, ZooKeeper에 등록하여 다른 노드들과 공유할 수 있도록 해야 한다.

클러스터가 변경될 때 마다 리스닝 클라이언트들에게 변경 정보 전송

새로운 클러스터 노드가 추가되거나, 삭제되는 등 클러스터 정보가 변경될 때 마다 연결된 모든 리스닝 클라이언트들에게 변경 정보를 전송하여 클라이언트가 즉각적으로 업데이트 하도록 한다.

ClusterNode 객체에서 노드와 관련된 동작 수행

지금은 ClusterNode 객체가 해당 노드의 정보만 유지하고 있으나, 해당 노드와 관련된 동작 (연결, 연결 해제 등)들을 수행할 수 있도록 확장.

버킷 코디네이터 리팩토링

버킷 코디네이터 리팩토링

handshake 패키지 정리

handshake 패키지 내부에 HandshakeRequestMessage 관련 클래스와 HandshakeResponseMessage 관련 클래스가 같이 있는 상황이다.
이를 handshake 패키지 내부에 request 패키지, response 패키지를 만들어, 올바르게 리팩토링 해야 한다.

원격 노드와 연결이 끊어지면 원격 노드 그룹에서 해당 노드 제거

원격 노드와 연결이 끊어지면 해당 노드가 종료되었거나, 문제가 생겨 올바르게 처리할 수 없는 상태이므로 원격 노드 그룹에서 해당 노드를 제거한다.

Session 클래스에 연결 해제를 위한 메서드 추가

현재 ctx.close() 메서드로 연결을 해제하고 있다.

클러스터 세션 연결이 해제될 때 클러스터 노드 정보 제거, 버킷 제거 등 수행해야 할 작업이 많다. 연결이 해제되어야 할 지점은 많을 것으로 예상되므로, 연결 해제를 위한 메서드를 추가하고, 그 메서드를 사용할 수 있어야 한다.

HANDSHAKE 메시지 코드 분리

HANDSHAKE 메시지 코드가 요청 및 응답 모두에 사용되고 서로 다른 핸들러를 등록하는 식으로 구분되어 있다.
이러한 방법은 명시적이지 않고, 오해의 여지가 있을 수 있으므로 HANDSHAKE 메시지 코드를 HANDSHAKE_REQUEST 및 HANDSHAKE_RESPONSE 로 분리해야 한다.

버킷 factor가 업데이트된 후 버킷을 저장하지 못하면 빈 factor가 발생함

새로운 액티브 버킷을 생성할 때 버킷 factor를 업데이트 할 때 ZooKeeper에 바로 반영되기 때문에 그 후 버킷을 저장하지 못할 경우 빈 factor가 발생함.
이를 해결하기 위해서, 액티브 버킷을 저장할 때에는 버킷 전체에 lock을 걸어, 한 노드만 버킷을 생성하고, 만약 실패했다면 factor 카운터를 초기화해야 한다.

버킷 제거 이벤트 반영

버킷이 제거되었을 때 그 이벤트를 받아서 해당 노드의 버킷 그룹에 버킷을 삭제해야 한다.

외부 설정 파일에서 설정 정보 로드

외부 설정 파일에서 설정 정보를 읽어 프로그램을 시작할 수 있도록 구현.

설정 파일은 yaml 형식 문서로 작성하며, 시스템 속성을 통해 설정 파일의 경로를 지정할 수 있어야한다.
Jackson 라이브러리를 활용하여 설정 파일을 객체와 매핑한다.

클러스터 간 통신 프로토콜 스택 구현

클러스터 간 통신 프로토콜 스택을 구현한다.

통신 프로토콜은 다음과 같이 구성된다.

• 패킷 길이 4 바이트
• 메시지 코드 1 바이트
• 메시지 내용

버킷이 변경될 때 마다 리스닝 클라이언트들에게 변경 정보 전송

새로운 마스터 버킷이 추가되거나, 마스터 버킷에 백업 버킷이 등록되는 등 버킷의 정보가 변경될 때 마다 연결된 모든 리스닝 클라이언트들에게 변경 정보를 전송하여 클라이언트가 즉각적으로 업데이트 할 수 있어야 한다.

클러스터의 각 노드들은 ZooKeeper의 버킷 디렉토리를 모니터링 하고 있으므로, 독립적으로 버킷 변경을 감지할 수 있다.