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

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

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

Nginx+Redis: делаем асихронное web-приложение для больших нагрузок

Как работает обычное web-приложение?
Примерно так:

Проходит время, нагрузка растёт и узким местом становится база данных. Разработчики, стараясь снять с неё нагрузку, переходят к асинхронной схеме. Тут база данных не используется в каждом запросе. В основном используется только быстрое noSQL-хранилище или специализированный сервер очередей, для передачи заданий пулу обработчиков. Основную работу эти обработчики выполнят уже позже, когда довольный клиент получит быстрый ответ и пойдёт заниматься своими делами:

Но нагрузка может расти и дальше. Оставим в стороне "горизонтальное" масштабирование при котором мы строим кластера и плодим инстансы приложений - речь сейчас не об этом. Что в последней схеме становится узким местом? База данных уже не в счёт: спрятанная за слоем очередей и обработчиков, кэшей и буферов, она может чувствовать себя спокойно. Обработчики великолепно масштабируются, ведь они "висят" на безразмерной шине очереди. Nginx - один из самых высопроизводительных серверов, за него не беспокоимся. noSQL-хранилища тоже как правило замечтально держат нагрузку и масштабируются.
Что остаётся? К сожалению "крайним" остаётся наше web-приложение. Это оно разбирает запрос, авторизует его, создаёт обьекты, манипулирует с ними, сериализует в базу или в очередь. А потом ещё вычитать данные, сериализовать для ответа... Приложение может содержать неэффективный код, плохо масштабироваться... Кстати, а зачем нам оно вообще нужно? Давайте уберём его из схемы:

 Как же так? Очень просто. Задача получить данные из запроса и уложить в очередь вообще-то тривиальная. И обратная задача тоже. Зачем программировать тривиальные вещи? Всё уж сделано за нас :)
Nginx при помощи HttpRedis2Module может уложить в noSQL-хранилище Redis любые параметры из запроса в виде такого набора ключ-значение, который нам нужен. И вычитать нужный нам набор ключей для возврата клиенту. Вы не используете параметры запросов? У вас обмен с клиентской частью в формате JSON? Нет проблем! Используя set-misc-nginx-module мы можем прямо в конфиге nginx-а описать правила получения данных из запроса: UrlDecode, JSONDecode, Base64Decode и т.п.

Теперь посмотрим, как настроить такое "сверхтонкое" web-приложение:

Redis: пишем Java-клиент

В одном из прежних постов я описывал свои впечатления от знакомства с Redis. Тогда я использовал библиотеку Jedis. А недавно мне попалось описание протокола Redis-сервера и я решил поупражняться в его освоении. Чтобы было нагляднее я "завернул" результат в простое swing-приложение, которое можно скачать на моём сайте. Итак...

Коротко о протоколе
Для соединения с сервером используем tcp-протокол, порт по умолчанию - 6379. Команды и наборы данных в ответах завершаются последовательностью "\r\n" (CRLF). Первый символ ответа указывает на тип возвращаемого значения. Тут ":" - число, "-" - сообщение об ошибке, "+" - однострочный ответ. Интереснее ответы, начинающиеся с "$". Это, так называемые "составные" ответы. Они содержат две строки, первая из которых - число байт, которые нужно прочитать во второй. Такие ответы будем получать наиболее часто, их возвращает команда GET для обычных ключей. Если же ключ необычный, например хэш, то ответ будет "многосоставной". В нём первый символ - "*", затем число результатов в ответе, затем результаты, каждый по две строке в виде составных ответов, начинающихся с "$".

Архитектура
В последней (на сегодня) версии Redis я насчитал более 120 команд. Из них в обычной практике понадобится не более десятка, но хорошая библиотека должна легко расширяться.
Схема работы будет такой: каждая команда будет представлена одним классом, в нём - специфическая логика по формированию запроса и интерпретации ответа. Сам метод, который пишет/читает данные будет реализован в их общем предке. Все классы будут реализовывать один и тот же абстрактный метод. Приложение о классах команд ничего знать не должно, для него у нас будет Factory, которое будет принимать запрос, подгружать в рантайме нужный класс, создавать его инстанс, инициализировать его (например отдавать ему уже открытый сокет) и дёргать его стандартный метод. В коде это выглядит так:

