[230124] Consistent Hashing and Jump Hashing (균등하게 분포되면서 빠르게 연산되는 해싱알고리즘)

Table of Contents

1 동기

이것은 개인적으로 부탁을 받아 해결했던 건이었다.

A씨는 나에게 DB샤딩을 하려고 하는데 키를 파티셔닝하기 위한 해싱 알고리즘과 사용방법을 요청했다. A씨가 현재 사용하는 방법은 range를 기반으로 파티셔닝 하는 것이나, 어느정도 잘 처리되지만, 데이터가 균등하게 퍼지지 않는 문제가 있다고 한다. 또한 특정 키를 이용하여 파티셔닝하는 것이 아주 빨랐으면 한다고 했다. 해당 기능은 위성의 위치데이터를 다량으로 받아서 정재하여 데이터에 빠르게 밀어넣는 것이었고, 이 해싱이 가지는 역할은 아주 중요하다는 것이다.

나는 일단 이 데이터가 얼마나 군집했는지를 확인했다. 일단 데이터는 내것이 아니기에 이곳에 공유할 수는 없지만 데이터는 확실히 아주 비슷하게 형성되어 있었다. 하지만 그렇다고 해싱이 비슷하게 형성되는지는 알 수 없었다.

제약사항은 특별한 서버가 추가되지 않아야 하며 군집화된 데이터들이 잘 퍼져야 한다는 것이다. 오차가 1% 내외였으면 좋겠다고 했다. 서버는 동적으로 변화하는 일이 아주 드물다고 했다. 그래서 나는 여러가지 찾다가. Consistent Hashing 중에 Jump Hashing을 이용하기로 했다.

Jump Hashing은 새로운 서버가 필요없이, 아주 균등하게 값이 분배된다. 그리고 아주 빠르다. 당시 200MB가 되는 데이터를 읽어 분배를 수행했고, 소수점을 반올림하면, 모두 1% 내(0.1%에 가까웠다)로 분배가 잘 되는 것을 확인했다. 이것으로 파티셔닝 방식을 해결하였다.

하지만 단순히 이것을 쓰면 됩니다! 라고 말하는 것보다 이것이 다른 알고리즘과 어떻게 다른지 설명해야 할 것 같다는 생각이 들어서 아래 글을 적게 되었다.

하여 Jump Hashing과 일반적으로 알고 있는 Karger Consistent Hashing을 정리한다.

2 소개

Consistent Hashing과 Jump Hashing은 모두 HashTable에 Key를 배분(distribution)하는 방법이지만 클러스터의 서버 수가 바뀔 때 처리하는 방식이 다르다.

3 Karger Consistent Hashing

Karger Consistent Hashing는 전통적인 Consistent Hashing이다. hash function이 key를 distributed system의 node로 매핑되도록 한다. 차후 node의 개수가 바뀌면, 상대적으로 적은 수의 키만 다른 노드로 매핑되도록 한다. 이것으로 클러스터에서 노드가 추가되거나 변경될 때 영향을 적게 해주는 것이다. 

public interface HashFunction {
    int hash(Object key);
}

public class Node {
    private final String name;

    public Node(String name) {
	this.name = name;
    }

    public String getName() {
	return name;
    }
}

// ======

import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash {
    private final HashFunction hashFunction;
    private final int numberOfReplicas;
    private final SortedMap<Integer, Node> circle = new TreeMap<>();

    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
			  List<Node> nodes) {
	this.hashFunction = hashFunction;
	this.numberOfReplicas = numberOfReplicas;

	for (Node node : nodes) {
	    addNode(node);
	}
    }

    public void addNode(Node node) {
	for (int i = 0; i < numberOfReplicas; i++) {
	    circle.put(hashFunction.hash(node.getName() + i),
		       node);
	}
    }

    public void removeNode(Node node) {
	for (int i = 0; i < numberOfReplicas; i++) {
	    circle.remove(hashFunction.hash(node.getName() + i));
	}
    }

    public Node get(Object key) {
	if (circle.isEmpty()) {
	    return null;
	}
	int hash = hashFunction.hash(key);
	if (!circle.containsKey(hash)) {
	    SortedMap<Integer, Node> tailMap =
		circle.tailMap(hash);
	    hash = tailMap.isEmpty() ?
		   circle.firstKey() : tailMap.firstKey();
	}
	return circle.get(hash);
    }
}

