Оптимизации системы разделения прав доступа в веб-приложении

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

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

В этой статье я рассмотрю:
  1. Битовые поля, оптимизация
  2. Serialize с денормализацией таблиц БД
  3. Вы узнаете, как работает система, подобная Zend ACL

На чём мы остановились

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

	message_view	message_create	message_delete	message_edit
User21	+	+		+
Ban	-	-	-	-
Users	+
Admin	+	+	+	+

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

Превращение первое. Использование битовых масок.

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

Вместо плюсов будут 1, отсутствие действия 0.

Что мы выигрываем?

Разнообразных действий в веб-приложении обычно не превышает более 64. Следовательно, для большинства случаев, 64 бита будет более чем достаточно. (8 байт)
Для сравнения, каждая ячейка такой базы данных будет занимать по 40 байт. Это столько же, как и если мы будем хранить каждое действие отдельно, только в этом случае, у нас будет несколько записей на одного пользователя. Экономия на лицо :)
Новая таблица будет выглядеть теперь так:

	allow	disallow
User21	1101	0000
Ban	0000	1111
Users	1000	0000
Admin	1111	0000

Стало менее наглядно для человека, но более наглядно для компьютера.

Теперь наша (описанная в прошлой статье) база данных выглядит:

rights_action
ObjectRightsID: INT(pk)	UserGroupID: INT(fk)	Allow: VARBINARY(4)	Disallow: VARBINARY(4)
rights_group (устанавливает группы пользователям)
UserRightsID: INT(pk)	UserGroupID: INT

При объединении прав подобъектов с глобальными категориями объектов, можно пользоваться простыми OR (A|B для allow) и SUB (A&!B для disallow) операциями.

Теперь разберемся с проблемами интерфейса для программиста, чтобы биты у нас в программе не запутались.
Введем определение бита для действия:

  public $actions=array();

  /* SetAction
    Добавить новое действие
  
    @param {string} ActionName - имя действия
    @param {int} bitNumber - номер бита в БД
    @return {Object ObjRights} - объект с установленными действиями
  */
  public function SetAction($ActionName, $bitNumber){
    //проверяем использование бита
    if (array_search($bitNumber, $this->actions))
      return false;
    //проверяем использование имени
    if (isset($this->actions[$ActionName]))
      return false;
    //Клонируем и добавляем новый бит
    $clone = clone $this;
    $clone->actions[$ActionName]=$bitNumber;
    
    return $clone;
  }

Произведем небольшой Рефакторинг класса из прошлой статьи. Во первых разделим классы пользователя и действий. Это необходимо потому, что действия у нас не должны быть связанны с пользователем, но они будут привязаны к объектам. (Например, у объектов сообщений будут действия чтения, удаления, редактирования. У объектов учётных записей — действия объединения, просмотра итд)

Что делать, чтобы биты действий не пересекались?

В случае, когда каждое действие определялось не номером бита, а строкой (например 'message_view'), всё было для программистов совершенно ясно. Была определенная договорённость (например определять действия Название объекта_название действия), что давало ясность, к какому объекту это принадлежит и множественные варианты для отсутствия пересечения.

Чтобы сохранить совместимость в БД, можно использовать, либо отдельную общую БД Тип объекта->действие->номер бита, либо договориться для этого использовать один файл на всех.

Я приведу пример такого файла:

//Создаём новый объект прав для использования в объектах сообщения
$MessageRights=new ObjRights();

//добавляем возможные действия с этими объектами
$MessageRights=$MessageRights->SetAction('message_view',1)->SetAction('message_read',2)->SetAction('message_edit',3)->SetAction('message_delete',4)->SetAction('message_create',5);

//Комментарии в сообщениях
$MessageRights=$MessageRights->SetAction('comment_view',6)->SetAction('comment_create',7)->SetAction('comment_delete',8);

//Пользователи... Здесь нам не нужны работы с комментариями, по этому используем своё поле действий.
//Создаём новый объект прав для использования в объектах пользователей
$UserRights=new ObjRights();

$UserRights=$UserRights->SetAction('user_edit',1)->SetAction('user_delete',2)->SetAction('user_create',3);

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

//Класс прав для пользователя
class UsrRights{
  public $groupID=array();
  function __construct($rightsID){
    //Чтение из базы данных прав пользователя (ролей) групп, к которым пользователь принадлежит
    $result=mysql_query("SELECT `group_rights`.groupID FROM `group_rights` WHERE `group_rights`.rightsID = $rightsID");

    $this->groupID = array();
    while ($t=mysql_fetch_assoc($result)){
      //Считываем все ID групп
      $this->groupID[] = $t['groupID'];
    }
    mysql_free_result($result);
  }
}

