Дополнительные темы HyperLogLog для Redis

Redis
Дополнительные темы HyperLogLog для Redis

1. Почвенный подсчет

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

1.1 Концепция

Количество элементов используется для подсчета количества уникальных элементов в наборе, таких как сценарии ежедневного спроса, статистика UV страницы или статистика онлайн-пользователей, зарегистрированных IP-адресов и т. д.

Если бы вас попросили реализовать это требование, как бы вы подумали о его реализации? Самый простой способ — записать все уникальные предметы в коллекцию. Установите S, добавляется новый элемент x, сначала определите, входит ли x в S, если нет, добавьте x в S, иначе не записывайте. Можно реализовать широко используемую структуру данных SET.

Но если это будет реализовано, если объем данных будет становиться все больше и больше, какие проблемы это вызовет?

  • Когда количество статистических данных становится больше, соответствующая память для хранения будет расти линейно.
  • Когда набор S больше, стоимость оценки того, находится ли элемент x в наборе S, будет выше.

Есть ли какое-либо другое решение, которое может уменьшить проблемы, вызванные двумя вышеуказанными проблемами?Ответ определенно да, и ниже приводится краткое введение.

1.2 Методы

Существует три часто используемых метода подсчета количества элементов: дерево B+, растровое изображение и вероятностный алгоритм.

  • Дерево В+. Эффективность вставки дерева B+ и поиска относительно высока. Вы можете быстро узнать, существует ли элемент, и вставить его. Если вы хотите вычислить значение кардинальности (значение неповторяющегося элемента), вам нужно только количество узлов в дереве. Но есть еще проблема не экономии места в памяти.
  • битовая карта. Битовая карта — это структура данных, которая хранит определенные данные через битовый массив. Счетчик оснований соответствует одному биту битового массива для каждого элемента, такого как битовый массив 010010101, который представляет [1, 4, 6, 8]. Для вновь добавленного элемента требуется только вычисление побитового ИЛИ для существующего битового массива и вновь добавленного элемента. Этот метод может значительно уменьшить объем памяти: если вы храните 100 миллионов данных, вам потребуется всего 100000000/8/1024/1024 ≈ 12 МБ памяти. По сравнению с деревом B+ это действительно экономит много, но в некоторых сценариях с очень большими данными, если есть 10 000 объектов со 100 миллионами данных, требуется 120 ГБ памяти.Можно сказать, что потребление памяти все еще довольно велико в некоторых случаях. сценарии.
  • Вероятностный алгоритм. Вероятностный алгоритм экономит место, жертвуя точностью. Для сценариев, не требующих абсолютной точности, вероятностный алгоритм является хорошим выбором, поскольку вероятностный алгоритм не хранит сам набор данных напрямую, а предсказывает его с помощью определенных вероятностных и статистических методов. базовое значение, гарантируя, что ошибка находится в определенном диапазоне, этот метод может значительно уменьшить объем памяти. HyperLogLog — это реализация вероятностного алгоритма, и нижеследующее посвящено этому алгоритму.

2. HyperLogLog

2.1 Принцип

Принципиальная идея HyperLogLog состоит в том, чтобы записать максимальное значение k первой единицы в битовой строке числа в наборе, задав набор из n элементов, что также можно понимать как максимальное количество последовательных нулей в младшие двоичные биты. Количество m уникальных элементов в наборе можно оценить по значению k, и m приблизительно равно 2^k.

Из сети исходит следующая картина.Давая определенное количество пользователей User, через Hash получается строка Bitstrings, и количество наибольших последовательных нулевых битов записывается как 4, а уникальное число User равно 2^4 = 16.

Код ниже демонстрирует это.

2.2 Демонстрация кода

Есть ссылки на код https://kuaibao.qq.com/s/20180917G0N2C300?refer=cp_1026

# content of hyperloglog_test.py
class BitsBucket(object):
    def __init__(self):
        self.maxbit = 0

    @staticmethod
    def get_zeros(value):
        for i in range(31):
            if (value >> i) & 1:
                break
        return i

    def add(self, m):
        self.maxbit = max(self.maxbit, self.get_zeros(m))

