Знакомство с типом данных Redis HyperLogLog

Redis

помещение

Проекты или требования, разработанные на определенный период времени в будущем, будут широко использоватьсяRedis, пока бизнес не слишком занят в это время, найдите время, чтобы просмотреть и просмотретьRedisсвязанный контент. Только что увидел блогUVа такжеPVСтатистика, я думал о том, что было упомянуто в книге, которую я недавно прочиталHyperLogLogтип данных, поэтому найдите время, чтобы проанализировать его использование и сценарии использования (Пока не исследуюHyperLogLogПринцип реализации).RedisсерединаHyperLogLogтип данныхRedid 2.8.9Введено, убедитесь, что при использованииRedisВерсия>= 2.8.9.

Введение в Гиперлоглог

基数计数(cardinality counting), который обычно используется для подсчета количества уникальных элементов в наборе. Очень распространенный пример — статистика статьиUV(Unique Visitor, независимый посетитель, обычно понимаемый как клиентIP). В условиях большого объема данных для достижения кардинального подсчета в большинстве случаев не выбирают хранение элементов полного кардинального множества, поскольку можно рассчитать затраты памяти на хранение. средний размер каждого учитываемого элемента32bit, то если будет подсчитано 100 миллионов данных, занимаемый объем памяти составит:

  • 32 * 100000000 / 8 / 1024 / 1024 ≈ 381M.

Если имеется несколько наборов и разрешено вычислять объединенные результаты подсчета нескольких наборов, сложность этой операции может быть разрушительной. Поэтому не буду использоватьBitmap,TreeилиHashSetСтруктура данных непосредственно хранит набор счетных элементов для подсчета, но исходя из того, что не преследуется абсолютно точных результатов подсчета, для подсчета используется вероятностный алгоритм подсчета кардинальности.В настоящее время существует три распространенных алгоритма вероятности:

  • Linear Counting(LC).
  • LogLog Counting(LLC).
  • HyperLogLog Counting(HLL).

Таким образом, HyperLogLog на самом деле представляет собой вероятностный алгоритм подсчета количества элементов, который не уникален для Redis.Redis реализует HyperLogLog на основе языка C и предоставляет соответствующие записи API команд.

RedisавторAntirezдля воспоминанийPhilippe FlajoletИзучение комбинаторики и анализ мощностных алгоритмов, поэтому в дизайнеHyperLogLogиспользуется в командеPhilippe Flajoletинициалы имениPFкак префикс. То есть,Philippe Flajoletкандидат наукHLLОсновной вклад в алгоритм, но на самом деле он неRedisсерединаHyperLogLogРазработчик типа данных. К сожалениюPhilippe FlajoletДоктор умер в Париже 22 марта 2011 года из-за болезни. этоPhilippe FlajoletДоктор фото из Википедии:

Redisкоторый предоставилHyperLogLogХарактеристики типа данных:

  • Основные характеристики: ИспользованиеHyperLogLog Counting(HLL)выполнить,Выполнять только расчет кардинальности, метаданные не сохраняются..
  • Использование памяти:HyperLogLogкаждыйKEYсамый занятый12Kобъем памяти, который может быть рассчитан близко к2^64Мощность различных элементов, его место для хранения хранится в разреженной матрице, а занимаемая площадь очень мала.Только когда число элементов подсчета постепенно увеличивается, а пространство, занимаемое разреженной матрицей, постепенно превышает порог, это будет преобразуется в плотную матрицу за один раз.Он будет занят после того, как станет плотной матрицей12Kпространство памяти.
  • Погрешность подсчета: результат базового подсчета составляет одну стандартную ошибку (Standard Error)за0.81%Приблизительное значение , когда количество данных невелико, результатом также может быть точное значение.

Небольшой объем памяти (до 12 КБ на KEY)HyperLogLogсамое большое преимущество, который имеет два относительно очевидных ограничения:

  • Вычисленный результат не является точным значением, имеется стандартная ошибка, которая обусловлена ​​вероятностным характером алгоритма.
  • Метаданные кардинальности не сохраняются, что не подходит для сценариев, в которых необходимо использовать метаданные для анализа данных.