//Класс соответствия прав и действий для объектов
class ObjRights{
  public $actions=array();
  public $groupallow=array(),$groupdisallow=array();
  /* SetAction
    Добавить новое действие
  
    @param {string} ActionName - имя действия
    @param {int} bitNumber - номер бита в БД
    @return {Object ObjRights} - объект с установленными действиями
  */
  public function SetAction($ActionName, $bitNumber){
    //проверяем использование бита
    if (array_search($bitNumber, $this->actions))
      return false;
    //проверяем использование имени
    if (isset($this->actions[$ActionName]))
      return false;
    //Клонируем и добавляем новый бит
    $clone = clone $this;
    $clone->actions[$ActionName]=$bitNumber;
    
    return $clone;
  }

  /* include_right
    Добавить все права подобъекта
  
    @param {int} RightsID - идентификатор права
    @return {Object ObjRights} - объект с установленными правами
  */
  public function include_right($RightsID){
    $clone=clone $this;
    $result=mysql_query("SELECT * FROM `action_rights` WHERE `action_rights`.rightsID = $RightsID");
    while ($t=mysql_fetch_assoc($result)){
      //Добавляем к каждой группе новые права
      $clone->calculate_allow($t['groupID'],$t['allow'],$t['disallow']);
    }
    mysql_free_result($result);
  
    return $clone;
  }

  /* calculate_allow
    Изменяет права определенной группы, добавляя новые способности
  
    @param {int} GroupID - идентификатор группы
    @param {string} AllowMask - двоичная маска допустимых действий для группы
    @param {string} DisallowMask - двоичная маска не допустимых действий для группы
  */
  private function calculate_allow($GroupID, $AllowMask, $DisallowMask){
    if (isset($this->groupallow[$GroupID])){
      //Длина - меньшее из масок - для совместимости
      $len=min(strlen($this->groupallow[$GroupID]),strlen($AllowMask));
      for ($i=0;$i<$len;$i++)
        //Allow |= Mask
        $this->groupallow[$GroupID]{$i}=chr(ord($this->groupallow[$GroupID]{$i})|ord($AllowMask{$i}));

      //Длина - меньшее из масок - для совместимости
      $len=min(strlen($this->groupdisallow[$GroupID]),strlen($DisallowMask));
      for ($i=0;$i<$len;$i++)
        //Disallow |= Mask
        $this->groupdisallow[$GroupID]{$i}=chr(ord($this->groupdisallow[$GroupID]{$i})|ord($DisallowMask{$i}));
    }else{
      $this->groupallow[$GroupID]=$AllowMask;
      $this->groupdisallow[$GroupID]=$DisallowMask;
    }
  }
  /* isAllow
    Проверяет группы пользователя и выдаёт разрешение на определенное действие над объектом
  
    @param {Object UsrRights} UserRights - идентификатор групп, в которых находится пользователь
    @param {string} ActionName - название действия
    @return {bool} - может ли пользователь сделать заданное действие?
  */
  public function isAllow($UserRights, $ActionName){
    //Существует имя?
    if (!isset($this->actions[$ActionName]))
      return false;
    //Берет номер бита по имени
    $Actionbit=$this->actions[$ActionName];
    
    foreach ($UserRights->groupID as $grpname){
      //Проверяем каждую группу
      if ($this->checkgrp($grpname,$Actionbit))
        //Если хоть в одной есть разрешение, то всё хорошо
        return true;
    }
    return false;
  }

  /* checkgrp
    Проверяет бит в группе объекта
  
    @param {int} GroupID - идентификатор группы
    @param {int} bit - номер бита
    @return {bool} - может ли заданная группа сделать заданное действие
  */
  private function checkgrp($GroupID, $bit){
    //Есть ли группа?
    if (isset($this->groupallow[$GroupID])){
      //проверяем само действие Allow & NOT Disallow & bit
      if ((ord($this->groupallow[$GroupID]{$bit>>3})&(~ord($this->groupdisallow[$GroupID]{$bit>>3}))&(1<<($bit&7)))!=0){
        return true;
      }
    }
    return false;
  }
}

* This source code was highlighted with Source Code Highlighter.

Использовать данную библиотеку просто. Необходимо сначала распределить допустимые права по классам объектов (пример выше), а затем инициализировав пользователя (меня его идентификатор на группы прав), проверять его с необходимыми правами в объекте:

//установка бит действий
$MessageRights = new ObjRights();
$MessageRights = $MessageRights->SetAction('message_view',0)->
                 SetAction('message_read',1)->
                 SetAction('message_edit',2)->
                 SetAction('message_delete',3)->
                 SetAction('message_create',4);
//...

//получаем все права пользователя (роли)
$CurrentUserRights = new UseRights($CurrentUser->rightsID);

//...

//Добавляем права объекта, с которыми должен иметь дело пользователь.
$PageRights = $MessageRights->include_right($MainPage->rightsID);

//Проверяем, может ли пользователь просматривать страницу?
if ($PageRights->isAllow($CurrentUserRights,'message_view')){
  //Да, может. Но что делать с сообщениями?

  //Пройдемся по каждому из них
  foreach($MainPage->Messages as $msg){
    //Добавляем к правам страницы (parent), личные права сообщения (child)
    $MsgRights = $PageRights->include_right($msg->rightsID);

    //И проверяем на читаемость
    if ($MsgRights->isAllow($CurrentUserRights,'message_view')){
      //И если оно читается, проверяем можем ли мы редактировать сообщения?
      if ($MsgRights->isAllow($CurrentUserRights,'message_edit'))
        $msg->editable_flag = 1;
      //А удалять сообщения?
      if ($MsgRights->isAllow($CurrentUserRights,'message_delete'))
        $msg->delete_flag = 1;
  
      DrawMessage($msg);
    }
  }
}

В результате, по сравнению с примером из первой статьи, мы в несколько раз ускорили доступ к БД и уменьшили количество обращений.

Но можно ли ещё быстрее?
Да, можно сделать ещё несколько оптимизаций кода, но я не буду, чтобы не терять наглядности (и так кода слишком много навалилось :) ).
Мы пойдём просто другим путём, улучшив алгоритм…

Превращение второе. Получение готовых PHP-объектов из БД.

Сейчас мы поговорим о том, как оптимизируют свой код строители сайтов с большой посещаемостью пользователей.
Создатели PHP создали две функции, с помощью которых можно сохранить и получить готовые структуры(массивы, объекты) данных.
Это функции serialize и unserialize.

А чем они нам помогут?

Сейчас в нашем коде, при выборке каждого сообщения (объекта), имеющего (неизменные) свои права, происходит дополнительная выборка из таблицы rights_action. Для каждого объекта — эта выборка получается одинаковой, пока мы не решим её изменить (добавив новые права объекту). За одно изменение прав нашего объекта, происходит более тысячи/миллионы считываний.
Зачем выполняется несколько лишних преобразований в необходимый нам формат. Так происходит каждое считывание. Таким образом, это можно сделать всего один раз (при генерации/изменении прав) и сохранить готовый результат. Для сохранения результата, и востановления нам помогут функции serialize/unserialize.

Доработаем нашу библиотеку:

  public function include_right($grp){
    //создаём ещё один такой объект (child)
    $clone=clone $this;

    //результат у нас выглядит, как готовая выборка
    $result=unserialize($grp);

    //результат лежит как array('GroupID'=>array('allow_bits','disallow_bits'),'GroupID2'=>array('allow_bits','disallow_bits'),...)
    foreach ($result as $groupID=>$allow)
      //проходимся по каждой группе, добавляя результаты к клону
      $clone->include_action($groupID,$allow[0],$allow[1]);

    return $clone;
  }

