Monthly Archives: Июнь 2022

Структура данных PackedPerms

Мотивация

При создании информационных систем с микросервисной архитектурой, желательно, чтобы аутентификация и авторизация пользователей была без сессии (без хранения состояния).

Использование JWT-токенов - неплохое решение. Токен может содержать имя пользователя, различные сведения о нем, в т.ч. числе его права и полномочия.

Но есть один неприятный момент. Если в нашей системе очень много прав, например, несколько сотен, то передача кодов прав в токене увеличит размер последнего. Само по себе это некритично, но токен передается в заголовке запроса, который по умолчанию в различных веб-серверах и веб-прокси ограничен от 4К до 8К. Можно, конечно же, увеличить размер заголовка, но все равно разумных ограничений может не хватить, тем более каждый такой запрос будет существенного размера. Далее будет предложен вариант передачи большего кол-ва прав/полномочий в токене.

Реализация

Для начала нужно всем правам (полномочиям) присвоить сквозную нумерацию - 0, 1, 2, и т.д. (необязательно начинать нумерацию с 0, допустимы пропуски в нумерации).

Идея состоит в том, что каждому номеру права будет сопоставлен бит в битовом массиве.

Если право есть, то бит по индексу с номером права будет установлен.

Биты будет конвертировать в строку в формате Base64. Далее эта строка добавляется в токен как значение для поля, например, "permissions".

Один символ в Base64 кодирует 6 битов.

Таким образом, 10 тысяч прав займу примерно 1667 байт.

10 000 бит / 6 = 1667 байт. 

Но это неокончательный размер. Из-за того, что структурные части токена кодируются в Base64, размер возрастет на 4/3 (почему 4/3 можете посмотреть в этом блоге). Итоговый размер 10 тысяч прав, передаваемых как часть токена составит 2.17 КБ.

1667 * 4 / 3 = 2223 байт (2.17 КБ).

Общая схема кодирования:

Исходный код реализации структуры данных можно посмотреть на github.

Упаковка прав/полномочий

Статический метод pack упаковывает идентификаторы прав, которые есть у пользователя в строку в формате Base64.

List<Integer> list = Arrays.asList(2, 4, 7, 8, 9, 10, 12, 14, 15, 
        1000, 2005, 10002, 10007);
String pack = PackedPerms.pack(list);
System.out.println(pack);

Результатом будет строка длинною 1668 символов:

KesAAAAAAA...AAAAAh

Проверка прав/полномочий

Проверка осуществляется статическими методами hasPermission и hasAnyPermission.

hasPermission - проверяет наличие одного полномочия

hasAnyPermission - проверяет наличие хотя бы одного полномочия из списка.

List<Integer> permissionIds = Arrays.asList(16, 4, 101);
String pack = PackedPerms.pack(permissionIds);
System.out.println(PackedPerms.hasPermission(pack, 16)); // true
System.out.println(PackedPerms.hasAnyPermission(pack, 100, 101, 102)); // true

Метод hasPermission отрабатывает за константное время O(1) без выделения дополнительной памяти.

Метод hasAnyPermission отрабатывает за линейное время O(k) без выделения дополнительной памяти.

Где k - кол-во проверяемых прав и обычно оно невелико.

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

Maven Central Repository

PackedPerms выделен в отдельную библиотеку и доступен в Maven Central Repository:

https://mvnrepository.com/artifact/kz.kesh/packed-perms