Выбор системы хранения и схема данных
Roman Eremenko
http://www.freesource.info/wiki/TZ/ServerIntegracii/SxemaDannyh
Это набросок, не успел оформить из-за сбоя электричества, но материал
там основывается на том документе что я рассылал ранее. Собственно
субж - жду критики, замечания и других предложений по организации субд
от Мельникова, ну и других:)
Ivan 'Evilistche' Melnikov
и только 10 минут назад получил приглашение в эту рассылку. Однако
завтра (сегодня) в первой половине дня меня не будет, поэтому пару
слов напишу прямо сейчас, хотя возможно ввиду обстоятельств они будут
мутноваты.
По описанному на вопросов/претензий не имею. Меня в системе хранения
очень интересовал вопрос о выяснении всех (прямых и непрямых) потомков
конкретного объекта. Я применял умную фразу "транзитивное замыкание по
отношению родитель-потомок", хотя до конца и не уверен в её
корректности. По сути задача взять селект <quote> select id from
abstract_object where parent_id=значение </quote> и вызвать его
рекурсивно. Эту задачу хотелось бы спихнуть прямо на сервер БД. Я не
большой специалист по postgre, поэтому не стану утверждать, что здесь
простого, ясного и очевидного решения не существует, хотя и хотелось
бы.
Я смотрел как это сделано до нас в том же OpenLDAP и ещё кое где - или
я ничего не понял, или там всё очень странно. Подробнее об этом к
четвергу. Есть также некоторые свои мысли.
Ещё одна задача касается более широкого и потому сложного отношения
объекта и групп, в которые он включён. В текущей схеме это отношение
задаёт нетривиальный ориентированный граф, в общем случае с циклами.
Опять же я думал много мыслей, однако здравыми они пока не кажутся.
Ivan 'Evilistche' Melnikov
Мне кажется, что в ABSTRACT_OBJECT стоит внести информацию о классе
объекта (примеры классов: User, Group, DNSObject). Это удобно когда у
тебя есть только ID и надо понять, что же с ним делать. Так как любой
объект должен по идее относится к какому-то классу, не вижу смысла
выносить эту информацию в отдельную таблицу.
Соответственно, нужно добавить таблицу (ID класса, имя класса).
Возможно, здесь нужны ещё какие-то поля, например, дающие информацию о
схеме (какие атрибуты в каких таблицах возможны/необходимы для объекта
такого класса).
Roman Eremenko
Относительно остальных сущностей - помнишь ты рисовал маркером большую схему? Напомни её каким нибудь образом, картинкой или диаграммой, а то выветрилась из памяти, а сейчас очень тут нужна.
Кстати, давайте определимся, чем мы рисуем UML (ORM, Буч, Бутч) диаграммы! Это ко всем относится:)
варианты
раз - http://voodoo.sourceforge.net/
два - http://amateras.sourceforge.jp/cgi-bin/fswiki_en/wiki.cgi?page=AmaterasUML
три -
неохота эклипсовскую тулзу, надо что-то standalone и cross-platform
Насчёт транзитивного замыкания - я посмотрю. Теоретически его можно вынести в процедуры, но есть ситуации, когда нам нужно выдавать всё дерево (поддерево) сразу?
Roman Eremenko
1)
http://www.osp.ru/os/2004/02/183939/
http://www.osp.ru/os/2004/02/183939/_p2.html
2)
Гон каких-то девелоперов про реляционные и иерархические субд, основной интерес - комменты, пример сложных джойнов. Оффтоп в общем небольшой
http://maximkr.livejournal.com/12147.html
Ivan 'Evilistche' Melnikov
Есть одна очень обидная вещь:
НЕТ В POSTGRESQL НИ CONNECT BY, НИ CTE (WITH RECURSIVE) в официальном
даже 8.3 - одни сплошные патчи.
Возможно, патч, добавляющий CONNECT BY, стоит включить в Postgre - он
достаточно стабилен, эффективен, его включают во многие поставки, к
тому же конструкция с CONNECT BY -- правильный способ работы с
иерархиями в оракле (или мне наврали. Рома?). Возможно, за предыдущее
предложение я буду вечно гореть в аду. Интересно мнение Жени и Димы по
этому поводу.
Roman Eremenko
я больше склоняюсь к тому что стандартными реляционными средствами всё это решается просто, если ты посмотрел первую ссылку, то там прям предлагается вариант описания файловой системы с помощью двух таблиц - связей и вершин.
Нам нужно тогда расписать - а какие собственно запросы у нас могут возникнуть, насколько они будут вложенные - и от этого уже отталкиваться и по возможности применить патч.
Оракл например не стесняется строить свой Ldap сервер (IDS) на основе DB-сервера и не думаю, что там особые какие фичи используются.
Вот какой недостаток я нашёл в постгре - мутная система репликации. Репликация нам нужна а)для взаимодействия модулей в рамках виртуальных серверов, б) для репликации собственно "доменной" информации.
Пункт а) мы можем исключить, если проектируем модули полностью автономными друг от друга, нужно просто продумать систему ключей, чтобы они были уникальными в пределах всего сервера.
Evgeny Sinelnikov
Дело в чем. В комментариях указаны два противоположных взгляда на проблему,
я больше склоняюсь к тому что стандартными реляционными средствами всё это решается просто, если ты посмотрел первую ссылку, то там прям предлагается вариант описания файловой системы с помощью двух таблиц - связей и вершин.
Нам нужно тогда расписать - а какие собственно запросы у нас могут возникнуть, насколько они будут вложенные - и от этого уже отталкиваться и по возможности применить патч.
Оракл например не стесняется строить свой Ldap сервер (IDS) на основе DB-сервера и не думаю, что там особые какие фичи используются.
Вот какой недостаток я нашёл в постгре - мутная система репликации. Репликация нам нужна а)для взаимодействия модулей в рамках виртуальных серверов, б) для репликации собственно "доменной" информации.
Пункт а) мы можем исключить, если проектируем модули полностью автономными друг от друга, нужно просто продумать систему ключей, чтобы они были уникальными в пределах всего сервера.
Насчёт общих ключей идея интересная. Но можно подуматьне только об уникальности ключей, но и о ссылочной целостности при перекрёстных ссылка в разных база установленных на одной СУБД.
По поводу структуры хочу привести ещё ряд ссылок, которые мы сегодня (уже вчера) обсуждали относительно структуры БД:
- Дерево каталогов NESTED SETS (вложенные множества) и управление им
- Nested Sets в PostgreSQL
- Деревья в базах данных
- Implementing An N-Level Nested Tree
- Написание расширений для PostgreSQL с использованием GiST
Единственное, на что стоит заложиться - это на связь между группами и контейнерами - и те, и другие у нас планировались иметь уникальный gid из общего множества. От этого ещё не поздно отказаться в пользу возможности включения контейера в группу, что будет означать, стекание группы на все объекты контейнера. То есть gid появляется не у всех контейнеров, а только у тех, которые добавлены в соотвествующую группу. Правда вот с транзитивным замыканием по отношению группа-объект_ в_группе, то тут во всех случаях какой-то бардак получается...
В общем, для начала можем говорить о правах на объекты и на некий корень, в который они свалены. А потом усложнять процедуру вычисления этих прав добавлением иерархии объектов.
Ещё один важный момент, который мы вчера (хм... или позавчера) разрешили - это права на группы. Дело в том, что новая модульная архитектура предполагает, что каждая служба сама хранит свои данные, и то, что это может быть дополнительная база в PostgreSQL - это только частный случай. Первоначально я предложи такой вариант (как было сказано "не В дереве а НА дереве (метафорично)"):
1) Отвественность за авторизацию несёт только сам сервис, но механизм у них всё равно стараемся сохранять единый.
2) Общий механизм вычисления прав по дереву или без него реализован в виде библиотеки.
3) Отдельные сервисы (конфигураторы) хранят права на свои объекты отдельно, но могут для них указывать идентификатор контейнера, использующегося при вычислении прав с помощью библиотеки.
4) При нарушении ссылочной целостности, когда в базе удаляется контейнер, на который сущtствуют ссылки извне, вычисление прав определяется политикой сервиса - либо права вычисляются без учёта прав внешнего контейнера, либо из предположения, что объект с подвешенной ссылкой, хранится в спец. контейнере, например корневом, либо доступ к нему запрещается, до момента исправления ссылочной целостности.
5) Объекты с нарушенной ссылочной целостностью стоит уметь искать, но для начала это не важно...
Кроме того в дереве так или иначе должен появляться специальный объект (в нашей терминологии даже субъект) - сервис или служба. Эта сущность должна получать SPN и вероятно uid, чтобы не придумывать дурацких механизмов по созданию спец. пользователей и маппингу на них не свойственных для пользователей принципалов kerberos - Service Principal Names. Любая служба получая идентификатор и SPN, сохраняется в виде объекта в дереве, и имеет, как и любой другой объект, свои ACL. Первоначально - это опять-таки таблица в плоском пространстве без иерархии.
--
Sin (Sinelnikov Evgeny)
ivan.a....@gmail.com
В сообщении от Friday 15 February 2008 09:54:18 Evgeny Sinelnikov написал(а):
> Приветствую,
[skip]
> Насчёт общих ключей идея интересная. Но можно подуматьне только об
> уникальности ключей, но и о ссылочной целостности при перекрёстных ссылка в
> разных база установленных на одной СУБД.
>
> По поводу структуры хочу привести ещё ряд ссылок, которые мы сегодня (уже
> вчера) обсуждали относительно структуры БД:
>
> - Дерево каталогов NESTED SETS (вложенные множества) и управление
> им<http://www.getinfo.ru/article610.html>
> - Nested Sets в PostgreSQL <http://dull.ru/2005/04/20/nested-sets/>
> - Деревья в базах данных <http://phpwiki.ru/Tree/Ns>
> - Implementing An N-Level Nested
> Tree<http://www.phpriot.com/articles/nested-trees-1>
> - Написание расширений для PostgreSQL с использованием
> GiST<http://www.altlinux.ru/events/writing_postgresql_extensions.html>
Ещё одна ссылка, раз уж на то пошло, из самых сокровенных запасов: самое
понятное описание Nested Sets :
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
> К этой теории хотелось бы добавить, что на практике объекты всё равно
> ханяться отдельно и лишь указывают на свою принадлежность тому или иному
> контейнеру, поэтому реализовать решение можно поэтапно. Доступ к объектам
> по имени не зависит от его нахождения в дереве, от этого зависят только
> эффективные права на этот объект. Предлагается первоначально реализовать
> плоский набор объектов, а потом добавить иерархию, усложняющую авторизацию
> стеканием прав и тому подобным.
Да, решение о способе хранения иерархической информации далеко от зрелости и
требует дополнительного тестирования. Nested Sets, Adjacency Lists и 28
способов работы с ними, или даже Path Enumeration - всё такое вкусное, но
имеет и свои недостатки.
Поэтому действительно, информацию о структуре дерева лучше вынести в
отдельную(ые) таблицу(ы), которые добавить потом.
Предлагаю выделить следующие этапы (итерации) развития системы авторизации:
1. Плоская структура, подобная /etc/passwd и /etc/groups, но с учетом будущего
и разделением, например, user, computer и service.
Один из вопросов здесь - главная группа пользователя posix. Предлагаю создать
3 группы для этой цели - users, computers и services.
2. ACL. Прямо поверх 1. Отсутствие иерарихий и прочего упростит реализацию.
3. Контейнеры. Следующие 2 подпункта имхо можно реализовывать достаточно
независимо, порядок неважен.
3а. Стекание прав.
3б. Наследование привилегий
4. Включение агентов (btw, именно это слово теперь предлагается использовать
для обозначения субъектов авторизации - user, computer и service -
возражения?) в контейнеры как в группу (ввод, включение по ссылке).
5. Группа в группе, но не в контейнере
6. Тоже самое, но уже и для контейнеров.
> Единственное, на что стоит заложиться - это на связь между группами и
> контейнерами - и те, и другие у нас планировались иметь уникальный gid из
> общего множества. От этого ещё не поздно отказаться в пользу возможности
> включения контейера в группу, что будет означать, стекание группы на все
> объекты контейнера. То есть gid появляется не у всех контейнеров, а только
> у тех, которые добавлены в соотвествующую группу. Правда вот с транзитивным
> замыканием по отношению группа-объект_ в_группе, то тут во всех случаях
> какой-то бардак получается...
Непонятно, зачем. Если группа может включаться в группу, что мешает
распространить то же отношение и на контейнер?
> В общем, для начала можем говорить о правах на объекты и на некий корень, в
> который они свалены. А потом усложнять процедуру вычисления этих прав
> добавлением иерархии объектов.
См. выше.
>
> Ещё один важный момент, который мы вчера (хм... или позавчера) разрешили -
> это права на группы. Дело в том, что новая модульная архитектура
> предполагает, что каждая служба сама хранит свои данные, и то, что это
> может быть дополнительная база в PostgreSQL - это только частный случай.
> Первоначально я предложи такой вариант (как было сказано "не В дереве а НА
> дереве (метафорично)"):
>
> 1) Отвественность за авторизацию несёт только сам сервис, но механизм у них
> всё равно стараемся сохранять единый.
> 2) Общий механизм вычисления прав по дереву или без него реализован в виде
> библиотеки.
> 3) Отдельные сервисы (конфигураторы) хранят права на свои объекты отдельно,
> но могут для них указывать идентификатор контейнера, использующегося при
> вычислении прав с помощью библиотеки.
> 4) При нарушении ссылочной целостности, когда в базе удаляется контейнер,
> на который сущtствуют ссылки извне, вычисление прав определяется политикой
> сервиса - либо права вычисляются без учёта прав внешнего контейнера, либо
> из предположения, что объект с подвешенной ссылкой, хранится в спец.
> контейнере, например корневом, либо доступ к нему запрещается, до момента
> исправления ссылочной целостности.
> 5) Объекты с нарушенной ссылочной целостностью стоит уметь искать, но для
> начала это не важно...
Возможно, нужно дать конфигуратору несколько вариантов хранения информации:
- с расширением схемы - добавлением таблиц;
- с добавлением отдельной БД и выносом ветки туда (вообще интересная идея -
выносить ветки в отдельные БД... хотя для наших целей это вряд ли
пригодится);
- с построением альтернативного дерева в другой БД, используя ту же систему
(код и представление) что и основное дерево, возможно с ссылками на субъектов
из основного дерева;
- с разработкой собственной системы авторизации (для специфичных задач); здесь
необходимо предусмотреть возможность взаимодействия с нашей системой -
дополнения или пересечения прав, стекание по основному дереву...
> Кроме того в дереве так или иначе должен появляться специальный объект (в
> нашей терминологии даже субъект) - сервис или служба. Эта сущность должна
> получать SPN и вероятно uid, чтобы не придумывать дурацких механизмов по
> созданию спец. пользователей и маппингу на них не свойственных для
> пользователей принципалов kerberos - Service Principal Names. Любая служба
> получая идентификатор и SPN, сохраняется в виде объекта в дереве, и имеет,
> как и любой другой объект, свои ACL. Первоначально - это опять-таки таблица
> в плоском пространстве без иерархии.
Поясню, что эти ACL могут использоваться для управления доступом К конкретному
сервису (конфигуратору), то есть кто чем там может рулить (конфигурировать).
Мне это кажется основным механизмом управления правами для конфигураторов, не
требующих сложных наворотов.
Pablo Juanych
update'ами на каждой ноде при вставке и удалении - она не выглядит так
уж страшно в нашем случае, ибо изменения дерева будут случаться редко
в сравнении с чтением.
Единственное в чем я не уверен, так это в оптимизации запроса поиска
ноды по полному пути - самая частая операция будет.
Прекомпиленые запросы для обхода дерева пользовать низя.
Соответственно нужно, чтобы система умела ловко спускаться по дереву
не возвращаясь наверх после получения очередной ноды, только в этом
случае сложность поиска по пути будет логарифмической.
Ну, это я ещё про постгрю почитаю, но если кто знает - пишите тута!
Если это невозможно, есть разнообразные методы, правда они снижают
нормализацию данных в базе, а значит триггеры на вставках и апдейтах и
обширные локи на этих же операциях - увы.
Связанный вопрос - насколько в постгре надежен механизм транзакций?
Есть у кого опыт, или чужие данные?
Единственное "но" - если мы хотим потенциальную возможность дробить
базу на несколько компов, то - опаньки!
Никаких nested sets, иначе поимеем nested sex с синхронизацией
распределенных поддеревьев.
В этом варианте только ID предка годится, ибо не требует обратного
крестного хода по дереву на каждый апдейт.
Dmitrij Maslennikov
Да, и не забываем о текущих задачах!
Dmitrij Maslennikov
Nested Sets приятны и даже главная их проблема - подъем вверх с
update'ами на каждой ноде при вставке и удалении - она не выглядит так
уж страшно в нашем случае, ибо изменения дерева будут случаться редко
в сравнении с чтением.
Единственное в чем я не уверен, так это в оптимизации запроса поиска
ноды по полному пути - самая частая операция будет.
Откуда такая уверенность, что запись -- редкая операция взялась? Все об этом пишут, а я никак не пойму. По-моему это от использования зависит, значит нам придется ограничить себя условием, что запись -- редкая операция, а оно нам нужно?
Единственное "но" - если мы хотим потенциальную возможность дробить
базу на несколько компов, то - опаньки!
Никаких nested sets, иначе поимеем nested sex с синхронизацией
распределенных поддеревьев.
В этом варианте только ID предка годится, ибо не требует обратного
крестного хода по дереву на каждый апдейт.
Нет, я думаю, нам не надо разносить базу по компам :) По крайней мере, пока такого не требовалось. Только несколько среплицированных серверов, а базы едины.
ivan.a....@gmail.com
Еще пара замечаний, пока качается ядро с OpenVZ.
Netsted Sets, по крайней мере в обычном их виде, не подходят для реализации
отношения группа-объект_в_группе - оно же не дерево, а граф.
Что же касается получения пути - пожалуй вполне можно организовать индекс или
вьюшку или вложенный запрос из пар (объект, предок) где предок - не
обязательно прямой, и оттуда уже формировать список предков. Если добавить в
схему level (длина пути по дереву до корня) - то вот тебе и путь, и очень
неплохо считаются стекающие ACL - как max(level) для определенного джойна.
В общем, стоит пощупать несколько вариантов и полюбоваццо на самое красивое
что получится. Но этот мост мы сожжем когда доберемся до него (c).
Pablo Juanych
> этом пишут, а я никак не пойму. По-моему это от использования зависит,
> значит нам придется ограничить себя условием, что запись -- редкая операция,
> а оно нам нужно?
А оно так и будет - в директорию пишуть редко, а "редко" здесь понятие
сравнительное, сравниваем с чтениями.
Важный момент: я говорю про запись в таблицы с иерархиями, даже не в
таблицы с объектами. Изменение списка и иерархии объектов (а не
свойств объектов) - это действительно редкая операция.
Самая же частая операция - поиск объекта в иерархии (т.е. не по ID, а
по пути). Вот её и стоит заоптимизировать по самые помидоры.
На мой взгляд, единственная задача для БД директории, требующая писать
столько же сколько читать, это аудит.
Соответственно, если предусмотреть разделение объектов аудита и данных
аудита на уровне таблиц, то проблема эта даже не возникнет и можно
вести иерархические деревья в виде nested sets, да и вообще в любом
удобном виде.
Pablo Juanych
> отношения группа-объект_в_группе - оно же не дерево, а граф.
Если я правильно помню, то этот граф не свободный, он с ограничениями
на отношения и стекание.
В общем, ентот граф разворачивается в два дерева (блин, или три??)
связанных как раз через узлы и вершины - записи в таблицах объектов.
А с двумя деревами в отдельных таблицах работать веселее чем с полным
графом в одной табличище ;)
> Что же касается получения пути - пожалуй вполне можно организовать индекс или
> вьюшку или вложенный запрос из пар (объект, предок) где предок - не
> обязательно прямой, и оттуда уже формировать список предков.
Согласен полностью - это всё вполне оптимизируется. Главное решить как.
> В общем, стоит пощупать несколько вариантов и полюбоваццо на самое красивое
> что получится. Но этот мост мы сожжем когда доберемся до него (c).
Ну, это как всегда - вопрос сроков. Если сроки терпят, можно
эксперименты себе позволить :)
Dmitrij Maslennikov
Ну, это как всегда - вопрос сроков. Если сроки терпят, можноСроки не терпят.
эксперименты себе позволить :)
Тебя не было, а вот мы решили сделать очень быстро решение работающее, но с сильно урезанным функционалом.
А потом его можно разширять сколько угодно. Тем более фирмам на 5-15 компьютеров никакие феерические возможности не требуются, а внедрение начнется именно с них.
Первое решение, предположительно, не будет иметь деревьев вообще, а только простые списки (список пользователей, групп и компьютеров).
Зато там будет отработан механизм разворачивания и будут необходимые элементы, например, DNS. И его можно будет показывать, а не только обещать :)
Roman Eremenko
Nested sets - красивое решение, единственная проблема - при вставке нового узла число апдейтов зависит от числа объектов в базе. Впрочем поля целочисленные и на уровне первоначального решения наверное не принципиально.
Прошу всё же отписаться по вопросам case/diagram-средств и выслать схему объектов (юзеры, acl, авторизации).
maslen...@gmail.com
> Я сейчас не буду комментировать все записи, немного утону:(
>
> Nested sets - красивое решение, единственная проблема - при вставке нового
> узла число апдейтов зависит от числа объектов в базе. Впрочем поля
> целочисленные и на уровне первоначального решения наверное не
> принципиально.
>
> Прошу всё же отписаться по вопросам case/diagram-средств и выслать схему
> объектов (юзеры, acl, авторизации).
>
нам сейчас важнее. А база и иерархия потом.
Roman Eremenko
То есть лучше спроектировать без завязки на глобальное дерево? В принципе так даже лучше...
maslen...@gmail.com
> Так там тоже деревья, не везде правда.
> То есть лучше спроектировать без завязки на глобальное дерево? В принципе
> так даже лучше...
уметь описывать зоны и добавлять в них записи. Вот минимальный сервер и
нужен, но ОЧЕНЬ быстро. Так как без него не работает kerberos.