Стало проще и нагляднее!
Правда в этом случае, у нас появляется проблема изменения прав (для каждой маски). Попробуем написать функции для этого:

  public function export_object_rights(){
    return serialize($this->selfrights);
  }

  public function allow_group($GroupID, $ActionName){
    if (!isset($this->actions[$ActionName]))
      return false;
    $bit=$this->actions[$ActionName];

    if (isset($this->groupallow[$GroupID])){
      $this->groupallow[$GroupID]{$bit>>3}|=(1<<($bit&8));
    }else{
      $this->groupallow[$GroupID]{$bit>>3}=(1<<($bit&8));
      for ($i=0;$i<($bit>>3);$i++)
        $this->groupallow[$GroupID]{$i}=chr(0);
    }

    if (isset($this->selfrights[$GroupID])){
      $this->selfrights[$GroupID][0]{$bit>>3}|=(1<<($bit&8));
    }else{
      $this->selfrights[$GroupID]=array();
      $this->selfrights[$GroupID][0]{$bit>>3}=(1<<($bit&8));
      for ($i=0;$i<($bit>>3);$i++)
        $this->selfrights[$GroupID][0]{$i}=chr(0);
      $this->selfrights[$GroupID][1]="";
    }
  } 

  public function reset_group($GroupID, $ActionName){
    if (!isset($this->actions[$ActionName]))
      return false;
    $bit=$this->actions[$ActionName];
    
    if (isset($this->groupallow[$GroupID])){
      $this->groupallow[$GroupID]{$bit>>3}&=255^(1<<($bit&8));
    }

    if (isset($this->groupdisallow[$GroupID])){
      $this->groupdisallow[$GroupID]{$bit>>3}&=255^(1<<($bit&8));
    }

    if (isset($this->selfrights[$GroupID])){
      $this->selfrights[$GroupID][0]{$bit>>3}&=255^(1<<($bit&8));
      $this->selfrights[$GroupID][1]{$bit>>3}&=255^(1<<($bit&8));

      $nul=true;
      for ($i=0;$i<strlen(selfrights[$GroupID][0]);$i++)
        if (selfrights[$GroupID][0]{$i})
          $nul=false;

      for ($i=0;$i<strlen(selfrights[$GroupID][1]);$i++)
        if (selfrights[$GroupID][1]{$i})
          $nul=false;

      if ($nul)
        unset(selfrights[$GroupID]);
    }
  } 

  public function disallow_group($GroupID, $ActionName){
    if (!isset($this->actions[$ActionName]))
      return false;
    $bit=$this->actions[$ActionName];

    if (isset($this->groupdisallow[$GroupID])){
      $this->groupdisallow[$GroupID]{$bit>>3}|=(1<<($bit&8));
    }else{
      $this->groupdisallow[$GroupID]{$bit>>3}=(1<<($bit&8));
      for ($i=0;$i<($bit>>3);$i++)
        $this->groupallow[$GroupID]{$i}=chr(0);
    }

    if (isset($this->selfrights[$GroupID])){
      $this->selfrights[$GroupID][1]{$bit>>3}|=(1<<($bit&8));
    }else{
      $this->selfrights[$GroupID]=array();
      $this->selfrights[$GroupID][1]{$bit>>3}=(1<<($bit&8));
      for ($i=0;$i<($bit>>3);$i++)
        $this->selfrights[$GroupID][1]{$i}=chr(0);
      $this->selfrights[$GroupID][0]="";
    }
  } 

* This source code was highlighted with Source Code Highlighter.

Жутковато выглядит, не правда-Ли? Я даже не проверял данный код :), я просто испугался — настолько всё жутко. Такой код красным по белому говорит нам о том, что что-то в архитектуре не так.
Предлагаю отрезать лишние и ненужные нам хвосты! Сделать код читаемым и более универсальным.

Режим лишние хвосты!

Наша структура сейчас выглядит так:
array(/*GroupID*/ 1 => array (allow => 0b100101000100100010 /*биты*/, disallow => 0b100010010000010001010), 4 => ...)

В этом виде с ней происходит serialize и она записывается в объект.
Но, во первых, сложно работать с действиями (приходится добавлять новые, редактируя PHP-файл).
Во вторых, вести поиск по битам не так легко. А давайте попробуем вернуться к первоначальному варианту, рассмотренному в предыдущей статье.

То есть теперь права доступа будут выглядеть так:
array(/*GroupID*/ 1 => array (/*Actions*/ 'message_read' => 1 /*+*/, 'message_edit' => 0 /*-*/), 4 => ...)
За счёт этого:
1) Поиск нужного действия происходит одной командой $array[GroupID][ActionName]. (уверен, что это поможет ускорить процесс поиска)
2) Нет необходимости добавление действий. Все они будут хранится у нас в объекте.
3) Выборка будет происходить одним циклом, только по группам пользователя.
4) Сами группы пользователей могут принять человеческий вид.
Единственный наглядный минус — структура будет занимать больше места. Плохо? Да, но в оптимизации всегда так — либо нагрузка на CPU, либо объемы памяти. Да и памяти БД оно съест не сильно много, по этому приступаем.

//Класс соответствия прав и действий для объектов
class ObjRights{
  public $groups=array();
  public $selfgroups=array();

  /*Главные функции работы с объектами*/
  
