? ? ? ? ? 今天學習的是是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內存為十億對象計數“。
- 前言
- (一)--Redis結構解析
- (二)--結構體分析(1)
- (三)---dict哈希結構
- (四)-- sds字符串
- (五)--- sparkline微線圖
- (六)--- ziplist壓縮列表
- (七)--- zipmap壓縮圖
- (八)--- t_hash哈希轉換
- (九)--- t_list,t_string的分析
- (十)--- testhelp.h小型測試框架和redis-check-aof.c日志檢測
- (十一)--- memtest內存檢測
- (十二)--- redis-check-dump本地數據庫檢測
- (十三)--- redis-benchmark性能測試
- (十四)--- rdb.c本地數據庫操作
- (十五)--- aof-append only file解析
- (十六)--- config配置文件
- (十七)--- multi事務操作
- (十八)--- db.c內存數據庫操作
- (十九)--- replication主從數據復制的實現
- (二十)--- ae事件驅動
- (二十一)--- anet網絡通信的封裝
- (二十二)--- networking網絡協議傳輸
- (二十三)--- CRC循環冗余算法和RAND隨機數算法
- (二十四)--- tool工具類(2)
- (二十五)--- zmalloc內存分配實現
- (二十六)--- slowLog和hyperloglog
- (二十七)--- rio系統I/O的封裝
- (二十八)--- object創建和釋放redisObject對象
- (二十九)--- bio后臺I/O服務的實現
- (三十)--- pubsub發布訂閱模式
- (三十一)--- latency延遲分析處理
- (三十二)--- redis-cli.c客戶端命令行接口的實現(1)
- (三十三)--- redis-cli.c客戶端命令行接口的實現(2)
- (三十四)--- redis.h服務端的實現分析(1)
- (三十五)--- redis.c服務端的實現分析(2)
- (三十六)--- Redis中的11大優秀設計