在本文中,您将学习如何在 Redis 键上执行位运算,以及设置、获取和比较二进制值。首先,让我们考虑一下“翻转位”通常如何成为存储信息的有用方法,以及我们如何使用 Redis 执行二进制运算。
以下面的例子为例:有 30 个美国职业棒球大联盟球队,每支球队每年进行 162 场比赛。每年总共进行 2430 场比赛。这些比赛大约在六个月内进行。我们知道一个月永远不会超过 31 天,因此我们可以使用 32 位数字的 31 位来存储单个球队在一个月内的比赛日程。
正如您已经知道的,一个 (1) 字节是 8 位,并且位在二进制(以 2 为底)数字中从“右到左”进行跟踪。零 (0) 位是最右边也是最小的。您可以用 8 位表示的最大数字是 256
11111111
(2^7)+(2^6)+(2^5)+(2^4)+(2^3)+(2^2)+(2^1)+(2^0)
128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 256
在下面的示例中,我们将使用 32 位数字(4 个字节),第 31 位(任何给定月份中最大的可能位置)的地址为 2^30。
假设纽约扬基队在 1 号、3 号到 10 号、13 号到 28 号和 31 号比赛。从最右边开始,其中零位代表第一天,在位中,它看起来像
1001111111111111111001111111101
^31st ^10th ^1st
Or in decimal:
1342174205
这表明我们需要 10 个字节来存储 MLB 球队的每月赛程。这意味着我们可以存储每支球队的赛程,大小为 10 * 30 字节(字节 * 球队数量),这不是很多字节,最重要的是,我们可以证明这是我们永远需要的最大空间,除非管理棒球的规则发生变化。
如果您想知道球队是否在 13 号比赛,您需要获得第 13 位的位掩码(使用左移运算符 <<)
1 << 12 // 4096
使用像 JavaScript 这样的语言,我们可以更清楚地演示左移和 31 位数字上的隐含 0 填充
parseInt('0000000000000000001000000000000', 2) // 4096
或者可视化为两个零和一的字符串的比较
1001111111111111111001111111101
& 0000000000000000001000000000000
^
1 & 1 === true
类似地,我们可以使用 OR(|) 运算符设置第 13 位
1342174205 | 4096
或者更明确地
1242174205 | Math.pow(2^12)
太棒了!现在让我们使用 Redis 来存储更多更大的二进制数据。
Redis 是一个基于键/值范例构建的数据结构存储,最基本的操作是将字符串存储在键中
redis-cli> set mykey 1
redis-cli> get mykey
redis-cli> "1"
Redis BITOP 系列命令允许您对字符串键执行位运算。使用命名良好的 SETBIT 和 GETBIT 命令,您可以... 设置和获取键上的位。您可以使用按位运算符 AND、OR 和 XOR 设置比较键,就像我们上面对 MLB 赛程所做的那样。例如,让我们打开第三位键测试
> SETBIT test 3 1
> GETBIT test 3 // 1
> GETBIT test 2 // 0 (not set)
这很容易。应该清楚如何通过设置球队赛程的某些位或创建掩码来完成上面的测试。
让我们使用位图来解决存储扬基队胜/负记录的问题。我们知道他们一年将进行 162 场比赛。如果 1 代表胜利,0 代表失败,我们可以创建一个 Redis 键 'yankees_record' 并像这样设置所有胜利
> SETBIT yankees_record 2 1 // Won game 2
> SETBIT yankees_record 3 1
> SETBIT yankees_record 10 1 // Breaking 6 game losing streak!
> SETBIT yankees_record 11 1
> ...
通过应用将一系列位映射到其他二进制值的位掩码,您可以进行非常快速且内存高效的分析比较。在下一节中,我们将学习一些使用此技术的典型示例。
Redis 数据库中的任何键都可以存储 (2^32 – 1) 位,或者略低于 512 MiB(目前)。这意味着每个键大约可以设置 42.9 亿列或偏移量。这是一个在单个键中引用的大量位。我们可以沿这些范围设置位来描述我们想要跟踪的项目的特征,例如查看给定文章的用户数量。
假设我们正在提供许多不同的文章,并且每篇文章都分配了一个唯一的标识符。还假设我们的网站上有 100,000 名活跃会员,并且每个用户也有一个唯一的标识符 - 一个介于 1 和 100,000 之间的数字。我们可以使用位运算来跟踪查看活动,方法是创建一个对该文章唯一的键,并设置与查看给定文章的用户 ID 对应的位。以下示例显示文章 808 已被用户 4、6、9-11 等查看
article:808:01-03-2018 : 00010100111010001001111...
此键代表特定日期的文章 808,通过翻转与用户分配的 ID 对应的偏移量处的位,有效地存储了当天查看者的唯一用户 ID。每当用户查看文章时,我们使用 SETBIT 命令在用户 ID 提供的偏移量处设置一位
client.GETBIT('article:808:01-03-2018', userId, 1)
让我们为三篇文章创建数据
const redis = require('redis');
const client = redis.createClient(/* your configuration info */);
const multi = client.multi();
// Create three articles with randomized hits representing user views
let id = 100000;
while(id--) {
multi.SETBIT('article1:today', id, Math.round(Math.random(1)));
multi.SETBIT('article2:today', id, Math.round(Math.random(1)));
multi.SETBIT('article3:today', id, Math.round(Math.random(1)));
}
multi.exec(err => {
// done
})
在这里,我们只是创建了三个 Redis 键,article(1-3):today,并在每个键上随机设置了 100,000 位 - 0 或 1。使用基于用户 ID 偏移量存储用户活动的技术,我们现在拥有了针对三篇文章的假设流量日的示例数据。
要计算查看过文章的用户数量,我们可以使用 BITCOUNT
client.bitcount('article1:today', (err, count) => {
console.log(count)
})
此方法很简单:查看文章的用户数等于键上设置的位数。现在,让我们计算文章查看的总数
client.multi([
["bitcount", "article1:today"],
["bitcount", "article2:today"],
["bitcount", "article3:today"]
]).exec((err, totals) => {
let total = totals.reduce(function(prev, cur) {
return prev + cur;
}, 0);
console.log("Total views: ", total);
})
一旦 MULTI 返回与 SETBIT 从 Redis 返回的每个操作的结果相对应的结果数组(位数),我们将计数减少为表示所有文章的总查看次数的总和。
如果我们反而对用户 123 今天查看了多少篇文章感兴趣,我们可以使用 GETBIT,它只是返回给定偏移量处的值(0 或 1)。结果将在 0-3 范围内
client.multi([
["GETBIT", "article1:today", 123],
["GETBIT", "article2:today", 123],
["GETBIT", "article3:today", 123]
]).exec((err, hits) => {
let total = hits.reduce(function(prev, cur) {
return prev + cur;
}, 0);
console.log(total); // 0, 1, 2 or 3
})
这些是从位表示中收集信息的非常有用和直接的方法。让我们更进一步,了解使用位掩码以及 AND、OR 和 XOR 运算符过滤位。
如果我们想检查用户 123 是否阅读过这两篇文章怎么办?使用 BITOP AND,这很容易实现
client.multi([
['SETBIT', 'user123', 123, 1],
['BITOP', 'AND','123:sawboth','user123','article1:today', 'article3:today'],
['GETBIT', '123:sawboth', 123]
]).exec((err, result) => {
let sawboth = result[2];
console.log('123 saw both articles: ', !!sawboth);
});
首先,我们创建一个掩码,用于隔离存储在键user123中的特定用户,该掩码在偏移量 123 处包含一个正位(再次,表示用户的 ID)。对两个或多个位表示执行 AND 运算的结果不会作为值由 Redis 返回,而是写入指定的键,在前面的示例中,该键指定为“123:sawboth”。此键包含位表示,用于回答文章键是否也包含与 user123 键的偏移量相同的正位的位表示的问题。
当尝试查找至少看过一篇文章的用户总数时,OR 运算符效果很好
client.multi([
['BITOP', 'OR','atleastonearticle','article1:today','article2:today','article3:today'],
['bitcount', 'atleastonearticle']
]).exec((err, results) => {
console.log("At least one: ", results[1]);
});
在这里,atleastonearticle 键标记在三篇文章中任何一篇中设置的所有偏移量处的位。我们可以使用这些技术来创建一个简单的推荐引擎。
例如,如果我们能够通过其他方式确定两篇文章是相似的(基于标签、关键字等),我们可以找到阅读过一篇并推荐另一篇的用户。为此,我们使用 XOR 查找所有阅读过第一篇文章或第二篇文章但不同时阅读的用户。然后,我们将该集合分成两个列表:阅读过第一篇文章的人和阅读过第二篇文章的人,并将这些列表进行比较以提供推荐
client.multi([
['BITOP','XOR','recommendother','article1:today','article2:today'],
['BITOP','AND','recommend:article1','recommendother','article2:today'],
['BITOP','AND','recommend:article2','recommendother','article1:today'],
['bitcount', 'recommendother'],
['bitcount', 'recommend:article1'],
['bitcount', 'recommend:article2'],
['del', 'recommendother', 'recommend:article1','recommend:article2']
]).exec((err, results) => {
// Note result offset due to first 3 setup ops
console.log("Didn't see both articles: ", results[3]);
console.log("Saw article2; recommend article1: ", results[4]);
console.log("Saw article1; recommend article2: ", results[5]);
})
虽然不是必须的,但我们还会获取每个列表的计数,并在完成后删除结果键。
要计算 Redis 中二进制值占用的总字节数,请将最大偏移量除以 8。在一个文章上存储 1,000,000 个用户的访问数据最多需要 ~125 kB - 对于如此丰富的分析数据,这不是很大的内存或存储开销。因为我们可以准确地测量所需的空间,这在规划存储成本、扩展等方面也给我们带来一些信心。
Sandro Pasquali 于 1997 年成立了一家名为 Simple 的技术公司,该公司销售了世界上第一个基于 JavaScript 的应用程序开发框架,并因其部署和广告技术而获得了多项专利,这些技术预见了基于互联网的软件的未来。他撰写了三本关于 NodeJS 的书籍。他为私人客户构建企业级软件,经常部署功能极其强大的 Redis 来帮助满足大型客户复杂的信息管理需求。