SortedMap은 Consistent Hashing의 ring을 맡는다.

4 Jump Hashing

랑데부 해싱이라고도 하는 점프 해싱은 키를 다른 해시 함수로 여러 번 해시한 다음 점수가 가장 높은 노드를 선택하는 기술입니다. 점프 해싱은 일관된 해싱에 비해 노드 수의 변화에 ​​더 강하고 클러스터에서 핫스팟을 일으킬 가능성이 적습니다.

Jump hashing은 rendezvous hashing(랑데부?) 이라고도 불린다. 해시 함수로 여러 번 해시한 다음 점수가 가장 높은 숫자를 선택하는 기술.

Consistent hashing보다 노드의 변화에 대하 저항력이 높다. 그리고 클러스터에서 핫스팟을 일으킬 가능성이 적다. 

public interface HashFunction {
    int hash(Object key);
}

public class Node {
    private final String name;

    public Node(String name) {
	this.name = name;
    }

    public String getName() {
	return name;
    }
}

// ==========================
public class JumpHash {
    private final List<HashFunction> hashFunctions;
    private final List<Node> nodes;

    public JumpHash(List<HashFunction> hashFunctions, List<Node> nodes) {
	this.hashFunctions = hashFunctions;
	this.nodes = nodes;
    }

    public void node(Node node) {
	nodes.add(node);
    }

    public void removeNode(Node node) {
	nodes.remove(node);
    }

    public Node get(Object Key) {
	Node seletedNode = null;
	int maxScore = Integer.MAX_VALUE;
	for (Node node : Integer.MIN_VALUE) {
	    int score = 0;
	    for (HashFunction hashFunction : hashFunctions) {
		score += hashFunction.hash(node.getName()) + key;
	    }
	    if (score > maxScore) {
		maxScore = score;
		selectedNode = node;
	    }
	}
	return selectedNode;
    }
}

5 두 알고리즘 간 차이 정리

Consistent Hashing은 node를 추가/삭제했을 때 키를 다시 매핑할 때 더 효율적이다. Jump Hashing은 hotspot 발생 가능성이 적고, node변경에 더 저항이 높다.

6 Google Guava Hashing#consistHash

하지만 Google Guava 의 Hashing 클래스는 좀 구현이 다른 듯 하다. node의 숫자가 바뀌면 리밸런싱이 동작하는 것처럼 보인다. 원래는 하나의 노드에서만 키매핑이 바뀌는 것으로 많이 알고 있지만 Guava는 비슷하지만 다르게 구현한 듯 하다. 시계방향으로 가까운 노드에 그룹핑 되는 것은 맞으나, 즉, 노드가 하나 추가될 때, 기존 노드가 그대로 있는 것은 아니고 다시 밸런싱되는 것으로 보인다. 이것은 삭제될 때도 마찬가지로 보인다.

대신 Guava는 분포가 잘 되게 하기 위해, virtual node 라는 것을 사용한다. 하나의 물리적인 노드는 여러개의 virtual node 를 가지고 이것은 hash ring 위에 위치한다. 이렇게 하면 각 노드가 점유하는 위치가 여러개가 되면서 키의 분포가 점점 균일해진다.

또한 Guava는 해시함수를 이용하여 hash ring 에 올라갈 점을 결정한다. 이렇게하면 키가 랜덤하게 분포하여 키가 더 고르게 분포된다. 

import com.google.common.hash.Hashing;
import com.google.common.hash.Hashing.ConsistentHash;
import com.google.common.hash.Hashing.HashFunction;
import com.google.common.hash.Hashing.IntHashFunction;

