Способ и устройство для сохранения данных с использованием хэширования

Изобретение относится к вычислительной технике. Технический результат заключается в улучшении эффективности сохранения данных. Способ сохранения данных с использованием хэширования включает предварительное конфигурирование базовых модулей хранения в количестве L и задающего соотношения между идентификаторами базовых модулей хранения и операцией модуля по L, причем L представляет собой натуральное число больше 1; вычисление ключевого значения данных, сохраняемых с использованием хэширования; осуществление операции модуля по L над полученным ключевым значением и, используя задающее соотношение между идентификаторами базовых модулей хранения и операцией модуля по L, вывод ключевого значения в операции модуля по L и соответствующих данных в базовый модуль хранения с соответствующим идентификатором базового модуля хранения; определение того, что предварительно сконфигурированная таблица хэширования в базовом модуле хранения не содержит подлежащих сохранению данных, и сохранение подлежащих сохранению данных и соответствующего ключевого значения. 2 н. и 9 з.п. ф-лы, 7 ил.

 

По настоящей заявке испрашивается приоритет по китайской патентной заявке №201010281747.0, поданной 13 сентября 2010 г. и озаглавленной «Способ и устройство для сохранения данных с использованием хэширования», все содержание которой включено в настоящий документ посредством ссылки.

Область техники, к которой относится изобретение

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

Уровень техники

Инструменты мгновенных сообщений (IM, Instant Messaging) имеют низкий технический порог для пользователей, и пользователи могут мгновенно выражать свои чувства несколькими высказываниями и делиться информацией с другими пользователями и друзьями. Соответственно, эффективность передачи информации с помощью IM относительно высока, и такие приложения становятся все более широко распространены.

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

В существующих технологиях IM-клиент часто использует алгоритмы хэширования и использует таблицы хэширования (хэш-таблицы) для достижения быстрого сохранения данных. В целом, алгоритмы хэширования включают в себя следующие: Redundancy Check 32 (CRC32), Message-Digest Algorithm 5 (MD5) и Secure Hash Algorithm (SHA). Алгоритмы хэширования могут быть использованы для конвертации строки данных в число для формирования ключевого значения (ключа), а ключевое значение может быть использовано в операции модуля (modulo) по большому простому числу M так, что данные могут быть равномерно распределены по таблице хэширования с размером M.

На фиг.1 показан существующий способ сохранения данных с использованием хэширования. Как показано на фиг.1, алгоритм хэширования, например MD5, используется для превращения данных в числовую форму и для формирования ключевого значения в качестве первых 8 байт превращенных в числовую форму данных, и затем ключевое значение используется для осуществления операции модуля по предварительно заданному большому простому числу M. Далее, данные и их соответствующее ключевое значение сохраняются в таблице хэширования, отображенные в соответствии с остатком операции модуля. Простое число M может быть определено в соответствии с фактическими потребностями и ключевыми значениями, получаемыми путем хэширования данных.

Когда хэширование разных данных формирует одинаковые ключевые значения, происходит конфликт (коллизия) ключей, и все данные с одинаковыми ключевыми значениями организуются в качестве связанного списка в таблице хэширования. Как показано на фиг.1, для данные 100 ~ данные 102 ключевые значения по модулю M имеют одинаковое значение 10; для данные 110 ~ данные 113 ключевые значения по модулю M имеют одинаковое значение 11, и эти элементы данных сохраняются в соответствующем связанном списке.

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

Следовательно, поскольку все данные сохраняются в одной таблице хэширования, требуемый объем памяти для хранения велик, и велики требования к оборудованию для хранения. В то же время для данных, имеющих конфликтующие ключевые значения при сохранении, таблица хэширования сохраняет эти данные в форме связанных списков, причем каждый элемент данных имеет одно и то же ключевое значение, что вызывает трудности для последующих операций запроса и считывания. С другой стороны, для данных, для которых ключевые значения не конфликтуют, по-прежнему необходимо резервировать в таблице хэширования объемы памяти для обработки конфликтующих ключей, и таблица хэширования на основе простого числа M требует просмотра для обеспечения того, что до сохранения данных отсутствовали идентичные данные, что снижает эффективность сохранения. Кроме того, для неконфликтующих данных, сохраненных в таблице хэширования, сложность запроса (эффективность) связана с простым числом M, используемым в таблице хэширования, тогда как для конфликтующих данных сложность запроса равна O(n), где n - количество элементов данных, сохраненных в связанном списке. Например, для обращения к данным «данные 111» на фиг.1 сначала получают ключевое значение для «данные 111», затем вычисляют Ключ % M для получения положения остатка, т.е. положения индекса, как показано в положении 11 на фиг.1. Далее просматривают связанный список в положении индекса до тех пор, пока данные, к которым нужно обратиться, не совпадут с данными 111, расположенными в таблице хэширования. Сохраненные данные 111 затем возвращаются пользователю. Таким образом, скорость такого доступа к данным мала, сложность доступа к данным высока, и эффективность запроса низка.

