Привет всем.

Да, да, нужно разработать клиент-серверную реляционную СУБД. Это мой КУРСОВОЙ в универе, ничего больше) К сожалению, читать исходники postgres, berkeley и других нету времени, так что пришлось создать топик (хотя сегодня думаю порыться в исходниках sqlite и leap).
Теорией немного подковался, теперь возникли более-менее конкретные вопросы, направленные на систематизацию и увязку знаний, плюс по деталям реализации.

1) Читал в wiki про ISAM (http://ru.wikipedia.org/wiki/ISAM), смутила фраза
"Второй набор данных — индексы, содержат указатели, которые позволят извлечь определенные записи без поиска по всей базе данных. Это несколько отличается от индексов в современных поисковых базах данных, так как в них индексы хранятся прямо в записях."
Вроде как многие современные СУБД используют b-деревья для индексов и хранят их отдельно от данных. В MSSql отведены отдельные страницы для индексов, если я не ошибаюсь. Да и вообще хранить индексы вместе с данными не очень рационально, как мне кажется. Может есть какие-то новые веяния? Как лучше хранить индексы: с данными или нет?
2) В каком виде лучше всего хранить индексы в оперативной памяти? Так же как и физически - b-дерево (или его часть, если есть ограничение по выделяемой ОЗУ)? Возможно вопрос немного странный, но в описании MуSql говорится про дополнительное использование хэш-таблиц: "Хеш-таблицы в памяти, используемые как временные таблицы."
3) Во время поиска (в т.ч. не по индексам), насколько я понимаю, постоянно придётся подгружать-выгружать данные в-из оперативную память. Чтобы ускорить эти процедуры, данные на внешнем накопителе разбивают на страницы? Стоит ли заморачиваться способом чтения файлов БД: вызовы CreateFile-ReadFile-WriteFile, fopen-fread-fwrite или через проекции в оперативную память File Mappings?
4) Как лучше организовать кэширование данных: по наиболее частым запросам или по наиболее используемым записям (в совокупности от нескольких запросов)? Или дело вкуса?

Буду благодарен за ответы.

kdvпо-моему, писать свою СУБД на курсовой - это слишком опрометчивое решение.
kdvВ общем, предсказываю фиаско. Вам теорию до начала написания кода читать и читать.
Возможно так кажется со стороны.

kdvТиори и Фрай "Проектирование баз данных"
Спасибо, посмотрю. Пока что прочитанный Дейт мне не слишком много нового дал.

kdv
автор
В каком виде лучше всего хранить индексы в оперативной памяти?

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

Это понятно. Так сделано,например, в MsSql, верно? Страница - это всего лишь промежуточный абстрактный уровень хранения так сказать, А сами индексы по структуре связаны в b-дерево. Может я не совсем понятно выразился, но в данном вопросе я хотел УТОЧНИТЬ саму структуру индекса подгруженного полностью или частично в оперативную память, вернее стоит ли её дополнять и преобразовывать. Для чего же тогда в MySql используются "Хеш-таблицы в памяти, используемые как временные таблицы."?

Dimitry Sibiryakov
За leap не скажу, но sqlite вроде бы как не клиент-серверная?..

Клиент-серверность я сделать смогу)) Меня сейчас интересует именно ядро СУБД. А организовать сокет и сделать обслуживание подключённых клиентов в потоке не очень сложно.

Первое, что надо сказать, это огромное спасибо, народ, что не поленились ответить. СПАСИБО всем, кто принял участие в обсуждение.

kdv
гм. я бы сказал, что Дейт тут вообще ни при чем.

Я сказал то же самое) Научный руководитель посоветовал читать Дейта "Введение в системы баз данных", но пользы это принесло мало.

kdv
без понятия. это фишка конкретного сервера или конкретного движка MySQL. Временные таблицы у всех по разному реализуются.

Я уже разобрался для чего) В таблицах InnoDB при БД небольшого размера, которая полностью или почти полностью вмещается в оперативную память, MySQL на основе B-дерева строит хэш-таблицу, считая, что в данном случае это ускорит доступ.

mayton
Даже если ты "прочитаешь" все исходники postgres, berkeley - это не поможет тебе быстро ответить на твои вопросы. Такой способ ПОЛУЧЕНИЯ ЗНАНИЙ - неприемлим.