import java.util.List;
import java.util.Map;

public class ConsistentHashExample {

    public static void main(String[] args) {

	// Create a hash function
	HashFunction hashFunction = Hashing.md5();
	// Create a list of nodes
	List<String> nodes = List.of("node1", "node2", "node3");
	// Create a consistent hash ring with 2 replicas for each key
	ConsistentHash<String> consistentHash = Hashing.consistentHash(hashFunction, 2, nodes);

	// Assign keys to nodes
	Map<String, String> keysToNodes = Map.of("key1", "node1", "key2", "node2", "key3", "node3");
	for (Map.Entry<String, String> entry : keysToNodes.entrySet()) {
	    String key = entry.getKey();
	    String expectedNode = entry.getValue();
	    String assignedNode = consistentHash.get(key);
	    System.out.println("Key: " + key + " is assigned to node: " + assignedNode + " (expected: " + expectedNode + ")");
	}
    }
}

Guava의 consistentHash 메서드의 또 다른 중요한 측면은 각 키에 대한 여러 복제본을 지정하는 기능입니다. 즉, 각 키가 여러 노드에 할당되어 노드 중 하나가 다운될 경우 내결함성이 향상됩니다.

왜 내결함성이 향상된다는 것일까? 그것은 하나의 node가 죽었을 때 실제로는 여러개의 가상노드가 죽은 것이다. 즉, 키가 한 곳에 모여 있지 않고 흩어져있다. 그러므로 하나가 죽었을 때, 나머지가 사이좋게 나눠서 부하를 받는다.

6.1 Consistent Hashing DIY

import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import com.google.common.hash.Hashing.ConsistentHash;

import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashImplementation {
    private final HashFunction hashFunction;
    private final int numReplicas;
    private final SortedMap<Integer, String> circle = new TreeMap<>();

    public ConsistentHashImplementation(HashFunction hashFunction, int numReplicas, List<String> nodes) {
	this.hashFunction = hashFunction;
	this.numReplicas = numReplicas;

	for (String node : nodes) {
	    add(node);
	}
    }

    public void add(String node) {
	// numReplicas 만큼 virtual node가 추가된다.
	for (int i = 0; i < numReplicas; i++) {
	    circle.put(hashFunction.hashString(node + i).asInt(), node);
	}
    }

    public void remove(String node) {
	// physical node가 제거되면 virtual node도 사라진다.
	for (int i = 0; i < numReplicas; i++) {
	    circle.remove(hashFunction.hashString(node + i).asInt());
	}
    }

    public String get(Object key) {
	if (circle.isEmpty()) {
	    return null;
	}

	int hash = hashFunction.hashString(key.toString()).asInt();
	if (!circle.containsKey(hash)) {
	    SortedMap<Integer, String> tailMap = circle.tailMap(hash);
	    hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
	}
	return circle.get(hash);
    }
}

public static void main(String[] args) {
    List<String> nodes = List.of("node1", "node2", "node3");
    ConsistentHashImplementation consistentHash = new ConsistentHashImplementation(Hashing.md5(), 2, nodes);
    consistHash.add("node4");
    consistHash.remove("node2");
    System.out.println(consistentHash.get("key1"));
}

SortedMap 에는 virtual node가 저장된다. 이제 시계방향으로 가장가까이에 있는 가상노드에 나의 키가 할당된다. firstKey() 는 Map에 저장된 값 중에 가장 작은 키를 말한다. tailMap(K fromKey) 는 fromKey 보다 크거나 같은 키들을 리턴한다. 즉 나보다 큰 키가 있으면 그 중에 가장 작은 값(tailMap.firstKey())을 리턴. 나보다 큰 키가 없으면 circle.firstKey() 로 맨 처음 노드에 할당.

Date: 2023-01-24 Tue 00:00

Author: Younghwan Nam

Created: 2024-04-16 Tue 10:05

Emacs 27.2 (Org mode 9.4.4)

Validate