Здравствуйте Алекс,
Monday, September 6, 2004, 12:14:09 AM, Вы писали:
>> за миллион значений не было ниодной коллизии! За полтора милииона тоже
>> нет коллизий. Большие значения проверить не могу - своппинг
AT> С ума сойти.
AT> У вас есть пространство значений
AT> PID - 16 bit
Количество одновременно живущих Апачей меньше 65536. Их много меньше.
Можно сделать так, чтобы каждый чайлд имел свой уникальный номер из
пространства скажем 1024 номеров (через flock лочим один из 1024
файликов). Имеем 10 бит.
Кстати у меня на FreeBSD 5.2.1-RELEASE PID-ы попадаются больше 65536.
AT> date - 32 бита (реально - меньше)
реально 25 бит на 1 год.
AT> count - ну пусть тоже 16 bit (реально - MaxRequestPerChild)
реально 8 бит использовать, а MaxRequestPerChild вполне подойдёт, если
он 256 или менее будет.
итого 10+25+8=43 бита. Хотя при скозной нумерации получается на
порядки меньше.
А вообще высокая вероятность того, что в Y минут Z секунд форкнется
PID такой же как вчера или позавчера или позапозавчера и т.д. ? Если
фиксировать время создания чайда и использовать его для генерации
уникальной куки, то адресное пространство времени можно сильно сжать.
Т.е. вместо времени мы берём секунды+минуты*60 ( если брать
секунды*60+минуты, то в начале суток велика вероятность получения
одинаковых PID-ов, а если брать не PID-ы, а один из 1024 номеров, то
от времени суток мы не зависим). Получаем, что время меняется от 0 до 3599. Это 12
бит.
Теперь имеем нормальную картину: 10+12+8 = 30 бит. Два бита ещё в
запасе остались. Их можно использовать для например на расширение
разрядности времени или на увеличение пространства возможных номеров
чайлдов до 4096.
AT> На взгляд - 64 бита. Вы их сжимаете в 32. Коллизии _будут_.
Так я знаю, что коллизии будут, если использовать приведенную схему из
прошлого письма. Я это и не отрицаю. Только их будет настолько мало,
что их можно не учитывать. Для примера сделаем запрос к Адриверу. Он
выдаёт последовательные номера кука. Сейчас он выдаёт:
Set-Cookie: uid=1516183441; expires=Wednesday, 01-Jan-2020 00:00:00 GMT;path=/;domain=.adriver.ru
2^32=4294967296
Т.е. сейчас Адривер заполнил где-то 30% адресного пространства 32 бит
(кстати интересно, что они будут делать, когда заполнится 100%). 1.5
миллиарда - столько пользователей интеренета не наберётся. При этом
Адривер ставит куку всем, даже если её не поддерживают. Это я к тому,
что колизий бу части адресного прдет мало. Потому как куки буду
отдавать только тем, кто их может принять. Плюс если кука была
поставлена год назад (или 6 месяцев, это можно варьировать) и по ней
не было возвратов, то я её у себя в базе хранить не буду. По моим
расчётам, я за год смогу поставить куку 30-40 млн посетителям. Это
сотая часть адресного пространства. Сложно говорить сколько тут будет
точно коллизий, но меньше 1%, это вполне допустимая погрешность.
С уважением,
Михаил Монашёв, SoftSearch.ru
Member of Independent Software Developers Forum (ISDEF)
mailto:postmaster@xxxxxxxxxxxxx
ICQ# 166233339
Без бэкапа по жизни.
