请选择 进入手机版 | 继续访问电脑版

Redis中国用户组(CRUG)论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
热搜: 活动 交友 discuz
查看: 325|回复: 0

Redis源码分析(二十六)--- slowLog和hyperloglog

[复制链接]
  • TA的每日心情
    开心
    2017-3-20 10:39
  • 签到天数: 90 天

    [LV.6]常住居民II

    358

    主题

    462

    帖子

    3650

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    3650

    最佳新人活跃会员宣传达人突出贡献优秀版主荣誉管理论坛元老

    发表于 2016-4-11 10:04:51 | 显示全部楼层 |阅读模式

    今天学习的是是2个log的文件,2个文件的实现功能都超出我原本理解的意思。开始时我以为就是记录不同的类型的日志,后来才慢慢的明白了额,slowLog记录的是超时的查询记录,而hyperloglog其实跟日志一点关系都没有,好吧,我再一次傻眼了,他其实是一种基数统计算法,应该分开了看,hyper + loglog的计算。好,接下来,我们开始学习一下Redis代码中是如何实现的。

           slowLog的官方解释:

    1. /* Slowlog implements a system that is able to remember the latest N  
    2. * queries that took more than M microseconds to execute.  
    3. *  
    4. * The execution time to reach to be logged in the slow log is set  
    5. * using the 'slowlog-log-slower-than' config directive, that is also  
    6. * readable and writable using the CONFIG SET/GET command.  
    7. *  
    8. * The slow queries log is actually not "logged" in the Redis log file  
    9. * but is accessible thanks to the SLOWLOG command.  
    10. *  
    11. *大致意思就是SlowLog记录的是系统最近N个超过一定时间的查询,就是比较耗时的查询  
    12. * ----------------------------------------------------------------------------
    复制代码

    里面定义了一个slowLog entry的结构体:
    1. /* This structure defines an entry inside the slow log list */  
    2. /* 慢日志结构体,将会插入到slowLogList,慢日志列表中 */  
    3. typedef struct slowlogEntry {  
    4.     robj **argv;  
    5.     int argc;  
    6.     //自身的id标识  
    7.     long long id;       /* Unique entry identifier. */  
    8.     //query操作所消耗的时间,单位为nanoseconds  
    9.     long long duration; /* Time spent by the query, in nanoseconds. */  
    10.     //查询发发生的时间  
    11.     time_t time;        /* Unix time at which the query was executed. */  
    12. } slowlogEntry;  
    13.   
    14. /* Exported API */  
    15. void slowlogInit(void); /* slowlog初始化操作 */  
    16. void slowlogPushEntryIfNeeded(robj **argv, int argc, long long duration); /* slowLogEntry压入列表操作 */  
    17.   
    18. /* Exported commands */  
    19. /* 开放给系统使用的命令 */  
    20. void slowlogCommand(redisClient *c);  
    复制代码

    里面定义的方法也非常简单。初始化init方法和插入方法,在服务端的server端,维护了一个slowLog的列表,会按照时间顺序插入超时的查询记录,也就是slowLogEntry记录:
    1. /* Initialize the slow log. This function should be called a single time
    2. * at server startup. */  
    3. /* slowLog的初始化操作 */  
    4. void slowlogInit(void) {  
    5.     //创建slowLog的List  
    6.     server.slowlog = listCreate();  
    7.     //第一个entry_id声明为0  
    8.     server.slowlog_entry_id = 0;  
    9.     listSetFreeMethod(server.slowlog,slowlogFreeEntry);  
    10. }  
    复制代码

    插入列表的方法:
    1. /* Push a new entry into the slow log.
    2. * This function will make sure to trim the slow log accordingly to the
    3. * configured max length. */  
    4. /* 插入一个entry到slowLog列表中,如果时间超出给定的时间范围时 */  
    5. void slowlogPushEntryIfNeeded(robj **argv, int argc, long long duration) {  
    6.     if (server.slowlog_log_slower_than < 0) return; /* Slowlog disabled */  
    7.     if (duration >= server.slowlog_log_slower_than)  
    8.         //如果entry的duration时间超出slowlog_log_slower_than时间,则添加  
    9.         listAddNodeHead(server.slowlog,slowlogCreateEntry(argv,argc,duration));  
    10.   
    11.     /* Remove old entries if needed. */  
    12.     while (listLength(server.slowlog) > server.slowlog_max_len)  
    13.         //如果列表长度已经超出slowLog的最大值,移除最后一个slowLogEntry  
    14.         listDelNode(server.slowlog,listLast(server.slowlog));  
    15. }  
    复制代码

    slowLog就是这样,非常简单明了,重点学习一下hyperloglog,作为一种基数统计算法,比如统计一篇莎士比亚的文章中,不同单词出现的个数,如果按照平常我们想到的做法,把里面的单词都存到hashset中,求出容量即可,但是当面对的是海量数据的时候,这得占据多大的内存呢,所以就有了后来我们说的“位图法“,位图可以快速、准确地获取一个给定输入的基数。位图的基本思想是使用哈希函数把数据集映射到一个bit位,每个输入元素与bit位是一一对应。这样Hash将没有产生碰撞冲突,并减少需要计算每个元素映射到1个bit的空间。虽然Bit-map大大节省了存储空间,但当统计很高的基数或非常大的不同的数据集,它们仍然有问题。但是比较幸运的是,基数统计作为一个新兴的领域,也已经有了许多开源算法的实现,基数统计算法的思想是用准确率换取空间,准确率可以稍稍差一点点,但是可以大大的缩减占用的空间。下面在网上找了3个比较典型的基数统计算法,这三种技术是:Java HashSet、Linear Probabilistic Counter以及一个Hyper LogLog Counter,我说其中的第二种和第三种。

           Linear Probabilistic Counter线性概率计数器是高效的使用空间,并且允许实现者指定所需的精度水平。该算法在注重空间效率时是很有用的,但你需要能够控制结果的误差。该算法分两步运行:第一步,首先在内存中分配一个初始化为都为0的Bit-map,然后使用哈希函数对输入数据中的每个条目进行hash计算,哈希函数运算的结果是将每条记录(或者是元素)映射到Bit-map的一个Bit位上,该Bit位被置为1;第二步,算法计算空的bit位数量,并使用这个数输入到下面的公式来进行估算:
    n=-m ln Vn
    注意:ln Vn=Loge(Vn) 自然对数
    在公式中,m是 Bit-map的大小,Vn是空bit位和map的大小的比率。需要重点注意的是原始Bit-map的大小,可以远小于预期的最大基数。到底小多少取决于你可以承受误差的大小。因为Bit-map的大小m小于不同元素的总数将会产生碰撞。虽然碰撞可以节省空间,但同时也造成了估算结果出现误差。所以通过控制原始map的大小,我们可以估算碰撞的次数,以致我们将在最终结果中看到误差有多大。

          hyperLogLog提供了比上面效率更高的算法。顾名思义,Hyper LogLog计数器就是估算Nmax为基数的数据集仅需使用loglog(Nmax)+O(1) bits就可以。如线性计数器的Hyper LogLog计数器允许设计人员指定所需的精度值,在Hyper LogLog的情况下,这是通过定义所需的相对标准差和预期要计数的最大基数。大部分计数器通过一个输入数据流M,并应用一个哈希函数设置h(M)来工作。这将产生一个S = h(M) of {0,1}^∞字符串的可观测结果。通过分割哈希输入流成m个子字符串,并对每个子输入流保持m的值可观测 ,这就是相当一个新Hyper LogLog(一个子m就是一个新的Hyper LogLog)。利用额外的观测值的平均值,产生一个计数器,其精度随着m的增长而提高,这只需要对输入集合中的每个元素执行几步操作就可以完成。其结果是,这个计数器可以仅使用1.5 kb的空间计算精度为2%的十亿个不同的数据元素。与执行 HashSet所需的120 兆字节进行比较,这种算法的效率很明显。这就是传说中的”如何仅用1.5KB内存为十亿对象计数“。


    转自:http://blog.csdn.net/androidlushangderen/article/details/40683763
    上一篇:Redis源码分析(二十五)--- zmalloc内存分配实现
    下一篇:Redis源码分析(二十七)--- rio系统I/O的封装


    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    阿里云
    阿里云

    Archiver|手机版|小黑屋|Redis中国用户组 ( 京ICP备15003959号

    GMT+8, 2017-3-28 00:28 , Processed in 0.116292 second(s), 32 queries .

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表