PFCOUNT

PFCOUNT

PFCOUNT key [key ...]

Доступно с версии:

2.8.9

Сложность по времени:

O(1) со очень малой средней константой времени, когда вызывается с одним ключом. O(N) с N, являющимся количеством ключей, и намного большими константами времени, когда вызывается с несколькими ключами.

Категории ACL:

@read, @hyperloglog, @slow,

При вызове с одним ключом возвращает приближённую мощность, вычисленную структурой данных HyperLogLog, хранящейся в указанной переменной, которая равна 0, если переменная не существует.

При вызове с несколькими ключами возвращает приближённую мощность объединения HyperLogLogs, передавая, объединяя в памяти HyperLogLogs, хранящиеся по предоставленным ключам в временный HyperLogLog.

Структура данных HyperLogLog может быть использована для подсчёта уникальных элементов в наборе, используя небольшое постоянное количество памяти, конкретно 12 Кб для каждого HyperLogLog (плюс несколько байт для самого ключа).

Возвращаемая мощность наблюдаемого набора не точна, а приближённа со стандартной ошибкой 0,81%.

Например, для подсчёта всех уникальных поисковых запросов, выполненных за день, программе нужно вызвать PFADD каждый раз, когда обрабатывается запрос. Оценённое количество уникальных запросов можно получить с помощью PFCOUNT в любое время.

Примечание: в качестве побочного эффекта вызова этой функции, возможно, HyperLogLog будет изменён, так как последние 8 байт кодируют последнюю вычисленную мощность для целей кэширования. Таким образом, PFCOUNT технически является командой записи.

Возвращаемое значение

Целочисленный ответ, конкретно:

• Приближённое число уникальных элементов, наблюдаемых через PFADD.

Примеры

PFADD hll foo bar zap
PFADD hll zap zap zap
PFADD hll foo bar
PFCOUNT hll
PFADD some-other-hll 1 2 3
PFCOUNT hll some-other-hll

Производительность

Когда PFCOUNT вызывается с одним ключом, производительность отличная, даже если теоретически постоянные времена обработки плотного HyperLogLog высокие. Это возможно, потому что PFCOUNT использует кэширование для запоминания ранее вычисленной мощности, которая редко изменяется, потому что большинство операций PFADD не будут обновлять любой регистр. Сотни операций в секунду возможны.

Когда PFCOUNT вызывается с несколькими ключами, выполняется слияние HyperLogLogs на лету, что медленно, кроме того, мощность объединения не может быть кэширована, поэтому при использовании с несколькими ключами PFCOUNT может занимать время порядка миллисекунд и не следует злоупотреблять им.

Пользователь должен помнить, что выполнение этой команды с одним ключом и с несколькими ключами семантически отличаются и имеют различную производительность.

Представление HyperLogLog

Redis HyperLogLogs представлены с помощью двойного представления: разряжённое представление, подходящее для HLL, считающего небольшое количество элементов (что приводит к небольшому количеству регистров, установленных на ненулевое значение), и плотное представление, подходящее для больших мощностей. Redis автоматически переключается с разряжённого на плотное представление по мере необходимости.

Разряжённое представление использует кодирование длины блока, оптимизированное для эффективного хранения большого числа регистров, установленных на ноль. Плотное представление — это строка Redis длиной 12288 байт для хранения 16384 счётчиков из 6 бит. Необходимость двойного представления происходит от того, что использование 12 Кб (которое является требованием памяти плотного представления) для кодирования только нескольких регистров для меньших мощностей чрезвычайно неэффективно.

Оба представления снабжены 16-байтовым заголовком, который включает магическое число, поле кодирования/версии и оценку кэшированной мощности, вычисленную и хранящуюся в формате little endian (самый значимый бит равен 1, если оценка недействительна, так как HyperLogLog был обновлён с момента вычисления мощности).

HyperLogLog, будучи строкой Redis, может быть получен с помощью GET и восстановлен с помощью SET. Вызов команд PFADD, PFCOUNT или PFMERGE с повреждённым HyperLogLog никогда не является проблемой, он может возвращать случайные значения, но не влияет на стабильность сервера. В большинстве случаев при повреждении разряжённого представления сервер распознаёт повреждение и возвращает ошибку.

Представление нейтрально с точки зрения размера слова процессора и порядка байтов, поэтому одно и то же представление используется 32-битными и 64-битными процессорами, big endian или little endian.

Дополнительные сведения о реализации Redis HyperLogLog можно найти в этой записи блога. Исходный код реализации в файле hyperloglog.c также легко читаем и понятен и включает полную спецификацию для точного кодирования, используемого для разряжённых и плотных представлений.