Раскрытие изобретения

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

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

Для достижения вышеуказанных задач настоящее изобретение представляет способ с использованием хэширования.

Способ включает в себя:

предварительное конфигурирование базовых модулей хранения в количестве L и задающего соотношения между идентификаторами базовых модулей хранения и операцией модуля по L, причем L представляет собой натуральное число больше 1;

вычисление ключевого значения данных, сохраняемых с использованием хэширования;

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

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

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

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

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

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

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

В способе количество базовых модулей хранения изменяется каждый раз путем удвоения.

Способ дополнительно может включать:

получение ключевого значения, соответствующего запросу обращения, на основе запроса обращения;

осуществление операции модуля над полученным ключевым значением по количеству базовых модулей хранения, и, на основе задающего соотношения между идентификаторами базовых модулей хранения и операции модуля по L, получение базового модуля хранения, соответствующего ключевому значению; и

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

В способе получения ключевого значения, соответствующего запросу обращения, может дополнительно включать:

получение запроса обращения;

определение того, содержит ли запрос обращения данные или идентифицированное ключевое значение;

когда запрос обращения содержит данные, вычисление ключевого значения, соответствующего данным обращения; и использование ключевого значения в качестве ключевого значения, соответствующего запросу обращения; а

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

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

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

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

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

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

осуществление поиска для определения того, содержит ли таблица хэширования идентифицированное ключевое значение; и

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

Предложенное устройство для сохранения данных с использованием хэширования содержит

множество базовых модулей хранения; модуль хранения задающего соотношения, модуль вычисления ключевого значения и блок операции модуля, причем:

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

модуль вычисления ключевого значения выполнен с возможностью вычисления ключевого значения подлежащих сохранению данных с использованием алгоритма хэширования и вывода ключевого значения в блок операции модуля;

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

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

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

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

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

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

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

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

Краткое описание чертежей

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

На фиг.2 показана диаграмма способа сохранения данных с использованием хэширования согласно вариантам осуществления настоящего изобретения.

На фиг.3 показана схематичная диаграмма для выбора базового модуля хранения для сохранения данных на основе ключевого значения данных и количества базовых модулей хранения в соответствии с вариантами осуществления настоящего изобретения.

На фиг.4 показана схематичная диаграмма таблицы хэширования в соответствии с вариантами осуществления настоящего изобретения.

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

На фиг.6 показана диаграмма процесса обращения к данным в соответствии с вариантами осуществления настоящего изобретения.

На фиг.7 показана схема устройства для сохранения данных с использованием хэширования согласно вариантам осуществления настоящего изобретения.

Осуществление изобретения

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

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

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

Шаг 201, предварительное конфигурирование базовых модулей хранения в количестве L и идентификаторов базовых модулей хранения с помощью задающего соотношения с использованием операции модуля по L.

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

Количество базовых модулей хранения предпочтительно равно простому числу (L). Например, если L является простым числом 3, то предварительно конфигурируются 3 базовых модуля хранения, и идентификаторы базовых модулей хранения с помощью задающего соотношения с использованием операции модуля по L могут быть установлены как 0, 1 и 2. Более конкретно, задающее соотношение между идентификаторами базовых модулей хранения и операцией модуля по L может быть следующим: если остаток операции модуля данных по L равен 0, данные соответственно сохраняются в базовом модуле хранения с идентификатором базового модуля хранения, равным 0; если остаток операции модуля данных по L равен 1, данные соответственно сохраняются в базовом модуле хранения с идентификатором базового модуля хранения, равным 1 и т.д.

Шаг 202, вычисление ключевого значения данных, сохраняемых с использованием хэширования.

На этом шаге алгоритм хэширования может представлять собой CRC32, MD5 или SHA. В примерных вариантах осуществления настоящего изобретения для вычислений используется алгоритм MD5.

