Быстрая генерация уникального ID

[jangle]

Допустим работает некий процесс в системе, и он сохраняет в некое абстрактное хранилище свою информацию. При этом в системе, может быть запущены десятки или сотни копий этого процесса, а хранилище на всех одно. Поэтому каждый экземпляр процесса генерирует уникальный айдишник, и по нему определяет, что данные под этим ID в хранилище принадлежат ему, а не другой копии. И теперь вопрос, как обеспечить уникальность ID для каждого процесса? Иначе в какой-то момент, может возникнуть коллизия, два копии сгенерят один ID и запишут данные в одну область памяти.
По PID процесса копии различить не удастся, поскольку может быть ситуация, когда один из процессов аварийно завершился, а в хранилище остались его данные, под его ID. И новый процесс под этим PID повредит свои данные, записав их в уже занятую область памяти. Поэтому нужен алгоритм, который умеет генерировать уникальные ID и при этом не имея доступа к информации об уже сгенерированных ID работающих в системе процессов. Пока кроме GUID+TImer в голову ничего не приходит, но опять же могут возникнут коллиции и работает медленно. Может есть более быстрый способ?

[FireFenix]

int(Последний сгенерированный ID) + 1

[Mikle]

Значение QueryPerformanceCounter при старте процесса = его ID.

[jangle]

int(Последний сгенерированный ID) + 1

Процесс ничего не знает о "последнем сгенерированным" ID, и даже есть ли другие процессы которые пишут в хранилище.
У него есть две функции для общения с внешним миром: Save(ID) для записи в хранилище и Load(ID) для чтения из хранилища. Он конечно может сначала выполнить Load(ID) и обнаружив что загружены ненулевые данные, решить что под этим ID уже сохранены данные, и сгенерировать другой ID. Но этот способ кажется некрасивым, и отнимает лишнее время, поскольку в определенный момент по мере заполнения хранилища данными такие промахи будут все чаще.

[Alec]

UUID?

[jangle]

UUID?

Спасибо, похоже это то что нужно.

Upd. К сожалению функция UuidCreate слишком тормозная.

[Qwertiy]

Код: Выделить всё

Now().ToString("yyyy_MM_dd HH_mm_ss ffffff")

Годится?

[Qwertiy]

А зачем вообще хранилище, если у каждого процесса свой кусок данных?

А использовать в качестве идентификатора ID процесса - не вариант?

[Proxy]

А использовать в качестве идентификатора ID процесса - не вариант?

По PID процесса копии различить не удастся, поскольку может быть ситуация, когда один из процессов аварийно завершился, а в хранилище остались его данные, под его ID. И новый процесс под этим PID повредит свои данные, записав их в уже занятую область памяти.

Вообще имхо PID плюс контрольная сумма времени первого обращения к хранилищу (или плюс random). Можно и вообще без PID, если дата время полностью, как у Qwertiy.

[jangle]

Код: Выделить всё

Now().ToString("yyyy_MM_dd HH_mm_ss ffffff")

Годится?

С полной датой до миллисекунд мне нравится, главное что быстрый способ.

[Qwertiy]

С полной датой до миллисекунд мне нравится, главное что быстрый способ.

Хорошо, что нравится, только 10^-6 - это микро

[jangle]

В общем способ работает, вопрос закрыт.

[Хакер]

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

[Qwertiy]

Почему jangle считает, что временная отметка даст гарантированно уникальный результат?

Покажите, как запустить два процесса в одно и то же время.

При таком способе

Код: Выделить всё

Module All
  Public Sub Main()
    For Q As Integer = 0 To 128
      System.Diagnostics.Process.Start("cmd", "/k echo >> time.txt " & Now().ToString("yyyy_MM_dd HH_mm_ss ffffff") & vbCrLf)
    Next Q
  End Sub
End Module

совпадающих меток не видно:

Код: Выделить всё

