Top-K

Top-K 是一种概率型数据结构，允许您在数据流中查找最频繁的项目。

Top-K 是 Redis Stack 中一种概率型数据结构，用于估计流中排名最高的 K 个元素。

在这种情况下，“排名最高”表示“与之关联的最高数量或分数的元素”，其中分数可以是元素在流中出现的次数 - 因此使该数据结构非常适合查找流中频率最高的元素。一个非常常见的应用是检测网络异常和 DDoS 攻击，其中 Top-K 可以回答以下问题：是否有指向相同地址或来自相同 IP 的请求流量突然增加？

确实，它与计数-最小草图的功能有一些重叠，但这两种数据结构有其区别，应应用于不同的用例。

Redis Stack 中的 Top-K 实现基于 Junzhi Gong 等人提出的 HeavyKeepers 算法。它舍弃了一些旧的方案，例如 “count-all” 和 “admit-all-count-some”，转而采用 “**count-with-exponential-decay**” 策略，该策略对老鼠（小流量）有偏见，而对大象（大流量）的影响有限。此实现同时使用两种数据结构：一个哈希表存储概率计数（类似于 Count-Min Sketch），以及一个最小堆存储计数最高的 `K` 个项目。这确保了高精度，同时执行时间比以前的概率算法快，并且内存使用量仅为排序集通常所需内存的一小部分。它还具有在元素添加或删除到 Top K 列表时可以获取实时通知的额外好处。

用例

趋势标签（社交媒体平台、新闻发布网络）

此应用程序回答以下问题：

• 在过去 X 小时内，人们提到的最多的 K 个标签是什么？
• 今天阅读/观看次数最多的 K 条新闻是什么？

数据流是来自社交媒体的帖子，从中可以解析出不同的标签。

TOPK.LIST 命令的时间复杂度为 `O(K*log(k))`，因此如果 `K` 很小，则无需单独维护所有标签的集合或排序集。您可以直接从 Top K 本身进行查询。

示例

此示例将向您展示如何跟踪在线购物时使用过的关键词 “bike”，例如 “bike store” 和 “bike handlebars”。请按照以下步骤进行。

• 使用 TOPK.RESERVE 初始化一个具有特定参数的 Top K 草图。注意：width、depth 和 decay_constant 参数可以省略，因为如果没有提供，它们将分别设置为默认值 7、8 和 0.9。

> TOPK.RESERVE key k width depth decay_constant

• 使用 TOPK.ADD 将项目添加到草图中。如您所见，可以同时添加多个项目。如果在添加其他项目时返回了一个项目，则意味着该项目已从最顶端项目的最小堆中降级，下面将意味着返回的项目不再位于前 5 名，否则将返回 `nil`。这允许对进入或退出 Top K 列表的项目进行动态重磅检测。在下面的示例中，添加 “pedals” 后，它将取代 “handlebars”，后者将被返回。另外请注意，第二次添加 “store” 和 “seat” 都没有返回任何内容，因为它们已经位于 Top K 中。

• 使用 TOPK.LIST 列出迄今为止输入的项目。

• 使用 TOPK.QUERY 查看某个项目是否位于 Top K 列表中。与 TOPK.ADD 一样，可以同时查询多个项目。

  >_ Redis CLI

  > TOPK.RESERVE bikes:keywords 5 2000 7 0.925
  OK
  > TOPK.ADD bikes:keywords store seat handlebars handles pedals tires store seat
  1) (nil)
  2) (nil)
  3) (nil)
  4) (nil)
  5) (nil)
  6) handlebars
  7) (nil)
  8) (nil)
  > TOPK.LIST bikes:keywords
  1) store
  2) seat
  3) pedals
  4) tires
  5) handles
  > TOPK.QUERY bikes:keywords store handlebars
  1) (integer) 1
  2) (integer) 0

  已复制！

  厌倦了使用 redis-cli？试试 Redis Insight - Redis 的开发者 GUI。

  获取 Redis Insight

  Python

  """
  Code samples for Top-K pages:
      https://redis.ac.cn/docs/latest/develop/data-types/probabilistic/top-k/
  """
  
  import redis
  
  r = redis.Redis(decode_responses=True)
  
  
  res1 = r.topk().reserve("bikes:keywords", 5, 2000, 7, 0.925)
  print(res1)  # >>> True
  
  res2 = r.topk().add(
      "bikes:keywords",
      "store",
      "seat",
      "handlebars",
      "handles",
      "pedals",
      "tires",
      "store",
      "seat",
  )
  print(res2)  # >>> [None, None, None, None, None, 'handlebars', None, None]
  
  res3 = r.topk().list("bikes:keywords")
  print(res3)  # >>> ['store', 'seat', 'pedals', 'tires', 'handles']
  
  res4 = r.topk().query("bikes:keywords", "store", "handlebars")
  print(res4)  # >>> [1, 0]
  

  已复制！

  Python 快速入门

  Node.js

  import assert from 'assert';
  import { createClient } from 'redis';
  
  const client = createClient();
  await client.connect();
  
  
  const res1 = await client.topK.reserve('bikes:keywords', 5, {
      width: 2000,
      depth: 7,
      decay: 0.925
  });
  console.log(res1);  // >>> OK
  
  const res2 = await client.topK.add('bikes:keywords', [
    'store',
    'seat',
    'handlebars',
    'handles',
    'pedals',
    'tires',
    'store',
    'seat'
  ]);
  console.log(res2);  // >>> [null, null, null, null, null, 'handlebars', null, null]
  
  const res3 = await client.topK.list('bikes:keywords');
  console.log(res3);  // >>> ['store', 'seat', 'pedals', 'tires', 'handles']
  
  const res4 = await client.topK.query('bikes:keywords', ['store', 'handlebars']);
  console.log(res4);  // >>> [1, 0]
  
  
  

  已复制！

  Node.js 快速入门

  Java

  package io.redis.examples;
  
  
  public class TopKExample {
      public void run(){
          UnifiedJedis unifiedJedis = new UnifiedJedis("redis://127.0.0.1:6379");
  
  
          String res1 = unifiedJedis.topkReserve("bikes:keywords", 5L, 2000L, 7L, 0.925D);
          System.out.println(res1); // >>> True
  
          List<String> res2 = unifiedJedis.topkAdd("bikes:keywords",
                  "store",
                  "seat",
                  "handlebars",
                  "handles",
                  "pedals",
                  "tires",
                  "store",
                  "seat");
  
          System.out.println(res2); // >>> [None, None, None, None, None, 'handlebars', None, None]
  
          List<String> res3 = unifiedJedis.topkList("bikes:keywords");
          System.out.println(res3); // >>> ['store', 'seat', 'pedals', 'tires', 'handles']
  
          List<Boolean> res4 = unifiedJedis.topkQuery("bikes:keywords", "store", "handlebars");
          System.out.println(res4); // >>> [1, 0]
      }
  }
  

  已复制！

  Java 快速入门

  C#

  
  using NRedisStack.RedisStackCommands;
  using NRedisStack.Tests;
  using StackExchange.Redis;
  
  
  
  public class Topk_tutorial
  {
  
      [SkipIfRedis(Is.OSSCluster)]
      public void run()
      {
          var muxer = ConnectionMultiplexer.Connect("localhost:6379");
          var db = muxer.GetDatabase();
  
  
          bool res1 = db.TOPK().Reserve("bikes:keywords", 5, 2000, 7, 0.925);
          Console.WriteLine(res1);    // >>> True
  
          RedisResult[]? res2 = db.TOPK().Add("bikes:keywords",
                  "store",
                  "seat",
                  "handlebars",
                  "handles",
                  "pedals",
                  "tires",
                  "store",
                  "seat"
          );
  
          if (res2 is not null)
          {
              Console.WriteLine(string.Join(", ", string.Join(", ", res2.Select(r => $"{(r.IsNull ? "Null" : r)}"))));
              // >>> Null, Null, Null, Null, Null, handlebars, Null, Null
          }
  
          RedisResult[] res3 = db.TOPK().List("bikes:keywords");
  
          if (res3 is not null)
          {
              Console.WriteLine(string.Join(", ", string.Join(", ", res3.Select(r => $"{(r.IsNull ? "Null" : r)}"))));
              // >>> store, seat, pedals, tires, handles
          }
  
          bool[] res4 = db.TOPK().Query("bikes:keywords", "store", "handlebars");
          Console.WriteLine(string.Join(", ", res4)); // >>> True, False
  
          // Tests for 'topk' step.
  
  
      }
  }
  
  

  已复制！

  C# 快速入门

尺寸

选择 Top K 草图的尺寸比较容易，因为您需要设置的两个参数是您要在列表中保留的元素数量（K）的直接函数。

如果您从了解所需的 k 开始，可以轻松推导出宽度和深度。

width = k*log(k)
depth =  log(k)  # but a minimum of 5

对于 decay_constant，您可以使用 0.9 的值，该值在许多情况下被发现是最佳的，但您可以尝试不同的值，并找到最适合您的用例的值。

性能

Top-k 中的插入操作的时间复杂度为 O(K + depth) ≈ O(K)，查找操作的时间复杂度为 O(K)，其中 K 是要保留在列表中的前 K 个元素的数量，depth 是使用的哈希函数的数量。

学术来源

• HeavyKeeper：一种用于查找前 K 个大象流量的精确算法。

参考资料

• 认识 Top-K：RedisBloom 中一个很棒的概率添加