А теперь мои любимые перцентили (как их можно не любить?). Пусть это будет сумма на которую пользователь закупился в нашем интернет-магазине.
◾️ У нас есть исходная коллекция, ключи в которой это время события, а в значениях есть цена корзины и идентификатор транзакции
◾️ Преобразуем её в коллекцию profit, где ключи это , значения пустые. Идентификатор транзакции здесь нам нужен чтобы одинаковые значения не затёрли друг друга (ключи ведь у нас уникальны)
◾️ Заводим profit:*:stats с ключами так же как и для количеств, а вот со значениями интереснее. В значения будем класть {count, total, p0, pIndex0, p50, pIndex50, p100, pIndex100, ...}, где зададим какие нам перцентили интересны (можем на каждые 2.5% завести если нужна точность, либо какие-то свои любимые взять)
◾️ Значения p* будут содержать в себе не значение этого перцентиля, а ключи из коллекции profit (впрочем, они содержат в себе значение, да), значения pIndex* это порядковый номер элемента соответствующий этому ключу внутри этого интервала
◾️ При первоначальном создании всех этих коллекций пока у нас ещё нет посчитанного интервала мы просто дважды проходимся по коллекции profit по ключам которые входят в интервал, первый раз считаем сколько там элементов, второй раз достаём ключи с нужных позиций (а т.к. коллекции у нас иммутабельны, никто не может сдвинуть элементы чтобы получился неправильный результат)
◾️ Когда исходные коллекции будут изменяться и нам нужно будет обновить интервал, применив разницу, мы сперва достанем текущий список ключей p* для нужных нам перцентилей из коллекции profit:*:stats
◾️ Взяли их, теперь выбираем из коллекции profit по где-нибудь 200 элементов (или сколько не жалко) вокруг этих ключей («вокруг» значит 100 элементов перед нашим ключом и 100 после)
◾️ Идём по diff'у между версиями коллекции profit внутри нашего интервала, там мы можем увидеть лишь два варианта: какой-то ключ был удалён, либо какой-то ключ был добавлен. Изменяем в ту сторону итоговое количество элементов (count). Считаем, нужно ли сдвигать индексы (pIndex*) на один влево/вправо. Если нужно, то мы знаем какие ключи есть вокруг p* и этот сдвиг тривиален
◾️ В процессе обработки diff'а если видим, что у нас заканчиваются элементы «вокруг ключей p*», то асинхронненько подтягиваем их уже относительно «подвиганных p*»
◾️ Коммитим результат
Готово. В итоге у нас потребляется константное количество памяти (количество перцентилей которые мы хотим посчитать константно, количество элементов на которые мы смотрим вокруг ключей соответствующих перцентилям тоже константно, их умножение, очевидно, константа), мы просто идём по диффу, двигаем маркеры туда-сюда. Т.е. например, если мы когда-то завели коллекцию profit:1Y (годовую), то она будет каждый день там по чуть-чуть обновляться и даже если у нас за год миллиарды этих чисел появляются (в контексте магазина миллиард транзакций за год звучит неплохо), то к концу года мы просто посмотрим в profit:1Y:stats и возьмём оттуда результат. Профит.
(хотя в реальности скорее всего необходимость завести такую табличку появится именно в конце года, но это уже не мои проблемы, нужно будет просто подождать)
#diffbelt
◾️ У нас есть исходная коллекция, ключи в которой это время события, а в значениях есть цена корзины и идентификатор транзакции
◾️ Преобразуем её в коллекцию profit, где ключи это , значения пустые. Идентификатор транзакции здесь нам нужен чтобы одинаковые значения не затёрли друг друга (ключи ведь у нас уникальны)
◾️ Заводим profit:*:stats с ключами так же как и для количеств, а вот со значениями интереснее. В значения будем класть {count, total, p0, pIndex0, p50, pIndex50, p100, pIndex100, ...}, где зададим какие нам перцентили интересны (можем на каждые 2.5% завести если нужна точность, либо какие-то свои любимые взять)
◾️ Значения p* будут содержать в себе не значение этого перцентиля, а ключи из коллекции profit (впрочем, они содержат в себе значение, да), значения pIndex* это порядковый номер элемента соответствующий этому ключу внутри этого интервала
◾️ При первоначальном создании всех этих коллекций пока у нас ещё нет посчитанного интервала мы просто дважды проходимся по коллекции profit по ключам которые входят в интервал, первый раз считаем сколько там элементов, второй раз достаём ключи с нужных позиций (а т.к. коллекции у нас иммутабельны, никто не может сдвинуть элементы чтобы получился неправильный результат)
◾️ Когда исходные коллекции будут изменяться и нам нужно будет обновить интервал, применив разницу, мы сперва достанем текущий список ключей p* для нужных нам перцентилей из коллекции profit:*:stats
◾️ Взяли их, теперь выбираем из коллекции profit по где-нибудь 200 элементов (или сколько не жалко) вокруг этих ключей («вокруг» значит 100 элементов перед нашим ключом и 100 после)
◾️ Идём по diff'у между версиями коллекции profit внутри нашего интервала, там мы можем увидеть лишь два варианта: какой-то ключ был удалён, либо какой-то ключ был добавлен. Изменяем в ту сторону итоговое количество элементов (count). Считаем, нужно ли сдвигать индексы (pIndex*) на один влево/вправо. Если нужно, то мы знаем какие ключи есть вокруг p* и этот сдвиг тривиален
◾️ В процессе обработки diff'а если видим, что у нас заканчиваются элементы «вокруг ключей p*», то асинхронненько подтягиваем их уже относительно «подвиганных p*»
◾️ Коммитим результат
Готово. В итоге у нас потребляется константное количество памяти (количество перцентилей которые мы хотим посчитать константно, количество элементов на которые мы смотрим вокруг ключей соответствующих перцентилям тоже константно, их умножение, очевидно, константа), мы просто идём по диффу, двигаем маркеры туда-сюда. Т.е. например, если мы когда-то завели коллекцию profit:1Y (годовую), то она будет каждый день там по чуть-чуть обновляться и даже если у нас за год миллиарды этих чисел появляются (в контексте магазина миллиард транзакций за год звучит неплохо), то к концу года мы просто посмотрим в profit:1Y:stats и возьмём оттуда результат. Профит.
(хотя в реальности скорее всего необходимость завести такую табличку появится именно в конце года, но это уже не мои проблемы, нужно будет просто подождать)
#diffbelt