Инструменты пользователя

Инструменты сайта


Перевод этой страницы:
development:database:guid

Применение GUID в поисковых запросах к БД

Как известно GUID (Globally Unique Identifier) - 128-битный уникальный идентификатор.

{231acc77-9513-4bb3-8bd1-0db43be76fd2}

Листая странички в интернете я в 100% случаев встречал реализации PHP-генераторов GUID на основе псевдослучайных чисел. То есть решалась задача создания уникального идентификатора.

Однако если углубится в изучение вопроса, то становится ясно, что помимо уникальности, GUID может передавать и некую информацию. В частности Microsoft использовала в качестве одного из параметров при генерации GUID MAC адрес сетевых адаптеров.

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

Постановка задачи

В этой статье я рассмотрю только одну область применения GUID, и соответственно, только те ограничения, которые присущи этой области.

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

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

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

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

Более того, если в рамках системы нашему скрипту передать GUID, то он сможет без труда понять откуда (из каких таблиц) ему взять информацию.

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

Итак наши ограничения:

  • Необходимо создать генератор GUID.
  • GUID должен передавать некую информаци.
  • Необходимо создать декодер GUID, для чтения этой информации.
  • GUID должен быть максимально случайным.
  • Для одних и тех передаваемых данных должен генерироваться один и тот же GUID (для формирования поисковых запросов к БД по самим GUID).
  • Заложить механизм проверки данных, на случай подсовывания сторонних GUID.

Вопрос случайности

Необходимо сразу поднять вопрос случайности формирования GUID при условии необходимости передачи информации.

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

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

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

Передаваемые данные

Прежде чем говорить о том какую информацию передать давайте еще раз рассмотрим сам GUID.

GUID имеет 32 шестнадцатеричных разряда, условно разбитых на 5 групп: {3fcdfc9f-5d46-43eb-95be-e1e595f223a2}. В принципе на эти группы не обращайте внимания, так как мы вольны размещать любую информацию в любые разряды. Более того мы можем разместить блок информации не последовательно, а раскидав их по разным разрядам, что увеличит криптостойкость вашего идентификатора.

Итак, что же мы можем передать.

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

А вот для чисел 128 бит - это просто раздолье, вы сможете передать:

  • Числовые идентификаторы.
  • Числовые значения.
  • Числовые коды - типы записей, коды таблиц и т.д..
  • Флажки, причем лучше всего передавать их в битах - так в одном разряде GUID вы сможете передать информацию о состоянии 4 флажков.
  • Числовой хеш валидации данных.
  • Метод шифрования.

Ну все то, что может быть описано числовым значением.

Давайте посмотрим несколько примеров. Обозначим разряды GUID слева направо, начиная с нуля:

 0 2 4...
{09906f48-0c79-4376-a179-75481fecbe83}
  • 0-5 - идентификатор записи.
  • 6-7 - тип записи (или код таблицы).
  • 8-11 - число 1.
  • 12-15 - число 2.
  • 16-19 - 16 флажков.
  • 20-27 - контрольная сумма (для валидации идентификатора).
  • 28-31 - метод шифрования.

Или к примеру такая хитрая структура:

  • 0, 1, 10, 12, 24, 7 - идентификатор записи.
  • 2, 23 - тип записи (или код таблицы).
  • 3, 4, 31, 28 - число 1.
  • 5, 6, 30, 21 - число 2.
  • 8, 29, 17, 15 - 16 флажков.
  • 9, 13, 22, 27, 11, 16, 25, 19 - контрольная сумма (для валидации идентификатора).
  • 14, 18, 20, 26 - метод шифрования.

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

К примеру у вас есть числовое поле, которое может принимать максимальное значение равное 50000. В этом случаи вы должны выделить 4 разряда - максимальное значение которое можно передать 4 разрядами: 164 - 1 = 65535.

Преобразование данных

Определившись со структурой GUID можно приступить к его формированию, которое начнется с преобразования исходных данных в шестнадцатеричную систему исчисления.

Для преобразования простых чисел и числовых идентификаторов можно использовать стандартную php функцию dechex(). Аргументом функции является десятичное число, а результатом - строка содержащая шестнадцатеричное число.

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

число разрядов в идентификаторе: 4
значение: 200
значение в шестнадцатеричной форме: с8
итоговое значение: 00с8

Контрольная сумма

Преобразовав данные, стоит подстраховаться и добавить некий хеш, построенный на основании входных данных, в идентификатор.