2011_08_19 21_46_26 187500
2011_08_19 21_46_26 406250
2011_08_19 21_46_26 359375
2011_08_19 21_46_26 437500
2011_08_19 21_46_26 515625
2011_08_19 21_46_26 671875
2011_08_19 21_46_26 718750
2011_08_19 21_46_27 078125
2011_08_19 21_46_26 765625
2011_08_19 21_46_26 921875
2011_08_19 21_46_27 203125
2011_08_19 21_46_27 312500
2011_08_19 21_46_27 406250
2011_08_19 21_46_27 546875
2011_08_19 21_46_27 734375
2011_08_19 21_46_28 171875
2011_08_19 21_46_27 906250
2011_08_19 21_46_28 484375
2011_08_19 21_46_28 343750
2011_08_19 21_46_28 578125
2011_08_19 21_46_28 703125
2011_08_19 21_46_29 140625
2011_08_19 21_46_28 859375
2011_08_19 21_46_28 796875
2011_08_19 21_46_28 984375
2011_08_19 21_46_29 218750
2011_08_19 21_46_29 437500
2011_08_19 21_46_29 843750
2011_08_19 21_46_29 609375
2011_08_19 21_46_30 218750
2011_08_19 21_46_30 015625
2011_08_19 21_46_30 468750
2011_08_19 21_46_29 953125
2011_08_19 21_46_30 125000
2011_08_19 21_46_30 921875
2011_08_19 21_46_31 328125
2011_08_19 21_46_30 328125
2011_08_19 21_46_30 578125
2011_08_19 21_46_31 875000
2011_08_19 21_46_32 140625
2011_08_19 21_46_32 734375
2011_08_19 21_46_32 343750
2011_08_19 21_46_33 375000
2011_08_19 21_46_33 656250
2011_08_19 21_46_32 937500
2011_08_19 21_46_33 859375
2011_08_19 21_46_34 078125
2011_08_19 21_46_34 390625
2011_08_19 21_46_34 515625
2011_08_19 21_46_34 859375
2011_08_19 21_46_35 015625
2011_08_19 21_46_35 281250
2011_08_19 21_46_35 453125
2011_08_19 21_46_36 437500
2011_08_19 21_46_35 625000
2011_08_19 21_46_36 187500
2011_08_19 21_46_35 937500
2011_08_19 21_46_36 625000
2011_08_19 21_46_36 281250
2011_08_19 21_46_37 062500
2011_08_19 21_46_37 921875
2011_08_19 21_46_37 562500
2011_08_19 21_46_38 484375
2011_08_19 21_46_38 203125
2011_08_19 21_46_39 093750
2011_08_19 21_46_39 281250
2011_08_19 21_46_38 890625
2011_08_19 21_46_40 156250
2011_08_19 21_46_39 453125
2011_08_19 21_46_40 421875
2011_08_19 21_46_40 750000
2011_08_19 21_46_39 687500
2011_08_19 21_46_42 578125
2011_08_19 21_46_42 312500
2011_08_19 21_46_41 703125
2011_08_19 21_46_40 906250
2011_08_19 21_46_42 015625
2011_08_19 21_46_42 765625
2011_08_19 21_46_43 078125
2011_08_19 21_46_43 343750
2011_08_19 21_46_43 750000
2011_08_19 21_46_45 625000
2011_08_19 21_46_44 421875
2011_08_19 21_46_43 890625
2011_08_19 21_46_45 031250
2011_08_19 21_46_44 750000
2011_08_19 21_46_45 359375
2011_08_19 21_46_45 968750
2011_08_19 21_46_45 750000
2011_08_19 21_46_46 484375
2011_08_19 21_46_46 890625
2011_08_19 21_46_46 718750
2011_08_19 21_46_46 203125
2011_08_19 21_46_47 109375
2011_08_19 21_46_47 437500
2011_08_19 21_46_48 531250
2011_08_19 21_46_48 250000
2011_08_19 21_46_47 656250
2011_08_19 21_46_47 828125
2011_08_19 21_46_49 312500
2011_08_19 21_46_49 468750
2011_08_19 21_46_49 062500
2011_08_19 21_46_49 750000
2011_08_19 21_46_50 281250
2011_08_19 21_46_49 921875
2011_08_19 21_46_52 015625
2011_08_19 21_46_51 125000
2011_08_19 21_46_50 546875
2011_08_19 21_46_52 437500
2011_08_19 21_46_52 625000
2011_08_19 21_46_52 937500
2011_08_19 21_46_53 390625
2011_08_19 21_46_53 812500
2011_08_19 21_46_54 218750
2011_08_19 21_46_54 593750
2011_08_19 21_46_55 578125
2011_08_19 21_46_55 328125
2011_08_19 21_46_55 109375
2011_08_19 21_46_56 031250
2011_08_19 21_46_57 062500
2011_08_19 21_46_55 875000
2011_08_19 21_46_56 562500
2011_08_19 21_46_57 843750
2011_08_19 21_46_57 484375
2011_08_19 21_46_58 390625
2011_08_19 21_46_59 265625
2011_08_19 21_46_59 000000
2011_08_19 21_46_58 656250

[Хакер]

Покажите, как запустить два процесса в одно и то же время.

Причём тут запуск процессов?

[Qwertiy]

Причём тут запуск процессов?

Вот:

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

[Хакер]

Это писал не ты. Я же имею претензии к твоим словам. Посмотри ещё раз.

[Qwertiy]

Это писал не ты. Я же имею претензии к твоим словам. Посмотри ещё раз.

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

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

[Хакер]

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

На основании чего сделан такой вывод?

[Qwertiy]

На основании чего сделан такой вывод?

Понял. Если процесс сам запрашивает время, то необходимо одинаковое время запроса, а не запуска процесса.

В любом случае, при добавлении к строке id процесса всё будет хорошо

[Mikle]

А если между запусками процессов часы были переведены?

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

Присоединяюсь к вопросу.

[Proxy]

А если между запусками процессов часы были переведены?

Вероятность того, что PID повторится невысока + вероятность того, что это ещё и совпадёт с переводом времени (летнее время там, где осталось, влечёт за собой только один раз в год повтор времени, так что только смена времени пользователем что-то значит) вообще стремится к нулю. К этому всему ещё можно добавить random.

Хакер писал(а):Почему хранилище не может обеспечить раздачу последовательных уникальных идентификаторов?

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

[jangle]

Почему jangle считает, что временная отметка даст гарантированно уникальный результат?

Если запуск копий различать с точностью до микросекунды, разве этого недостаточно?

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

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

[Хакер]

Если запуск копий различать с точностью до микросекунды, разве этого недостаточно?

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

[jangle]

А если между запусками процессов часы были переведены?

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

Присоединяюсь к вопросу.

Потому что распредёленная система должна уникально идентифицировать приходящую информацию без центра координации.
Допустим нет доступа к коду функции которая управляет хранилищем, а есть три функции вызываемые из внешней библиотеки: Save, Load, Delete
Вот ими надо обойтись.

[Mikle]

летнее время там, где осталось, влечёт за собой только один раз в год повтор времени

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

[jangle]

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

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

[Mikle]

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

Я не это имел ввиду. Есть синхронизация времени через интернет, и это может с некоторой не очень маленькой вероятностью породить два процесса с одним ID в случае использования в качестве ID времени запуска.

[Proxy]

Я не это имел ввиду. Есть синхронизация времени через интернет, и это может с некоторой не очень маленькой вероятностью породить два процесса с одним ID в случае использования в качестве ID времени запуска.

Севшая батарейка ака регулярный сброс времени тоже. Но рассчитывать на это глупо (особенно если ключ состоит из всех 3-х компонентов). С тем же успехом md5 страдает коллизиями, с тем же успехом пароли из 16-32 символов можно подобрать с 3 попыток, это паранойя.

Допустим нет доступа к коду функции которая управляет хранилищем, а есть три функции вызываемые из внешней библиотеки: Save, Load, Delete

Пускай ещё будет GetPKey (она же с инкрементом ключа и записью)... Одновременный доступ ограничить не такая большая проблема.