Различен ефективен брой

Изборът на броя на уникалните стойности за определен период от време не е много често срещана задача. В .io трябва да определим броя на уникалните потребители, посещаващи сайта за всеки период от време.

Разбира се, има много просто обикновено SQL решение. Достатъчно е да запазите уникални потребителски идентификатори и времето за влизане в проста таблица:

Тогава решението ще изглежда така:

# Отделен избор на обикновен брой в Mysql

Това решение обаче е доста бавно дори на малки маси (милиони записи).

# Много бавно и това са 2,5 милиона записа в таблицата

Общият брой на публиката, за която вярваме, е около 50 милиона души на ден, така че това не ни устройваше.

MySQL и преброяване (различно)

Mysql не е много подходящ за решаване на проблеми. Но си струваше да опитам. За да накарате всичко да работи по-бързо, можете да направите няколко оптимизации.

1. Правилен индекс

Mysql пак ще сканира всички редове от заявката, за да намери уникални идентификатори. Графата време ще ви помогне да ги намалите значително. Следователно трябва да отиде първо в индекса:

2. Квант време

В нашия случай минималният период от време за отчитане на стойности не може да бъде по-малък от един ден. Няма смисъл да запазвате повече от един запис за всеки потребител в един ден. Така че трябва да се направи времевата колона тип дата и сложи уникален индекс:

# Часовата колона е от тип дата, сега всеки ден ще има само един запис с уникален идентификатор

Вертика и преброяване (различно)

Тази векторна база данни е добре оптимизирана за съвкупно вземане на проби. Преброяването на количеството през избрания интервал от време обаче работи само 2-3 пъти по-бързо от Mysql.

# Малко по-бързо от Mysql

приблизителен_ брой_различен ()

Vertica поддържа агрегирана функция приблизителен_ брой_различен (), което отчита приблизително броя на уникалните стойности. Той работи с порядък по-бързо от обикновената заявка, но има грешка от около 1%:

Redis и HyperLogLog

Redis има специално предназначение за съхранение HyperLogLog. Тя ви позволява да съхранявате ключове там и след това да получавате броя на уникалните ключове в този магазин. Ограничението е, че списъкът на съхранените ключове не може да бъде получен. Предимството е, че едно такова хранилище отнема само 12 KB, е в състояние да съхранява 2 64 елемента и връща резултата с грешка от само 0,8%.

Устройство HyperLogLog

HyperLogLog е вероятностен алгоритъм за преброяване на уникални елементи.

Принципът на алгоритъма може да бъде обяснен с прост пример от живота. Представете си, че хвърляте монета от известно време, като броите броя на непрекъснатите последователни глави. Ако завършите с поредица, която е само 3 глави подред, тогава можем да предположим, че не сте хвърляли монета много дълго. От друга страна, ако сте ударили 15, тогава вероятно сте прекарали по-голямата част от деня.

Но ако имате късмет и за първи път получите последователност от 10 глави, след което сте спрели това безсмислено упражнение, тогава приблизителната преценка за прекараното време ще бъде изключително погрешна. За да увеличите точността на сближаването, ще трябва да повторите експеримента, но този път използвайте 10 монети и 10 листа хартия, на които ще запишете най-дългите последователности от опашки. По този начин преценката на прекараното време ще бъде много по-точна.

HyperLogLog изчислява хеш на всеки нов елемент. Част от този хеш (в двоично представяне) се използва за индекса на регистъра (разделяме набора от нули и единици на m-брой подмножества, нашите двойки са монета + лист хартия). А другата част се използва за изчисляване на дължината на последователността на първите нули и максималната стойност на тази последователност (дължината на последователността на изпуснатите опашки). Вероятността за поредица от n + 1 нули е половината от вероятността за поредица с дължина n.

Следователно, използвайки стойностите на различни регистри, които са свързани с максималните последователности от нули за дадено подмножество, HyperLogLog е в състояние да осигури приблизителна мощност с висока точност. Ако има m-подгрупи и n-елементи, тогава всяка група ще има n/m уникални елементи средно и средната стойност за всички подгрупи дава доста точна оценка на стойността на log2 (n/m).

Преброяване на уникални стойности

В най-простия случай е достатъчно да съхраните всички стойности в елемента HLL:

# Функцията pfcount ще върне броя на уникалните стойности в ключа hll, ще видим 1

Тук сме запазили 1 елемент (номер 1) в ключа "hll" и сме показали броя на уникалните елементи. Нека добавим още няколко елемента към същия ключ:

# Сега ще видим 3 на екрана

Както трябва, получихме резултата 3 (т.е. само 3 уникални елемента са написани в този ключ).

И най-важното е, че този подход работи с 3-4 порядъка по-бързо от подобно решение, базирано на SQL.

Филтри за време

Стандартното решение обаче не е достатъчно. Трябва да можем да изберем период за отчитане на уникални стойности. В този случай Redis е в състояние да залепи HLL ключове точно по време на извличане:

# Изборът ще върне 5 - броя уникални елементи в два HLL клавиша наведнъж

За вземане на проби може да се използва произволен брой ключове hll. И ние трябва да получим броя на уникалните потребители през деня. Следователно, за да го разрешите, е достатъчно да запазите потребителския идентификатор в ключа HLL, когато той посещава страницата. Името на ключа ще съдържа суфикс - датата на посещение:

# Запазване на информация за посещението за деня

Сега трябва да изберете броя на уникалните потребители за всеки период от време. За да направите това, трябва да залепите всички ключове за датите в рамките на този интервал:

# Резултатът ще бъде броят на уникалните посетители в периода от 10.06 до 13.06.2016

Най-важното нещо

SQL инструментите са бедни при преброяване на уникални стойности. Особено ако трябва да филтрирате списъка. За малки количества данни е достатъчно да се използват правилните индекси в MySQL. За обеми над 1 милион записи, помислете за използването на HyperLogLog съхранение в Redis.

Прости и бързи опции за прехвърляне на ключовете Redis на друг сървър.

Колко наистина са изградени големите MySQL системи

2 примера за денормализация за оптимизация на база данни

Как да решим често срещани проблеми с NoSQL

Видове и методи за използване на репликация като пример за MySQL

Основни понятия за изостряне и репликация

Търсене на голямо количество текст

Разделяне на база данни в няколко независими бази данни

Подобряване на скоростта на заявките с MySQL Handlersocket

Какво представляват индексите в Mysql и как да ги използваме за оптимизиране на заявките

Проверка на работата на Mysql под товар Sysbench

Как да преразпределя данни между сървъри

Въведение в хеш таблици, основни методи за справяне със сблъсъци

Разделяне на таблици с данни на различни възли

Препоръки за настройка на Redis за оптимизиране на ресурсите и подобряване на стабилността на производствен сървър

Най-лошите практики при работа по нарастващи проекти

Правилна конфигурация на Mysql за товари и не само. Актуализирано.

Оптимизиране на изхода на пагинация

Анализиране на бавни заявки (профилиране) в MySQL с Percona Toolkit

Лесен начин за избор на индекси за Mysql

Активиране и работа с журнала за бавни заявки в Mysql

DROP INDEX в Mysql

Преглед на профил на заявки в Mysql

5 параметъра за оптимизиране в Mysql за wordpress