Равномерное распределение трафика по нескольким ссылкам

[lance]

Привет гофак!
Хочу написать скрипт для раскидывания трафика 50 на 50 по двум и более ссылкам (т.е. на каждую равномерно). Сколько трафика придет заранее не знаю.

ТДС, трекерами и прочей фигней пользоваться не хочу, поэтому хочу накидать свой скрипт на PHP.

Какое решение придумал: делаю условный переключатель - переменную со значением 1 и 0, которое записывается в файл (можно и БД, но хочу без нее обойтись). Первый уник направляется на ссылку1, переменной присваивается значение 1, второй уник идет уже на ссылку2, поскольку у переменной уже значение 1, после перехода в файл записывается значение 0 и т.д. Таким образом достигаем равномерности распределения.

Вопрос: будет ли это работать на объемах 100k/d? Может есть более изящное решение?

[editeur]

На объемах в 100к при разумном количестве ссылок хорошо будет работать обычный random. Чем больше объем тем ближе к 50/50.

rand(0, N-1)

[lance]

Этот вариант сразу отсек, т.к. нужной точности распределения он не даст.

[editeur]

Сообщение от lance

Этот вариант сразу отсек, т.к. нужной точности распределения он не даст.

Прям надо точно 50000/50000, 50031 на 49969 не подойдет?

С файлами тебе придется постоянно этот файл лочить перед тем как в него что-то писать и читать, запросы же идут параллельно. Так что с определенного момента это станет узким местом, запросы будут выстраиваться в очередь. На объемах в несколько миллионов в день это работать будет.

[Marines]

Сообщение от lance

Вопрос: будет ли это работать на объемах 100k/d? Может есть более изящное решение?

есть. бритва Оккамы называется. инеблагодари

[lance]

Сообщение от editeur

Прям надо точно 50000/50000, 50031 на 49969 не подойдет?

Надо конечно у математиков спросить, но мне кажется, что расхождение больше будет.

Сообщение от editeur

С файлами тебе придется постоянно этот файл лочить перед тем как в него что-то писать и читать, запросы же идут параллельно. Так что с определенного момента это станет узким местом, запросы будут выстраиваться в очередь. На объемах в несколько миллионов в день это работать будет.

По поводу файлов согласен, что объемы сорвут всю схему и траф уйдет на ошибку PHP Поэтому и создал топик.

Вообщем спасибо за ответы . Попробую пока действительно на rand, если расхождение будет больше 10%, то буду дальше думать.

[editeur]

Сообщение от lance

Надо конечно у математиков спросить, но мне кажется, что расхождение больше будет.

Будет, но редко. На 100 по 100000 получилось всего два раза с разницей близкой к 800, то есть к 50400/49600

PHP код:

<?php
for ($i = 0; $i < 100; $i++) {
        $x = 0;
        for ($j = 0; $j < 100000; $j++)
                $x += rand(0, 1);
        echo abs(50000-$x)."\n";
}
?>

164
120
25
280
73
20
58
18
367
114
200
105
146
131
64
70
112
47
83
37
102
278
85
212
31
375
183
105
109
122
134
74
164
7
206
20
155
167
69
222
104
133
127
338
121
187
99
30
132
43
141
42
24
210
8
55
144
265
395
232
11
58
31
148
9
79
185
117
38
264
145
160
102
171
14
226
153
14
181
257
292
7
125
153
291
152
74
100
40
81
45
32
3
128
171
52
41
176
4
256

[AntonIon]

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

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

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

[number4]

все эти mt_rand() и openssl_pseudo_random() - полная херня.
Я усредненным распределением трафа на N линков занимался и проводил исследования.
Смысл вот в чем:
есть скажем 10 линков, на которые надо раскидывать рандомно траф. Идеально хочется, чтобы в неограниченном будущем все эти 10 линков получили по одинаковому кол-ву трафа.
То есть
Есть скажем в сутки 10000 трафа. Есть 10 линков. Ожидается, что на каждый линк упадет по 1к трафа.
Если юзать mt_rand без ухищрений, то получается херня типа
на один линк упало 800, на другой 1200 - очень большой разброс от усредненного 1000.
Я специально считал разбросы от усредненного значения, чтобы найти оптимальное решение. То есть в идеале надо, чтобы от среднего 1000 разброс вправо-влево был не более 100 (то есть 10%). Если ставится цель, чтобы траф распределялся наиболее равномерно, то 10% это оптимальный вариант.

mt_rand() дает хреновое усреднение, если делать рандомную выборку:
mt_rand(1,10) - на 10 линков
если сделать round(mt_rand(10,100)/10) - будет чуть получше, так как выбирается рандом не из 10 чисел, а из 90
Но все равно если брать статистику скажем на 10,000 итераций,
то в итоге получается разброс до 30% от усредненного значения. А это слишком много.
openssl_pseudo_rand дает примерно так же.
можно читать из /dev/urandom - будет чуть получше, брать 10 символов, перемешать и вытаскивать случайный.
но тут есть ньанс: одно дело когда трафа 10к в сутки и пару линков на рандом, другое дело, когда 200-300к и около 20 линков на рандом. Тут уже хочется чтобы:
1) рандом работал быстро
2) равномерно распределял траф с минимальным отклонением от среднестатистического значения, без учета накопления статистики

в итоге оказалось, что обычный простой shuffle() дает самый лучший вариант.

то есть так:
у нас есть 10 линков в массиве:
$links=array(
1=>'link1',
2=>'link2',
..
10=>'link10',
);

делаем
shuffle($links);shuffle($links); (два раза, ага)
$redirect=$links[0]

вот при таком варианте разброс от среднестатистического значения составляет около 5% (то есть на один линк упадет 950, на другой 1050, к примеру)
Что вполне приемлимо

А теперь как это выглядит на практике у меня (суточная статистика):

topbanner8 3 487
topbanner2 3 453
topbanner4 3 407
topbanner7 3 379
topbanner5 3 374
topbanner3 3 372
topbanner6 3 346
topbanner1 3 345

----
как видно, 3400 это среднее значение, около которого идет разброс в ту или иную сторону

[AntonIon]

shuffle() же rand() использует. Только srand() на него не влияет. А по сути, это обычный rand().