Последовательное Хеширование

Автор оригинала: Arpit Bhayani.

Последовательное хеширование-это метод хеширования, который очень хорошо работает в динамической среде, где распределенная система часто масштабируется вверх и вниз. Основная концепция последовательного хеширования была введена в статье Последовательное хеширование и случайные деревья: Распределенные протоколы кэширования для облегчения горячих точек во Всемирной паутине но она приобрела популярность после знаменитой статьи, представившей DynamoDB – Dynamo: Высокодоступное хранилище ключей Amazon . С тех пор последовательное хеширование набрало обороты и нашло массу вариантов использования при эффективном проектировании и масштабировании распределенных систем. Два известных примера, которые исчерпывающе используют эту технику,-это BitTorrent для своих одноранговых сетей и Akamai для своих веб-кэшей. В этой статье мы глубоко погрузимся в необходимость последовательного хеширования, его внутренности и, что более важно, попутно реализуем его с помощью массивов и Двоичного поиска .

Прежде чем перейти к основному методу последовательного хеширования, мы сначала проясним несколько вещей, одна из которых-хеш-функции. Хэш-функции-это любые функции, которые отображают значение из домена произвольного размера в другой домен фиксированного размера, обычно называемый хэш-пространством. Например, сопоставление URL-адресов с 32-битными целыми числами или HTML-содержимого веб-страниц с 256-байтовой строкой. Значения, генерируемые в качестве выходных данных этих хэш-функций, обычно используются в качестве ключей для обеспечения эффективного поиска исходной сущности.

Примером простой хэш-функции является функция, которая отображает 32-битное целое число в 8-битное целочисленное хэш-пространство. Функция может быть реализована с помощью арифметического оператора modulo , и мы можем достичь этого, взяв modulo 256 , который дает числа в диапазоне [0, 255] , занимающие 8 бит для его представления. Хэш-функция, которая сопоставляет ключи с такой целочисленной областью, чаще всего применяет по модулю N , чтобы ограничить значения или хэш-пространство диапазоном [0, N-1] .

Хорошая хэш-функция обладает следующими свойствами

• Эта функция является вычислительно эффективной и генерируемые значения легко найти
• Эта функция в большинстве случаев общего использования ведет себя как псевдослучайный генератор, который равномерно распределяет данные без какой-либо заметной корреляции

Теперь, когда мы увидели, что такое хэш-функция, мы рассмотрим, как мы могли бы использовать их и построить несколько масштабируемую распределенную систему.

Скажем, мы создаем распределенную систему хранения, в которой пользователи могут загружать файлы и получать к ним доступ по требованию. Служба предоставляет пользователям следующие API-интерфейсы

• upload для загрузки файла
• fetch для извлечения файла и возврата его содержимого

За кулисами система имеет узлы хранения, на которых хранятся файлы и к которым осуществляется доступ. Эти узлы предоставляют функции put_file и fetch_file , которые помещают и получают содержимое файла на/с диска и отправляют ответ на главный сервер API, который, в свою очередь, отправляет его обратно пользователю.

Чтобы выдержать начальную нагрузку, система имеет 5 узлов Stogare, которые хранят загруженные файлы распределенным образом. Наличие нескольких узлов гарантирует, что система в целом не перегружена, а хранилище распределено почти равномерно.

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

# storage_nodes holding instances of actual storage node objects
storage_nodes = [
    StorageNode(name='A', host='10.131.213.12'),
    StorageNode(name='B', host='10.131.217.11'),
    StorageNode(name='C', host='10.131.142.46'),
    StorageNode(name='D', host='10.131.114.17'),
    StorageNode(name='E', host='10.131.189.18'),
]


def hash_fn(key):
    """The function sums the bytes present in the `key` and then
    take a mod with 5. This hash function thus generates output
    in the range [0, 4].
    """
    return sum(bytearray(key.encode('utf-8'))) % 5


def upload(path):
    # we use the hash function to get the index of the storage node
    # that would hold the file
    index = hash_fn(path)

    # we get the StorageNode instance
    node = storage_nodes[index]

    # we put the file on the node and return
    return node.put_file(path)


def fetch(path):
    # we use the hash function to get the index of the storage node
    # that would hold the file
    index = hash_fn(path)

    # we get the StorageNode instance
    node = storage_nodes[index]

    # we fetch the file from the node and return
    return node.fetch_file(path)

Используемая здесь хэш-функция просто суммирует байты и принимает значение по модулю 5 (поскольку в системе имеется 5 узлов хранения) и, таким образом, генерирует выходные данные в хэш-пространстве [0, 4] . Это выходное значение теперь представляет индекс механизма хранения, который будет отвечать за хранение файла.

Скажем, у нас есть 5 файлов ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt-если мы применим к ним хэш-функцию, то обнаружим, что они хранятся на узлах хранения E, A, B, C и D соответственно.

Все становится интересным, когда система набирает некоторую тягу и ее нужно масштабировать до 7 узлов, что означает, что теперь хэш-функция должна делать mod 7 вместо mod 5 . Изменение хэш-функции подразумевает изменение отображения и ассоциации файлов с узлами хранения. Сначала нам нужно администрировать новые ассоциации и посмотреть, какие файлы необходимо переместить с одного узла на другой.

С новой хэш – функцией те же 5 файлов ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt теперь они будут связаны с узлами хранения D, E, F, G, A. Здесь мы видим, что изменение хэш-функции требует от нас перемещения каждого из 5 файлов в другой узел.

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

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

Последовательное хеширование решает эту ситуацию, сохраняя хэш-пространство огромным и постоянным, где-то в порядке [0, 2^128 - 1] и узел хранения, и объекты сопоставляются с одним из слотов в этом огромном хэш-пространстве. В отличие от традиционной системы, где файл был связан с узлом хранения в индексе, куда он был хэширован, в этой системе шансы столкновения между файлом и узлом хранения бесконечно малы, и поэтому нам нужен другой способ определения этой ассоциации.

Вместо использования подхода, основанного на столкновении, мы определяем ассоциацию как-файл будет связан с узлом хранения, который присутствует непосредственно справа от его хэшированного местоположения. Определение ассоциации таким образом помогает нам

• держите хэш – функцию независимой от количества узлов хранения
• держите ассоциации относительными, а не обусловленными абсолютными коллизиями

Последовательное хеширование в среднем требует переноса только k/n единиц данных при масштабировании вверх и вниз; где k-общее количество ключей, а n-количество узлов в системе.

Очень наивный способ реализовать это-выделить массив размером, равным хэш – пространству, и поместить файлы и узел хранения буквально в массив на хешированном месте. Чтобы получить ассоциацию, мы выполняем итерацию от хэшированного местоположения элемента вправо и находим первый узел хранения. Если мы достигаем конца массива и не находим ни одного узла хранения, мы возвращаемся к индексу 0 и продолжаем поиск. Этот подход очень прост в реализации, но страдает следующими ограничениями

• требуется огромная память для хранения такого большого массива
• поиск ассоциации путем итерации каждый раз вправо-это O(hash_space)

Лучший способ реализовать это-использовать два массива: один для хранения узлов хранения, называемых nodes , и другой для хранения позиций узлов хранения в хэш-пространстве, называемых keys . Существует взаимно однозначное соответствие между двумя массивами – узел хранения nodes[i] присутствует в позиции keys[i] в хэш-пространстве. Оба массива хранятся отсортированными в соответствии с массивом keys .

Хеш-функция в последовательном хешировании

Мы определяем total_slots как размер всего этого хэш-пространства, обычно порядка 2^256 , и хэш-функция может быть реализована, взяв SHA-256 с последующим mod total_slots . Поскольку total_slots огромен и является константой, следующая реализация хэш-функции не зависит от фактического количества узлов хранения, присутствующих в системе, и, следовательно, остается незатронутой такими событиями, как масштабирование и масштабирование.

def hash_fn(key: str, total_slots: int) -> int:
    """hash_fn creates an integer equivalent of a SHA256 hash and
    takes a modulo with the total number of slots in hash space.
    """
    hsh = hashlib.sha256()

    # converting data into bytes and passing it to hash function
    hsh.update(bytes(key.encode('utf-8')))

    # converting the HEX digest into equivalent integer value
    return int(hsh.hexdigest(), 16) % total_slots

Добавление нового узла в систему

Когда возникает необходимость масштабирования и добавления нового узла в систему, в нашем случае нового узла хранения, мы

• найдите положение узла, в котором он находится в хэш-пространстве
• заполните новый узел данными, которые он должен обслуживать
• добавьте узел в хэш-пространство

Когда новый узел добавляется в систему, он влияет только на файлы, которые хэшируются в местоположении слева и связаны с узлом справа, в котором будет помещаться новый узел. Все остальные файлы и ассоциации остаются незатронутыми, что сводит к минимуму объем переносимых данных и требуемое изменение сопоставления.

Из приведенной выше иллюстрации мы видим, что когда новый узел K добавляется между узлами B и E, мы меняем ассоциации файлов, присутствующих в сегменте B-K, и назначаем их узлу K. Данные, принадлежащие сегменту B-K, можно найти в узле E, с которым они были ранее связаны. Таким образом, единственные затронутые файлы, которые нуждаются в миграции, находятся в сегменте B-K; и их ассоциация изменяется от узла E к узлу K.

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

def add_node(self, node: StorageNode) -> int:
    """add_node function adds a new node in the system and returns the key
    from the hash space where it was placed
    """

    # handling error when hash space is full.
    if len(self._keys) == self.total_slots:
        raise Exception("hash space is full")

    key = hash_fn(node.host, self.total_slots)

    # find the index where the key should be inserted in the keys array
    # this will be the index where the Storage Node will be added in the
    # nodes array.
    index = bisect(self._keys, key)

    # if we have already seen the key i.e. node already is present
    # for the same key, we raise Collision Exception
    if index > 0 and self._keys[index - 1] == key:
        raise Exception("collision occurred")

    # Perform data migration

    # insert the node_id and the key at the same `index` location.
    # this insertion will keep nodes and keys sorted w.r.t keys.
    self.nodes.insert(index, node)
    self._keys.insert(index, key)

    return key

Удаление нового узла из системы

Когда возникает необходимость уменьшить масштаб и удалить существующий узел из системы, мы

• найдите положение узла, который будет удален из хэш-пространства
• заполните узел справа данными, которые были связаны с удаляемым узлом
• удалите узел из хэш – пространства

Когда узел удаляется из системы, он влияет только на файлы, связанные с самим узлом. Все остальные файлы и ассоциации остаются незатронутыми, что сводит к минимуму объем переносимых данных и требуемое изменение сопоставления.

Из приведенной выше иллюстрации мы видим, что при удалении узла K из системы мы меняем ассоциации файлов, связанных с узлом K, на узел, лежащий непосредственно справа от него, то есть узел E. Таким образом, единственные файлы, затронутые и нуждающиеся в миграции, – это те, которые связаны с узлом К.

Для того чтобы реализовать это на низком уровне с помощью узлов и ключей массива, мы получаем индекс, где узел K лежит в массиве ключей с помощью двоичного поиска. Как только у нас есть индекс, мы удаляем ключ из массива keys и узел хранения из массива nodes , присутствующего в этом индексе.

def remove_node(self, node: StorageNode) -> int:
    """remove_node removes the node and returns the key
    from the hash space on which the node was placed.
    """

    # handling error when space is empty
    if len(self._keys) == 0:
        raise Exception("hash space is empty")

    key = hash_fn(node.host, self.total_slots)

    # we find the index where the key would reside in the keys
    index = bisect_left(self._keys, key)

    # if key does not exist in the array we raise Exception
    if index >= len(self._keys) or self._keys[index] != key:
        raise Exception("node does not exist")

    # Perform data migration

    # now that all sanity checks are done we popping the
    # keys and nodes at the index and thus removing the presence of the node.
    self._keys.pop(index)
    self.nodes.pop(index)

    return key

Связывание элемента с узлом

Теперь, когда мы увидели, как последовательное хеширование помогает свести миграцию данных во время увеличения и уменьшения масштаба к абсолютному минимуму, пришло время посмотреть, как эффективно мы можем найти “узел справа” для данного элемента. Операция поиска ассоциации должна быть очень быстрой и эффективной, поскольку она будет вызываться для каждого отдельного чтения и записи, происходящего в системе.

Чтобы реализовать это на низком уровне, мы снова берем рычаги бинарного поиска и выполняем эту операцию в O(log(n)) . Сначала мы передаем элемент в хэш-функцию и извлекаем позицию, в которой элемент хэшируется в хэш-пространстве. Эта позиция затем двоично ищется в массиве keys , чтобы получить индекс первого ключа, который больше позиции (полученной из хэш-функции). если в массиве keys нет ключей больше позиции, то мы обводим круг назад и возвращаем 0-й индекс. Полученный таким образом индекс будет индексом узла хранения в массиве nodes , связанном с элементом.

def assign(self, item: str) -> str:
    """Given an item, the function returns the node it is associated with.
    """
    key = hash_fn(item, self.total_slots)

    # we find the first node to the right of this key
    # if bisect_right returns index which is out of bounds then
    # we circle back to the first in the array in a circular fashion.
    index = bisect_right(self._keys, key) % len(self._keys)

    # return the node present at the index
    return self.nodes[index]

Исходный код с реализацией последовательного хэширования в Python можно найти по адресу github.com/arpitbbhayani/consistent-hashing .

Последовательное хеширование-один из самых важных алгоритмов, помогающих нам горизонтально масштабировать и управлять любой распределенной системой. Алгоритм работает не только в сегментированных системах, но и находит свое применение в балансировке нагрузки, разделении данных, управлении серверными липкими сеансами, алгоритмах маршрутизации и многих других. Многие базы данных обязаны своим масштабом, производительностью и способностью справляться с огромной нагрузкой последовательному хэшированию.

• Хэш – функции- Википедия
• Последовательное хеширование – Википедия
• Последовательное хеширование – Стэнфорд
• Последовательное хеширование и случайные деревья
• Динамо: Высокодоступный магазин ключей и ценностей Amazon

• Python Кэширует Целые числа
• Дробное каскадирование – Ускорение бинарного поиска
• Семантика копирования при записи
• Что делает MySQL LRU cache scan устойчивым
• Построение конечных автоматов с помощью сопрограмм Python

Эта статья была первоначально опубликована на моем сайте. блог – Последовательное хеширование .

Если вам понравилось то, что вы прочитали, подпишитесь на мою рассылку и получите сообщение, доставленное прямо в ваш почтовый ящик, и дайте мне знать @arpit_bhayani .