OSDev

для всех
Текущее время: 21 окт 2017, 06:21

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 11 мар 2015, 22:19 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1056
Для, dragon
dragon писал(а):
FAT без каких то улучшений сольёт, если добавить в одну директорию 100000000 файлов и попытаться поискать несколько файлов по имени (он и на миллионе сольёт, но пусть будет 100 млн., чтобы построить дерево поиска в памяти было нецелесообразно).

Кому сольёт? Насколько мне известно ни в одной из популярных ФС такая индексация не предусмотрена. В том же NFTS поиск линейный. И при просмотре папки строиться индекс из за чего операционная система тормозит.

Любой поиск это по сути индексация или другими словами накладные расходы.
Хотелось бы узнать где реально нужно 100 Миллонов файлов? И какие операции предполагаются с этой коллекцией файлов? Просто это объем сопоставим с мировыми библиотеками:
Библиотека Конгресса, - фонд 155,3 млн
Библиотека имени Ленина. - фонд 44,8 млн

Если нужен доступ по имени то поверх ФАТ можно сделать сортировку в каталоге по алфавиту и бинарный поиск. Это скорее вопрос администрирования ОС.

Я уже намекал, что если нам нужен поиск по ФС то оставить ключевые поля как выше. Как самый оптимальный. Дополнительные индексы предполагаю оставить на откуп администраторам/программистам.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 11 мар 2015, 22:33 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
pavia писал(а):
Насколько мне известно ни в одной из популярных ФС такая индексация не предусмотрена. В том же NFTS поиск линейный. И при просмотре папки строиться индекс из за чего операционная система тормозит.

Как-как? По слогам, пожалуйста.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 11 мар 2015, 23:04 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1056
А чего тут не понятного? Если взять любую или почти любую файловую систему. И провести эксперимент положить в один каталог кучу файлов. То при открытие файла OpenFile, операционная система будет тормозить, зависать. Связано это с тем что ни в одной ФС не предусмотрена оптимизация этого процесса. У ОС есть два пути решения:

1) Использовать примитивный алгоритм, который есть в любой реляционной СУБД когда та ищет записи в таблице. А именно запрос "Select". Так вот что делает СУБД? Ровно как и ОС+ФС одно и тоже. Это простой цикл от 0 до числа элементов в таблице каталога. К каждому элементу таблице применяется условие. В данном примере это простое условие сравнение двух строк имени файла элемента таблице и шаблона из поиска.
2) В более продвинутых ОС в памяти строится индекс(или индексный файл). Как правило этот индекс хранится в памяти ЭВМ. Записи в нём отсортированы. И поиск по такому индексу идёт уже не линейно, а бинарно. Что ускоряет поиск. И ещё для сжатия индекса используют представление в виде суффиксального-дерева.

Возвращаясь к примеру. Для 100 милилонов при средней длине файла допустим 40 байт(по моей статистике в двое меньше). Можете прикинуть сколько времени займёт первый алгоритм и сколько второй. Первый упрёться в производительность диска. И будет около 1-3 минут только читать с диска.
Второй быстрее при поиске, при наличии индекса управиться за доли секунды. Проблема в том что построение перестойка и поддержание суффиксного-дерева отнимает много времени и в реальных ФС это не встречается. Суффиксное-дерево всегда нужно поддерживать в строгой форме. Если мы уходим от строгой формы, то теряем скорость. Что в принципе можно сделать в ФС, но на практике это дополнительные расходы на которые пока что никто не отважился или почти никто.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 12 мар 2015, 00:04 
Аватара пользователя

Зарегистрирован: 14 май 2012, 22:17
Сообщения: 96
pavia писал(а):
Недавно увидел интересный пост по ФС.
http://freepascal.ru/forum/viewtopic.ph ... =30#p84869
И в соседней теме ответ. Почему так делать не надо.


Ссылка на пост - интересная, а где ответ "Почему так не надо"?

Начнем с абстракций. Вот в сетях есть уровни OSI. Это достаточно академическое построение оказалось на редкость жизненным. Почти все сетевые протоколы так классифицируют и при проектировании своего протокола это помогает, но почему нет ничего подобного для систем хранения? Мне кажется необходимо начать с такой иерархии а дальше рассмотреть существующие решения и как они коррелируются с нашим представлением. И далее по опыту проектировать своё. В массы это не пойдет - затопчут :) Торвальдс например пытался топтать zfs назвав "чудовищным смешением уровней". Я не согласен, просто это новый взгляд на хранение и даже он по нынешним временам устаревает (не по объему конечно) и выглядит как хорошая классика.

pavia писал(а):
И что хочется обсудить. Думаю что интерфейс для работы с файлами несколько устарел. И надо делать ещё и интерфейс вида IntrSQL (не помню как точно пишется, имею ввиду STL SQL).


Интерфейс к файловым системам vfs/vnode придумал sun в 80-е. Они-же уже в 90-е считали его устаревшим:
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B8A8A7B4E6EBA36DFF240870A7883688?doi=10.1.1.112.6473&rep=rep1&type=pdf
и предлагали расширить. Плохо было именно с метаданными. Прошло 20 лет, но интерфейс всё тот-же. И я совершенно точно уверен, что ничего в этом интерфейсе не изменится. Могут добавить вызов-другой, но генеральная линия будет непобедима.

Где выход? Выход - NFS4.1 (и потомки). Стандарт к сожалению огромный, но под него уже есть клиенты, опенсорсный сервер Ганеша, который пилят несколько лет очень известные компании и несколько проприетарных решений к системам хранения (по странному стечению обстоятельств именно тех компаний, которые никак ганешу не допилят). Стандарт немного кривоват (например MDS в нем один), но есть и рассматриваются предложения как улучшить. Взяв на вооружение этот стандарт, о том чтобы делать клиентов под операционки можно забыть. кстати, Lustre (WarmCloud) недавно объявила что будет предоставлять доступ через NFS4.1 вместо собственных клиентов.

pavia писал(а):
Поэтому ФАТ работает быстрее других ФС.


Что значит быстрая ФС? Есть ориентированные на запись и на чтение. На запись хорошо работает подход "запись новых данных как журнала" (гуглить logfs). Вы пишете все что хотите записать - данные, метаданные, изменения каталога, файл inode единой записью и замыкаете записью нового суперблока. На чтение такая система медленная (всё-же в куче!), но есть-же кэш. Памяти сейчас навалом. Кстати, элементы этого есть в btrfs.

dragon писал(а):

FAT без каких то улучшений сольёт, если добавить в одну директорию 100000000 файлов и попытаться поискать несколько файлов по имени (он и на миллионе сольёт, но пусть будет 100 млн., чтобы построить дерево поиска в памяти было нецелесообразно).


Для хранения больших данных, не помещающихся в память есть подходящие структуры данных - Log structered merge tree. Это база данных ведётся в памяти и периодически сбрасывается на диск. также периодически производится суммирование и очистка базы (merge). Гугловская Bigtable именно так и работает.

pavia писал(а):
Файловые системы не раз хотел обсудить. Но не раз убеждаюсь, что всё было придумано в 70-тых годах. И создать что-то принципиально новое тут невозможно. Остаётся только доработка существующих ФС.


А какие именно системы Вы считаете достойными? Давайте рассмотрим их подробнее...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 12 мар 2015, 01:38 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
pavia писал(а):
Так вот что делает СУБД? Ровно как и ОС+ФС одно и тоже. Это простой цикл от 0 до числа элементов в таблице каталога. К каждому элементу таблице применяется условие.

М-м-м... А индексы в СУБД, которые через create index, не? Они не для этого? Просто чтоб место занимали?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 12 мар 2015, 10:06 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1056
Цитата:
М-м-м... А индексы в СУБД, которые через create index, не? Они не для этого? Просто чтоб место занимали?
Они нужны для быстрой сортировки. Вот вы часто данные сортируете? Я не очень. Поэтому у меня свои планы насчёт организации СУБД и БД.

Может это у меня печальный опыт с СУБД? Есть программа не мая. База 1,5 ГБ индекс 15 ГБ!!!
При этом программа жутко тормозит! Из-за того что постоянно перестраивает индексы!
Всё бы ничего, но простая операция удаление и добавление одного элемента занимает 1,5 минуты
При этом в таблице всего 10 000 записей(выжимка из основной таблици). За месяц СУБД уже перелопатила половину записей, Надеюсь до конца месяца СУБД закончит работу. Правда СУБД ещё и сбоит 10-50%. Я используя ФС уже проделал аналогичную работу за 1 неделю с объемом в 10 раз больше. И того можно сказать что индекс дал замедление 100 раз. Для справки программа построена на основе MySQL.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 12 мар 2015, 12:21 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 938
Откуда: Дагоба
pavia писал(а):
Зря вы так про НС.

Это не он. Это я. viewtopic.php?f=2&t=688&p=8601#p8601

pavia писал(а):
1. Обычные люди пользователи компьютеров которые слышали про НС и считают что они могу всё.
2. Каста это программисты которые уже попробовали НС и разочаровались в них. Они уверены что НС это шарлатанство.