Да, для быстрого получения знаний это не подходит. Сейчас читаю статьи по СУБД, большинство из них правда на английском, но мне это не сильно мешает)

mayton
API не имеет значения. Все файловые API примерно одинаковы. На низком уровне это - открыть файл. Прочитать байть (или блок байтов). Закрыть файл. В качестве страницы можешь выбрать строку dbf-файла. Или блок строк. Это удобно т.к. строки dbf имеют физически одинаковый размер.

Имеет. File Mappings работают через механизм страничной организации виртуальной памяти. fread и компания осуществляют дополнительную буферизацию данных и могут без "доточки" использоваться для чтения небольших порций. ReadFile и КО - то, что в конце концов вызовет fread - лучше использовать для чтения больших объёмов и разбираться с буферизацией самому, но зато сам знаешь где и как буферизиризация происходит.

mayton
Это глубокая оптимизация. На данном этапе это не имеет абсолютно никакого значения т.к. не с чем сравнивать и нет нагрузочного теста. Сделай хотя-бы работающий макет. А там будет видно.

Да, я от кэширования отказался. Просто не успею. Лучше потом добавить, если время будет.

opendsa
1. Это однопользовательская база или много пользовательская.
2. Каким временем Вы располагаете.
3. Нужно что бы работало или просто показать и сдать.

Многопользовательская, подробнее ниже.
Времени маловато.
Чтобы работало и сдать. Не сверхсложное, но и чтобы стыдно не было.

opendsa
На этом уровне все абстракция.
Вам нужно создать прозрачный механизм быстрого поиска ( прямой и коственной адресации данных через индексы).
Диск <-> Память (индекс) + Диск <-> Память (Данные)
Обычно для этого используется абстракция под названием ROWID.
Только формулы , алгоритмы сортировок и блок схемы уже потянут на курсовую.

ROWID - это, насколько я понимаю, физический адрес записи (файл->блок->страница->номер_записи), который заодно используется как уникальный идентификатор???

opendsa
Как вы ответили на первый вопрос ?
Много пользовательская ?
Значит погружайтесь в мутексы ( синхронизацию паралельного выполнения)
и распределение ресурсов,
Тут еще одну курсовую хватит.

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

opendsa
Механизм LRU тут еще на одну курсовую насобирать можно.
Учитывая приоритетность вытеснения ( Данные , Индексы, Метаданные и т д.)

Как я уже написал, кэширование исключил из планов.

opendsa
все зависит от того, что требуется от прототипа.

Как раз сижу над спецификацией, чтобы можно было начать разрабатывать архитектуру.

mayton
Парень! Это всего-лишь курсовой! Автору надо просто продемонстрировать РСУБД. И ничего более. Выполнить программу-минимум. Я понимаю твоё рвение, но это, поверь не тот случай.


opendsa
Человек спрашивает - я отвечаю.

Из тех вопросов которые он задает 3 качественных курсовых можно сделать.

И на диплом и даже на дисерт хватит при должном подходе.

Да всё нормально, мне как минимум нужно было узнать "потолок" этой работы и оценить время.

Возможно завтра покажу спецификацию требований.

Ещё раз: всем спасибо.

Наверное, будет правильным, если я отпишусь о результатах)
СУБД написана, курсач сдан.

Был создан прототип колоночной СУБД. В общем-то с самого начала я на такую схему и рассчитывал - сделать что-то новое в строковых хранилищах очень тяжело. А колоночные на данный момент - непочатый край работы, куча вариантов и идей)) Ну надеюсь, мысль понятна. Хотя скажу сразу: при разработке мне показалось, что строковую было бы написать гораздо легче.

Что конретно было реализовано (Язык - C со вставками C++ :) ):
- Менеджер страниц (диск <-> память) с поддержкой многопоточности
- Полные индексы на основе B+ деревьев (без кластерных, добавление новой записи идёт точно в конец таблицы)
- Многопоточная обработка запросов: вставка и выборка (без удаления). Выборка только с критерием AND (немного упростил задачу :))
- 5 базовых типов данных: INT32, UINT32, DOUBLE, STRING (аналог char в mysql), TEXT - просто текст нефиксированной длины, максимально 32 килобайта. В общем потом добавил byte и short int. Это непринципиально как вы понимаете.
- Многопользовательский доступ по сети.

