Способ и устройство обработки объекта данных

Способ и устройство обработки объекта данных

Иллюстрации

Показать все

Реферат

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

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

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

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

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

Предполагаемая длина является ключевым параметром определяемого содержимым способа деления на фрагменты (Определяемое содержимым деление на фрагменты, CDC) для управления гранулярностью при делении на фрагменты. В общем, способ CDC подает на выход последовательность фрагментов переменной длины для конкретного объекта данных, при этом длины различных фрагментов статистически подчиняются закону нормального распределения и предполагаемую длину используют для регулировки среднего значения нормального распределения. В общем, среднее значение нормального распределения представлено средней длиной фрагмента. Так как случайная величина принимает среднее значение с наибольшей вероятностью при нормальном распределении, среднюю длину фрагмента также называют пиковой длиной, и она может быть равна предполагаемой длине в идеальных условиях. Например, в CDC способе контрольную сумму f (w байт) данных в скользящем окне вычисляют в реальном времени. Когда определенные биты f (w байт) соответствуют заранее заданному значению, позицию скользящего окна выбирают как границу фрагмента. Так как обновление содержимого данных может привести к случайному изменению контрольной суммы, если условие f(w байт) & 0×FFF=0 установлено как условие соответствия, где & является операцией побитового И в двоичном поле, a 0×FFF является шестнадцатеричным представлением 4095, одно соответствие контрольной сумме может теоретически произойти в 4096 случайных изменениях f(w байт), то есть граница фрагмента может быть найдена каждый раз при перемещении вперед скользящего окна на 4КБ (4096 байт). Длина фрагмента при идеальных обстоятельствах является предполагаемой длиной фрагмента (Предполагаемая длина фрагмента) в CDC способе и для краткости называется предполагаемой длиной.

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

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

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

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

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

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

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

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

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

Фиг. 1 - вид, показывающий блок-схему варианта осуществления способа обработки объекта данных;

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

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

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

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

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

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

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

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

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

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

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

В способе, предложенном в варианте осуществления настоящего изобретения, объект данных может быть разделен на фрагменты данных, а фрагменты данных, полученные после деления, могут быть использованы как блоки дедупликации данных, так что объект данных может быть сохранен или передан по назначению, при этом без потери данных уменьшается использование памяти для хранения. Конечно, фрагмент данных, выработанный при делении, может быть в дальнейшем использован для целей, отличных от дедупликации данных. Вариант осуществления настоящего изобретения включают в себя следующее: этап (а), вводят объект данных (Объект данных) в устройство деления на фрагменты, при этом объект данных может поступать из памяти, находящейся как в устройстве деления на фрагменты, так и вне указанного устройства, например, объект данных может быть файлом или потоком данных, при условии удовлетворения требованию операции дедупликации, которое не ограничено в варианте осуществления настоящего изобретения; этап (б), делят объект данных на один или более блоков (Блоки), оценивают коэффициент сжатия каждого блока путем использования способа взятия выборок, делают запрос в таблицу соответствия политики деления на фрагменты и агрегируют в один сегмент (Сегмент) данных соседние последовательные блоки, коэффициенты сжатия которых принадлежат одному и тому же диапазону коэффициентов сжатия, при этом выборочный коэффициент сжатия является мерой сжимаемости фрагмента данных и выборочный коэффициент сжатия совпадает с коэффициентом сжатия блока, когда взятие выборок осуществляют на всем блоке; этап (в), делают запрос в таблицу соответствия политики деления на фрагменты для каждого сегмента данных, выбирают предполагаемую длину в соответствии с диапазоном коэффициентов сжатия и диапазоном длин, которые соответствуют сегменту данных, и делят сегмент данных на последовательности фрагментов (Фрагмент) в соответствии с выбранной предполагаемой длиной, что делают с использованием определяемого содержимым способа деления на фрагменты; и этап (г), сращивают соседние фрагменты, которые находятся на разных сегментах данных, и вычисляют значение хэш-функции для каждого фрагмента для дедупликации данных, при этом этап сращивания не является обязательным и значение хэш-функции может быть вычислено непосредственно без сращивания. На этапе (б) объект данных снова делят на последовательности сегментов данных с использованием информации о выборочном коэффициенте сжатия последовательности блоков. Может присутствовать несколько способов деления, например, в другом способе реализации: на этапе (б) можно ссылаться не на диапазон коэффициентов сжатия, а вместо этого объединять в один сегмент данных соседние последовательные блоки, для которых разница между значениями выборочных коэффициентов сжатия меньше заданного порога.

