Теория хранения файлов на сервере

Первоначально данная статья была размещена на Хабре, но по комментариям в нее были внесены некоторые дополнения, развивающие и объясняющие идеи, изложенные в статье.

За последнее время мне пришлось активно работать с сайтами, которые большие объемы информации хранят в файловой системе. Это разнообразные сайты фото и файловых хостингов, а также сайты с загрузкой видео контента, некоторые сайты проектировались и программировались мной с нуля, некоторые переписывались, дописывались или "приводились в порядок".

Должен отметить, что хранение файлов в файловой системе является для многих программистов областью, которая проходит мимо их внимания.

Для начала дам небольшой обзор распространенных ошибок:

1. файл храниться в файловой системе под кириллическим названием. Собственно, происходит следующее: пользователь загружает файл под именем, скажем, "безымянный-1.jpg", программист с тем же именем запихивает его в каталог, в котором хранятся файлы. Надеюсь, не нужно объяснять какие проблемы это за собой может повлечь?

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

И третья самая распространенная ошибка:

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

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

1. директория не должна «тормозить», то есть в одной директории не должно храниться более 1000 файлов или каталогов (число взято с запасом). По данному пункту напомню, что каталог  файловой системы, можно рассматривать как файл со списком файлов, которые находятся в этом каталоге. Имея полный путь к файлу, мы должны просмотреть последовательно несколько файлов «каталогов», для того, что бы в последнем найти физический адрес (первый кластер нужного нам файла). Естественно, чем больше в каждом каталоге файлов и вложенных каталогов, тем больше времени занимает данная операция. Идеально, что бы весь список файлов содержащихся в одном каталоге, помещался в одном кластере на диске, что бы головка винчестера могла прочитать данный «файл-каталог» в «одно касание».

2. Имена файлов не должны повторяться. Наверное, данный пункт даже расшифровывать не нужно  - одинаковые имена совсем не говорят об одинаковом содержимом и наоборот.

3. Желательно не хранить две копии одного файла. Это не является большой проблемой, если мы храним картинки (хотя как сказать… пара тысяч повторяющихся картинок в хорошем качестве и пяти гигабайт как не бывало). Но при хранении на диске чего то более серьезного по объему повторяющиеся файлы уже являются большой проблемой (например, три четыре одинаковых дистрибутива линукса.

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

Начну с последнего требования не хранить две копии файла. Для определения целостности файла давно и вполне успешно используется md5 хеш для php,  эта задача решается функцией md5_file(filename), которая вычисляет MD5 хэш файла, имя которого задано аргументом filename используя алгоритм MD5 RSA Data Security, Inc. и возвращает этот хэш. Хэш представляет собой 32-значное шестнадцатеричное число.

Если два файла одинаковы  у них и хеш будет одинаков, если разные - то разный. Сейчас в меня «полетят камни» сопровождающиеся рассуждениями о коллизиях и ненадежности md5. Отвечу по порядку md5 не надежна? Но мы же не ставим задачу обмануть «вероятного противника»! Мы просто получаем уникальный идентификатор файла и все. А по поводу коллизий...  я не настаиваю на повторении моего метода один в один, используйте другую функцию. Только задумайтесь, два в двести пятьдесят шестой степени это - очень много! Если мне говорят, про возможность возникновения коллизий, я прошу человека привести пример двух строк или двух файлов, md5 хеш, которых одинаков... пока еще мне не было приведено такой пары  так, что возможность является чисто теоретической. Однако в комментариях на хабре мне привели две строки, которые дают одинаковый md5 хеш, что же один вариант возникновения коллизий теперь известен. Однако не предполагаю, что на практике это имеет действительно большое значение.

В качестве примера приведу обе строки:

d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a
085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70 

и 

d131dd02c5e6eec4693d9a0698aff95c2fcab5O712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a0 85125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e9
9f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70
Каждый из этих блоков даёт MD5-хеш, равный 79054025255fb1a26e4bc422aef54eb4.

Пункт второй – «имена файлов не должны повторяться, напрямую вытекает из третьего. Если в качестве имени файла на диске мы используем строку его md5 хеша, то имена файлов не повторяются (реальные имена файлов (те, которые загрузил пользователь), мы можем хранить в базе данных). В случае загрузки пользователями двух одинаковых файлов, мы  получаем у них одинаковые имена. И первое - файлы не будут дублированы, второе -  мы не беспокоимся по поводу имен в директориях.

Теперь чуть более сложно, по поводу хранения файлов на диске. Я создаю структуру вложенных каталогов, опираясь на имена файлов.  Здесь тоже полный простор для фантазии. Я ни в коем случае не призываю слепо копировать мой способ. Обычно я делаю два, три уровня вложенности каталогов. Первый уровень - это первые две буквы названия файла (не забыли, название файла это его md5 хеш!);второй уровень это третья и четвертая буквы…

Каждый уровень вложенности дает мне * на 256 каталогов.

То есть, если в один каталог я могу загрузить не более 1000 файлов, то при одном уровне вложенности я могу безопасно разместить на диске 256 000 файлов; при двух уровнях вложенности – 65 536 000; при трех – 16 777 216 000 и так далее.  Длинна строки md5 хеша позволяет нам сделать 16 уровней вложенности в каталогах. На мой взгляд, этого хватит для обеспечения работы самых емких дисков. Хотя, исходя из практика, обычно, и трех уровней хватает «за глаза» для проектов любой сложности.

И напоследок. В тех же комментариях на хабре мне прозрачно намекнули, что я «лью воду из пустого в порожнее», так как данные вещи всем и хорошо известны. Что же возможно это и так. На «моем счету» около 20 крупных переписанных или дописанных проектов, и я нигде не встречал подобной системы хранения файлов. Максимум на что хватало фантазии разработчиков, это именовать каталоги по дате, а в внутри них уже файлы по порядковому номеру. Это было на сайте одного интернет издания… издание на протяжении пяти лет (до попадания ко мне в руки) каждый день публиковало статьи и соответственно через пять лет количество каталогов содержащих файлы выросло до полутора тысяч. То есть вплотную приблизилось к границе, за которой начинается «торможение» по файловой системе. Как правило программисты торопятся сдать проект, не задумываясь о тех объемах информации, которые будут находится на сайте через год два или десять лет.

Comments