Автор: Эрик Липперт.
Оригинал статьи: GUID guide, part two.
Как же обеспечивается уникальность GUID без центрального органа управления наподобие системы ISBN?
Для начала обратите внимание на то, что количество возможных GUID гораздо больше, чем количество возможных ISBN. Поскольку последняя из тринадцати цифр содержит контрольную сумму, остаётся лишь 1012 возможных ISBN. Это порядка сотни уникальных ISBN на каждого жителя Земли. Это примерно 240, то есть ISBN можно представить 40-разрядным числом (без контрольной суммы). Количество возможных GUID составляет 2128; это примерно 40 миллиардов миллиардов миллиардов уникальных GUID на каждого жителя Земли. Это даёт нам основание полагать, что конфликтов не будет; ведь у нас целая куча GUID-ов для выбора!
Существует несколько стратегий уникальности GUID, фактически сведения об используемой стратегии закодированы в первых четырёх битах третьей "группы"; почти каждый GUID имеет вид {xxxxxxxx-xxxx-1xxx-xxxx-xxxxxxxxxxxx} или {xxxxxxxx-xxxx-4xxx-xxxx-xxxxxxxxxxxx}.
Если эта группа начинается с единицы, алгоритм обеспечения уникальности по существу является разновидностью стратегии ISBN. Уникальность GUID-а "в пространстве" обеспечивается путём выбора нескольких битов MAC-адреса сетевой карты компьютера. Мудреная задача уникальности MAC-адреса сетевой карты как-то решается кем-то другим; как именно, нас не заботит. Стоимость решения оплачивает потребитель при покупке сетевой карты.
Мы знаем, что можем положиться на это как на источник уникальности в пространстве. Большинство оставшихся битов представляют собой метку времени высокого разрешения. Следовательно, каждый сгенерированный GUID уникален в пространстве и времени, и, соответственно, уникален глобально.
На практике данная система имеет пару слабых мест. Самое очевидное заключается в том, она не работает как следует, если у компьютера нет сетевой карты! GUID первой версии, сгенерированный на компьютерах без сетевой карты, может не быть уникальным. Менее очевидное состоит в том, что существует незначительная вероятность генерации двух GUID-ов " одновременно". Два генератора GUID могут быть одновременно запущены на двух процессорах одного компьютера. Или после генерации GUID часы компьютера могут быть сознательно "переведены назад", и повторно будет сгенерирован тот же самый GUID. GUID содержит несколько "дополнительных" битов для предотвращения проблем со временем, так что на практике они не встречаются.
Есть несколько интересных следствий данного алгоритма.
1. GUID практически полностью неслучайное число. Похоже, многие люди ошибочно полагают, что GUID – источник случайности, хотя на деле это источник уникальности.
2. GUID-ы, сгенерированные по данному алгоритму на одном компьютере, могут быть монотонно возрастающими. Это действительно хорошее свойство GUID; GUID-ы часто используются в качестве первичного ключа базы данных, намного легче вставить большое количество строк в таблицу с первичным ключом-индексом, если строки уже отсортированы и вставляются после предыдущих записей. Это доказывает ужасность идеи с использованием последовательности GUID-ов в качестве последовательности случайных 128-разрядных чисел; случайные числа обычно не возрастают монотонно!
3. Программный код или документы, содержащие GUID, сгенерированный по первому алгоритму, однозначно идентифицируют компьютер, использовавшийся для создания GUID. Искушенный читатель может узнать интересные сведения о книге по её ISBN. Если тринадцатая цифра GUID – единица, опытный человек также может определить, когда и где был сгенерирован GUID. Этот факт использовался при поиске автора знаменитого вируса Melissa. Мы подробно обсудим это следствие в следующий раз.
4. Ни одна из частичных последовательностей битов GUID-а не обладает свойством уникальности (об этом писал Рэймонд Чен в 2008 г.). В самом деле, у нас нет причины полагать, что меньший набор битов будет обладать теми же свойствами, что и больший набор битов! Вы ведь не считаете, что половина самолета будет летать подобно целому самолету.
В следующий раз мы поговорим о GUID-ах, у которых тринадцатая цифра – четверка; у них уникальность обеспечивается совсем по-другому.
Комментариев нет:
Отправить комментарий