Для чего нужен этот хеш. Представьте, что вы используете GUID внутри текстовых полей комментариев для подгрузки необходимой информации. И кто-то решил проверить, а что же вернет скрипт если ему передать другой идентификатор. В этом случаи он подставляет свой идентификатор, система по своим алгоритмам преобразует идентификатор и получает ряд данных, возможно абсурдных, но все же данных. Среди этих данных будет и «расшифрованная» контрольная сумма.

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

Допустим в рамках своей системы вы используете один миллиард идентификаторов, тогда вероятность подбора существующего составит примерно 3×10-28 %.

вероятность = [кол-во существующих идентификаторов] / [общее число идентификаторов]

Вероятность = 109 / 2128 = 3×10-30 = 3×10-28%

Сами понимаете такая вероятность ничтожна. Правда если учесть, что пространство и время бесконечны, то и это событие вполне возможно :-).

Еще раз повторюсь, что хеш контрольной суммы должен формироваться на основании всех передаваемых данных.

Метод шифрования

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

Однако я предлагаю создать множество методов шифрования базирующихся на общем принципе.

В качестве примера давайте рассмотрим следующий метод шифрования.

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

Значение разряда: с
Величина смещения: +6
Результат смещения: 12
Результат шифрования: 2

На базе этого принципа мы построим 256 методов шифрования. Почему 256? Просто потому, что мы можем передать значение в диапазоне от 0 до 255 используя всего два шестнадцатеричных разряда.

По сути нам нужно создать массив правил, для этого можно написать простую функцию которая будет генерировать md5 хеши 256 случайных чисел. В качестве ключей этого массива лучше всего использовать шестнадцатеричные числа от 00 до ff. В последующем будет проще получать необходимый метод шифрования, зная его шестнадцатеричный код.

Теперь давайте подумаем - мы должны передавать метод шифрования, который занимает 2 разряда. Значит у нас остается 30 разрядов для передачи данных и контрольной суммы. Но в качестве методов шифрования мы используем md5 хеш, который имеет 32 разряда. Так вот первые 30 разрядов будут определять значения смещений каждого разряда, а вот два последних разряда, переведенных в бинарный код, определят направления смещения:

77da7555b17b4d75b4b1f0bc38ddf9 - исходные данные
7bfc542f812f49ed914ac4540bc29528 - метод шифрования
00101000001010000010100000101000 - смещение (повторение шестнадцатеричного числа 28 в двоичной форме)
0ccec136309c849823f7dc683d9b84 - результат шифрования

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

Код метода шифрования: 7d
Полученная строка: 7d0ccec136309c849823f7dc683d9b84

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

Приведение к классическому виду

Сформировав сроку с зашифрованными данными придадим ей классический вид GUID. Для этого заключим строку в фигурные скобки и добавим знаки '-' в соответствующих местах:

Зашифрованная строка: 7d0ccec136309c849823f7dc683d9b84
GUID: {7d0ccec1-3630-9c84-9823-f7dc683d9b84}

Обратное преобразование

Для обратного преобразования нам необходимо проделать те же шаги, но в обратном порядке:

  1. Получаем GUID.
  2. Удаляем из него знаки '-' и фигурные скобки.
  3. Выделяем метод шифрования.
  4. Производим дешифрование.
  5. Проверяем контрольную сумму.
  6. Возвращаем данные.
{7d0ccec1-3630-9c84-9823-f7dc683d9b84} - GUID
7d0ccec136309c849823f7dc683d9b84 - зашифрованная строка
7d - код метода шифрования
0ccec136309c849823f7dc683d9b84 - зашифрованные данные
7bfc542f812f49ed914ac4540bc29528 - метод шифрования
00101000001010000010100000101000 - смещение
77da7555b17b4d75b4b1f0bc38ddf9 - расшифрованная строка, из которой мы получим исходные данные

Обертка

Как вариант, можно обернуть весь механизм кодирования и декодирования в объект. Все поля и методы по преобразованию данных объекта пометить как приватные. А для работы с классом предусмотреть два публичных метода:

  • get() - на основе полученных аргументов возвращает GUID.
  • set() - на основе GUID возвращает массив исходных данных.

Резюме

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

Что касается структуры и методов шифрования, то тут можно построить бесконечное число схем, что гарантирует вам надежное шифрование и «случайность» ваших идентификаторов. К тому же мало вероятно, что кто-то сможет разработать декодер, не зная ваш принцип и методы шифрования.

development/database/guid.txt · Последние изменения: 2015.09.19 05:29 (внешнее изменение)