Эффективный тест членства в группе для ACL на AppEngine - PullRequest
Новая
       27

Эффективный тест членства в группе для ACL на AppEngine

0 голосов
/ 25 января 2012

Я создаю список контроля доступа для объектов в моем хранилище данных. Каждая запись ACL может иметь список всех идентификаторов пользователей, которым разрешен доступ к соответствующей записи. Тогда мой запрос на получение списка сущностей, к которым пользователь может получить доступ, будет довольно простым:

select * from ACL where accessors = {userId} and searchTerms >= {search}

Проблема в том, что он может поддерживать только 2500 пользователей, прежде чем он достигнет предела записи индекса, и, конечно, было бы очень дорого помещать запись ACL с большим количеством пользователей, потому что многие записи индекса должны были бы быть изменены.

Поэтому я подумал о добавлении списка групп пользователей, которым разрешен доступ к объекту. Это может значительно снизить количество записей индекса, необходимых для каждой записи ACL, но запросы становятся длиннее, потому что мне приходится запрашивать каждую возможную группу, в которой находится пользователь: 

select * from ACL where accessors = {userId} and searchTerms >= {search}
for (GroupId id : theSetOfGroupsTheUserBelongsTo) {
    select * from ACL where accessingGroups = {id} and searchTerms >= {search}
}

mergeAllTheseResultsTogether()

, что займет много времени, будет гораздо сложнее пролистать и т. Д.

Кто-нибудь может порекомендовать способ получить список объектов из ACL, который не ограничивает число обращающихся пользователей?

Изменить для более подробной информации:

Я ищу и сортирую длинный набор академических тем, которые используются в школе. Некоторые из тем созданы администраторами и должны быть общешкольными. Другие создаются учителями и, вероятно, имеют отношение только к этим учителям. Я хочу создать иерархию коллекций в стиле google-docs-list, которая рассматривает каждую тему как документ. Поле searchTerms будет списком слов в названии темы - не так много внутреннего текста для поиска. Каждая тема будет находиться как минимум в одной коллекции («корневой» коллекции организации) и может быть в 10-20 других коллекциях, управляемых разными людьми. В идеале не должно быть верхнего предела числа коллекций, в которых может появиться документ. Моя задача здесь состоит в том, чтобы составить список всех сущностей, к которым у определенного пользователя есть доступ по крайней мере для чтения - аналогом в документах Google будет Просмотр «Все элементы».

1 Ответ

2 голосов
/ 14 марта 2012

Предполагая, что ваши документы и разрешения групп изменяются реже (или менее критично по времени), чем пользовательские запросы, я предлагаю следующее (именно так я решаю похожую проблему):

В вашем ACL,включают поля

  • аксессоры <- все идентификаторы пользователя, которые могут получить доступ к документу </li>
  • numberOfAccessors <- хранить длину аксессоров при каждом изменении этого поля </li>
  • searchTerms

Имя ключа для ACL будет выглядеть примерно так: "indexed_document_id||index_num"

index_num в ключе позволяет вам иметь несколько объектов, хранящих список пользователей, в случае если их более 5000(ограничение хранилища данных для элементов в списке) или столько, сколько вы хотите иметь в списке, чтобы снизить стоимость загрузки одного (хотя вам не нужно делать это часто).

Не забывайте, что документ, к которому необходимо получить доступ, должен быть родительским элементом объекта индекса .таким образом вы можете выполнить запрос select __key__ вместо select * (это позволяет избежать десериализации полей accessor и searchTerms).Вы можете искать и возвращать parent () объекта без необходимости доступа к какому-либо из полей.Подробнее об этом и другом поисковом дизайне в этом сообщении в блоге .К сожалению, эта публикация блока не охватывает индексы ACL, подобные нашим.

Отказ от ответственности: я столкнулся с проблемой этого дизайна в том, что к какому документу пользователь имеет доступ, зависит от того, следят ли они за этим пользователем.Это означает, что, если они подписались или отменили подписку, там может быть большое количество существующих документов, из которых пользователь должен быть добавлен / удален.Если это так, то вы можете застрять в той же дыре, что и я, если будете следовать моей технике.В настоящее время я планирую справиться с этим путем обновления индексов для старых документов в фоновом режиме.У кого-то еще, отвечающего на этот вопрос, может быть решение, запеченное в нем - если нет, я могу опубликовать его как отдельный вопрос.

Анализ операций с этой структурой данных:

Добавить индексированныйdocument:

  1. Для каждой группы, имеющей доступ к документу, создайте сущность, включающую всех пользователей, которые могут получить к ней доступ, в поле доступа
  2. Если их слишком многочтобы поместиться в одно поле, сделать больше сущностей и увеличить значение index_num (используя счетчики с заштрихованными значениями).

O (n * m), где n - количество пользователей, а m - количество поисковых запросов * 1041.*

Запрос индексированного документа:

  1. select __key__ from ACL where accessors = {userid} and searchTerms >= {search} (хотя я не уверен, почему вы на самом деле делаете "> =", в моих запросах это всегда "=")
  2. Получить все родительские ключи из этих ключей
  3. Отфильтровать дубликаты
  4. Получить эти родительские документы

O (n + m)где n - количество пользователей, а m - количество поисковых запросов - это довольно быстро.он использует зигзагообразное объединение двух индексов (один для методов доступа, другой для поисковых запросов).это предполагает, что сканирование индекса gae является линейным.они могут быть логарифмическими для запросов "=", но я не знаком с дизайном их индексов, и я не проводил никаких тестов для проверки.Также обратите внимание, что вам не нужно загружать какие-либо свойства объекта индекса.

Добавить доступ пользователя к определенному документу

  1. Проверьте, непользователь уже имеет доступ: select __key__ from ACL where accessor = {userid} and parent = {key(document)}
  2. Если нет, добавьте его: select * from ACL where parent = {key(document)} and numberOfAccessors < {5000 (or whatever your max is)} limit 1
  3. Добавьте {userid} к методам доступа и поместите сущность

O (n) где n - количество людей, которые имеют доступ к документу.

Удалить доступ пользователя к определенному документу

  1. select * from ACL where accessor = {userid} and parent = {key(document)}
  2. Удалить {userid} из средств доступа и поместить объект

O (n) где n - количество людей, имеющих доступ к документу.

Сжатие индексов

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

  1. Чтобы выяснить, есть ли что-нибудь, что нужно сжать для конкретного документа: select * from ACL where parent = {key(document)} and numberOfAccessors < {2500 (or half wahtever your max is)}
  2. Для каждой / любой пары из них: удалить одну, добавив методы доступа к другой

O (n) где n - количество людей, имеющих доступ к документу

...