Вариант 1 осуществления изобретения

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

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

Коэффициент сжатия используют для измерения степени, до которой могут быть сжаты данные, и коэффициент сжатия вычисляют следующим образом: коэффициент сжатия = объем сжатых данных/исходный объем данных. Способ оценки коэффициента сжатия следующий: извлекают сегмент выборочных данных для каждого блока, что делают на основе доли S выборки, сжимают выборочные данные с использованием некоторого алгоритма сжатия данных, например, алгоритма LZ сжатия без потерь и алгоритма RLE кодирования, вычисляют коэффициент сжатия, и используют коэффициент сжатия для выборки в качестве коэффициента сжатия блока, из которого делали выборку. Более высокая доля выборки означает, что коэффициент сжатия выборки будет ближе к фактическому коэффициенту сжатия блока, из которого делали выборку.

Для сжимаемого сегмента данных его коэффициент сжатия в общем меньше 1; для несжимаемого сегмента данных, из-за добавления служебных символов метаданных, таких как поле описания, длина сегмента данных после сжимающего кодирования может быть больше исходной длины данных, в результате чего коэффициент сжатия может быть больше 1. Ввод коэффициента сжатия включает в себя ряд диапазонов коэффициентов сжатия, при этом пересечение различных диапазонов коэффициентов сжатия пусто и объединение всех диапазонов коэффициентов сжатия представляет собой полный диапазон значений коэффициента сжатия [0, ∞).

Термин «характеристика коэффициента сжатия» относится к использованию коэффициента сжатия как параметра для агрегации блоков. Если коэффициент сжатия или значение, полученное после операции над коэффициентом сжатия блока, удовлетворяет заранее заданному условию, блок соответствует характеристике коэффициента сжатия. Более конкретно, характеристика коэффициента сжатия может быть диапазоном коэффициентов сжатия, а именно, диапазоном для коэффициента сжатия, и также может быть порогом разности между значениями коэффициентов сжатия соседних блоков. Как ясно из таблицы 1, в качестве характеристики коэффициента сжатия используют диапазон коэффициентов сжатия. Объект данных делят на семь блоков: блоки от 1 до 7. Благодаря взятию выборки для каждого блока и оценке их коэффициентов сжатия, получают выборочный коэффициент сжатия, например, выборочный коэффициент сжатия блока 1 равен 0,4, а выборочный коэффициент сжатия блока 2 равен 0,42; каждый выборочный коэффициент сжатия принадлежит одному диапазону коэффициентов сжатия, например, коэффициент сжатия, равный 0,4, принадлежит диапазону [0, 0,5) коэффициентов сжатия, а коэффициент сжатия, равный 0,61, принадлежит диапазону [0,5, 0,8) коэффициентов сжатия. Так как каждый блок соответствует одному выборочному коэффициенту сжатия, то также можно считать, что каждый блок принадлежит одному диапазону коэффициентов сжатия; блоки, которые принадлежат одному диапазону коэффициентов сжатия агрегируют в один сегмент данных и, следовательно, блок 1 и блок 2 могут быть агрегированы в сегмент 1 данных, блок 3, блок 4 и блок 5 могут быть агрегированы в сегмент 2 данных, а блок 6 и блок 7 могут быть агрегированы в сегмент 3 данных.

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

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

При делении сегмента данных на фрагменты данных, необходимо найти границу фрагмента данных. Фрагмент данных находится между соседними границами.

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