1. public class RedisFactory {
2.   
3.   private Socket s;
4.   public static final String COMMAND_AUTH = "redisui.connector.command.Auth";
5.   public static final String COMMAND_KEYS = "redisui.connector.command.Keys";
6.   public static final String COMMAND_GET = "redisui.connector.command.Get";
7.   public static final String COMMAND_TYPE = "redisui.connector.command.Type";
8.   public static final String COMMAND_HGETALL = "redisui.connector.command.Hgetall";
9.   public static final String COMMAND_DEL = "redisui.connector.command.Del";
10.   
11.   public void connect(String host, String port, String pass) throws Exception {
12.     String[] params = {host, port, pass};
13.     exec(COMMAND_AUTH, params);
14.   }
15.   
16.   public Response exec(String cmd, String[] params) throws Exception {
17.     Class<? extends CommandBased> command = Class.forName(cmd).asSubclass(CommandBased.class);
18.     CommandBased ci = command.newInstance();
19.     ci.setS(this.s);
20.     Response r = ci.exec(params);
21.     this.s = ci.getS();
22.     return r;
23.   } 
24. }

Так, во имя стандартизации мы параметры в запрос передаём как массив строк, а ответ получаем в виде такого себе объекта-оборотня Response:

1. public class Response {
2.  
3.   private String type;
4.   private byte[] out;
5.   public static final String TYPE_LINE = "+";
6.   public static final String TYPE_ERROR = "-";
7.   public static final String TYPE_INT = ":";
8.   public static final String TYPE_STRING = "$";
9.   public static final String TYPE_ARRAY = "*";
10.  
11.   public Response(String type, byte[] out) {
12.     this.type = type;
13.     this.out = out;
14.   }
15.  
16.   public String getLineOut() {
17.     ...
18.   }
19.   
20.   public int getIntOut() {
21.     ...
22.   }
23.   
24.   public String getStringOut() {
25.     ...
26.   }
27.  
28.   public String[] getArrayOut() {
29.     ...
30.   }
31.  
32.   public String getType() {
33.     return type;
34.   }
35. }

На стороне приложения мы либо знаем, какого типа будет ответ и в таком случае вызываем нужный getter, либо обрабатываем все варианты, получая тип конкретного ответа из getType().
И, наконец, пример класса команды:

1. public class Get extends CommandBased {
2.  
3.   @Override
4.   public Response exec(String[] params) throws Exception {
5.     String command = "get "+params[0]+"\r\n";
6.     Response res = interrupt(command);
7.     if (res.getType().equals(Response.TYPE_ERROR)) {
8.       throw new Exception(res.getLineOut());
9.     }
10.     return res;
11.   }
12. }

Как видим, добавлять новые команды в такую библиотеку - одно удовольствие.

Результат:

За пару часов работы получился прототип, который ищет ключи по маске, позволяет просматривать их содержимое и удалять их.
По мере добавления функционала буду выкладывать новые версии у себя на сайте. Если кому пригодится - всегда на здоровье :).

Использование Redis в Java WEB applcation

В жизни каждого достаточно большого web-проекта наступает момент, когда требования к производительности заставляют поставить между кодом и данными в базе что-то достаточно быстрое и нетребовательное... Например Memcached или Redis. Первый инструмент достаточно известен, и обладает серьёзным недостатком: всё что не в памяти - удаляется. Второй - практически полноценная noSQL БД. И благодаря этой своей природе может быть крайне полезна, в первую очередь как дополнение к традиционной SQL СУБД. Действительно, так ли редко мы складываем в таблицы что-то совсем не "табличное"? Например, недавно мы вынесли в базу хранилище сессий пользователей (очень удобно для горизонтального масштабирования web-фронтэндов). Возникли проблемы с нагрузкой, потребовалась "тонкая" настройка и т.п. А ведь всё дело в том, что хранение таких данных в реляционной базе вообще-то "притянуто за уши". Что мы пишем в сесию? Правильно, пары ключ-значение. При чём тут SQL?. Короче, Redis с этой задачей справился идеально, что позволило нашему SQL-серверу снова "расправить крылья".

