Консистентное хеширование: принципы и применение

Введение

Техника хеширования
В информатике, согласованное хеширование. Статья впоследствии была адаптирована для решения технической задачи отслеживания файлов в одноранговых сетях, таких как распределенная хеш-таблица. Teradata использовала эту технику в своей распределенной базе данных, выпущенной в 1986 году, хотя и не использовала этот термин. Teradata до сих пор использует концепцию хеш-таблицы для решения именно этой задачи. Akamai Technologies была основана в 1998 году учеными Дэниелом Левином и Ф. Томсоном Лейтоном (соавторами статьи, вводящей термин "согласованное хеширование"). В сети доставки контента Akamai согласованное хеширование используется для балансировки нагрузки внутри кластера серверов, а стабильный алгоритм поиска пары – для балансировки нагрузки между кластерами. Согласованное хеширование также используется для снижения влияния частичных сбоев системы в крупных веб-приложениях, обеспечивая надежное кэширование без повсеместных последствий сбоя. Согласованное хеширование также является основой распределенных хеш-таблиц (DHT), которые используют хеш-значения для разделения пространства ключей между распределенным набором узлов, а затем создают накладную сеть связанных узлов, обеспечивающую эффективный поиск узлов по ключу. Rendezvous hashing, разработанный в 1996 году, представляет собой более простой и универсальный метод. Он достигает целей согласованного хеширования, используя существенно отличающийся алгоритм HRW (highest random weight) – алгоритм наибольшего случайного веса.

Основная техника

В задаче балансировки нагрузки, например, когда BLOB необходимо назначить одному из серверов в кластере, можно использовать стандартную хеш-функцию следующим образом: мы вычисляем хеш-значение для этого BLOB, и, предположив, что полученное значение хеша равно *h*, выполняем операцию взятия по модулю с количеством серверов (в данном случае *N*), чтобы определить сервер, на котором можно разместить BLOB: *h mod N*; следовательно, BLOB будет помещен на сервер, чей идентификатор является преемником *h* на единичном круге. Однако, при добавлении или удалении сервера во время сбоя или масштабирования (при изменении *N*), все BLOB на каждом сервере должны быть переназначены и перемещены из-за перехеширования, что является дорогостоящей операцией. Последовательное хеширование было разработано для решения проблемы переназначения каждого BLOB при добавлении или удалении сервера в кластере. Основная идея заключается в использовании хеш-функции, которая отображает как BLOB, так и серверы на единичный круг, обычно в радианах. Например, *hash(x)* (где *hash(x)* – хеш BLOB или идентификатор сервера, например IP-адрес или UUID). Затем каждый BLOB назначается следующему серверу, который встречается на круге по часовой стрелке. Обычно для поиска "позиции" или сервера для размещения конкретного BLOB используется алгоритм двоичного поиска или линейного поиска со сложностью *O(log N)* или *O(N)* соответственно; и на каждой итерации, выполняемой по часовой стрелке, производится операция *server_id(h)* (где *server_id(h)* – идентификатор сервера в кластере), чтобы найти сервер для размещения BLOB. Это обеспечивает равномерное распределение BLOB по серверам. Но, что более важно, если сервер выходит из строя и удаляется из круга, переназначению подлежат только те BLOB, которые были отображены на этот сервер, – следующему серверу по часовой стрелке. Аналогично, при добавлении нового сервера он добавляется на единичный круг, и перераспределению подлежат только BLOB, отображенные на этот сервер. Важно отметить, что при добавлении или удалении сервера подавляющее большинство BLOB сохраняют свои прежние назначения, а добавление одного сервера приводит к перемещению лишь небольшой доли BLOB. Хотя процесс перемещения BLOB между кэш-серверами в кластере зависит от контекста, обычно, вновь добавленный кэш-сервер определяет своего "преемника" и перемещает все BLOB, чье отображение принадлежит этому преемнику (то есть чье хеш-значение меньше, чем у нового сервера), с него. Однако, в случае кэша веб-страниц, в большинстве реализаций перемещение или копирование не требуется, если кэшированный BLOB достаточно мал. Когда запрос попадает на вновь добавленный кэш-сервер, происходит промах кэша, выполняется запрос к фактическому веб-серверу, и BLOB кэшируется локально для последующих запросов. Избыточные BLOB на ранее использовавшихся кэш-серверах удаляются в соответствии с политикой вытеснения кэша.

In the problem of load balancing, for example, when a BLOB has to be assigned to one of servers on a cluster, a standard hash function could be used in such a way that we calculate the hash value for that BLOB, assuming the resultant value of the hash is , we perform modular operation with the number of servers ( in this case) to determine the server in which we can place the BLOB: ; hence the BLOB will be placed in the server whose is successor of in this case. However, when a server is added or removed during outage or scaling (when changes), all the BLOBs in every server should be reassigned and moved due to rehashing, but this operation is expensive. Consistent hashing was designed to avoid the problem of having to reassign every BLOB when a server is added or removed throughout the cluster. The central idea is to use a hash function that maps both the BLOB and servers to a unit circle, usually radians. For example, (where is hash of a BLOB or server's identifier, like IP address or UUID). Each BLOB is then assigned to the next server that appears on the circle in clockwise order. Usually, binary search algorithm or linear search is used to find a "spot" or server to place that particular BLOB in or complexities respectively; and in every iteration, which happens in clockwise manner, an operation (where is the value of the server within the cluster) is performed to find the server to place the BLOB. This provides an even distribution of BLOBs to servers. But, more importantly, if a server fails and is removed from the circle, only the BLOBs that were mapped to the failed server need to be reassigned to the next server in clockwise order. Likewise, if a new server is added, it is added to the unit circle, and only the BLOBs mapped to that server need to be reassigned. Importantly, when a server is added or removed, the vast majority of the BLOBs maintain their prior server assignments, and the addition of server only causes fraction of the BLOBs to relocate. Although the process of moving BLOBs across cache servers in the cluster depends on the context, commonly, the newly added cache server identifies its "successor" and moves all the BLOBs, whose mapping belongs to this server (i. e. whose hash value is less than that of the new server), from it. However, in the case of web page caches, in most implementations there is no involvement of moving or copying, assuming the cached BLOB is small enough. When a request hits a newly added cache server, a cache miss happens and a request to the actual web server is made and the BLOB is cached locally for future requests. The redundant BLOBs on the previously used cache servers would be removed as per the cache eviction policies.

Уменьшение отклонения

Чтобы избежать перекоса нескольких узлов внутри радиана, возникающего из-за неравномерного распределения серверов в кластере, используется несколько меток. Эти дублирующие метки называются "виртуальными узлами", то есть множеством меток, указывающих на один "реальный" узел или сервер в кластере. Количество виртуальных узлов или дублирующих меток, используемых для конкретного сервера в кластере, называется "весом" этого сервера.