De-dupe機能概要

  データ・デデュプリケーション(De-dupe)
  De-dupe機能概念
  対象データの分割方式
  同一性の判定方法
  インデックスの情報格納と管理

データ・デデュプリケーション(Data Deduplication)の deduplication は「複製」を表す duplication の前に「隔離」とか「除去」を現すde が付いた言葉です。同じように de が付く言葉では debug が(業界的に)有名です。"deduplication"でひとつの単語として成立しているのですが、de を意識して "de-duplication" という記述が用いられることも多く見られます。

日本語での標記は「重複除去」や「重複除外」などいくつかの使われ方がされています。 一度データを溜め込んで処理する方式の製品では「重複除去」があっているし、溜め込む途中で処理する製品は「重複除外」があっているように思えますが、一般的に「重複排除」が浸透してきています。

JDSFでの記述は de を区別するとともに短縮して "De-dupe" 、日本語で「重複排除」を使用することにいたしました。


データ・デデュプリケーション
De-dupe機能は格納もしくは保持するデータ容量を少なくする技術です。同様の機能にデータ圧縮やシングル・インスタンス機能などがありますが、データを細分化して処理する De-dupe機能はより進化したデータ効率化技法として注目を集めています。

格納するデータを少なくする技術
データ圧縮 先頭から読み込んだときのデータの繰り返しを認識
シングル インスタンス ファイル単位の重複を認識
データ・デデュプリケーション 分割したブロック単位の重複を認識

◆バックアップシステム用途とは限らない
◆インデックス情報がないと元に戻せない
De-dupe機能概念

De-dupe機能の処理には3つの特徴的な処理があります。

①対象データの分割

②同一性の判定

③インデックス情報の格納と管理

De-dupe機能は格納対象データを特定のルールに従って分割することが特徴的です。分割されたブロックは元データに復元するためのインデックスとあわせて管理されます。

また、データブロック毎に自分が保持しているデータと同一かどうかの判定を行います。新規のデータブロックは、インデックスとともに格納され、同一のブロックはインデックスのみの格納を行いうことで、容量の削減を実現します。

それぞれの処理において各社各様の方式を用い製品の特徴をうたっているため、甲乙つけがたい多くの製品が世の中に出回る現状となっています。

De-dupe機能概念
対象データの分割方式

De-dupe機能の処理を大雑把に分類して見ましょう。

対象のデータを特定のブロックに分割し、ブロック単位に重複の判定を行なうことがDe-dupe機能の特徴ですが、ブロックの分割方法は大きく2つに区別されます。

①固定長型

②可変長型

固定長型は文字通り決まったサイズに分割していくため、負荷の軽い処理となります。しかし、対象データがデータの挿入により更新された場合は、それ以降のデータブロックの重複排除効果が下がってしまう可能性があります。

可変長型は特定の区切り方のルールに従って分割する方法です。ルールについて情報を公開している製品は今のところ見当たりません。バックアップイメージのような大きなデータを処理対象とする場合は非常に有効な手段となります。

固定長型 可変長型
決まったサイズに対象データを分割し処理を行う 数KByte~数百KByte
特定の区切りルールに従い様々なサイズに分割 平均 数十KByte程度
データの挿入に弱い データの挿入に強い
比較的処理が軽い  
同一性の判定方法

分割した各ブロックを重複排除するための判定方法もいくつかの方式が採用されています。

①ハッシュベース方式

②バイナリ比較方式

③独自技術方式

④複数組み合わせ方式

ハッシュベース方式は汎用的なハッシュ算出ロジックを使用してブロックごとのハッシュキー(フィンガープリントなどとも呼ばれます)を作成し比較する方式です。

バイナリ比較方式は実データをバイナリレベルで比較する方式です。

独自技術方式は汎用的なハッシュ算出ロジックを利用しないで、何らかのダイジェストキーを作成する方式となります。

複数組み合わせ方式は上記の方式を組み合わせ、何段階かに分けて処理を行なう方式です。例えば、ハッシュキーで同一だったものに対してさらにバイナリ比較するといった処理になります。

ハッシュベース方式
MD5やSHA-1などの汎用の演算方式でハッシュ値 (フィンガープリント)を求め、比較する方式
バイナリ比較方式
実データを比較する方式
独自技術方式
上記のどちらでもない独自の比較方式
複数組み合わせ方式
上記の複数の方式を組み合わせて比較する方式

インデックスの情報格納と管理

De-dupe機能では、分割したブロックとそのハッシュキーと、実データのブロック構成のインデックスを管理する必要があります。管理方式やその検索エンジンは各社各様で、分類のしようがありませんが、インデックスの管理において、「グローバル・デデュープ」という言葉が使われることがあります。

De-dupeシステムを増強しようと考えた場合、容量増加はディスクエンクロージャの追加で済みますが、処理能力の増加はDe-dupeヘッド(コントローラと呼ぶのか?)を増設する必要が出てきます。この場合、インデックス管理が独立してしまうと、同じデータでも再度格納しなければならなくなります。De-dupeヘッド間で情報がやり取りできれば、同一ブロックの重複した保持が筐体間でも防ぐことが出来ます。

各社の製品で「グローバル」という言葉をいろいろな意味で使用するケースがありますが、JDSFでは「グローバル・デデュープ」を上記のように解釈しています。


通常は… グローバル・デデュープ
アプライアンス製品では筐体単位にインデックス情報を管理する。 筐体同士が情報をやり取りし、共通のインデックス情報を管理する。
筐体追加すると、新規にインデックスを管理し始める必要がある。

処理能力増強に伴う筐体追加でも重複排除率をそのまま維持できる。
(参考: Storage Magazine Sep 2008)