Порождение уникальных идентификаторов записей в базах данных

М.Н.Михеенков

Диалог СФТ, maxm@jvd.msk.su

Общие требования.

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

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

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

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

Некоторые серверы БД имеют улучшенные средства поддержки целостности и изоляции частей схемы БД, такие как хранимые процедуры, в том числе и удаленные (stored procedures, remote sp), триггеры (triggers), доступ из сервера БД к серверам приложений и так далее. Такие средства могут быть использованы для реализации метода идентификации, и учитываться при выборе метода.

Рассмотрим подробнее эти требования.

Однозначное определение. Это, вероятно, наиболее серьезно воспринимаемое требование. Его выполнение достаточно просто обеспечить, создав для поля ID уникальный индекс, не допускающий повторяющихся или неопределенных значений. О некоторых методах порождения уникального ID будет говориться ниже. Рассмотрим другие вопросы, относящиеся к однозначному определению.

Наиболее часто при определении уникальности опускается множество для которого определяется уникальность и, по умолчанию, под этим множеством понимается хранимая таблица. Соответственно, в случае использования конструкции UNION [INTO ] языка SQL ^*) или ее аналогов, объединяющих в одно множество записи нескольких таблиц или запросов, уникальность ID может быть потеряна. Пользователю или разработчику необходимо учитывать это не только при разработке собственной системы ID, но и при использовании системы, предоставляемой СУБД, например, при автонумерации ключа по умолчанию с одного и того же значения.

select * into #tmp1 from table1
uniun
select *
from table2 where f1=@SomeVar

Пример 1.1.

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

Вопросы избыточности и производительности. Избыточность идентификатора тесно связана с порождением уникальных значений и с производительностью. Для многих случаев чем выше избыточность, тем проще генерация ID и добавление записи, но тем меньше производительность при остальных операциях, причем производительность может меняться как линейно при увеличении размера ключевого поля, так и скачком при смене типа на более "емкий", например, с числового на символьный. Для каждой конкретной СУБД разработчику необходимо определить отношения производительности в случае использования различных типов при индексации, поиске, операции объединения. Очевидно, выбор типа влияет и на размер дискового пространства, занимаемого данными, индексами, журналами. Оценив при проектировании количество идентифицируемых записей единовременно и за все время жизни системы, можно выбрать необходимый тип. Кроме скорости обработки, необходимо также учитывать удобство использования данного типа при генерации ID и при дальнейшей работе с ним. Некоторые методы генерации, к примеру, значительно удобнее использовать с целыми числами в качестве ID.

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

Рассмотрим несколько способов идентификации записей. Эти способы вполне применимы в реальных системах. Кроме того, на этом примере можно проиллюстрировать требования к подобным методам.

Примеры методов порождения идентификаторов.

Метод последовательного увеличения ID

Метод заключается в том, что каждый последующий идентификатор получается увеличением максимального на единицу. При реализации обычно используется один из двух вариантов. В первом непосредственно вычисляется максимальное значение идентификатора. Во втором - максимальное значение хранится как отдельная запись во вспомогательной таблице; при порождении идентификатора он также записывается во вспомогательную таблицу. Второй вариант может быть использован для того, чтобы избежать поиска максимального элемента по таблице данных (если это занимает существенное время), а также при необходимости генерации строго неповторяющихся ID, даже если запись или записи с максимальным ID были удалены. Во втором случае, если нежелательны ""дыры"" в нумерации при откате транзакций, на время выполнения записи необходимо заблокировать вспомогательную таблицу для чтения другими процессами. При повреждении вспомогательной таблицы она может быть легко восстановлена вычислением максимального ID по одной или нескольким таблицам. Разумеется, гарантированность неповторения стертых максимальных ID при этом теряется. Вспомогательная таблица обычно используется, и тогда, когда необходима уникальность ID за рамками одной таблицы (см. выше).

insert foo_table
select max(id) + 1, <прочие данные>;
from foo_table

Пример 2.1, первый вариант.

begin transaction 
insert foo_table 
select id, <рочие данные>
from id_source 

update id_source 
set id = id + 1
commit transaction 

Пример 2.2, второй вариант.

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

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

Метод использования текущих времени/даты