  /* include_right
    Добавить все права подобъекта
  
    @param {serialize array} RightsID - права объекта массивом
    @return {Object ObjRights} - объект с установленными правами
  */
  public function include_right($RightsID){
    $clone=clone $this;
    
    //Вместо дополнительных SQL-запросов, просто уже имеет готовый двухмерный массив
    $clone->selfgroups = unserialize($RightsID);
    
    foreach ($clone->selfgroups as $groupID=>$actions){
      if (isset($clone->groups[$groupID])){
        //Если группа присутствует, изменяем правила для действий в данной группе
        foreach ($actions as $actname=>$allow){
          if (isset($clone->groups[$groupID][$actname]))
            // 1 - allow, 0 - disallow
            $clone->groups[$groupID][$actname]&=$allow;
          else
            $clone->groups[$groupID][$actname]=$allow;
        }
      }else
        //Если группа отсутствует, добавляем такую группу
        $clone->groups[$groupID]=$actions;
      
    }
    
    return $clone;
  }

  /* isAllow
    Проверяет группы пользователя и выдаёт разрешение на определенное действие над объектом
  
    @param {array} UserRights - идентификатор групп, в которых находится пользователь
    @param {string} ActionName - название действия
    @return {bool} - может ли пользователь сделать заданное действие?
  */
  public function isAllow($UserRights, $ActionName){
    
    foreach ($UserRights as $groupname){
      //Проверяем каждую группу
      if (isset ($this->groups[$groupname]) &&
        isset ($this->groups[$groupname][$ActionName]) &&
        $this->groups[$groupname][$ActionName])
          return true;
    }
    return false;
  }

  /* export_rights
    Возвращает права объекта в формате для БД. (serialize array)
  
    @return {string} - serialize array
  */
  public function export_rights(){
    return serialize($this->selfgroups);
   }
   
   
   /*Функции работы с правами объекта*/
  
  /* allow
    Устанавливает права объекту на определенное действие
  
    @param {int} GroupID - идентификатор группы
    @param {string} ActionName - название действия
  */
   public function allow($GroupID, $ActionName){
     if (!isset($this->selfgroups[$GroupID]))
       $this->selfgroups[$GroupID]=array();
    $this->selfgroups[$GroupID][$ActionName] = 1;
   }
   
  /* disallow
    Устанавливает запрещенные права объекту на определенное действие
  
    @param {int} GroupID - идентификатор группы
    @param {string} ActionName - название действия
  */
   public function disallow($GroupID, $ActionName){
     if (!isset($this->selfgroups[$GroupID]))
       $this->selfgroups[$GroupID]=array();
    $this->selfgroups[$GroupID][$ActionName] = 0;
   }
   
  /* reset
    Убирает любые права объекту на определенное действие
  
    @param {int} GroupID - идентификатор группы
    @param {string} ActionName - название действия
  */
   public function reset($GroupID, $ActionName){
     if (isset($this->selfgroups[$GroupID]) && isset($this->selfgroups[$GroupID][$ActionName]))
      unset($this->selfgroups[$GroupID][$ActionName]);
    if ($this->selfgroups[$GroupID] === array())
      unset ($this->selfgroups[$GroupID]);
   }
}

* This source code was highlighted with Source Code Highlighter.

В базе данных все эти записи будут храниться, прямо в отдельном поле объекта таблицы. То есть вот так:

page
pageID	page_name	page_rights (права в serialize виде)
messages
messID	pageID	message_rights (права в serialize виде)	message_header	message_text

Что можно делать ещё?

Для любителей JSON, можно использовать вместо serialize/unserialize => json_encode/json_decode, которые по идее должны работать быстрее и занимать меньше места в БД.

Для любителей более человечных названий групп, ничего не потребуется для того, чтобы все GroupID сменить с int на string.

Можно использовать $_SESSION, если пользователь залогинился, для запоминания всех его прав $User->current_user->rights (и другой пользовательской информации), чтобы не обращаться к базе данных и не производить лишних действий. Единственный минус — чтобы пользователю сменить права доступа, ему необходимо будет перелогиниваться.

Работающий пример

Битовые маски:
Работающий пример
test0.php
rights0.php

Serialize:
Работающий пример
test.php
rights.php

Послесловие

Очень похожие механизмы работы с правами предлагает Zend (последний пример с Serialize).
Основы вы уже узнали здесь (как оно функционирует и откуда растут ноги).
Zend_Acl предлагает похожую библиотеку описания взаимодействий. Кому именно, как пользоваться Zend_Acl, может почитать в интернете. Думаю, что после этой статьи вы быстро разберетесь.

p.s. спасибо всем, кто оставил комментарии к прошлой статье на эту тему. Без вас не было бы этой статьи.