요새 golang으로 캐시서버를 만들고 있는 중입니다.
물론 golang 학습을 위해 구성하고 있기에, mini project 성격이 강합니다.
계획은 간단한 key-value 캐시서버를 만들고, 여러 대의 캐시서버를 두는 분산 캐시서버를 만드는 것입니다.
분산 캐시서버를 만들 때, 가장 중요한 부분 중 하나가 key값을 여러 대의 서버에 어떻게 분배할 것인가 하는 문제입니다.
보통 이런 경우, 해시함수를 이용하여, key값을 해싱한 후, 그 값을 서버대수로 나눈 나머지로 서버를 결정하는 방식을 많이 사용합니다.
하지만, 이런 방식은 서버가 추가되거나 제거될 때, 많은 key값들이 영향을 받게 됩니다.
예를 들어, 3대의 서버가 있을 때, key1이 서버 1에 매핑되었다고 합시다.
이 상황에서 서버가 하나 추가되어 4대가 되면, 기존 key1은 다른 서버에 매핑됩니다.
문제가 되는 이유는 cache miss가 많이 발생할 수 있다는 점입니다.
아니 사실상, 거의 모든 key값들이 다시 매핑될 수 있습니다.
cache서버에서 miss가 발생할수록, 실제 DB에 접근하는 횟수가 늘어나게 되고, 성능저하로 이어질 수 있습니다.
이를 해결하기 위해, consistent hash (일명 ring hash) 방식을 사용합니다.
이 방식은 서버가 추가되거나 제거되더라도, 영향을 받는 key값의 수를 최소화합니다.
이를 위해, 해시값의 범위를 원형으로 생각하고, 각 서버를 이 원형에 배치합니다.
key값도 해싱하여 원형에 배치하고, key값이 위치한 곳에서 시계방향으로 가장 가까운 서버를 선택합니다.
이렇게 하면, 서버가 추가되거나 제거되더라도, 영향을 받는 key값은 그 서버에 매핑된 key값들 뿐입니다.
CASE : 추가되는 경우
예를 들어, 3대의 서버가 있을 때, key1이 서버 1에 매핑되었다고 합시다.
그런데, 서버가 하나 추가되어 4대가 되면, key1이 여전히 서버1에 매핑됩니다.
이는, key1이 위치한 곳에서 시계방향으로 가장 가까운 서버가 여전히 서버 1이기 때문입니다.
따라서, 영향을 받는 key값은 서버 3과 서버 4 사이에 매핑된 key값들 뿐입니다.
CASE : 제거되는 경우
마찬가지로, 4대의 서버가 있을 때, key2가 서버 3에 매핑되었다고 합시다.
그런데, 서버 3이 제거되어 3대가 되면, key2는 서버 4에 매핑될 수도 있습니다.
하지만, 이 경우에도 영향을 받는 key값은 서버 3에 매핑된 key값들 뿐입니다.
따라서, consistent hash 방식을 사용하면, 서버의 추가나 제거에 따른 영향을 최소화할 수 있습니다.
이를 통해, cache miss를 줄이고, 시스템의 성능을 향상시킬수 있습니다.
하지만 consistent hash 방식도 완벽하지는 않습니다.
서버가 고르게 분포되지 않으면, 특정 서버에 부하가 집중될 수 있습니다.
이를 해결하기 위해, 각 서버에 여러 개의 가상 노드(replicas)를 할당하는 방식을 사용합니다.
가상 노드는 실제 서버를 대표하는 노드로, 해시링에 여러 번 배치됩니다.
이를 통해, 서버가 고르게 분포되도록 할 수 있습니다.
참고자료:
https://en.wikipedia.org/wiki/Consistent_hashing
https://www.baeldung.com/cs/consistent-hashing
구현은 golang으로 할 예정이지만, 설명하기 쉬운 python으로 작성해 보았습니다.
구현전 전체 설계도는 다음과 같습니다.
사용자 요청은 gateway로 들어오고, gateway는 key값을 consistent hash(ring hash)를 이용하여
적절한 캐시서버 주소를 반환합니다.
gateway는 해당 캐시서버에 key-value 저장/조회 요청을 전달합니다.
캐시서버는 key-value를 메모리에 저장하고, 조회 요청에 응답합니다.
메인함수부터 먼저 살펴보겠습니다.
if __name__ == "__main__":
cache_list = []
for i in range(3):
info= {
'ip' : f'192.168.0.{i+1}',
'cache' : SimpleCache()
}
cache_list.append(info)
ring_hash_mgr = RingHashManager()
ring_hash_mgr.init_node([cacheinfo["ip"] for cacheinfo in cache_list])
gateway = Gateway(RingHashMgr=ring_hash_mgr, cacheinfo=cache_list)
client = Client(cache=gateway)
client.run()
한 줄씩 살펴보면,
- 먼저, 3대의 캐시서버를 생성합니다. 각 캐시서버는 SimpleCache 인스턴스로 표현됩니다.
- 다음으로, RingHashManager 인스턴스를 생성하고, 캐시서버의 IP주소를 해시링에 추가합니다.
- 그다음으로, Gateway 인스턴스를 생성합니다. 이때, ring hash 매니저와 캐시서버 정보를 전달합니다.
- 마지막으로, Client 인스턴스를 생성하고, 게이트웨이를 캐시 인터페이스로 전달합니다.
클라이언트는 사용자로부터 명령어를 입력받아, 게이트웨이를 통해 캐시서버에 요청을 전달합니다.
필요한 클래스들을 하나씩 코드로 살펴보겠습니다.
우선 앞서 얘기한 ring hash 부분을 구현해 보겠습니다.
from zlib import crc32
class RingHashManager:
def __init__(self, replicas=3, backups=1, hashFunc=crc32):
self.hashFunc = hashFunc if hashFunc else crc32
self.replicas = replicas
self.backups = backups
self.ring = {} # key: hash, value: node
self.nodes = [] # sorted list of nodes
각 변수에 대한 설명은 다음과 같습니다.
- replicas: 각 서버당 생성할 가상 노드의 수입니다. 기본값은 3입니다.
- backups: key 조회 시 몇 개의 서버를 백업으로 조회할지 결정합니다. 기본값은 1입니다.
- hashFunc: 해시 함수입니다. 기본값은 crc32입니다.
- ring: 해시링을 나타내는 딕셔너너리입니다. key는 해시값, value는 서버 노드입니다.
- nodes: 정렬된 서버 노드의 리스트입니다.
다음으로, 서버 노드를 추가하는 메서드를 구현해 보겠습니다.
def add_node(self, node):
for i in range(self.replicas):
replica_key = f"{node}:{i}"
hash_value = self.hashFunc(replica_key.encode('utf-8'))
self.ring[hash_value] = node
self.nodes.append(hash_value)
self.nodes.sort()
print(f"Node {node} added.")
이 메서드는 주어진 서버 노드를 해시링에 추가합니다. 각 서버당 replicas 수만큼 가상 노드를 생성하여 해시링에 추가합니다.
nodes 리스트를 정렬하여, 나중에 key 조회 시 빠르게 찾을 수 있도록 합니다. 보통은 이진탐색을 사용합니다.
다음으로, 서버 노드를 제거하는 메서드를 구현해 보겠습니다.
def remove_node(self, node):
for i in range(self.replicas):
replica_key = f"{node}:{i}"
hash_value = self.hashFunc(replica_key.encode('utf-8'))
del self.ring[hash_value]
self.nodes.remove(hash_value)
self.nodes.sort()
print(f"Node {node} removed.")
이 메서드는 주어진 서버 노드를 해시링에서 제거합니다. 각 서버당 replicas 수만큼 생성된 가상 노드를 해시링에서 제거합니다.
다음으로, key값에 매핑된 서버 노드를 조회하는 메서드를 구현해 보겠습니다.
def get_node_index(self, key):
if not self.ring:
return None
hash_value = self.hashFunc(key.encode('utf-8'))
# value보다 크거나 같은 첫번째 노드의 인덱스를 찾음, 이진탐색 사용
low = 0
high = len(self.nodes) - 1
while low <= high:
mid = (low + high) // 2
if self.nodes[mid] >= hash_value:
high = mid - 1
else:
low = mid + 1
return low % len(self.nodes)
def get_node(self, key):
primary_index = self.get_node_index(key)
return self.ring[self.nodes[primary_index]]
이 메서드는 주어진 key값에 매핑된 서버 노드를 조회합니다.
key값을 해싱하여, 해시링에서 시계방향으로 가장 가까운 서버 노드를 찾습니다.
이를 위해 이진탐색을 사용하여, 효율적으로 서버 노드를 찾습니다.
여러 노드가 있을 땐 백업을 두고 싶을 수도 있습니다. 이를 위해, get_nodes 메서드를 구현해 보겠습니다.
def get_nodes(self, key): # return primary and backup nodes
primary_index = self.get_node_index(key)
result = []
seep_ips = set()
total_nodes = len(self.nodes)
for i in range(total_nodes):
index = (primary_index + i) % total_nodes
node_ip = self.ring[self.nodes[index]]
if node_ip not in seep_ips:
result.append(node_ip)
seep_ips.add(node_ip)
# 중복된 IP가 있을 경우, 백업 노드 수를 초과하지 않도록 함
if len(result) == (self.backups + 1) or len(result) == total_nodes: # +1 for primary
break
return result
이 메서드는 주어진 key값에 매핑된 서버 노드와 백업 노드들을 조회합니다.
이를 위해, primary 노드부터 시작하여 시계방향으로 순회하면서, 중복되지 않는 서버 노드를 result 리스트에 추가합니다.
중복된 IP가 있을 경우, 백업 노드 수를 초과하지 않도록 합니다.
전체 ring hash 매니저 클래스는 다음과 같습니다.
from zlib import crc32
class RingHashManager:
def __init__(self, replicas=3, backups=1, hashFunc=crc32):
self.hashFunc = hashFunc if hashFunc else crc32
self.replicas = replicas
self.backups = backups
self.ring = {} # key: hash, value: node
self.nodes = [] # sorted list of nodes
def init_node(self, nodes):
for node in nodes:
self.add_node(node)
def add_node(self, node):
for i in range(self.replicas):
replica_key = f"{node}:{i}"
hash_value = self.hashFunc(replica_key.encode('utf-8'))
self.ring[hash_value] = node
self.nodes.append(hash_value)
self.nodes.sort()
print(f"Node {node} added.")
def remove_node(self, node):
for i in range(self.replicas):
replica_key = f"{node}:{i}"
hash_value = self.hashFunc(replica_key.encode('utf-8'))
del self.ring[hash_value]
self.nodes.remove(hash_value)
self.nodes.sort()
print(f"Node {node} removed.")
def get_node_index(self, key):
if not self.ring:
return None
hash_value = self.hashFunc(key.encode('utf-8'))
# find the first node whose hash is >= hash_value
# use binary search for efficiency
low = 0
high = len(self.nodes) - 1
while low <= high:
mid = (low + high) // 2
if self.nodes[mid] >= hash_value:
high = mid - 1
else:
low = mid + 1
return low % len(self.nodes)
def get_node(self, key):
primary_index = self.get_node_index(key)
return self.ring[self.nodes[primary_index]]
def get_nodes(self, key): # return primary and backup nodes
primary_index = self.get_node_index(key)
result = []
seep_ips = set()
total_nodes = len(self.nodes)
for i in range(total_nodes):
index = (primary_index + i) % total_nodes
node_ip = self.ring[self.nodes[index]]
if node_ip not in seep_ips:
result.append(node_ip)
seep_ips.add(node_ip)
if len(result) == (self.backups + 1) or len(result) == total_nodes:
break
return result
캐시는 다음과 같이 간단하게 구현합니다.
from typing import Protocol
class CacheInterface(Protocol):
def get(self, key: str) -> str:
...
def set(self, key: str, value: str) -> None:
...
def delete(self, key: str) -> bool:
...
class SimpleCache:
def __init__(self):
self.store = {}
def get(self, key: str) -> str:
return self.store.get(key, None)
def set(self, key: str, value: str) -> None:
self.store[key] = value
def delete(self, key: str) -> bool:
if key in self.store:
del self.store[key]
return True
return False
게이트웨이는 다음과 같이 구현합니다.
ring hash 매니저를 사용하여, key값에 매핑된 캐시서버를 조회합니다.
조회된 캐시서버에 요청을 전달합니다.
class Gateway:
def __init__(self, RingHashMgr: RingHashManager, cacheinfo=None):
self.ringHashMgr = RingHashMgr
self.cacheinfo = cacheinfo
def get(self, key: str) -> str:
node_ip = self.ringHashMgr.get_node(key)
for cache in self.cacheinfo:
if cache["ip"] == node_ip:
node = cache["cache"]
break
value = node.get(key)
print(f"GET {key} - {value} from node {node_ip}")
return value
... (set, delete 메서드도 유사하게 구현)
클라이언트 역할을 하는 클래스도 구현해 줍니다.
class Client:
def __init__(self, cache=None):
self.cache = cache
def push_get(self, cmd):
key = cmd.split()[1]
if self.cache:
print(f"value: {self.cache.get(key)}")
def push_set(self, cmd):
key, value = cmd.split()[1], cmd.split()[2]
if self.cache:
self.cache.set(key, value)
def push_delete(self, cmd):
key = cmd.split()[1]
if self.cache:
self.cache.delete(key)
def run(self):
while True:
cmd = input("Enter command: ")
if cmd == "exit":
break
if cmd.startswith("GET") or cmd.startswith("get"):
self.push_get(cmd)
elif cmd.startswith("SET") or cmd.startswith("set"):
self.push_set(cmd)
elif cmd.startswith("DELETE") or cmd.startswith("delete"):
self.push_delete(cmd)
else:
pass
결과는 다음과 같습니다.
'text > Python' 카테고리의 다른 글
| python으로 간단한 In-Memory Key-Value DB 만들기 (1) | 2025.07.13 |
|---|---|
| 등수 반환 문제 고찰 (0) | 2023.10.20 |
| 심심해서 해본 글자 돌리기 (0) | 2023.02.20 |
| python 으로 구현하는 간단간단 검색엔진 로직 (1) | 2022.12.30 |
| 편집거리 알고리즘을 통한 검색어 자동완성 보정 (ft . Levenshtein Distance) (0) | 2022.11.26 |
댓글