Как ясно из примера таблицы 2, диапазон значений коэффициентов сжатия разделен на три диапазона коэффициентов сжатия: [0, 0,5), [0,5, 0,8) и [0,8, ∞). Эти диапазоны коэффициентов сжатия не пересекаются и выборочный коэффициент сжатия каждого сегмента данных принадлежит одному диапазону коэффициентов сжатия, что также можно понимать как то, что каждый сегмент данных соответствует одному диапазону коэффициентов сжатия. Кроме того, диапазон значений длин сегмента данных поделен, по меньшей мере, на один диапазон длин. Эти диапазоны длин не пересекаются и, следовательно, каждый сегмент данных соответствует одному диапазону длин. Диапазон длин и диапазон коэффициентов сжатия совместно определяют предполагаемую длину сегмента данных. Например, если диапазон длин сегмента А данных составляет [0 МБ, 10 МБ), выборочный коэффициент сжатия сегмента А данных находится в диапазоне [0, 0,5) коэффициентов сжатия и предполагаемая длина, совместно определенная диапазоном [0 МБ, 10 МБ) длин и диапазоном [0, 0,5) коэффициентов сжатия, равна 32 КБ, то предполагаемая длина сегмента А данных равна 32 КБ. Аналогично, в соответствии с диапазоном длин, которому принадлежит длина сегмента В данных, и диапазоном коэффициентов сжатия, которому принадлежит выборочный коэффициент сжатия сегмента В данных, может быть получена предполагаемая длина сегмента В, равная 256 КБ. После получения предполагаемой длины, каждый сегмент данных может быть поделен на фрагменты данных в соответствии с предполагаемыми длинами. Например, сегмент А данных делят на фрагменты данных в соответствии с предполагаемой длиной, равной 32 КБ, а сегмент В данных делят на фрагменты данных в соответствии с предполагаемой длиной, равной 256 КБ, при этом «Б» в КБ является сокращением для байта (Байт), 1 КБ=1024 Байт и 1 МБ=1024 КБ.

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

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

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

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

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

Когда этап 12 содержит этап сращивания подпоследовательностей фрагментов, этап 13 могут осуществить до сращивания подпоследовательностей фрагментов, и также его могут осуществить после сращивания подпоследовательностей фрагментов.

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

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

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

Заметим, что на этапе 11 может быть использовано более одного способа деления на сегменты. Например, в другом варианте реализации, политика сегментации, используемая на этапе 11, может быть модифицирована следующим образом: агрегируют в один сегмент данных соседние последовательные блоки, для который разница значений выборочных коэффициентов сжатия меньше заданного порога. Другими словами, то, что разница значений выборочных коэффициентов сжатия меньше заданного порога, является характеристикой коэффициента сжатия. По-прежнему будем использовать таблицу 1 в качестве примера, где предполагается, что разницу значений выборочных коэффициентов сжатия, которая меньше значения 0,1, используют в качестве порога. Тогда 0,42-0,4<0,1 и, следовательно, блок 1 и блок 2 располагают в одном сегменте данных; и 0,53-0,42>0,1, и, следовательно, блок 3 и блок 2 не располагают в одном сегменте данных. По аналогии блок 1 и блок 2 располагают в первом сегменте данных, блок 3 и блок 4 располагают во втором сегменте данных, а блок 5, блок 6 и блок 7 располагают в третьем сегменте данных.

Вариант 2 осуществления изобретения

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

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

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

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

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

25: Агрегируют в сегмент данных последовательные блоки с одинаковой характеристикой коэффициента сжатия в соответствии с таблицей соответствия политики деления на фрагменты.

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

В этом варианте осуществления изобретения после осуществления этапа 26, обработка объекта данных завершена и достигнут эффект деления объекта данных на фрагменты данных. Последующие этапы 27, 28 и 29 являются дополнительным расширением способа обработки объекта данных.

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

28: Вычисляют в качестве контрольных сумм значения хэш-функций фрагментов.

29: Подают на выход фрагменты и контрольные суммы каждого фрагмента и, при желании, также могут б