Результаты:
Тестовая таблица - INT (индекс/primary index в MySQL), INT, STRING, TEXT, DOUBLE, INT.
Время вставки 5000 записей - в 2 раза больше, чем в MySQL (0.16 и 0.08).
Время выборки 2000 записей из 5000, находящихся в таблице более чем в 10 раз меньше (0.0012 и 0.03).
Естесственно, это результаты только прототипа, а не полноценной СУБД, но при конечной реализации я думаю результаты не изменятся слишком сильно. Код СУБД - не оптимизировался специально, результаты только за счёт колоночной модели.
Тесты при многопользовательском доступе не проводились.

Замечания:
Самые сложные места в разработке - это проектирование архитектуры и синхронизация потоков (для синхронизации доступа к B+ дереву пришлось придумывать спин-блокировку с 3-мя состояниями :)).

Резюме:
Преимущества и недостатки колоночных СУБД подтверждены на практике.
Если кому-то придёт в голову взять на курсовой и диплом СУБД, вот мой совет - ну его нафиг)

Если кому-то интересно - поделюсь исходником. Но в паблик выкладывать не буду... Из-за катастрофической нехватки времени код более-менее нормальный только в модуле менеджера страниц.

kdvгигант...

спасибо, коль не шутите.

smansdbSoFx00 Самые сложные места в разработке - это проектирование архитектуры и синхронизация потоков (для синхронизации доступа к B+ дереву пришлось придумывать спин-блокировку с 3-мя состояниями :)) На Java синхронизация многопоточности выполняется элементарно…

Java - это не язык для написания быстрой СУБД. Я плохо знаком с явой, но вряд ли средства синхронизации в ней сильно отличаются от имеющихся на Win32 и алгоритмических: те же критические секции и проч. Тройной спинлок нужен для быстрой многопоточной работы с b+ индексами. Поясню: один поток начинает читать индекс, второй тоже хочет читать. Если тупо блокировать работу с индексом - огромное падение производительности, т.к. второй поток вынужден ждать окончания чтения, вместо выполнения параллельно. Поэтому надо вводить 3 состояния - чтение, запись, не_используется и на их основе строить логику новой спинблокировки.

DPH3Хм, на Java очень богатая библиотека примитивов синхронизации, в том числе атомарные операции, неблокирующие очереди и прочие радости современной науки :)
Стоит их внимательно изучить перед реализацией, там много уже готового.

Теоретически, для курсовой работы, Java - вполне себе язык для разработки БД. Тем более что БД на Java вполне себе есть, даже opensource :)

Проблемы будут со сборкой мусора под нагрузкой, но и они решаемые.

Поверю на слово, скорее всего так и есть: там бы это всё выглядело более строго) Но всё-таки java - не технология для написания БЫСТРОЙ Субд. Компилируемые C/C++ в любом случае быстрее. А мне ведь ещё надо было адекватно сравнить с MySql и прочими)

ЗЫ А атомарные операции поддерживаются на уровне процессора.

авторЭ-э-э... Т.е. ты не читал Рихтера? Там целая глава посвящена именно
разводу читателей и писателей. Двумя мутексами.

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

MasterZiv
smansdb пишет:

> На Java синхронизация многопоточности выполняется элементарно…

Это гон. Она везде одинаково сложна. Не сама синхронизация (она
везде проста), а проектирование приложения таким образом, чтобы
правильно делать синхронизацию.


+1

MasterZiv
На самом деле есть специальные алгоритмы прохода по дереву, которые
позволяют не блокировать дерево целиком. А конкретные страницы
индекса блокируются обычными блокировками страниц данных в рамках
транзакций.


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

авторЯ фигею, господа. Оказывается есть некий универ, где такая задача это всего лишь курсовой. Если это так, то в стране должны производиться десятки клиент-серверных реляционных СУБД.

Вы считаете, что я лгу? Тема - результат моей самоуверенности, универ - в Минске, БГУИР называется.

автор
проверить + взвести 2 мутекса одновременно. Все это нужно защищать 3-им мутексом на входе.


У меня вообще используется один синхронизирующий примитив - одна спинлок-переменная) Приоритет при синхронизации больше у читателей и это лучше для колоночной СУБД, т.к. они select-ориентированные.
Ладно, пойду искать в Рихтере вышеназванный пример.