Этот текст посвящен тому, как ускорить выборку закрытых данных в многопользовательских проектах.
Некоторые вещи рассмотренные вначале могут быть уже хорошо вам известны, но учитывая, что вопросы о разграничении прав доступа задаются регулярно, я счел нужным рассмотреть их подробнее.
Для гуру ценным там может быть разве что обоснования, чем именно нехорош этот метод. Если для вас это и так понятно, перейдите сразу к пункту «двоичные маски», там и содержится самое основное.
Многие сервисы позволяют пользователю размещать в сети различные данные, при этом самому размещающему, как правило, требуется ограничивать круг лиц, которые могут просматривать, комментировать его записи или изображения. Для этих целей разработчики создают различные системы контроля прав.
При этом следует учесть, что в большинстве сервисов элементы выводятся в виде списка, и элементы чтение которых не разрешено в списке показывать не следует. В отличии, например, от файловой системы, где можно показать файл в списке, и проверить права уже на этапе открытия, скрытая запись блога или «превью» фотографии не должны показываться вообще, так как уже несут в себе некоторую информацию.
Примером такого разделения является система секретности в государственных учреждениях, то есть каждый имеет субъект некоторый уровень доступа, и каждый объект имеет некоторый уровень секретности, для чтения объекта требуется уровень доступа не меньший уровня секретности.
Для интернет сайтов, как правило, выполняется разделения по уровням: «знакомые», «друзья», «родственники». Кроме того по тому же принципу (только для действий) работает механизм «кармы» на сайте habrahabr.ru
Таким образом выборка осуществляется по двум таблицам:
Таким образом выбрать разрешенные записи можно следующим образом:
Представленный метод имеет один существенный недостаток, мы ограничены только сравнением уровня доступа, т.е. в рассматриваемом случае запись доступная друзьям, будет доступна и родителям, что, согласитесь, не всегда удобно.
ACL — система списков доступа, в которой роли (группе) можно разрешить или запретить некоторое действие над произвольным объектом. При этом один объект может наследовать от другого права доступа.
Также принадлежность к роли может быть вычислено на лету по отношению к объекту.
Это называется «виртуальными группами», например виртуальной группой может быть «владелец», которая вычисляется как user_id=object.owner_id. Дисковые квоты также можно реализовать как виртуальную группу: пользователи у которых загружено менее N мегабайт.
ACL является невероятно гибким и удобным инструментом при работе с правами, подробнее про ACL вы можете прочитать в книге "Защищенный код", в которой очень подробно расписан механизм списков доступа в ОС Windows, если у вас вызывает отторжение все, что связано с Microsoft или вы хотите сразу задействовать этот механизм на вашем сайте, то вам стоит обратиться к документации библиотеки zend_acl.
Несмотря на все плюсы, ACL имеет существенные недостатки:
Итак, как правило, у пользователя есть несколько групп, предположим, «друзья», «коллеги» и «родственники», которым он хочет разрешать читать определенные записи.
При этом:
Таким образом имеем следующую структуру:
Таким образом, выборка записей происходит с помощью следующего запроса:
В принципе в таком виде может хранить вся картина прав, но делать этого не стоит.
Не смотря на простоту и элегантность решение оно имеет существенные недостатки, которые будут рассмотрены ниже, там же я постараюсь показать решения.
Въедливый читатель уже заметил прореху в наших рассуждениях: прочитать запись может только тот пользователь, которому это явно разрешено.
По-умолчанию же в большинстве случаев записи являются открытыми, и читать их может кто угодно.
Можно решить это с помощью хитрого запроса с LEFT JOIN, но в итоге мы имеем условие на присоединяемую таблицу, что есть вселенское зло.
Можно сделать виртуальную группу «Все», в которую входит любой пользователь и которой разрешено читать публичные записи. Но это не очень хорошо по отношению к ресурсам и вообще некрасиво на каждый чих создавать бессмысленные записи.
Поэтому введем новое свойство у records: public, это нам позволит:
Еще в последнем запросе используются нехорошее слово DISTINCT, да и выборка идет по трем таблицам, да еще и с отношениями один ко многим, это не может не беспокоить.
Для того чтобы что-то получить, надо чем-то пожертвовать, введем некоторые граничные условия:
Исходя из этого сократим число таблиц до двух:
аccess и mask- двоичные маски определяющие доступ для групп владельца записи и принадлежность к группам данного пользователя.
Т.е. каждому биту маски соответсвует группа, int у нас имеет 32 разряда, поэтому и количество групп ограничено 32 (несколько бит можно зарезервировать).
Связи пользователей:
Доступ к записям:
Таким образом, выяснить имеет ли пользователь право читать запись можно выполнив побитовое "&" над масками. Побитовые операции-быстрые, потому что на них все и основано.
Таким образом запрос выглядит так:
Или с учетом поля public:
При тестировании сравнивалась производительность решения с пользовательскими группами и решения с битовыми масками.
Как мы видим выигрыш весьма существенный, что оправдывает ограничения накладываемые последним методом.
Отдельно скажу, что на реальном проекте применяется ACL (собственной разработки), которая съедает изрядную часть ресурсов и создает существенные сложности для разработчиков.
Время выборки усредненное по 4-м пользователям созданным вручную. Все остальные пользователи создавались автоматически, каждый такой пользователь имел 10 друзей и 10 записей «для друзей»
Как видно из результатов скорость выборки различается на 2 порядка, при этом решение с таблицами расширяемое, скорость выборки мало зависит от количество записей
Следует заметить, что если пользователь состоит в двух группах («друзья» и «коллеги»), то на скорость выборки по маске это не влияет. А выборка по группам (задействуется DISTINCT) занимает несколько секунд (ужас ужас), я даже не стал использовать это в сводной таблице.
Получается, что для повышения производительности системы прав, можно создавать дополнительные легко индексируемые инструменты.
Я никоим образом не призываю отказываться от ACL или других сложных систем разграничения прав, но при этом в некоторых использовать оптимизированные под конкретную задачу решения.
Если вы знаете более эффективные способы разграничения прав доступа, или осведомлены о, неизвестных мне, аспектах рассмотренных милости прошу в комментарии.
Некоторые вещи рассмотренные вначале могут быть уже хорошо вам известны, но учитывая, что вопросы о разграничении прав доступа задаются регулярно, я счел нужным рассмотреть их подробнее.
Для гуру ценным там может быть разве что обоснования, чем именно нехорош этот метод. Если для вас это и так понятно, перейдите сразу к пункту «двоичные маски», там и содержится самое основное.
Многие сервисы позволяют пользователю размещать в сети различные данные, при этом самому размещающему, как правило, требуется ограничивать круг лиц, которые могут просматривать, комментировать его записи или изображения. Для этих целей разработчики создают различные системы контроля прав.
При этом следует учесть, что в большинстве сервисов элементы выводятся в виде списка, и элементы чтение которых не разрешено в списке показывать не следует. В отличии, например, от файловой системы, где можно показать файл в списке, и проверить права уже на этапе открытия, скрытая запись блога или «превью» фотографии не должны показываться вообще, так как уже несут в себе некоторую информацию.
Разделение прав на основе уровня доступа.
Примером такого разделения является система секретности в государственных учреждениях, то есть каждый имеет субъект некоторый уровень доступа, и каждый объект имеет некоторый уровень секретности, для чтения объекта требуется уровень доступа не меньший уровня секретности.
Для интернет сайтов, как правило, выполняется разделения по уровням: «знакомые», «друзья», «родственники». Кроме того по тому же принципу (только для действий) работает механизм «кармы» на сайте habrahabr.ru
Таким образом выборка осуществляется по двум таблицам:
| records — записи | ||
| id | int | Идентификатор записи |
| us_id | int | Владелец |
| level | int | Уровень секретности |
| user_levels — уровни доступа | ||
| us_id | int | Пользователь |
| cor_id | int | Связанный пользователь |
| level | int | Уровень доступа |
Таким образом выбрать разрешенные записи можно следующим образом:
SELECT `records`.`id`
FROM `records`, `level`
WHERE `records`.`us_id`=`user_levels`.`us_id`
AND `records`.`level`<=`users`.`level`
AND `user_levels`.`cor_id`=$us_id;Представленный метод имеет один существенный недостаток, мы ограничены только сравнением уровня доступа, т.е. в рассматриваемом случае запись доступная друзьям, будет доступна и родителям, что, согласитесь, не всегда удобно.
ACL
ACL — система списков доступа, в которой роли (группе) можно разрешить или запретить некоторое действие над произвольным объектом. При этом один объект может наследовать от другого права доступа.
Также принадлежность к роли может быть вычислено на лету по отношению к объекту.
Это называется «виртуальными группами», например виртуальной группой может быть «владелец», которая вычисляется как user_id=object.owner_id. Дисковые квоты также можно реализовать как виртуальную группу: пользователи у которых загружено менее N мегабайт.
ACL является невероятно гибким и удобным инструментом при работе с правами, подробнее про ACL вы можете прочитать в книге "Защищенный код", в которой очень подробно расписан механизм списков доступа в ОС Windows, если у вас вызывает отторжение все, что связано с Microsoft или вы хотите сразу задействовать этот механизм на вашем сайте, то вам стоит обратиться к документации библиотеки zend_acl.
Несмотря на все плюсы, ACL имеет существенные недостатки:
- В документации к zend_acl, содержится фрагмент про хранение списков, в котором написано: программист может хранить таблицу доступа, где ему заблагорассудиться, например сериализовав.
В этом и кроется главное загвоздка, структура таблиц доступа достаточно нетривиальна и ее довольно сложно нормализовать для хранения, т.е. как правило они и хранятся в сериализованном виде.
Получается, что для того, чтобы узнать может ли пользователь читать запись, эту запись необходимо сначала получить, потом инициировать ее ACL и только потом проверить доступ.
Т.е. для получения списка, или (оееей) количества элементов, нам надо выбирать больше записей, чем необходимо отобразить, да еще из неопределенными граничными условиями.
Сделать это на этапе выборки, прямо в запросе практически не возможно.
Да многие базы данных позволяют работать с сериализованными структурами, и даже индексировать их, но издержки на это, все равно слишком велики. - Гибкость ACL компенсируется сложностью настройки, практика показывает, что даже разработчики с великим трудом могут составить ACL для своих нужд, что говорить о конечных пользователях.
Поэтому я считаю, что механизм ACL является избыточным, для большинства нужд, поэтому их следует там, где это действительно необходимо, а для частых простых случаев (как раз ограничение чтения) использовать более простые инструменты.
Пользовательские группы.
Итак, как правило, у пользователя есть несколько групп, предположим, «друзья», «коллеги» и «родственники», которым он хочет разрешать читать определенные записи.
При этом:
- один и тот же пользователь может входить в несколько групп одновременно (быть «другом» и «коллегой», хотя это и противопоказано)
- запись может быть открыта для одной или нескольких групп (например о вашем желании сменить работу должны знать друзья и родственники, а вот коллегам знать об этом совсем не обязательно).
Таким образом имеем следующую структуру:
| records — записи | ||
| id | int | Идентификатор записи |
| us_id | int | Владелец |
| record_permissions — кому можно читать | ||
| record_id | int | Идентификатор записи |
| group | int | Идентификатор группы |
| group_members- члены групп | ||
| us_id | int | Пользователь |
| group | int | Идентификатор группы |
Таким образом, выборка записей происходит с помощью следующего запроса:
SELECT DISTINCT `records`.`id` , `records`.`name`
FROM `records` , `record_permissions` , `group_members`
WHERE `records`.`public` =0
AND `records`.`id` = `record_permissions`.`record_id`
AND `record_permissions`.`group_id` = `group_members`.`group_id`
AND `group_members`.`us_id` =$us_idВ принципе в таком виде может хранить вся картина прав, но делать этого не стоит.
- Хранить права на действия лучше в ACL, на практике вы никогда не воспользуетесь этими данными.
- Права на изменение, создание, удаление меняются гораздо реже, и если вы такой фанат нормализации БД храните их хотя бы в отдельной таблице, дабы не захламлять ту, с которой работаете (или сделайте view, если СУБД это умеет)
Не смотря на простоту и элегантность решение оно имеет существенные недостатки, которые будут рассмотрены ниже, там же я постараюсь показать решения.
Публичные записи.
Въедливый читатель уже заметил прореху в наших рассуждениях: прочитать запись может только тот пользователь, которому это явно разрешено.
По-умолчанию же в большинстве случаев записи являются открытыми, и читать их может кто угодно.
Можно решить это с помощью хитрого запроса с LEFT JOIN, но в итоге мы имеем условие на присоединяемую таблицу, что есть вселенское зло.
Можно сделать виртуальную группу «Все», в которую входит любой пользователь и которой разрешено читать публичные записи. Но это не очень хорошо по отношению к ресурсам и вообще некрасиво на каждый чих создавать бессмысленные записи.
Поэтому введем новое свойство у records: public, это нам позволит:
- Вытягивать без лишних обращений к системе привилегий записи для блоков вроде: «последнее на сайте»
- Выводить записи для незарегистрированных пользователей так же не задействуя проверку прав.
- Добавлять открытые записи путем простого UNION в запросе (UNION работает крайне быстро, его даже рекомендуют использовать вместо OR и IN, для особо запутанных случаем)
Двоичные маски.
Еще в последнем запросе используются нехорошее слово DISTINCT, да и выборка идет по трем таблицам, да еще и с отношениями один ко многим, это не может не беспокоить.
Для того чтобы что-то получить, надо чем-то пожертвовать, введем некоторые граничные условия:
- Пользователь может открыть записи только для своих групп.
Мало кому может понадобиться открыть свои записи «друзьям Васи», да и в этом случае это будет непросто сделать на уровне интерфейса. - Пользователь может иметь ограниченное число групп.
Человек может запомнить 5±2 объекта, в большом количестве групп легче запутаться, чем что-либо понять.
Исходя из этого сократим число таблиц до двух:
| records — записи | ||
| id | int | Запись |
| us_id | int | Пользователь |
| access | int | Маска доступа |
| public | bool | Флаг публичной записи |
| user_references- отношения пользователей | ||
| us_id | int | Пользователь |
| cor_id | int | Связанный пользователь |
| mask | int | Маска отношений |
аccess и mask- двоичные маски определяющие доступ для групп владельца записи и принадлежность к группам данного пользователя.
Т.е. каждому биту маски соответсвует группа, int у нас имеет 32 разряда, поэтому и количество групп ограничено 32 (несколько бит можно зарезервировать).
Пример.
Связи пользователей:
| Друзья | Семья | Коллеги | Пользователь | Итого |
| 1 | 0 | 0 | Друг | 1 |
| 0 | 1 | 0 | Мама | 2 |
| 0 | 0 | 1 | Коллега | 4 |
| 1 | 0 | 1 | Друг-коллега | 5 |
Доступ к записям:
| Друзья | Семья | Коллеги | Запись | Итого |
| 0 | 0 | 0 | Только я | 0 |
| 0 | 1 | 0 | Мама привет! | 2 |
| 0 | 0 | 1 | Рабочее | 4 |
| 1 | 1 | 0 | Хочу уволиться! | 3 |
Таким образом, выяснить имеет ли пользователь право читать запись можно выполнив побитовое "&" над масками. Побитовые операции-быстрые, потому что на них все и основано.
Таким образом запрос выглядит так:
SELECT `records`.`id` , `records`.`name`
FROM `records` , `user_references`
WHERE `records`.`public` =0
AND `records`.`us_id` = `user_references`.`us_id`
AND `records`.`access` & `user_references`.`mask`
AND `user_references`.`cor_id` =$us_idИли с учетом поля public:
SELECT `records`.`id` , `records`.`name`
FROM `records` , `user_references`
WHERE `records`.`public` =0
AND `records`.`us_id` = `user_references`.`us_id`
AND `records`.`access` & `user_references`.`mask`
AND `user_references`.`cor_id` =$us_id
UNION
SELECT `records`.`id` , `records`.`name`
FROM `records`
WHERE `public` =1Тестирование.
При тестировании сравнивалась производительность решения с пользовательскими группами и решения с битовыми масками.
Как мы видим выигрыш весьма существенный, что оправдывает ограничения накладываемые последним методом.
Отдельно скажу, что на реальном проекте применяется ACL (собственной разработки), которая съедает изрядную часть ресурсов и создает существенные сложности для разработчиков.
| Условия | По маске (сек) | По группам (сек) | Скорость в раз |
| MySql 4, 30 000 записей, 100 пользователей, 1000 связей, UNION | 0,00215 | 0,0107 | 4,98 |
| MySql 4, 500 000 записей, 10 000 пользователей, 100 000 связей | 0,00185 | 0,1346 | 72,76 |
| MySql 4, 500 000 записей, 10 000 пользователей, 100 000 связей UNION | 0,00215 | 0,1383 | 64,33 |
| MySql 5, 500 000 записей, 10 000 пользователей, 100 000 связей | 0,00135 | 0,169 | 125,19 |
Время выборки усредненное по 4-м пользователям созданным вручную. Все остальные пользователи создавались автоматически, каждый такой пользователь имел 10 друзей и 10 записей «для друзей»
Как видно из результатов скорость выборки различается на 2 порядка, при этом решение с таблицами расширяемое, скорость выборки мало зависит от количество записей
Следует заметить, что если пользователь состоит в двух группах («друзья» и «коллеги»), то на скорость выборки по маске это не влияет. А выборка по группам (задействуется DISTINCT) занимает несколько секунд (ужас ужас), я даже не стал использовать это в сводной таблице.
Итоги.
Получается, что для повышения производительности системы прав, можно создавать дополнительные легко индексируемые инструменты.
Я никоим образом не призываю отказываться от ACL или других сложных систем разграничения прав, но при этом в некоторых использовать оптимизированные под конкретную задачу решения.
Если вы знаете более эффективные способы разграничения прав доступа, или осведомлены о, неизвестных мне, аспектах рассмотренных милости прошу в комментарии.
