WinFS и прочие DBFS

 
+
-
edit
 

Balancer

администратор
★★★★☆
Мой постинг в Новости - OpenSource - Database File System for Linux

Может и тут кому-то будет интересно.




Файловые системы с DB (не знаю, как в этой, читать лениво, но аналогичные WinFS и ZopeDB) предназначены не для отмены файлов и папок, а для расширения понятия файла до понятия "объект". У каждого файла кроме контента должны быть атрибуты. Это могут быть примитивные атрибуты ОС - R/O, exec и т.п. Это могут быть расширенные атрибуты, введённые в формат - ID-тэги, EXIF и т.п. второе - это костыли, которыми пытаются поправить убогость нынешних FS.

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

Вот нужно мне, скажем, для Plain/text-файлов хистори общения указывать, например, имена "от кого" и "кому". Сейчас - надо изобретать свой формат. В DBFS - можно будет просто ввести два поля для нового типа, наследуемого от базового.

А про то, что DB - "тормоза" - это говорят люди, не работавшие реально с контентом на нормальных БД. Сколько будет занимать сканирование хотя бы по именам каталога с 1 млн файлов? А в проавильно спроектированной ДБ - от долей секунд до секунд. Нынешние FS совершенно не занимаются никакой индексацией и т.п...

Кстати, с нормальной DBFS можно будет, наконец, отказаться от идиотской древовидной структуры каталогов перейдя, наконец, к естественной из направленных графов. Т.е. когда у каталога, скажем, может быть больше одного родителя. "Авианосец" может позиционироваться и в разделе "Море" и в разделе "Авиация". В нынешних FS это невозможно. В новых DBFS - достаточно будет к полям типа "Childs" добавить поля "Parents".
 
+
-
edit
 

Balancer

администратор
★★★★☆
Вдогонку, тем, кто не любит теорию, а предпочитает практику.

Вот прямо мой текущйи пример на экранеь. Берём iTunes (раз не любим MS). У него, на ряду с прочим, есть такая приятная фича, как играть MP3, в которых в ключевых тэгах есть фрагмент, вбитый в строке поиска в шапке проигрывателя. Т.е. прямо во время игры вписываем там "beat" в поле ввода, остаётся список песен Beatles (ну, возможно, ещё что-то попадёт, если больше писать лень). Чтобы всё это работало быстро и без тормозов, iTunes предварительно сканирует все каталоги с целью сбора информации о всех MP3 в единую медиатеку. Которую хранит внутри себя в БД. А если этой БД будет сразу файловая система? Удобно и программистам и пользователям (одна "база" может в разных программах работать. А, например, картинки - обложки альбомов можно будет линковать прямо в параметры песни)

Второй пример - ближе сообществу Linux'оидов (iTunes, кажется, только под OSX и Win32 есть). Делаю я CMS для своего сайта. Именно на нормальной графовой системе. Основные атрибуты объектов хранятся в БД. Скажем, чтобы ширина и высота картинки были в БД, и не требовалось для их вычисления файл открывать. Или чтобы описание файла шло не где-то там, а прямо в его параметрах. Да, отчасти велосипед изобретаю, тот же Zope-DB есть, но мне Python и Zope не подходят. Была бы на сервере DBFS - я бы не потратил на разработку такой системы с нуля около полугода (хоть и ненапряжной) работы. А просто воспользовался бы возможностями OS. Но пока - такого нет.

Ждём-с... :) (и лепим на время ожидания свои костыли)
 

61284

опытный
★★
может я штото не понял но вроде и чичаз ништо не мешает превратить древовидную структуру в путаницу, к примеру

mkdir -p ./Вооруженные\ силы/Море/Авианосец
mkdir ./Вооруженные\ силы/Авиация
ln -s ../Море/Авианосец ./Вооруженные\ силы/Авиация/Авианосец
ln -s ../Море/Авианосец ./Вооруженные\ силы/Авиация/Авианесущий\ Корабль
ln -s Авианосец ./Вооруженные\ силы/Море/Авианесущий\ Корабль

и вот Авианосец виден в 'Вооруженные силы/Море' и в 'Вооруженные силы/Авиация' под именами 'Авианосец' и 'Авианесущий Корабль'
 
+
-
edit
 

Balancer

администратор
★★★★☆
Находясь внутри такого "Авианосца" не увидишь, что он относится и к "ВМФ" и к "Авиации".

Симлинки - это как раз одни из костылей.

Тем более, что пример этот - только одна из множества возможностей использования доп. атрибутов

Сколько сейчас времени занимает поиск по всему диску всех файлов, отредактированных в заданном диапазоне времени? А с DBFS - это доли секунды. Ну, секунды, если файлов много, а машина слабая.
 
+
-
edit
 

Mishka

модератор
★★☆
Ром, при таком подходе, у тебя легко выходят орграфы с циклами со всеми вытекающими последствиями. Т.е. можно говорить о простом графе.

ЗЫ Ограф без циклов эквивалентен лесу деревьев.
 
+
-
edit
 