Шаг 203, осуществление операции модуля по L над полученным ключевым значением и, используя задающее соотношение, вывод ключевого значения в операции модуля по L и соответствующих данных в базовый модуль хранения с соответствующим идентификатором базового модуля хранения.

На этом шаге операция модуля применяется к полученному ключевому значению (KEY) из шага 202 с использованием количества базовых модулей хранения (L) в качестве основания. То есть, для полученного ключевого значения KEY получают остаток с использованием количества базовых модулей хранения в качестве основания операции модуля. С помощью KEY MOD L может быть получен идентификатор базового модуля хранения посредством задающего соотношения с использованием операции модуля по L для выбора соответствующего базового модуля хранения.

На фиг.3 показан выбор базового модуля хранения для сохранения данных в соответствии с ключевым значением данных и количеством базовых модулей хранения в соответствии с вариантом осуществления настоящего изобретения. Как показано на фиг.3, используя в качестве примера L=3, ключевое значение KEY mod 3==0, и соответствующие данные выводятся в базовый модуль хранения с номером 0 (соответствующий идентификатор базового модуля хранения равен 0); ключевое значение KEY mod 3==1, и соответствующие данные выводятся в базовый модуль хранения с номером 1; и ключевое значение KEY mod 3==2, и соответствующие данные выводятся в базовый модуль хранения с номером 2.

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

На этом шаге сначала определяют, что таблица хэширования не содержит данных, соответствующих ключевому значению и совпадающих с подлежащими сохранению данными. Затем ключевое значение и соответствующие данные сохраняют. Количество предварительно сконфигурированных таблиц хэширования базовых модулей хранения может быть задано в качестве простого числа, которое может быть большим простым числом. Таблица хэширования может использовать множество параллельных хэш-групп (hash bucket) на основе предварительно заданного простого числа.

На фиг.4 показана реализация таблицы хэширования в соответствии с вариантами осуществления настоящего изобретения. Как показано на фиг.4, таблица хэширования предпочтительно параллельно использует 3 хэш-группы, то есть количество хэш-групп равно 3. Например, когда количество предварительно сконфигурированных базовых модулей хранения равно 3 и когда ключевое значение KEY mod 3==0, и соответствующие данные выводятся в базовый модуль хранения с номером 0, идентификаторы хэш-групп равны 0, 3 и 6, соответствуя ключевым значениям 0, 3 и 6 соответственно. Глубина каждой хэш-группы равна 5.

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

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

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

Шаг 502, сохранение ключевого значения и соответствующих данных.

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

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

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

Шаг 504, определение того, превышает ли количество добавлений предварительно заданного шагового значения предварительно заданное пороговое значение. Если количество добавлений превышает предварительно заданное пороговое значение, то процесс завершается. Если количество добавлений не превышает предварительно заданное пороговое значение, то осуществляется переход на шаг 501.

На этом шаге к произведению предварительно заданного шагового значения и количества добавлений применяется операция модуля по количеству N базовых модулей хранения, и остаток операции модуля по N равен 0. То есть, предварительно заданное шаговое значение умножается на количество добавлений, затем результат произведения берется по модулю количества N базовых модулей хранения, и остаток операции модуля равен 0. Формула следующая:

Key mod N=(Key+m∗step)modN=0, или

(m∗step)modN=0

При этом: Key - ключевое значение, соответствующее сохраненным данным; N - количество базовых модулей хранения; m - предварительно заданное количество раз, которое может быть добавлено к шаговому значению (step); step - предварительно заданное шаговое значение.

После этого процесс в соответствии со способом сохранения данных с использованием хэширования завершается.

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

В соответствии с вариантом осуществления настоящего изобретения, когда существующий объем хранения данных должен быть увеличен в параллели, например, при увеличении количества параллельных базовых модулей хранения, потребуется обеспечить только то, чтобы количество добавленных базовых модулей хранения было кратно количеству начальных базовых модулей хранения. Причем операция модуля, осуществляемая над ключевым значением, соответствующим подлежащим сохранению данным, использует обновленное количество базовых модулей хранения. Например, если количество L базовых модулей хранения возрастает каждый раз с помощью удвоения, может быть использовано следующее уравнение: (m∗step)mod(2n∗L)=0 (n=0, 1, 2, 3…). Шаговое значение «step» может быть определено тогда на основе этого уравнения. После определения шагового значения также может быть определено решение для увеличения места для данных в параллели, тем самым эффективно удовлетворяя потребности по параллельному наращиванию места для хранения данных.

