Есть ли жизнь за отсечкой
Мне Denis, в комментария на тему Приоритетные очереди 2, подсказал отличную тему, как бороться с перекрутами в системах управления рекламой, о чём сегодня и поговорим…
Проблема такая существует, и она отражается не только на амбициях программиста, который хочет сделать идеальную систему, работающую как швейцарские часы, но и на бизнесе, которому перекрут обходится в некоторую копеечку (рекламодателю сложно доказать что он должен оплатить перекрут, а площадке сложно объяснить почему ему не заплачено за сверх-показы).
С точки зрения бизнеса, я вижу один, самый простой, с моей точки зрения, выход, — не учитывать перекрученные показы/клики и т.п. Но гордость программиста требует минимизации перекрута 
Не зависимо от того, какие ограничения мы используем (показы, клики, деньги, …), способ всегда один — мы останавливаем показы. Значит проблема сводится к тому, как вовремя остановиться, не показав лишнего. Вариант, когда мы остановились вовремя, но пользователь кликнул на баннер после остановки показов, рассматривать не будем, это невозможно предсказать, мы просто не будем засчитывать этот клик.
Предположим, что у нас система состоит из одного сервера. Казалось бы, какие могут быть проблемы в этом случае? Даже если у нас обработка идёт в несколько потоков, мы всегда можем вынести ограничения в общую память и не парится что у нас будет перекрут. Но всё не так просто. Как мы показываем баннер? Мы откуда-то берём баннер (очередь, список, и т.п.), проверяем ограниения (по показам, кликам, географии, по сайтам и т.п.), и, если баннер подходит, отдаём его и увеличиваем количество показов (что там ещё далается зависит от системы, может уменьшаем ограничения). Засада случается в момент, когда на отдачу работает несколько потоков. Первый поток взял баннер, проверил ограничения по показам, перешёл к проверке других ограничений. В это время второй поток тоже проверил ограничения и перешёл к проверке других ограничений. Первый поток отдал баннер и увеличил количество показов, которое упёрлось в ограничения. Но второй поток об этом ничего не знает и тоже отдал баннер и увеличил количество показов. Получили перекрут. Как с этим бороться?
Честно говоря, я такую проблему в реальной жизни не решал, но порассуждаю. Первый способ который приходит в голову — превентивное увеличение счётчика. Перед началом проверки ограничений поток увеличивает показания счётчика, делает все проверки и, либо уменьшает количество показов, если баннер не подошёл, либо просто отдаёт баннер. Это решает проблему с перекрутом, но создаёт другую проблему — если одновременно два потока увеличивают показания счётчика и оба нарываются на ограничение в количество показов. В этом случае получается недокрут. Но мне не кажется это проблемой, потому что потоки не могут всё время работать синхронно и создавать такого рода коллизии, рано или поздно всё докрутится.
Второй способ — система осуществляет все проверки, увеличивает количество показов и проверяет не упёрлось ли оно в ограничения. Это легко делается ипользованием атомарных операций, которые возвращают предыдущее показание счётчика. Если мы достигли ограничений, мы просто переходим к следующему баннеру в очереди. В этом случае у нас не будет перекрутов и недокрутов. Засад в этом способе пока не вижу
Сильно усложняет задачу наличие нескольких серверов на отдачу баннеров. В этом случае у нас нет общей памяти с ограничениями. Первое решение “в лоб” которое я вижу — это отдельный сервис для хранения счётчиков. Главное обеспечить атомарность, что, с моей точки зрения, не сложно. Но мне такое решение не по душе. Во-первых, это узкое место в системе. Хотя маловероятно, что на современном железе мы упрёмся в ограничение по производительности (даже имея сеть в миллиард показов в сутки, пиковая нагрузка врядли превысит 15-20 тыс. запросов в секунду, что реально обработать), меня раздражает само наличие этого узкого места. Во-вторых, надёжность. Я могу себе представить в какую проблему выльется необходимость обеспечить надёжность решения. Нужно ставить дублирующий сервер с которым основной постоянно синхронизируется, но это не беда. Беда — это необходимость проверки что сервер работает, хранение где-то списка серверов под замену, переключение на резервный в случае падения и т.п. Это всё решаемо, но это работа, много работы, которая не очень интересна
Второе решение — это кластеризация. В этом случае мы разделяем баннеры по разным серверам. Когда приходит запрос, он идёт на все сервера, каждый из серверов выбирает наиболее подходящий баннер, а сервер, принимающий запросы от пользователей, решает какой баннер будет показан и сообщает серверу что показан именно его баннер. Одна из проблем такого решения — нагрузка одним запросом всех серверов. Это значит, что каждый из серверов должен быть способен обрабатывать все входящие запросы. Я пока не знаю как решить эту проблему. Как вариант, можно кластеризировать баннеры по какому-то общему параметру. Например, по формату баннера, по сети и т.п. Но мне кажется, что должно быть более элегантное решение. Если я его найду, обязательно поделюсь мыслями по этому поводу.
Вот такие получились рассуждения, надеюсь, кому-то это поможет, натолкнёт на мысли
Tags: крутилка, оптимизация, программирование
К сожалению мне тоже ничего интересного в голову не пришло с точки зрения бизнеса, кроме остановки показов в общем случае
Знаю, что есть сеть(одна точно), где “левые” показы просто не учитываются позже, при агрегации статистики, но в общем, это тоже самое.
Тех. сторона.
Где хранить отсечки. Например, у нас есть максимальное кол-во кликов в сутки.
Понятное дело, что при больших нагрузках РСУБД нам не подходит, слишком медленно и оверхед по cpu/памяти/диску.
Варианты стораджей оперативка/диск.
Оперативка: однопоточный демон tcp/ip с атомарными командами inc/dec/set/get/flush/load.
Диск: существует несколько довольно быстрых стораджей типа triviadb, memcachedb(внутри bdb). Они дают хорошее быстродействие и надежность, при этом быстрее РСУБД, но конечно помедленее самописного демона с хранением в оперативке. Но их стоит все же рассматривать как простую альтернативу, при очень неплохом(тысячи реквестов на запись в секунду). Они дают еще и дополнительные бонусы, например, у memcachedb вроде бы есть репликация.
Мы так или иначе пишем “сырую” инфорацию о событии на диск, чтобы ее потом обработать при подсчете статистики. Это может быть log file или та же самая РСУБД.
Если у нас “падает” демон для отсечек, то в это время мы показываем какую-нибудь фигню или РО с очень большими лимитами, а в фоне поднимаем демона, загружаем в него последнее сохраненное состояние + парсим raw log до момента падения. Как только мы это сделали, можно снова показывать РО, у которых проверка отсчеки критична.
Как правильно было подмечено, это дополнительные сложности.
Про кластеризацию.
Интересная идея, но тут мне кажется главным является то, что в какой-то момент времени, мы не можем выбирать наиболее подходящее РО из всех в рамках одного сервера. Например, у нас 5000 РО, мы должны в реальном времени расчитать их веса, сделать сортировку, и т.д.
На мой взгляд, тут задачу можно решить проще. Нужно сделать разбиение РО на группы таким образом, чтобы в каждой группе было более менее равное кол-во вероятных событий(показов, кликов). Тогда можно выбирать группу РО рандомно при каждом запросе, и проблема агргеации результатов отпадет, так как каждый конкретный запрос обрабатывается только 1 сервером.
Да, база при больших нагрузках используется только как “бекап” системы и как средство хранения счётчиков и отчётов для их отображения пользователям…
Если рассматривать систему вцелом, то у меня получается следующая архитектура. База, к которой всё хранится (mysql). Интерфейсы, через которые всё это управляется. Http-демона, обрабатывающие запросы (в памяти хранятся все небходимые объекты, к базе обращаемся периодически за обновлениями и для сброса счётчиков). Демона пишут в файлы логи, которые раз в час агрегирируются со всех серверов и обрабатываются, а результат сбрасывается в базу в виде отчётов.
Были мысли вынести логирование на отдельный сервер, куда данные будут попадать по tcp или udp, но тут придётся реализовывать проверку работоспособности, что усложняет задачу. Как-нить позже займусь этим вопросом.
Кстати, а почему бы не хранить в демоне счётчики, а не отсечки? Отсечки каждый демон может закешировать у себя, а за счётчиками ходить к демону. Тогда при падении демона можно продолжать показвать с какими-нить ограничениями, скажем, поделить ограничения на количество серверов.
Считать в реальном времени веса на 5000 РО — это сильно, я стараюсь это делать с какой-то периодичностью, а не под каждый вызов. Правда не всегда, наверное, есть такая возможность. В этом случае какраз кластеризация должна спасти, просто надо придумать, как считать веса не зная заранее суммы параметров по всем РО. Ну или, например, если у нас 5 серверов, то каждый из них может выбрать один баннер из 1000 и отдать не только баннер, но и базу на основе которой высчитывался приоритет. Тогда основной сервер, который будет выбирать что показать из 5 баннеров, сможет посчитать у кого вес больше и принять решение. Тут нужно думать приминительно к конкретной задачи. Но задача интересная.
ЗЫ: вот мой демон для счётчиков: http://www.saterenko.ru/memcounter/ только я пока его к реальным задачам так и не прикрутил, поигрался и оставил
Кстати, а ВЫ — это какая система?
Мы вот сделали:
https://plus1.wapstart.ru
Реклама на wap-сайтах, для меня это тёмный лес
Знаком с wap-ом и мобильными технологиями, но никогда не занимался им серьёзно. Судя по статистике, у вас система легко может работать на одном сервере, не должно быть проблем с синхронизацией, вернее они не должны возникать 
ЗЫ: а сайт приятный
На самом деле уже не совсем так, реквестов(по логу) у нас гораздо больше(в разу), чем реальных показов в силу специфики сети:-)
Всё конечно зависит от специфики, но я считаю, что один сервер вполне может держать 50-70М запросов в сутки