Делаем алгоритм шардинга. Два решения: простое и красивое

Надеюсь все знают что такое шардинг. Ну а если вы всего лишь "слышали об этом где-то", то вы по-своему счастливый человек. Шардинг данных это решение "последнего выхода", когда никакие другие оптимизации системы хранения данных вроде индексации, денормализации и кластеризации уже не помогают. При шардинге вы берёте свою таблицу (или коллекцию для noSQL) размером в десять миллионов записей и разрезаете её, к примеру, на 10 таблиц по миллиону. Эти таблицы могут лежать в разных базах (нодах) на разных серверах. Так мы получаем то, за что разработчики высоконагруженных проектов так любят шардинг: бесконечное горизонтальное масштабирование. Чтобы определить для каждой записи ноду в которую её нужно положить или где её следует потом искать мы должны реализовать алгоритм определения ноды исходя из ключа и общего числа нод. Для записей определённой структуры с заранее известным "ключевым" полем это сделать несложно. Если вы режете таблицу пользователей с инкрементным id в качестве ключа, то можно просто определить диапазоны id  для каждой ноды. То же самое при разбиении набора записей с датой в качестве ключа. Но возьмём тяжёлый случай: ключ имеет произвольную структуру. Это не последовательное число и не дата. Просто строка. Как гарантированно отнести такой ключ к определённой ноде?

Ниже я предложу два решения: первое я сочинил сам, второе "подсмотрел" в исходниках jedis - популярного "драйвера" для подключения java-приложений к noSQL хранилищу Redis. 

Простое решение

Если вы давно читаете мой блог, то уже догадались, что моё решение будет простым до вульгарности. Так и есть: 

1. Берём хэш ключа
2. Приводим первый байт хэша к int. Берём модуль числа.
3. Если число больше 9 берём остаток от деления числа на 10. В любом случае у нас теперь число из диапазона 0...9
4. Делим 10 на число нод. Получаем коэффициент как double.
5. Делим число полученное их хэша ключа на найденный коэффициент и приводим результат к int. Результат и будет номером ноды для данного ключа. 

    public static int getShardNumber(int shardsCount, String key) throws Exception {
        if (shardsCount<1) throw new Exception("invalid shards count");
        MessageDigest md = MessageDigest.getInstance("SHA-1");
        md.update(key.getBytes("UTF-8"));
        byte[] bb = md.digest();
        int n = Math.abs((int) bb[0]);
        if (n>=10) n = n%10;
        double delimiter = (double)10/shardsCount;
        return (int) (n/delimiter);
    }

Красивое решение

Оно тоже основано на хэшировании ключей. Но тут разработчики уже используют алгоритм MD5 и приводят результат к long, используя несколько первых байт хэша. Использовать этот алгоритм сложнее: сначала мы генерируем "карту" которая ставит каждой из нод в соответствие 160 чисел полученных из хэшей. Эта карта служит потом основой для получения номера ноды для произвольного ключа.

public static TreeMap<Long, Integer> nodes;
 
public static void buildShardMap(int shardsCount) {
    nodes = new TreeMap<Long, Integer>();
    for (int i = 0; i<shardsCount; i++) {
        for (int n = 0; n < 160; n++) {
            nodes.put(hash("SHARD-" + i + "-NODE-" + n), i);
        }
    }
}
 
public static long hash(String key) {
    try {
        if (md5Holder.get() == null) {
            md5Holder.set(MessageDigest.getInstance("MD5"));
        }
    } catch (NoSuchAlgorithmException e) {
        throw new IllegalStateException("no md5 algorythm found");
    }
    MessageDigest md5 = md5Holder.get();
    md5.reset();
    md5.update(SafeEncoder.encode(key));
    byte[] bKey = md5.digest();
    return ((long) (bKey[3] & 0xFF) << 24)
            | ((long) (bKey[2] & 0xFF) << 16)
            | ((long) (bKey[1] & 0xFF) << 8) | (long) (bKey[0] & 0xFF);
}
 
public static int getShardNumber(String key) {
    SortedMap<Long, Integer> tail = nodes.tailMap(hash(key));
    if (tail.isEmpty()) {
        return nodes.get(nodes.firstKey());
    }
    rerturn tail.get(tail.firstKey());
}

Сравниваем

Первое решение:

• Проще: нет предварительного этапа, не нужно сохранять состояние между обращениями
• Быстрее. Разница, впрочем, незначительная, особенно при большом числе обращений

Второе решение:

• Обеспечивает более качественное распределение ключей по нодам. В первом алгортиме для некоторых наборов ключей самая нагруженная из нод может быть заполнена почти вдвое больше чем самая ненагруженная. При использовании второго алгоритма "дисперсия" заметно меньше.