class HyperLogLogTest(object):
    def __init__(self, n, bucket_cnt=1024):
        self.n = n
        self.bucket_cnt = bucket_cnt
        self.bits_bucket = [BitsBucket() for i in range(bucket_cnt)]

    @staticmethod
    def generate_value():
        return random.randint(1, 2**32 - 1)

    def pfadd(self):
        for i in range(self.n):
            value = self.generate_value()
            bucket = self.bits_bucket[((value & 0xfff0000) >> 16) % self.bucket_cnt]
            bucket.add(value)

    def pfcount(self):
        sumbits_inverse = 0
        for bucket in self.bits_bucket:
            if bucket.maxbit == 0:
                continue
            sumbits_inverse += 1.0 / float(bucket.maxbit)
        avgbits = float(self.bucket_cnt) / sumbits_inverse
        return 2**avgbits * self.bucket_cnt

Класс BitsBucket предназначен для вычисления максимального количества последовательных младших битов в наборе.HyperLogLogTest реализует два метода: pfadd — для случайного добавления n элементов в набор наборов, а pfcount — для вычисления среднего значения кардинальности для сегментов Bucket_cnt.

Почему вы считаете Bucket_cnt ведра?Потому что этот алгоритм является случайным и вероятностным, если ведро имеет очень большую частоту ошибок, то предлагается концепция усреднения ведра, и статистические данные разбиваются на m ведер, и каждое ведро считает свое Оценки кардинальности, и, наконец, эти оценки усредняются для получения общей оценки кардинальности.

Протестируйте это сейчас:

# content of hyperloglog_test.py
def main(bucket_cnt=1024):
    print("bucket cnt: {}, start".format(bucket_cnt))
    for i in range(100000, 1000000, 100000):
        hyperloglog = HyperLogLogTest(i, bucket_cnt)
        hyperloglog.pfadd()
        pfcount = hyperloglog.pfcount()
        print("original count: {} ".format(i),
              "pfcount: {}".format('%.2f' % pfcount), "error rate: {}%".format(
                  '%.2f' % (abs(pfcount - i) / i * 100)))
    print("bucket cnt: {}, end \n\n".format(bucket_cnt))


buckets = [1, 1024]
for cnt in buckets:
    main(cnt)

Протестировано с Bucket_cnt равным 1 и 1024 соответственно, результаты следующие:

➜  HyperLogLog git:(master) ✗ python3 hyperloglog_test.py
bucket cnt: 1, start
original count: 100000  pfcount: 65536.00 error rate: 34.46%
original count: 200000  pfcount: 131072.00 error rate: 34.46%
original count: 300000  pfcount: 131072.00 error rate: 56.31%
original count: 400000  pfcount: 524288.00 error rate: 31.07%
original count: 500000  pfcount: 1048576.00 error rate: 109.72%
original count: 600000  pfcount: 2097152.00 error rate: 249.53%
original count: 700000  pfcount: 262144.00 error rate: 62.55%
original count: 800000  pfcount: 1048576.00 error rate: 31.07%
original count: 900000  pfcount: 262144.00 error rate: 70.87%
bucket cnt: 1, end

bucket cnt: 1024, start
original count: 100000  pfcount: 97397.13 error rate: 2.60%
original count: 200000  pfcount: 192659.65 error rate: 3.67%
original count: 300000  pfcount: 287909.86 error rate: 4.03%
original count: 400000  pfcount: 399678.34 error rate: 0.08%
original count: 500000  pfcount: 515970.76 error rate: 3.19%
original count: 600000  pfcount: 615906.34 error rate: 2.65%
original count: 700000  pfcount: 735321.47 error rate: 5.05%
original count: 800000  pfcount: 808206.55 error rate: 1.03%
original count: 900000  pfcount: 950692.17 error rate: 5.63%
bucket cnt: 1024, end

Видно, что Bucket_cnt=1, ошибка очень большая, и алгоритм в принципе можно использовать, когда она равна 1024. HyperLogLog, реализованный в Redis, более сложен и может контролировать ошибку в пределах 0,81%. Давайте сосредоточимся на применении HyperLogLog в Redis.

3. Реализация HyperLogLog в Redis

HyperLogLog в Redis появился в версии 2.8.9.Подробности можно найти в сообщении в блоге, написанном автором Redis antirez:Redis new data structure: the HyperLogLog

3.1 Использование

Использование включает в себя 3 команды:

  • pfadd добавляет элемент к ключу
  • pfcount подсчитывает количество уникальных элементов в ключе
  • Pfmerge объединяет элементы в нескольких ключах
127.0.0.1:6379> PFADD pf_tc tc01
(integer) 1
127.0.0.1:6379> PFADD pf_tc tc02
(integer) 1
127.0.0.1:6379> PFADD pf_tc tc03
(integer) 1
127.0.0.1:6379> PFADD pf_tc tc04 tc05 tc06
(integer) 1
127.0.0.1:6379> PFCOUNT pf_tc
(integer) 6
127.0.0.1:6379> PFADD pf_tc tc04 tc05 tc06
(integer) 0
127.0.0.1:6379> PFCOUNT pf_tc
(integer) 6