Использование команды HyperLogLog

Redisкоторый предоставилHyperLogLogЕсть три команды для типа данныхAPI:PFADD,PFCOUNTа такжеPFMERGE.

PFADD

PFADDПараметры команды следующие:

PFADD key element [element …]

Версии Redis, поддерживающие эту команду: >= 2.8.9 Сложность времени: сложность добавления элемента составляет O (1)

  • Функция: преобразует все параметры элементаelementдобавить в ключ какkeyизHyperLogLogв структуре данных.

PFADDПоследовательность выполнения команды следующая:

PFADDКоманда используется следующим образом:

127.0.0.1:6379> PFADD food apple fish
(integer) 1
127.0.0.1:6379> PFADD food apple
(integer) 0
127.0.0.1:6379> PFADD throwable
(integer) 1
127.0.0.1:6379> SET name doge
OK
127.0.0.1:6379> PFADD name throwable
(error) WRONGTYPE Key is not a valid HyperLogLog string value.

Несмотря на то чтоHyperLogLogСтруктура данных, по сути, представляет собой строку, но ее нельзяStringТипKEYиспользоватьHyperLogLogсвязанные команды.

PFCOUNT

PFCOUNTПараметры команды следующие:

PFCOUNT key [key …]

Версии Redis, поддерживающие эту команду: >= 2.8.9 Временная сложность: сложность возврата значения количества элементов одного HyperLogLog составляет O (1), а среднее постоянное время относительно невелико. Когда параметр представляет собой несколько ключей, сложность равна O(N), а N — количество ключей.

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

PFCOUNTКоманда используется следующим образом:

127.0.0.1:6379> PFADD POST:1 ip-1 ip-2
(integer) 1
127.0.0.1:6379> PFADD POST:2 ip-2 ip-3 ip-4
(integer) 1
127.0.0.1:6379> PFCOUNT POST:1
(integer) 2
127.0.0.1:6379> PFCOUNT POST:1 POST:2
(integer) 4
127.0.0.1:6379> PFCOUNT NOT_EXIST_KEY
(integer) 0

PFMERGE

PFMERGEПараметры команды следующие:

PFMERGE destkey sourcekey [sourcekey ...]

Версии Redis, поддерживающие эту команду: >= 2.8.9 Временная сложность: O(N), где N — количество объединяемых структур данных HyperLogLog, постоянное время выполнения этой команды относительно велико.

  • Функция: поставить несколькоHyperLogLogСтруктуры данных объединяются в новый ключ какdestkeyизHyperLogLogструктура данных, объединеннаяHyperLogLogмощность близка ко всем входамHyperLogLogВидимый набор (Observed Set) мощности объединения.
  • Возвращаемое значение команды: будет возвращаться только строкаOK.

PFMERGEКоманда используется следующим образом

127.0.0.1:6379> PFADD POST:1 ip-1 ip-2
(integer) 1
127.0.0.1:6379> PFADD POST:2 ip-2 ip-3 ip-4
(integer) 1
127.0.0.1:6379> PFMERGE POST:1-2 POST:1 POST:2
OK
127.0.0.1:6379> PFCOUNT POST:1-2
(integer) 4

Случай использования HyperLogLog для подсчета UV

Предположим, теперь есть простой сценарий, который заключается в подсчете сообщений в блоге.UV,ТребоватьUVПодсчет не обязательно должен быть точным, и при этом он не должен сохранять клиента.IPданные. В следующем сценарии используйтеHyperLogLogНапишите простую программу и закодируйте реализацию.

Последовательность шагов в этом процессе может быть скорректирована, но выполняемые операции в основном одинаковы. Кратко предположим, что контент и статистические данные статьи возвращаются фоновым сервисом, а два интерфейса разработаны отдельно. представлятьRedisрасширенный клиентLettuceполагаться:

