Bit Mask Resurrection

    По мотивам топиков:
    Упаковка булевых переменных для хранения и поиска в базе
    Хранение набора чекбоксов в одном поле БД. Битовая маска.
    В этих топиках была похоронена замечательная идея. Что ж, попробуем её возродить ещё раз…


    Начну с примера. Пользователь должен иметь доступ к определённым функциям сайта. Всего этих функций, к примеру, 1000. Есть группы, к которым привязывается определённый набор функций. Пользователь может принадлежать сразу нескольким группам. За один запрос к сайту, может выполниться сразу несколько функций. Довольно реальная задача, не так ли?

    Группы будем хранить в таблице groups. Для хранения набора функций к группе, самое очевидное решение, создать связывающую таблицу:
    CREATE TABLE `functions_to_group` (
    `group_id` int(4) unsigned NOT NULL,
    `function_id` int(4) NOT NULL
    UNIQUE KEY `f_to_g` (`group_id`,`function_id`)
    )


    Теперь при запросе к функции нужно сделать запрос к базе:
    "SELECT
    `function_id`
    FROM
    `functions_to_group`
    WHERE
    `group_id` in (" .implode(",", $user_groups). ") and
    `function_id` = " .$current_function_id;


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

    Можно одним махом, т.е. запросом, получить все доступные функции и тягать за собой массив из нескольких сот элементов:
    "SELECT
    `group_id`,
    `function_id`
    FROM
    `functions_to_group`
    WHERE
    `group_id` in (" .implode(",", $user_groups). ")"


    Как-то некрасиво… Всё, что нам нужно, это проверка, есть ли в наборе данных определённое значение. Вот тут битовая маска как нельзя кстати. Но хранить маску в целом числе теперь не вариант. У нас ведь 1000 функций.
    Нафик числа, нам нужны бинарные данные, ну так вот и есть такая функция pack(), как раз нам сойдёт.
    Пишем простенький класс:
    class BitMask
    {
    function __construct(){}

    function GetMask($num)
    {
    // если 0, то возвращаем нулевой байт
    if (!$num)
    {
    return "\0";
    }

    // само число определяет позицию единичного бита в бинарной строке
    $num--;
    //определяем кол-во нулевых байт, предшествующих значащему биту
    $null_bytes = floor($num / 8);
    //выставляем единичный бит в значащем байте...
    $number = pow(2, $num % 8);

    //и пакуем всё это дело
    return pack('@' .$null_bytes. 'C', $number);
    }

    function InMask($needle, $findIn)
    {
    //проверяем, есть ли в строке искомое значение,
    //т.е. побитово умножаем и отрубаем нулевые биты
    return (bool)strlen(trim($needle & $findIn, "\0"));
    }

    }


    Теперь пакуем весь набор функций для группы в одну строку, например, вот так:
    $x = new BitMask();

    $group_access = $x->GetMask(0);

    while (list($k, $v) = each($_POST['functions_to_group']))
    {
    $group_access |= $x->GetMask($v);
    }


    Всё. На выходе получаем одну бинарную строку, которую можно хранить в таблице groups. При авторизации на сайте делаем один запрос к таблице groups:
    "SELECT
    `functions_bitmask`
    FROM
    `groups`
    WHERE
    `group_id` in (" .implode(",", $user_groups). ")"


    и побитово складываем наборы всех групп пользователя:
    $user_private_access = $x->GetMask(0);

    while (list($k, $v) = each($user_groups_access))
    {
    $user_private_access |= $v;
    }


    Для проверки, есть ли доступ к функции, делаем так:
    if ($x->InMask($x->GetMask($function_id), $user_private_access))
    {
    // есть доступ
    }
    else
    {
    // нет доступа
    }


    максимальный размер бинарной строки = ceil(max_function_id / 8) байт,
    в нашем случае для 1000 элементов, максимальный размер будет 125 байт.

    В строке длиной 255 символов, max_function_id = 2040.

    Поделиться публикацией
    Комментарии 36
      +4
      Извините, но это классическая демагогия — сначала создать себе трудности, а потом успешно с ними побороться. Кто Вам мешал вычитывать список допустимых функций при «авторизации на сайте» (а не делать select каждый раз), не храня их при этом в базе в виде бинарной строки, которую сложнее обновлять и которую нельзя использовать в сложных запросах (а значит, если такие запросы нужны, параллельно придётся поддерживать не-bitmask структуру)?

      И ещё — скажите, а что станет с системой прав, организованной таким образом, если приложение попросит базу отдавать данные в другой кодировке?
        +2
        Кто Вам мешал вычитывать список допустимых функций при «авторизации на сайте»
        Я про это написал, список может может сосотоять из нескольких сот функций или тысяч. Вместо хранения массива, я храню строку, которая в 8 раз меньше кол-ва функций.

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

          При чём тут кодировка, если я храню бинарную строку
          В поле какого типа Вы её храните? как выглядит соответствующий фрагмент в create table?
            +1
            Фокусов в базе нет. Я не делаю хитрых запросов с битовыми операциями в базе. В данном случае хранилище не имеет никакого значения.

            список допустимых функций высчитывается для пользователя 1 раз.
            Давайте возьмём не 1000, а 1000000 функций. Что лучше загнать в память, массив из миллиона элементов или строку размером 125 kB?
              0
              Загоняйте в память всё, что угодно. Хоть с помощью acb сжимайте этот битмаск. Повторюсь, вопрос именно в том, в каком виде данные хранятся в БД — Вы же именно с этого начали, и именно это вызывает споры и возражения.
              Жду ответа на вопрос о типе поля с битовой маской.
                0
                В mysql — blob, binary varchar.
                Можно в файлах хранить. Храните где и как удобней, это не важно.
                  0
                  Спасибо за пояснения. Цензурного ответа у меня нет, извините. Но могу сообщить, что в некоторых распространённых СУБД (например, в Oracle) работа с BLOB — далеко не самые высокопроизводительные и удобные для реализации операции.
                    0
                    Не понимаю чего вы хотите добиться этим разговором. Я описал метод упаковки данных. Если вы не видите других проблем, кроме типа BLOB в БД, и ваша БД ну очень тормозит с BLOB, то храните в файлах или прямо в памяти. Надеюсь в вашей операционной системе не тормозят операции чтения/записи файов.
                    Не нужно вытягивать слова, которые конкретно не касаются топика, а потом искать цензурный ответ.
                      0
                      Вы заявили, что собираетесь реабилитировать хранение bitmask-структур в БД. Попытка была неубедительной, о чём было сказано. В ответ Вы предложили хранить данные в файлах.
                      Цель разговора — выявить недостатки подхода и не позволить Вам убедить кого-то создать в БД структуру, за котороую этого человека потом проклянут все, кто с ней будет работать.
                        +1
                        Ох, тяжело=(
                        Главной идеей топика не было «Давайте-ка всё упакуем и будем хранить это именно в БД в BLOB, и больше нигде нильзя, только так». Я писал не ГДЕ хранить, а ЧТО хранить. Битовую маску.
                        Можно по-другому придраться:
                        — На чём вы это написали?
                        — На PHP
                        — Нет, php тормозит. Битовые маски говно. Вот если бы на C++…

                        Давайте лучше поговорим непосредственно про недостатки и скорость работы непосредственно самой маски и операций над ней.
                          –1
                          Да, тяжело. Ладно, давайте попробуем ещё раз.
                          Вы заявили, что куча селектов хуже одного вычитывания битовой маски. Если оставить в стороне соображения по поводу BLOB, то спорить с этим сложно — дцать операций медленнее одной. Однако всё равно остаётся вопрос из самого первого комментария к этому посту — ЗАЧЕМ (а не «что» и «где») хранить в БД непригодные к использованию в других запросах, тяжеломодифицируемые и трудноотлаживаемые данные?

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

                          Кучу селектов можно было заменить и на однократный select, но обычных неупакованных данных — Вы сами предлагали это в числе прочего. Но вот о том, что после вычитывания можно в памяти перевести список идентификаторов функций в битовую маску, с которой потом быстро работать — почему-то не подумали.

                          Может быть, есть другой пример, в котором хранение битовой маски в БД является лучшим решением. Но это явно не тот случай — здесь можно оптимизировать запросы, менять схему работы (проверять права не перед выполнением операции, а при логине/обращении к странице), наконец, поставить рядом in-memory db и при проверке прав обращаться к ней.
                            +1
                            ЗАЧЕМ (а не «что» и «где») хранить в БД непригодные к использованию в других запросах, тяжеломодифицируемые и трудноотлаживаемые данные?
                            Вы правы, незачем. Хранить данные в БД опасно. Особенно, если кол-во записей в таблице не превысит ста.

                            В лучшем случае время внесения изменений заметно возрастёт из-за постоянных блокировок. В худшем какие-то изменения будут потеряны.
                            Да, внесение изменений в базу — это беда. Лучше данные в БД вообще не изменять. Согласен.

                            Но вот о том, что после вычитывания можно в памяти перевести список идентификаторов функций в битовую маску, с которой потом быстро работать — почему-то не подумали.
                            Да, я правда не подумал, что можно высчитать миллионный массив, а потом прогнать миллионный цикл и создать битовую маску. Респект.

                            Может быть, есть другой пример, в котором хранение битовой маски в БД является лучшим решением.
                            К сожалению, у меня не хватит жизни описать примеры, которые каждый хабраюзер считает лучшим решением. Если вы нашли лучшее применение, пожалуйста. Это буду счастлив, если моя статья хоть чуть-чуть вам помогла. И буду рад, если вы приведёте лучшее решение.

                            Описанный способ, работы с битовой маской с успехом использую в своих проектах. Хранить битмаску в BLOB полях в таблице, кол-во записей в которой не превисит даже 50, я не считаю злом. Но это не тема моего топика. Кэширование я тоже не считаю злом, но, простите, про кэширование на хабре уже писали.
                              –1
                              Ваш сарказм противоречит сам себе. То миллионные массивы, то 50 записей в таблице.

                              Пожалуйста, попробуйте абстрагироваться от своего кода и понять простую, но выстраданную сединами многих программистов (и моими в том числе) мысль: если программист хочет странного — он что-то делает неправильно, и это потом аукнется.
                              Хранить упакованные до битовых полей данные в БД — это странное. Хотя бы потому, что никаких средств для работы с такими данными в стандарте SQL не предусмотрено.
                              Вы правда считаете себя умнее и дальновиднее авторов стандарта?
                                +1
                                То миллионные массивы, то 50 записей в таблице.
                                50 записей в таблице groups. Вы не следите за темой, а опять цепляетесь за возбуждающие вас слова=)

                                Вы, действительно, кроме страдания никаких чувств не вызываете.

                                никаких средств для работы с такими данными в стандарте SQL не предусмотрено
                                БД в данном случае ничто иное как просто хранилище. БД вообще не вкурсе, что я туда записал. Неужели вы пишете запросы на чистом ANSI SQL? И храните в БД только целочисленные данные?

                                И на предложение хранить данные в файле, всегда отвечаете: в БД это хранить нельзя.
                                — Едьте на поезде.
                                — Спасибо. Но я боюсь высоты.

                                Хранить упакованные до битовых полей данные в БД — это странное.
                                =))) Это настолько же странно, как хранить в БД email, имя или фамилию. Вротмненоги.
          0
          Полностью согласен. «Замечательная идея», в очередной раз описаная в данной теме, «была похоронена» именно в связи с тем что показала свою полную недееспособность. А данная статья, лично для меня, нечто вроде «в очередной раз на те же грабли».
          +2
          Мдя…
          Строки в БД — зло! Они очень медленные в обработке. И в сложном запросе точно ничего не проверишь! Логику доступа к функциям обычно и очень правильно прописывают в приложении, а права доступа к ним регламентируют по групам доступа, которых редко бывает больше 10 (только в очень сложных проектах).
          Давайте не будем усложнять себе жизнь.
            +1
            В данном случае я НЕ использую выборку по бинарной строке.

            а права доступа к ним регламентируют по групам доступа
            именно об этом я и писал.
              0
              Нужно начинать с того, что зло — это запросы вида "… `group_id` in (" .implode(",", $user_groups). ") ..."
                0
                Ну тогда нужно начинать с того, что все запросы — зло.
              –3
              откройте для себя ENUM
              dev.mysql.com/doc/refman/5.0/en/enum.html
                0
                Давайте попробуем применить в данном примере, только что открытый мною ENUM.
                  0
                  ENUM поддерживает только мускуль.
                    0
                    В топике я привёл пример использования длинных битовых масок. Есть ещё куча вариантов решения этого примера. Но как использовать тут ENUM или SET, я совершенно не понимаю.
                      –1
                      ну так покурите мануал по ссылке и поймете
                  +1
                  Господа, больше позитива! :)
                    –2
                    Я вот не пойму, кто мешает сделать каждой «функции» свой столбец. Или кол-во функций не ограничено? Тогда уже речь об объектах доступа.
                      +1
                      1000 столбцов?
                        0
                        Что это за объект, где нужно присваивать полномочия 1000 функциям?
                          0
                          Даже если сто — это не такая большая цифра для большой системы. Будете делать 100 столбцов?
                      +1
                      Решение удачное и используется мной уже давно. Особенно актуально в highload проектах.
                        0
                        хорошее решение. Мы использовали подобное для хранения набора прав. Надо будет попробовать и ваше решение )
                          0
                          Скажите, а будет ли работать подобное решение, если количество возможных функций сайта — число переменное и может постоянно изменяться? Можно ли как-то модифицировать этот метод для варьируемого количества функций без перестройки всех наборов прав при изменении количества функций сайта?
                            0
                            Можно даже ничего не модифицировать. Единственное, что можно добавить, это при уменьшении ко-ва функций отрубить лишние символы во всех сформированных бинарных строках, чтобы не хранить лишние данные.
                            0
                            использовал подобную по замыслу систему в магазине игрушек.
                            используем инт, каждый бит отвечает за свой тип.
                            16 возможных типов «развития» способностей, включать можно несколько, при вставке — сборка:
                            $razvitie=0;
                            for ($z=0;$z<count($razv);$z++)
                            {
                            $razvitie=$razvitie|$razv[$z];
                            }

                            и вывод в товаре:
                            $bit=1;
                            for ($z=0;$z<16;$z++)
                            {
                            if ((int)($line['razvitie']&$bit)!=0)
                            echo тип категории такой-то
                            $bit=$bit<<1;
                            }
                            для данных целей — самое то, думаю. предел — лишь количество бит в типе…
                            ЗЫ: привет z80 ;)
                              0
                              да, $razv[$z] — массив типов, в цыкле вывод:
                              и $bit=$bit<<1;
                              они и собираются ;)
                                0
                                Это было описано в двух предыдущих топиках на эту тему (см. выше). Integer имеет ограничение в 32 бита. Я описал метод работы с гораздо большими наборами.

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

                            Самое читаемое