Balancer

администратор
★★★★☆
Mishka>Ром, при таком подходе, у тебя легко выходят орграфы с циклами со всеми вытекающими последствиями. Т.е. можно говорить о простом графе.

У меня сейчас Авиабаза на таком принципе устроена :D
Ну и пусть циклы, жалко что ли?

Проблема циклов вылезает только при наследовании параметров.

Я для себя решил так - ни один из предков не должен оказаться ребёнком. Т.е. если при рекурсивном просмотре вверх по родителям мы натыкаемся на своего ребёнка, до этого не найдя наследуемого параметра - вся цепочка бракуется.

Mishka>ЗЫ Ограф без циклов эквивалентен лесу деревьев.

Это как? Т.е. - "лес деревьев"?
У каждого узла дерева таки всегда один родитель. Кажется, по определению (лень книжки доставать).
 
+
-
edit
 

Mishka

модератор
★★☆
Balancer>У меня сейчас Авиабаза на таком принципе устроена :D
Balancer>Ну и пусть циклы, жалко что ли?
Balancer>Проблема циклов вылезает только при наследовании параметров.

Проблема весьма существенна при любой рекурсивной операции (например, обходе). Становиться более существенно при замене рекурсии на циклы, т.к. нужна память для обнаружения циклов. Задача нахождения-обнаружения циклов, если мне не изменяет память, NP-полная.

Balancer>Я для себя решил так - ни один из предков не должен оказаться ребёнком. Т.е. если при рекурсивном просмотре вверх по родителям мы натыкаемся на своего ребёнка, до этого не найдя наследуемого параметра - вся цепочка бракуется.

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

Mishka>>ЗЫ Ограф без циклов эквивалентен лесу деревьев.
Balancer>Это как? Т.е. - "лес деревьев"?
Balancer>У каждого узла дерева таки всегда один родитель. Кажется, по определению (лень книжки доставать).[»]

Лес деревьев - это набор деревьев. Все деревья могут быть отображены в один орграф. Он будет без циклов. И обратно, любой орграф может быть разложен в лес деревьев. Понятно, что есть минимальное покрытие или все возможные комбинации.
 
+
-
edit
 

Balancer

администратор
★★★★☆
Mishka>Лес деревьев - это набор деревьев. Все деревья могут быть отображены в один орграф. Он будет без циклов. И обратно, любой орграф может быть разложен в лес деревьев. Понятно, что есть минимальное покрытие или все возможные комбинации.

Поясни на пальцах, сам не соображу, как при этом подходе у одной ноды может быть больше одного родителя и при этом мы будем избавлены от возможности организации циклов?

Да, ещё забыл - у меня проверка на этапе связывания - невозможно установить линк между парой предполагаемый_родитель - предполагаемый_ребёнок если среди родителей предполагаемого_родителя есть предполагаемый_ребёнок.

Т.е. при реальной работе циклов уже нет.
 
+
-
edit
 

Mishka

модератор
★★☆
Balancer>Поясни на пальцах, сам не соображу, как при этом подходе у одной ноды может быть больше одного родителя и при этом мы будем избавлены от возможности организации циклов?
[»]

Возможность не устраняется, а вот конкретный орграф без циклов. Т.е. не произвольный орграф, а заданный. Пример - ссылки forward. Множественное наследование в С++.

 
+
-
edit
 

Mishka

модератор
★★☆
Balancer>Да, ещё забыл - у меня проверка на этапе связывания - невозможно установить линк между парой предполагаемый_родитель - предполагаемый_ребёнок если среди родителей предполагаемого_родителя есть предполагаемый_ребёнок.
Balancer>Т.е. при реальной работе циклов уже нет.[»]

Правильно - ты проверил всех родителей и все пути - т.е. полный перебор.
 
+
-
edit
 

Balancer

администратор
★★★★☆
Mishka>Правильно - ты проверил всех родителей и все пути - т.е. полный перебор.

Естественно. Просто делается один раз, при добавлении элемента, а не каждый - при извлечении данных :)
 
+
-
edit
 

Mishka

модератор
★★☆
Mishka>>Правильно - ты проверил всех родителей и все пути - т.е. полный перебор.
Balancer>Естественно. Просто делается один раз, при добавлении элемента, а не каждый - при извлечении данных :)[»]

За это ты платишь памятью. Бесплатных пироженых не бывает. :rolleyes: И у тебя должен быть связанный двойной связью (double link) граф, т.к. ты хочешь ходить в обе стороны - из родителя ты хочешь знать всех детей, а из детишек - всех родителей. Можно говорить о матрице смежности или другой, но они очень уж разряженные получаются. Можно организовывать двунаправленными списками, но накладные расходы достаточно велики. Есть и другие методы организации неплотных массивов.
 
+
-
edit
 

Balancer

администратор
★★★★☆
Ну, память, опять же, только в первый раз нужна, при организации связи.

А двунаправленные связи перестали быть накладными (для меня) ещё во времена 486 :) С тех пор всегда их и использую.
 

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru