DFSとは？深さ優先探索（Depth‑First Search）と分散ファイルシステム（Distributed File System）の違いと実用例
エバープレイ編集部はじめに — 「DFS」とは何を指すのか
ITの文脈で「DFS」と書かれている場合、代表的に以下の2つの意味で使われます。文脈によって指す対象が全く異なるため、本稿では両方を取り上げて解説します。
- Depth-First Search（深さ優先探索） — アルゴリズム／グラフ探索法
- Distributed File System（分散ファイルシステム、または製品名としての DFS）— ストレージ／ファイル共有の仕組み
1. DFS（Depth‑First Search：深さ優先探索）
概要
深さ優先探索（DFS）は、グラフや木の各頂点を「深く」探索していく基本的な探索アルゴリズムです。スタック（再帰呼び出しは暗黙のスタック）を使って、隣接する未訪問ノードを優先的に辿ります。幅優先探索（BFS）と対になる基本テクニックの一つで、探索順序や到達性の判定、サイクル検出、トポロジカルソート、強連結成分の抽出など多くのアルゴリズムの基礎です。
動作原理（簡潔な説明）
任意の開始ノードから以下を繰り返します：
- 現在のノードを訪問済みとしてマークする
- そのノードの未訪問の隣接ノードがあればそのノードへ移動（再帰的に続ける）
- 隣接ノードがなければ一つ前のノードに戻り、残りの隣接ノードを試す（バックトラック）
疑似コード（再帰版）
function DFS(node):
visited[node] = true
for each neighbor in adjacency_list[node]:
if not visited[neighbor]:
DFS(neighbor)
計算量
- 時間計算量：隣接リスト表記の場合 O(V + E) — 各頂点と各辺を最大一度ずつ処理
- 空間計算量：O(V) — 訪問配列＋再帰スタック（最悪で深さが V）
- 隣接行列を用いる場合は時間 O(V^2)
主な応用例
- 到達可能性の判定（あるノードに到達できるか）
- サイクル検出（有向グラフのバックエッジ検出）
- トポロジカルソート（有向非巡回グラフでの順序付け、DFSの終了時刻を利用）
- 強連結成分（Kosaraju法やTarjan法はDFSに依存）
- 迷路の自動生成や解法（バックトラッキング）
実装上の注意点とバリエーション
- 再帰深度の制約：言語の再帰深度を超えるとスタックオーバーフローするため、深いグラフでは明示的なスタックを使った反復版を使う
- 順序依存性：隣接ノードの列挙順で探索順が変わる。結果（例えばトポロジカルソートの順序）に影響する
- 無向グラフでは親ノードに戻る際に誤ってサイクル判定しないよう親管理が必要
- 逆辺・横辺・木辺の分類はアルゴリズム解析に有用
2. DFS（Distributed File System：分散ファイルシステム）
概要
分散ファイルシステム（Distributed File System, DFS）は、複数のサーバ・ノードにまたがってファイルとメタデータを配置し、利用者やアプリケーションに一貫したファイルシステム（名前空間）を提供する仕組みです。目的はスケーラビリティ、可用性、耐障害性、性能向上などです。代表的な実装例には HDFS（Hadoop Distributed File System）、Ceph、GlusterFS、Lustre、Microsoft DFS（DFS Namespaces + DFS Replication）などがあります。
構成要素と基本的な役割
- 名前空間（Namespace）：ファイル・ディレクトリの論理的な配置とアクセスパス（例：/data/projectA/...）
- メタデータサーバ（NameNode、MDS など）：ファイルのメタ情報（ディレクトリ構造、ブロック配置、所有権、アクセス権）を管理
- データノード（DataNode、OSD など）：実際のデータブロック・オブジェクトを保存
- クライアント：名前解決後、直接データノードに読み書きすることが多い（パフォーマンスのため）
レプリケーションと一貫性モデル
分散ファイルシステムではデータを複製し冗長性を確保しますが、複製方法によって一貫性・遅延特性が変わります。
- 同期レプリケーション：書き込みが複製先の同意を得てから完了。強い一貫性を提供するが遅延が大きくなりがち
- 非同期レプリケーション：書き込み完了を早くするために複製を遅延。性能は良いが最終的整合性（eventual consistency）となる場合がある
- マスター/スレーブ（リーダー/フォロワ）方式とマルチマスター方式：管理と競合解決の設計が異なる
代表的な実装例と特徴
- HDFS（Apache Hadoop）：
- NameNode（メタデータ）とDataNode（ブロック）で構成。データはブロック単位で複製（デフォルト複製係数 3）
- ビッグデータ処理向けに最適化（大きなファイル、連続アクセス）
- Ceph：
- オブジェクトストレージ基盤（RADOS）上にファイルシステム（CephFS）を構築。高可用で自己修復機能を持つ
- GlusterFS：
- 分散ボリュームを簡易に作れる。拡張性と運用の容易さを重視
- Microsoft DFS（Windows DFS）：
- DFS Namespace（論理的なフォルダツリー）と DFS Replication（ファイルレベルのレプリケーション）で構成
- Active Directory と連携し、ファイルサーバ群を単一の名前空間で提供
設計上のトレードオフ（CAPと運用面）
分散システム設計では CAP 定理（Consistency, Availability, Partition tolerance）が基本的な制約として効いてきます。ネットワーク分断や遅延がある状況下で、どの属性を優先するかによって設計が変わります。例えば、金融系の重要データは強い一貫性を選び、最も可用性や応答速度が必要なサービスは最終整合性やリスク管理を組み合わせます。
運用上のポイントとベストプラクティス
- メタデータの冗長化と監視：NameNodeやMDSの障害が全体に影響するため、冗長化と健全性監視が必須
- バックアップとリカバリ：レプリケーションは障害からの復旧を助けるが、論理的な誤削除やランサムウェア対策には別途バックアップ戦略が必要
- アクセス制御と認証：Active Directory、Kerberos、TLS などを用いて認証と通信の暗号化を行う
- ネットワーク設計：帯域と遅延を考慮した配置、データローカリティの最適化（HDFS はデータローカリティを重視）
- 監視とメトリクス：IOPS、レイテンシ、再同期待ち、ストレージ使用率などを常時監視
DFS（アルゴリズム）と DFS（分散FS）の関係・混同しやすい点
同じ略称ですが、背景や用途は大きく異なります。ただし開発や運用の現場では両者が交差する場面もあります。例えば、分散ファイルシステム内部のグラフ構造の探索や、ファイルの依存関係解析に DFS（深さ優先探索）が使われることがあります。用語は文脈で明確にすることが重要です。
まとめ（ポイントのおさらい）
- DFS は文脈で「深さ優先探索（Depth‑First Search）」か「分散ファイルシステム（Distributed File System）」を指す。混同に注意する
- 深さ優先探索はグラフアルゴリズムの基礎で、計算量は O(V+E)、再帰・スタックで実装可能。強連結成分やトポロジカルソートなど多くの応用がある
- 分散ファイルシステムはスケーラビリティ／可用性／耐障害性を目的に設計され、名前空間・メタデータ・データノード・レプリケーションなどの要素で構成される。HDFS, Ceph, GlusterFS, Microsoft DFS などが代表例
- 設計では一貫性モデル、レプリケーション方式、監視・バックアップ、セキュリティを慎重に検討する必要がある
