distchen / distchen.github.io Goto Github PK
View Code? Open in Web Editor NEWHome Page: http://www.chenyp.com
Home Page: http://www.chenyp.com
Redis 3.2版本之后,新增了对GEO(地理位置)的支持(#1 ),地理位置大概提供了6个命令,分别为:
在数学上,基数是集合论中刻画任意集合大小的一个概念。
除了Redis的五种常见数据类型外(#1 ),Redis提供了HyperLogLog结构。这个结构可以非常省内存的去统计各种计数,比如注册ip数、每日访问IP数、页面实时UV、在线用户数等。
这里看到所有的用处都是xxx数,所以这个数据结构的特点就是,可以比较准确的估算出你要统计的数量,但是却无法知道统计的详细内容。比如统计每日访问IP数,可以获取当时访问过的IP总数量,但是没法知道这些IP都是什么。
有得必有失,当然你要统计上面提到的那些内容,可以用集合来处理,这样可以知道数量,也能获得所有的详细列表。但是一个大型的网站,每天IP比如有100万个呢,我们粗算一个IP消耗15字节,那么100万个IP就是15M,如果1千万,就是150M。
再来看看HyperLogLog,在Redis中每个键占用的内容都是12K,理论存储近似接近2^64个值,不管存储的内容是什么。12K,知道这个数据结构的作用了吧。这也是为什么他不能知道里面的详细内容了。这是一个基于基数估算的算法,只能比较准确的估算出基数,可以使用少量固定的内存去存储并识别集合中的唯一元素。而且这个估算的基数并不一定准确,是一个带有 0.81% 标准错误(standard error)的近似值。
HyperLogLog结构,在范围允许的情况下无论多少值,都只会占用12K内存。
这样比如我们把每日IP记录下来,假设每天有一亿个IP访问,如果使用集合的话,一天的内存使用就是1.5G,假设我们存储一个月的记录,就需要45G容量。但是使用HyperLogLog的话,一天12K,一个月360K。如果我们不需要知道IP具体信息的话,完全可以把这些记录留在内存一年、或者不删都行。如果需要,我们也会把所有的IP访问记录通过其他途径存储起来。把每天的信息存储起来,我们可以计算每月IP总数(MERGE),一年的IP总数等(去重)。
下面介绍一下HyperLogLog的命令,其实他和集合的命令比较像,只是命令少,不能获取列表而已。另外这个数据结构需要2.8.9及以上的版本才能使用。
在执行这个命令之后,HyperLogLog内部的结构会被更新,如果执行完之后HyperLogLog内部的基数估算发生了变化,那么就会返回1,否则(认为已经存在)就返回0。
这个命令还可以只有键,没有值,这样就只是创建空的键,不放值。如果这个键存在,不做任何事情,返回0;不存在的话就创建,并返回1。
redis> pfadd ip:20160929 "1.1.1.1" "2.2.2.2" "3.3.3.3"
(integer) 1
redis> pfadd ip:20160929 "2.2.2.2" "4.4.4.4" "5.5.5.5" # 存在就只加新的
(integer) 1
redis> pfcount ip:20160929 #元素估计数量没有变化
(integer) 5
redis> pfadd ip:20160929 "2.2.2.2" # 存在就不会增加
(integer) 0
当命令作用于单个键的时候,返回这个键的基数估算值。如果键不存在,则返回0。
当作用于多个键的时候,返回这些键的并集估算值。类似于把这些键都合并了之后,在调用这个命令输出。
这个命令在作用于单个值的时候,时间复杂度为O(1),并且具有非常低的平均常数时间;在作用于N个值的时候,时间复杂度为O(N),这个命令的常数复杂度会比较低些。
redis> pfadd ip:20160929 "1.1.1.1" "2.2.2.2" "3.3.3.3"
(integer) 1
redis> pfcount ip:20160929
(integer) 3
redis> pfadd ip:20160928 "1.1.1.1" "4.4.4.4" "5.5.5.5"
(integer) 1
redis> pfcount ip:20160928 ip:20160929
(integer) 5
这个命令的时间复杂度为O(N),其中N为要合并的HyperLogLog的个数。不过这个命令的常数时间复杂度比较高。
redis> pfadd ip:20160929 "1.1.1.1" "2.2.2.2" "3.3.3.3"
(integer) 1
redis> pfadd ip:20160928 "1.1.1.1" "4.4.4.4" "5.5.5.5"
(integer) 1
redis> pfmerge ip:201609 ip:20160928 ip:20160929
OK
redis> pfcount ip:201609
(integer) 5
数据量一大,统计基数也成了一个麻烦事。进行基数统计时,使用Hyperloglog算法,占用内存小,误差小,实乃不错的方法。
算法的论文是《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》,可以在谷歌学术上下载下来看看,简述下其**核心。
在理想状态下,将一堆数据hash至[0,1],每两点距离相等,1/间距 即可得出这堆数据的基数。然而实际情况往往不能如愿,只能通过一些修正不断的逼近这个实际的基数。实际采用的方式一是分桶,二是取kmax。分桶将数据分为m组,每组取第k个位置的值,所有组中得到最大的kmax,(k-1)/kmax得到估计的基数。
HLL算法的另一个主观上的理解可以用抛硬币的方式来理解。以当硬币抛出反面为一次过程,当你抛n次硬币全为正面的概率为1/2^n。当你经历过k(k很大时)次这样的过程,硬币不出现反面的概率基本为0。假设反面为1,正面为0,每抛一次记录1或者0,当记录上显示为0000000...001时,这种可以归结为小概率事件,基本不会发生。转换到基数的想法就是,可以通过第一个1出现前0的个数n来统计基数,基数大致为2^(n+1)时。硬币当中可以统计为(1/21+1/42+1/8*3...),大致可以这么去想。
BitMap就是通过一个bit位来表示某个元素对应的值或者状态,其中key就是对应元素本身。在某些特定的应用场景下,使用BitMap非常适合,如:
还有很多其它应用场景,使用BitMap的场景大多在于需要记录对象状态(登录、签到、打开、关闭等),这里的对象可以是用户,也可以是其它。总的来说,只要需要记录状态与否,BitMap可能就有用武之地。
Redis从2.2.0开始新增了如下三个与bitmap相关的命令:
setbit
getbit
bitcount
在介绍这三个命令之前,先看一个神奇的示例:
127.0.0.1:6379> set demo B
OK
127.0.0.1:6379> get demo
"B"
127.0.0.1:6379> setbit demo 7 1
(integer) 0
127.0.0.1:6379> get demo
"C"
可以看到,使用了一条setbit demo 7 1
命令之后,demo 的值就从B
就变成了 C
,这是怎么发生的?
setbit key offset value
结合上面的示例,我们来对此命令进行解释。首先我们应该知道:
字符 | 十进制 | 二进制 |
---|---|---|
B | 66 | 01000010 |
C | 67 | 01000011 |
再看指令说明,设置value指定offset处的bit值,那么setbit demo 7 1
就是将字符B
的第7位设置为1,也就是将01000010的最后一个0设为1。因此值变成了01000011,也就是字符C
,这就是字符变化的原因。
如何将C变回去,很简单,将第7位变成0即可:
127.0.0.1:6379> set demo C
OK
127.0.0.1:6379> setbit demo 7 0
(integer) 1
127.0.0.1:6379> get demo
"B"
事实上,bit的取值也只能是0或1。
getbit key offset
弄明白了setbit
,getbit
就很好理解了:取出字符串指定偏移上的bit:
127.0.0.1:6379> set demo B
OK
127.0.0.1:6379> getbit demo 6
(integer) 1
127.0.0.1:6379> getbit demo 7
(integer) 0
字符B
的二进制是01000010。
bitcount key [start end]
127.0.0.1:6379> set demo B
OK
127.0.0.1:6379> bitcount demo
(integer) 2
bit的取值只能是0或者1,如果每一位代表一个对象,那么一个key就可以记录2^32个对象的状态,占用空间 2^32bit = 512Mb。
除此外,数据库中位图索引的实现(#6 )也与此类似。
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.