<dependency>
    <groupId>io.lettuce</groupId>
    <artifactId>lettuce-core</artifactId>
    <version>5.2.1.RELEASE</version>
</dependency>

Кодировка следующая:

public class UvTest {

    private static RedisCommands<String, String> COMMANDS;

    @BeforeClass
    public static void beforeClass() throws Exception {
        // 初始化Redis客户端
        RedisURI uri = RedisURI.builder().withHost("localhost").withPort(6379).build();
        RedisClient redisClient = RedisClient.create(uri);
        StatefulRedisConnection<String, String> connect = redisClient.connect();
        COMMANDS = connect.sync();
    }

    @Data
    public static class PostDetail {

        private Long id;
        private String content;
    }

    private PostDetail selectPostDetail(Long id) {
        PostDetail detail = new PostDetail();
        detail.setContent("content");
        detail.setId(id);
        return detail;
    }

    private PostDetail getPostDetail(String clientIp, Long postId) {
        PostDetail detail = selectPostDetail(postId);
        String key = "puv:" + postId;
        COMMANDS.pfadd(key, clientIp);
        return detail;
    }

    private Long getPostUv(Long postId) {
        String key = "puv:" + postId;
        return COMMANDS.pfcount(key);
    }

    @Test
    public void testViewPost() throws Exception {
        Long postId = 1L;
        getPostDetail("111.111.111.111", postId);
        getPostDetail("111.111.111.222", postId);
        getPostDetail("111.111.111.333", postId);
        getPostDetail("111.111.111.444", postId);
        System.out.println(String.format("The uv count of post [%d] is %d", postId, getPostUv(postId)));
    }
}

Выходной результат:

The uv count of post [1] is 4

Можно использовать большее количество различных клиентовIPперечислитьgetPostDetail(), а затем посчитайте ошибку.

Не по теме - как правильно считать УФ

Если вам нужна точная статистикаUV, необходимо обратить внимание на несколько моментов:

  • Память или емкость диска должны быть соответствующим образом подготовлены, потому что, согласно текущему алгоритму подсчета количества элементов, нет алгоритма, который может точно считать без сохранения метаданных.
  • Если необходимо провести анализ поведения пользователей, то метаданные в конечном итоге должны быть сохранены, что должно опираться на систему больших данных.У автора нет опыта в этом отношении, поэтому я пока не буду об этом говорить.

Предполагая, что без учета стоимости памяти мы все еще можем использоватьRedisделать это точно и в режиме реального времениUVСтатистика, простота в использованииSetтип данных, добавитьUVпросто используйтеSADDкоманда, статистикаUVпросто используйтеSCARDкоманда (временная сложностьO(1), вы можете использовать его с уверенностью). Пример:

127.0.0.1:6379> SADD puv:1 ip-1 ip-2
(integer) 2
127.0.0.1:6379> SADD puv:1 ip-3 ip-4
(integer) 2
127.0.0.1:6379> SCARD puv:1
(integer) 4

Если эта статистика отображается только на стороне пользователя, то можно использовать асинхронный дизайн:

При небольшом объеме функции всех вышеперечисленных приложений могут выполняться в одном сервисе, а очередь сообщений может быть заменена асинхронной схемой пула потоков.

резюме

Эта статья является лишь кратким введениемHyperLogLogиспользование и статистикаUVсценарии использования. В общем: в сценариях, где (1) объем необработанных данных огромен, (2) требования к использованию памяти как можно меньше, (3) есть определенная ошибка в подсчете и (4) хранение метаданные не требуются, их можно использовать первыми.HyperLogLogсчитать.

Использованная литература:

(Конец этой статьи c-3-d e-a-20191117)

Технический публичный аккаунт ("Throwable Digest"), который время от времени выкладывает оригинальные технические статьи автора (никогда не занимайтесь плагиатом и не перепечатывайте):

Развлекательный публичный аккаунт («Скульптуры из песка каждый день») выбирает интересные фотографии, тексты и видео о скульптурах из песка, чтобы время от времени публиковать их, чтобы облегчить жизнь и работу:

Категории