Я отношу себя ко второму пункту по одной простой причине: не существует ни одного практического доказательства эффективности нейросети. Все рекламные проспекты коммерческих продуктов на самом деле представляют собой "чёрные ящики", на которых написано "нейросеть" (обман трудящихся исключительно для создания восторженного душевного трепета потенциального лоха-потребителя), но внутри они представляют собой другие механизмы, не имеющие с НС ничего общего.
Приведу пример коммерческого разочарования. Первые версии FineReader использовали нейросеть в качестве первого этапа распознавания. Но довольно быстро от неё отказалась по описанным мной причинам. Больше никогда к НС не возвращались.

pavia писал(а):
3. А есть 3 каста которая использовала логику таки создали искусственный интеллект.
Можно сказать что это профессионалы ИИ они работают в мега корпорациях. Это они создали Океё гугл. Между прочем тот умеет отвечать на вопросы.
Есть автопилот самолёта, есть систем распознавания текста. Есть системы говорилок которые неотличимы от человека.

Ключевой вопрос: а причём здесь НС?
Такое впечатление, что ваше знакомство с НС и ИИ ограничилось парой популярных статей.

pavia писал(а):
Лично у меня есть идеи. Не совсем ИИ скорее вопрос обучения и кластеризации, но тут у мня есть идея как решить задачу века. Но руки пока не доходят дело в том что для проверки гипотезы надо написать много кода.

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

pavia писал(а):
К чему я это дело в том что современный ФС и БД строятся на основе Б+ деревьев. Но это же бред! Самая лучшая ФС была и остаётся ФАТ. Именно в ней реализован реляционный принцип.
Поэтому ФАТ работает быстрее других ФС.

Ооооо, похоже, вы ничего не понимаете не только в нейросетях, но также в реляционных базах данных и в файловых системах. FAT - одна из самых медленных файловых систем.

pavia писал(а):
Б+ деревья рассчитаны на случайный доступ при минимуме памяти. Но в фат доступ ещё меньше чем в Б+. Сейчас памяти много, да и доступ к памяти линейный. Отсюда видно превосходства ФАТ над другими ФС по большинству параметров.

Вы, похоже не понимаете принципиальной разницы между FAT и B+ Tree. Эти понятия ортогональны друг другу. FAT - это способ хранения файла на диске (аллокирование дискового пространства). B+ Tree - это структура директории.

pavia писал(а):
dragon писал(а):
FAT без каких то улучшений сольёт, если добавить в одну директорию 100000000 файлов и попытаться поискать несколько файлов по имени (он и на миллионе сольёт, но пусть будет 100 млн., чтобы построить дерево поиска в памяти было нецелесообразно).

Кому сольёт? Насколько мне известно ни в одной из популярных ФС такая индексация не предусмотрена.

Сольёт, например, ReiserFS - одной из первых файловых систем, основанной на B+ деревьях.

pavia писал(а):
Хотелось бы узнать где реально нужно 100 Миллонов файлов?

Например, в HTTP Proxy cache.

pavia писал(а):
И какие операции предполагаются с этой коллекцией файлов?

Поиск файла по имени.

pavia писал(а):
Если нужен доступ по имени то поверх ФАТ можно сделать сортировку в каталоге по алфавиту и бинарный поиск.

Допустим, вам нужно постоянно добавлять/удалять файлы. Как вы будете поддерживать свою сортировку в ФАТ? Будет ли создание нового файла работать быстро?

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 12 мар 2015, 15:19 
Аватара пользователя

Зарегистрирован: 16 апр 2010, 10:10
Сообщения: 319
Откуда: Псковская обл.
Про удаление файлов в FAT: часто проще отформатировать раздел - секунды против минут.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 12 мар 2015, 15:26 
Аватара пользователя

Зарегистрирован: 14 май 2012, 22:17
Сообщения: 96
iz56 писал(а):
Про удаление файлов в FAT: часто проще отформатировать раздел - секунды против минут.


Если удаляется больше половины - форматируем и записываем заново :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: почему осдев такой рграниченый
СообщениеДобавлено: 12 мар 2015, 18:07 
Аватара пользователя

Зарегистрирован: 16 апр 2010, 10:10
Сообщения: 319
Откуда: Псковская обл.
Почему osdev такой ограниченный - потому что старый. Вспомним логарифмические линейки. Вспомним артиллеристские таблицы - это очень производительные и одновременно узкоспециализированные решения. Как только вопрос производительности ушел на второй план - сразу как-то все решили что можно и более универсальные решения использовать . В какой-то момент производительность обесценит все наши наработки - как мне писали - зачем еще одна дос - хм , через 20 лет ,этот вопрос можно будет отреверсить обратно.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу Пред.  1, 2, 3, 4  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB