Разработка базы данных

[whiskas 144]

В далеком прошлом я начал делать хранилище вещей на ОС (пародия на АЕ2). Для этой задачи я хранил все данные в оперативной памяти. При увеличении размера хранилища у меня начало падать по нехватки памяти. Я решил выгружать все данные в различные файлики и так у меня родилась база данных (пародия на бд). Хранил каждый вид предмета в отдельном файлике, вроде все кул но тут идет большое но "открытие каждого файлика тратится 1 тик" и когда файликов много и тебе нужно найти какой-то определенный файл по какомуто филду то это будет длиться вечность. Для этого я перенял идею баз данных и создал индексы. Индексы у меня были самые примитивные, это тупо таблица ключ значение. Я начал добавлять индексы по всех полях по которых ищу. Все вроде работало и хранилище стало намного больше. И тут я долго ним пользовался, файликов поднакопилось и программа опять начала падать по нехватки ОЗУ. Индексы слишком большие и не влазят в память. А у меня в планах еще увеличивать хранилище.
Так вот к чему я веду. У кого-то есть идеи как можно хранить индексы поярче в ОС? Меня там ограничивает что почти каждая команда требует 1 тик. Ничего не лезет в голову как решить эту проблему.

Изменено 15 августа, 2021 пользователем whiskas

[eu_tomat 2 154]

1 час назад, whiskas сказал:

открытие каждого файлика тратится 1 тик

В качестве БД можно использовать один постоянно открытый файл или же ограниченное количество открытых файлов. Это позволит исключить затраты на открытие-закрытие файлов.

[AtomicScience 76]

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

Изменено 16 августа, 2021 пользователем AtomicScience

[whiskas Автор вопроса 144]

1 час назад, AtomicScience сказал:

unmanaged диски

можна пример? Ато не доконца понимаю что это означает

[prop 19]

Реализуй btree индекс.

 

https://db.grussell.org/imp.html

 

https://www.codeproject.com/Articles/7410/Implementation-of-a-B-Tree-Database-Class

[whiskas Автор вопроса 144]

9 минут назад, prop сказал:

Реализуй btree индекс.

Он не поможет. Ибо в 1 файлике хранить это все не смогу. А в многих файликах идет по 1 тику на открытие. 

[eu_tomat 2 154]

5 часов назад, whiskas сказал:

можна пример? Ато не доконца понимаю что это означает

Держа диск в руке, нажимаем правую кнопку мыши. В появившемся интерфейсе нужно выбрать режим "unmanaged". Теперь этот диск будет определяться не как filesystem, а как drive с соответствующим набором свойств и методов.

 

Компонент drive позволяет посекторно читать с диска и писать на него примерно в 6-7 раз быстрее, нежели при работе с компонентом filesystem.

 

36 минут назад, whiskas сказал:

в 1 файлике хранить это все не смогу.

А что мешает всё хранить в одном файле? К слову, использование режима unmanaged очень похоже на работу с единственным файлом. Также поверх unmanaged-диcка можно написать свою файловую систему, позволяющую держать нужное количество файлов постоянно открытыми.

[whiskas Автор вопроса 144]

3 часа назад, eu_tomat сказал:

А что мешает всё хранить в одном файле?

я про то дерево. Что дерево в 1 файле не смогу хранить иза того что оно не поместится в ОЗУ при сериализации. А твой вариант с постоянно открытым файлом и записивать посекторно думаю может сработать

[eu_tomat 2 154]

5 минут назад, whiskas сказал:

твой вариант с постоянно открытым файлом и записивать посекторно думаю может сработать

Да, это первое, что стоило попробовать. Но, насколько я помню, filesystem позволяет одновременно держать открытыми максимум 16 файлов.

 

Поэтому рано или поздно потребуется ограничить количество файлов и хранить несколько виртуальных файлов внутри одного, используя аналог файловой системы. В этом случае проще будет использовать единственный файл. А уже тогда можно будет с лёгкостью отказаться от компонента filesystem, получив дополнительное ускорение. И B-tree будет выглядеть более уместно.

 

Просто советчики немного забежали вперёд, а по сути их предложения вполне обоснованы.

[whiskas Автор вопроса 144]

да дерево это понятно что круто. Но я думаю легче будет сделать хеш таблицу

[ECS 1 903]

В 17.08.2021 в 03:36, whiskas сказал:

да дерево это понятно что круто. Но я думаю легче будет сделать хеш таблицу

Даже в случае с хеш-таблицей держать все индексы БД в памяти - такая себе затея, т.к. оператива не резиновая, а скрафтить RAID на 12 мбайт не составит особого труда. Основной проблемой при работе с индексами, хранящимися на диске, у тебя будет скорость чтения и реиндексации при записи, т.к. опенкомповские диски прям сильно лимитированы по I/O операциям. Даже если прикрутить к хеш-таблице бинарный поиск, то это слабо поможет жирным БД, исчисляемых мегабайтами, т.к. глубина рекурсии при поиске может достигать нескольких тысяч. К сожалению, чем жирнее БД, тем более заковыристый алгоритм требуется для ее поддержки, и заюзать древовидную структуру для хранения индексов будет оптимально, т.к. для чтения с диска нужно минимизировать число узлов, которые обходит поисковая система. Ну а про удаление/вставку со сдвигом индексов и говорить нечего

[ProgramCrafter 544]

12 часа назад, ECS сказал:

опенкомповские диски прям сильно лимитированы по I/O операциям

Надо бы ещё проверить, как ведут себя кассеты из аддонов, особенно самая большая.

(Если кому-то понадобится ФС, поддерживающая кучу файлов, для кассет - можете меня тыкать, у меня осталось немного доработать.)

[ECS 1 903]

19 минут назад, ProgramCrafter сказал:

Если кому-то понадобится ФС, поддерживающая кучу файлов, для кассет - можете меня тыкать, у меня осталось немного доработать

)))

 

https://computercraft.ru/topic/4340-tapfat-faylovaya-sistema-dlya-kasset/?tab=comments#comment-49345

[whiskas Автор вопроса 144]

Использовать вещи не поназначению -_-. Я так когдато пытался подключить 2 компа к 1 монитору и общатся через него). Ибо у сетевой карты задержка 1 тик а вдруг монитор смог бы быстрее. Я уже не помню получилось или нет. Ну подключить точно получилось. Компы общались. Но быстрее чем 1 тик не помню

Изменено 20 августа, 2021 пользователем whiskas

[eu_tomat 2 154]

41 минуту назад, ProgramCrafter сказал:

Надо бы ещё проверить, как ведут себя кассеты из аддонов, особенно самая большая.

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

[whiskas Автор вопроса 144]

А есть ли ограничение на размер 1 файла?

[eu_tomat 2 154]

1 час назад, whiskas сказал:

А есть ли ограничение на размер 1 файла?

OpenComputers никак не препятствует созданию файлов размером с целый диск или даже RAID-массив.

[hohserg 197]

10 часов назад, whiskas сказал:

Я так когдато пытался подключить 2 компа к 1 монитору и общатся через него)

Можно к нескольким компам подключить один мост очков OpenPeripherals и через виджет обмениваться инфой

[eu_tomat 2 154]

Оставлю здесь результат обсуждения в чате по этим двум постам:

В 20.08.2021 в 10:16, ProgramCrafter сказал:

Надо бы ещё проверить, как ведут себя кассеты из аддонов, особенно самая большая.

В 20.08.2021 в 11:03, eu_tomat сказал:

Кассеты работают в сотни раз медленнее дисков.

Я не учёл того, что размер данных, считываемых с кассеты, ограничен лишь размером доступной оперативной памяти, на что мне указал в чате@ProgramCrafter.

 

Поэтому не смотря на то, что для чтения с кассеты требуется потратить один тик на позиционирование плюс один тик на чтение, итоговая скорость чтения с кассеты может оказаться в десятки раз выше скорости чтения жёсткого диска. Но возможность использовать преимущество чтения огромного блока в конченом счёте будет определяться конкретными условиями.

 

Недостаточный запас свободной оперативной памяти даже если и позволит считать блок данных, не обязательно позволит его использовать, это сильно зависит от используемого алгоритма. Также чтение большого блока данных может оказаться попросту ненужным, так как тот же алгоритм B-tree позволяет обойтись меньшим количеством данных, но находящихся в независимых друг от друга блоках. И про затраты в два тика времени также не стоит забывать.

 

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

[eu_tomat 2 154]

Также я выяснил, что максимальный размер считываемого блока для компонента filesystem составляет 2048 байт против 512 для компонента drive. И при использовании максимальных размеров блока скорости чтения filesystem и drive уравниваются. Учитывая это знание, я бы выбирал между filesystem и drive, исходя из оптимального размера блока.

 

Но это справедливо для постоянно открытых файлов. В ином случае к затратам на чтение требуется добавить затраты на открытие и закрытие.