Redis源码分析（二十六）--- slowLog和hyperloglog

rwewqe

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

       slowLog的官方解释:



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

里面定义了一个slowLog entry的结构体:



    /* This structure defines an entry inside the slow log list */  
    /* 慢日志结构体，将会插入到slowLogList,慢日志列表中 */  
    typedef struct slowlogEntry {  
        robj **argv;  
        int argc;  
        //自身的id标识  
        long long id;       /* Unique entry identifier. */  
        //query操作所消耗的时间，单位为nanoseconds  
        long long duration; /* Time spent by the query, in nanoseconds. */  
        //查询发发生的时间  
        time_t time;        /* Unix time at which the query was executed. */  
    } slowlogEntry;  
      
    /* Exported API */  
    void slowlogInit(void); /* slowlog初始化操作 */  
    void slowlogPushEntryIfNeeded(robj **argv, int argc, long long duration); /* slowLogEntry压入列表操作 */  
      
    /* Exported commands */  
    /* 开放给系统使用的命令 */  
    void slowlogCommand(redisClient *c);  

里面定义的方法也非常简单。初始化init方法和插入方法，在服务端的server端，维护了一个slowLog的列表，会按照时间顺序插入超时的查询记录，也就是slowLogEntry记录：



    /* Initialize the slow log. This function should be called a single time
     * at server startup. */  
    /* slowLog的初始化操作 */  
    void slowlogInit(void) {  
        //创建slowLog的List  
        server.slowlog = listCreate();  
        //第一个entry_id声明为0  
        server.slowlog_entry_id = 0;  
        listSetFreeMethod(server.slowlog,slowlogFreeEntry);  
    }  

插入列表的方法:



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

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内存为十亿对象计数“。