DFS (Depth-First Search / Distributed File System)

Pojem DFS se v informatice používá ve dvou zcela odlišných významech:

Prohledávání do hloubky je algoritmus pro procházení grafů nebo stromových struktur. Strategií tohoto algoritmu je postupovat v jedné větvi co nejdále do hloubky, dokud nenarazí na konec (list) nebo na již navštívený uzel, a teprve poté se vrátit k nejbližšímu rozcestí (backtracking).

• Datová struktura: K implementaci se typicky používá zásobník (stack) nebo rekurze.
• Využití: Hledání cest v bludišti, topologické uspořádání, detekce cyklů v grafu.
• Složitost: $O(V + E)$, kde $V$ je počet vrcholů a $E$ počet hran.

Distributed File System je technologie, která umožňuje přistupovat k souborům rozptýleným na různých serverech tak, jako by byly uloženy na jednom lokálním disku. Uživatel vidí jednu logickou strukturu složek, i když fyzicky data leží na deseti různých strojích.

• NFS (Network File System): Klasika v Unixových systémech.
• Microsoft DFS: Součást Windows Serveru, která sjednocuje sdílené složky do jednoho jmenného prostoru (Namespace).
• HDFS (Hadoop Distributed File System): Navržen pro ukládání obrovských objemů dat (Big Data) napříč tisíci levných serverů.

• Škálovatelnost: Snadné přidání dalších serverů pro zvýšení kapacity.
• Redundance: Data mohou být replikována na více místech. Pokud jeden server vypadne, soubory jsou stále dostupné odjinud.
• Transparentnost: Uživatel nemusí vědět, na kterém konkrétním serveru je jeho soubor uložen.

Zajímavost: Algoritmus DFS se často přirovnává k procházení bludiště s nití (jako Ariadnina nit). Jdete pořád dál, a když narazíte na zeď, vracíte se po niti zpět, dokud nenajdete jinou odbočku.

Zpět na Algoritmy nebo Zpět na Architekturu