127.0.0.1:6379> PFADD pf_tc01 tc07 tc08 tc09 tc10 tc01 tc02 tc03
(integer) 1
127.0.0.1:6379> PFCOUNT pf_tc01
(integer) 7
127.0.0.1:6379> PFMERGE pf_tc pf_tc01
OK
127.0.0.1:6379> PFCOUNT pf_tc
(integer) 10
127.0.0.1:6379> PFCOUNT pf_tc01
(integer) 7

Это кажется очень точным? Давайте напишем скрипт, чтобы проверить это.

3.2 Анализ ошибок

Напишите кусок кода Python ниже, чтобы проверить ошибку

class HyperLogLogRedis(object):
    def __init__(self, n):
        self.n = n
        self.redis_client = redis.StrictRedis()
        self.key = "pftest:{}".format(n)

    @staticmethod
    def generate_value():
        return random.randint(1, 2**32 - 1)

    def pfadd(self):
        for i in range(self.n):
            value = self.generate_value()
            self.redis_client.pfadd(self.key, value)

    def pfcount(self):
        return self.redis_client.pfcount(self.key)


def main():
    for i in range(100000, 1000000, 100000):
        hyperloglog = HyperLogLogRedis(i)
        hyperloglog.pfadd()
        pfcount = hyperloglog.pfcount()
        print("original count: {} ".format(i),
              "pfcount: {}".format('%.2f' % pfcount), "error rate: {}%".format(
                  '%.2f' % (abs(pfcount - i) / i * 100)))

main()

Кодовая часть еще немного доработана на основе 2.2, а функция HyperLogLog из redis заменена на ту часть, которую тестировал лично я.

Результаты теста следующие:

➜  HyperLogLog git:(master) ✗ python3 hyperloglog_redis.py
original count: 100000  pfcount: 99763.00 error rate: 0.24%
original count: 200000  pfcount: 200154.00 error rate: 0.08%
original count: 300000  pfcount: 298060.00 error rate: 0.65%
original count: 400000  pfcount: 394419.00 error rate: 1.40%
original count: 500000  pfcount: 496263.00 error rate: 0.75%
original count: 600000  pfcount: 595397.00 error rate: 0.77%
original count: 700000  pfcount: 712731.00 error rate: 1.82%
original count: 800000  pfcount: 793678.00 error rate: 0.79%
original count: 900000  pfcount: 899268.00 error rate: 0.08%

Основная ошибка составляет около 0,81%, поэтому стандартная ошибка составляет 0,81%, поскольку Redis использует 16384 сегмента, формула стандартной ошибки HyperLogLog составляет 1,04/sqrt(m), m — количество сегментов, поэтому в Redis m = 16384. , стандартная ошибка составляет 0,81%.

3.3 Анализ памяти

Redis использует 16384 корзины для хранения и расчета HyperLogLog, сколько памяти это займет? Redis может подсчитывать до 2 ^ 64 данных, что означает, что максимальное количество битов каждого сегмента требует для хранения 6 бит (2 ^ 6 = 64). Тогда занятая память 16384*6/8=12кб.

В первом разделе упоминалось, что BitMap требуется 12 МБ для 100 млн данных.Если данных 2^64, для грубого расчета требуется 1500 ТБ, а для HyperLogLog требуется только 12 КБ. Можно предположить, что HyperLogLog является мощным, но это не означает, что растровое изображение Это не хорошо.Каждая структура данных имеет свои наиболее подходящие сценарии применения.Можно лишь сказать, что HyperLogLog является очень мощным алгоритмом в сценарии кардинальной статистики.

Если небольшое количество элементов Redis будет разреженной структурой хранения, ее размер будет меньше 12 КБ, используя плотную структуру памяти, фиксированный размер 12 КБ, используя сохраненную строку для достижения растрового изображения Redis, т. е. последовательного сегмента 16384, на каждый ствол приходится 6 Биты.

Подробнее читайте в исходном коде Redis:GitHub.com/Антиэнтузиазм/Горячие…

Статьи по Теме:

Соответствующий код находится вGitHub.com/VP предлагает/Job-Job-Day…

Более подробные статьи и обсуждения Redis, пожалуйста, обратите внимание на общественное число: «Tianshi Technology Разное»

Категории