Последующие описания иллюстрируют процесс обращения к данным.

На фиг.6 показана диаграмма процесса обращения к данным в соответствии с настоящим изобретением. Как показано на фиг.6, процесс включает в себя:

Шаг 600, получение запроса обращения и определение, содержит ли запрос обращения данные или идентифицированное ключевое значение. Если запрос обращения содержит данные, осуществляется переход на шаг 601. Если запрос обращения содержит идентифицированное ключевое значение, осуществляется переход на шаг 611.

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

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

Шаг 602, получение базового модуля хранения, соответствующего ключевому значению.

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

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

Шаг 604, возврат сообщения ошибки обращения и завершение процесса.

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

Шаг 605, определение того, имеют ли сохраненные данные, соответствующие ключевому значению, установленный флаг конфликта. Если данные не имеют установленного флага конфликта, осуществляется переход на шаг 606. В обратном случае осуществляется переход на шаг 607.

Шаг 606, возврат сообщения об успешном обращении, включающего данные, соответствующие ключевому значению.

Шаг 607, добавление предварительно заданного шагового значения к ключевому значению, соответствующему данным обращения.

На этом шаге Key=Key+step. После добавления к ключевому значению, соответствующему данным обращения, предварительно заданного шагового значения, определяют, имеют ли сохраненные данные, соответствующие ключевому значению обновленному с использованием добавления шагового значения, установленный флаг конфликта.

Шаг 608, определение того, что количество добавлений предварительно заданного шагового значения превысило предварительно заданное пороговое значение. Если количество добавлений превысило предварительно заданное пороговое значение, осуществляется переход на шаг 609. В противном случае осуществляется возврат на шаг 603.

Шаг 609, возврат сообщения ошибки обращения и завершение процесса.

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

Шаг 612, осуществление поиска для определения того, содержит ли таблица хэширования идентифицированное ключевое значение. Если таблица хэширования не содержит идентифицированное ключевое значение, осуществляется переход на шаг 613. В обратном случае осуществляется переход на шаг 614.

Шаг 613, возврат сообщения ошибки обращения и завершение процесса.

Шаг 614, возврат сообщения об успешном обращении, включающего данные, соответствующие идентифицированному ключевому значению.

После этого процесс обращения к данным завершается.

Как описано выше, в соответствии с вариантами осуществления настоящего изобретения способ обращения к данным использует распределенный алгоритм хэширования. Во-первых, идентификатор базового модуля хранения выбирается на основе ключевого значения, соответствующего данным обращения; затем осуществляется поиск и обращение к таблице хэширования в соответствующем базовом модуле хранения. Таким образом, сложность запроса может быть существенно снижена, и скорость доступа к данным может быть повышена. Для запроса обращения к данным, когда имеется конфликт хэширования, сложность запроса равна O(m), где m - количество добавлений предварительно заданного шагового значения. Скорость ответа на обращение значительно возрастает. Кроме того, для запроса обращения с идентифицированным ключевым значением сложность запроса равна O(1).

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Способ по п. 2, отличающийся тем, что после умножения предварительно заданного шагового значения на количество добавлений и осуществления операции модуля над результатом умножения на количество базовых модулей хранения остаток операции модуля равен 0.

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

5. Способ по любому из пп. 1-3, отличающийся тем, что дополнительно включает:
получение ключевого значения, соответствующего запросу обращения, на основе запроса обращения;
осуществление операции модуля над полученным ключевым значением по количеству базовых модулей хранения и на основе задающего соотношения между идентификаторами базовых модулей хранения и операции модуля по L получение базового модуля хранения, соответствующего ключевому значению; и
осуществление поиска в таблице хэширования базового модуля хранения с целью получения данных, к которым нужно обратиться.

6. Способ по п. 5, отличающийся тем, что получение ключевого значения, соответствующего запросу обращения, дополнительно включает:
получение запроса обращения;
определение того, содержит ли запрос обращения данные или идентифицированное ключевое значение;
когда запрос обращения содержит данные, вычисление ключевого значения, соответствующего данным обращения; и использование ключевого значения в качестве ключевого значения, соответствующего запросу обращения; а
когда запрос обращения содержит идентифицируемое ключевое значение, использование идентифицированного ключевого значения в качестве ключа, соответствующего запросу обращения.

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

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

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

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

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