Вспомню, как я с этим разбирался...
После недолгого изучения разных источников нашёл вот эту wiki. Это перевод официальной документации. Пользовался почти исключительно этим сайтом. Но прежде чем начать изучение, установим себе эту систему.
На официальном сайте скачиваем версию (на данный момент последняя стабильная - 2.0). Это архив с исходниками, собираем сами: после распаковки в каталоге делаем make. После сборки запускаем сервер с помощью:

$ ./redis-server

По умолчанию он поднимается на порту 6379 и дальше с ним можно взаимодействовать хотя бы даже и обычным telnet-ом. Но мы не будем так суровы :)
Для начала сделаем минимальные правки в конфиге: redis.conf в каталоге приложения - поставим daemonize yes, это позволит нам запускать сервер не отдавая ему консоль. Более тонкую настройку оставим на потом.
Запускать сервер теперь будем с явным указанием конфига:

$ ./redis-server redis.conf 

Для освоения минимального набора команд воспользуемся консольным клиентом, который есть в сборке:

$ ./redis-cli <команда> <параметры ...>

Например, чтобы сохранить пару ключ-значение в Redis:

$ ./redis-cli set mykey myval
$ OK

... а чтобы получить значение по ключу:

$ ./redis-cli get mykey

$ "myval"

Redis поддерживает несколько типов данных для значений, которые мы "вкладываем" в ключи. Это строки, списки, множества и хэши. Детальнее посмотрите в руководстве, на пока понадобятся лишь имена команд, для каждого типа данных "геттеры" и "сеттеры" свои. Например для хэшей это:
hget, hset, hmset, hgetall... пока достаточно... (установить значение поля хэша, получить его, установить все поля-значения и получить все). Детально разбираться не будем, всё равно работать нам не в консоли. Достаточно просто понимать, какие есть инструменты.

Теперь переходим к Java.
Для работы с Redis есть несколько библиотек. Самая "живая" из них - Jedis, поддерживает версию 2.0, что нам и требуется.
Скачиваем её отсюда. Подключаем jedis-1.5.2.jar к проекту. Пишем класс для взаимодействия с redis:

1. /*
2. * Redis get|set implementation
3. */
4.  
5. package net.multipi.connector.redis;
6.  
7. import java.io.IOException;
8. import java.util.Map;
9. import java.util.Set;
10. import redis.clients.jedis.Jedis;
11.  
12. public class RedisConnector {
13.     private Jedis cli;
14.     
15.     /**
16.      * constructor: connect to Redis server and authorization
17.      * @param host
18.      * @param port
19.      * @param password
20.      */
21.     public RedisConnector(String host, int port, String password) {
22.         cli = new Jedis(host, port, 5000);
23.         cli.auth(password);
24.         try {
25.             cli.connect();
26.         } catch (Exception ex) {
27.             ex.printStackTrace(System.err);
28.         }
29.     }
30.  
31.     /**
32.      * calculate keys count (eg count of active sessions)
33.      * @return
34.      */
35.     public long getKeysCount() {
36.         return cli.dbSize();
37.     }
38.  
39.     /**
40.      * get all keys that begin with "begin" string
41.      * @param begin
42.      * @return
43.      */
44.     public Set<String> getAllKeys(String begin) {
45.         return cli.keys(begin+"*");
46.     }
47.  
48.     /**
49.      * set session values as map
50.      * @param sess
51.      * @param m
52.      * @return
53.      */
54.     public boolean setAll(String sess, Map<String, String> m) {
55.         String r = cli.hmset(sess, m);
56.         return (r.equals("OK"));
57.     }
58.  
59.     /**
60.      * set session values as map and set expire the session
61.      * @param sess
62.      * @param m
63.      * @param expire
64.      * @return
65.      */
66.     public boolean setAll(String sess, Map<String, String> m, int expire) {
67.         boolean rez = false;
68.         String r = cli.hmset(sess, m);
69.         long er = cli.expire(sess, expire);
70.         rez = (r.equals("OK") && er>0);
71.         return rez;
72.     }
73.  
74.     /**
75.      * set one of session values
76.      * @param sess
77.      * @param key
78.      * @param value
79.      * @return
80.      */
81.     public boolean set(String sess, String key, String value) {
82.         boolean rez = false;
83.         Map m = getAll(sess);
84.         if (m!=null) {
85.             m.put(key, value);
86.             rez = setAll(sess, m);
87.         }
88.         return rez;
89.     }
90.     
91.     /**
92.      * set or update session values and set expire
93.      * @param sess
94.      * @param key
95.      * @param value
96.      * @param expire
97.      * @return
98.      */
99.     public boolean set(String sess, String key, String value, int expire) {
100.         boolean rez = false;
101.         Map m = getAll(sess);
102.         if (m!=null) {
103.             m.put(key, value==null ? "" : value);
104.             rez = setAll(sess, m, expire);
105.         }
106.         return rez;
107.     }
108.     /**
109.      * check if session exists
110.      * @param sess
111.      * @return
112.      */
113.     public boolean isExists(String sess) {
114.         return cli.exists(sess);
115.     }
116.     /**
117.      * get session values
118.      * @param sess
119.      * @return
120.      */
121.     public Map<String, String> getAll(String sess) {
122.         return cli.hgetAll(sess);
123.     }
124.  
125.     /**
126.      * det session values and prolongs session
127.      * @param sess
128.      * @param expire
129.      * @return
130.      */
131.     public Map<String, String> getAll(String sess, int expire) {
132.         Map m = cli.hgetAll(sess);
133.         cli.hmset(sess, m);
134.         cli.expire(sess, expire);
135.         return m;
136.     }
137.  
138.     /**
139.      * get one of session values
140.      * @param sess
141.      * @param key
142.      * @return
143.      */
144.     public String get(String sess, String key) {
145.         return cli.hget(sess, key);
146.     }
147.  
148.     /**
149.      * delete session with all session data
150.      * @param sess
151.      * @return
152.      */
153.     public boolean del(String sess) {
154.         Long del = cli.del(sess);
155.         return del>0;
156.     }
157.  
158.     /**
159.      * close connection
160.      */
161.     public void close() {
162.       if (cli.isConnected()) {
163.             try {
164.                 cli.disconnect();
165.             } catch (IOException ie) {}
166.         }
167.     }
168. }

Как видно из кода все методы библиотеки есть простые java-обёртки над командами Redis. А все наши методы - вызовы методов библиотеки. В конструктор нужно передать ip-адрес машины на которой запущен Redis-сервер, порт и пароль доступа к серверу. Третьим параметром передаём время ожидания ответа сервера в миллисекундах. Вообще, если есть такая возможность Redis лучше всего поднимать на той же машине, где работает наше приложение. Скорость обработки запросов у Redis на базе из миллиона записей составляет 1-2 миллисекунды. В сравнении с этим потери 20-50 ms на соединение (в лучшем случае) выглядят неприятно. Требования к памяти у Redis весьма скромные.
Использование Redis в качестве сессионного хранилища приятно ещё и тем, что в нём реализован механизм "устаревания" ключей. Достаточно установить срок жизни ключу и сервер сам "приберёт" его через указанное время. В текущей версии была неприятная особенность: после обновления значения ключ становился "вечным". Поэтому мы "напоминаем" ключам время жизни после апдейта, там где это нужно.
Ещё одна особенность едва не испортила впечатление от Jedis: при использовании внутреннего механизма пула соединений в этой библиотеке спустя 5-10 минут работы под нагрузкой система "засыпала", без видимой причины и без каких-либо ошибок прекращая реагировать на запросы. От пула пришлось отказаться, благо высокая скорость обработки запросов делала контроль за числом открытых коннектов задачей чисто "академической" важности.
В целом: инструмент весьма порадовал. После изнурительной борьбы за производительность запросов на "основной" БД скорость ответов от Redis создаёт прямо-таки фантастическое впечатление. А возможность работать с сервером "чем угодно", просто посылая команды на порт так и провоцирует написать свою реализацию клиента.