В основу этого метода положено использование значений даты и времени на момент создания записи, комбинируемые в ID. Некоторые СУБД поддерживают тип данных timestamp. Поля этого типа автоматически обновляются при создании или модификации записи. Таким образом, добавив такое поле в таблицу, можно после добавления записи скопировать значение этого поля в ID, где оно уже не будет меняться. Достоинством этого метода является отсутствие вспомогательных данных и простота реализации. Но у него есть и недостатки. Во-первых, ID, им создаваемый, весьма и весьма избыточен, что отражается на производительности при использовании такого ID. Во-вторых, необходимы либо оговоренные внутренние средства СУБД, препятствующие созданию нескольких записей в один квант времени (как одним процессом, так и несколькими), либо включение в структуру ID идентификатора процесса, его породившего, и задержек внутри процесса. Кроме того, даже при работе с одним источником даты и времени, например, на сервере БД, эти значения являются внешними для СУБД и могут быть сброшены в начальное состояние или некорректно изменены, нарушая тем самым работу БД. В случае же, если источником времени являются пользовательские рабочие станции, то текущее время можно считать произвольным. Следовательно, дату и время нельзя строго считать уникальными для каждой записи. Таким образом, данный метод в общем случае является методом случайного ID с большой избыточностью и соответственно обрабатывается (более точно - этот метод сближается с методом случайного ID при выполнении дополнительных действий, убирающих из "дат и времен" позиции с мало меняющимися значениями - прим. ред.).

Метод случайного ID

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

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

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

Метод кучи ID

Логика работы этого метода довольно проста - идентификаторы, которые будут использоваться, заводятся заранее. При добавлении записи из таблицы-источника удаляется, например, максимальный ID и назначается записи, а при удалении записи - возвращается в таблицу-источник.

begin transaction 
declare @max_id int 

select @max_id = max(id) 
from id_source 

insert foo_table 
select @max_id,<прочие данные> 
delete id_source 
where id = @max_id 

commit transaction 

Пример 2.3.

create trigger table_trigger 
on foo_table 
for delete 
as 

<остальные команды триггера> 

insert id_source 
select id 
from deleted 

<остальные команды триггера> 

Пример 2.4.

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

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

delete id_source 
from id_source, foo_table 
where id_source.id = foo_table.id 

Пример 2.5.

или

delete id_source 
where id in 
(select id from foo_table) 

Пример 2.6.

Добавление и модификация системы идентификаторов.

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

Способы добавления и модификации системы ID можно классифицировать по-разному. Например, как внутренние и внешние. Под внешними понимаются способы, при которых операции производятся внешними по отношению к СУБД средствами. Для этого необходимо создать некоторую программу (или воспользоваться уже существующей), которая произведет необходимые действия. Такой программой может быть программа-клиент, запрашивающая у сервера данные и помещающая их на сервер уже с идентификаторами. Так же могут использоваться операции импорта/экспорта данных и их обработка во внешнем формате. Этот способ может быть особенно удобен в тех случаях, когда журнализация отключается только для операций экспорта/импорта.

Можно попробовать обойтись без внешних программ и добавить или модифицировать идентификацию силами СУБД. Добавление системы идентификации может оказаться существенно сложнее модификации.

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

begin transaction 
declare @rcount int, @old_id smallint, @id id_type 
select @rcount = count(*) 
from old_table 

while @rcount > 0 
begin 
select @old_id = max( id ) 
from old_table 
exec get_id @id output 
insert new_table ( id, a, b, c) 
select @id, a, b, c 
from old_table 
where id = @old_id 

delete old_table 
where id = @old_id 
select @rcount = @rcount - 1 
end 
commit transaction 

Пример 3.1.
Здесь и далее get_id - процедура генерации

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

declare @id id_type
while exists
(select count (*) from old)
begin
begin transaction
exec get_id @id output
set rowcout 1
select * into #tmp from old

insert new (id,a,b,c)
select @id, a,b,c
from #tmp

delete old 
from old, #tmp
where old.a = #tmp.a
and old.b = #tmp.b
and old.c = #tmp.c

set rowcout 0
truncate table #tmp
commit transaction
end

Пример 3.2

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

Заключение

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