【Redisソース分析】Redis怠け者削除(lazy free)の概要
10901 ワード
張仕華
質問です:Redisは単一プロセスの単一スレッドモードですか?
下の図はRedis 5である.0起動後の効果.LWPはスレッドIDであり、NLWPはスレッド数である.5.0のredis serverには4つのスレッド,1つのプライマリスレッド48684,3つのbio(background IO,バックグラウンドioタスク)スレッド,3つのバックグラウンドスレッドがそれぞれ異なるioタスクを実行していることがわかり,1つのkeyを削除する際のioスレッド実行に重点を置いた.
Redisは非同期削除コマンドunlinkを追加し、大きなkeyを削除するときにプライマリスレッドがブロックされることを防止します.その原理はunlinkを実行すると、削除する必要があるデータがチェーンテーブルに掛けられ、専用のスレッドが削除を担当することです.元のdelコマンドはブロックされています.1000万個のデータの集合に対してdelとunlinkをそれぞれ実行することによってその効果を観察した.
大きなコレクションの削除を見てください
まず、スクリプトを使用して1000万要素の集合testsetを生成し、delコマンドを使用して削除します.次のようにします.
上記の実験をやり直し、今回はunlinkで削除してみます.
漸進的な削除を試みる
以下を参照してください.http://antirez.com/news/93
この問題を解決するために,Redis著者のAntirezはまず漸進的な削除によって解決することを考慮した.Redisも、lru eviction、keyの期限切れ、および漸進的なrehashのような漸進的な戦略を多くの場所で使用する.原文は以下の通り.
削除するオブジェクトをチェーンテーブルに配置し、定期的にタスクを実行し、その一部だけを削除します.
これは何か問題がありますか.原文の例を見てみましょう.
削除が速く増加しない場合、上記の例ではメモリが急騰する.(どんな場合にこのようなケースが発生するかはわかりませんが).そこで著者らは、メモリが増加するか減少するかを判断することによって、削除タスクの実行頻度を動的に調整する適応的な削除を設計し始めた.コードの例は以下の通りである.
この方法は、結局、1つのスレッドにおいて、回収が特に頻繁であると、redisのqpsが低下し、qpsは通常の65%にしか達しないため、欠陥がある.
そこでredis著者antirezは非同期スレッド回収を考慮し始めた.
非同期スレッド
共有オブジェクト
非同期スレッドはなぜ共有データが多く共有できないのか,マルチスレッド間で競合が発生する可能性が高い.そのため、パフォーマンスのためには、まず共有データを消滅させなければなりません.
ではredisはどこで共有データを使うのでしょうか
共有方法
以下のコード例は、Redis 2である.8.24.
まずsaddの実行時に下位データがどのように保存されているかを見てみましょう
下層は以下のように保存される(gdbプロセスは以下の通りであり、比較的難解であり、以下の説明を参照).
以下の構造体で説明すると、sadd testset val 1、testset、val 1がどこに保存されているかを見ることができます. 1.まず、すべてのkeyはdict.ht[0]のdictht構造体に保存される.上の構造体から、dicthtのtableはdictEntry 2次ポインタであることがわかります. 2.sadd testset val 1を実行すると、testsetはdictEntryの1つのkeyであり、keyはvoidポインタであり、実際の記憶状況はtestsetがcharタイプ として保存される. 3.testsetがハッシュを通過する後indexが3であると仮定するとdict.ht[0].table[3].keyはtestset,dict.ht[0].table[3].v.valはvoidポインタであり、robjタイプ が実際に格納される. 4.第3のステップのrobjにはptrポインタがあり、dictタイプを指します.dictのうちの1つのentryのkeyは、val を指す別のrobjポインタを指す.
つまり、値を取得するプロセスは次のとおりです.
次に、2つの共有オブジェクトの典型的なシーンを見ます. 1.sunionstoreコマンド コード実装を見てください.
次のコマンドを実行します.
次にtestsetの要素を表示して、その参照カウントが2になったかどうかを確認します.
smembers testset 2.smembersコマンド 要素を返すときは、返すコードに重点を置きます.
robjオブジェクトを直接戻りパラメータとして使用します
また,クライアント転送パラメータもrobjオブジェクトであり,直接値としてオブジェクトに保存される.
共有時に削除する方法
では、共有オブジェクトは単一スレッドの場合、どのように削除されますか?
delコマンドの実装を見てみましょう
delはdictDeleteを呼び出し、最終的に各データ型の独自の構造関数を呼び出す
集合タイプは次の関数を呼び出します.
値のrefcountを1だけ減らすことがわかります
共有データの解決方法
新しいバージョンでは、共有データの解決方法
sunionstoreとsmembersコマンドを使用して、共有をどのように解決するかを見てみましょう.
次のコードはredis 5.0.3バージョンで説明されています.
値を増やしたときはsdsになりました
現在の保存構造は次のとおりです.
クライアントに戻ると、次のようにsdsになります.
効果
効果はどうですか?
まず値をとるときにrobjの間接参照からsdsの直接参照に変わります.
次に共有を減らすとメモリの消費量が増加し、sdsを使用すると、各sdsのメモリ消費量はrobjよりも小さくなります.この修正をantirezがどのように評価するかを見てみましょう.
2つの意味を言いました.1つはメモリの使用がより効率的になったことです.
2つ目は、より少ない間接参照により、redisが以前よりも高速になり、クライアントの出力がより簡潔で高速になることです.
非同期スレッド非同期スレッドの実装は後で詳細に説明する
に質問
1.マルチスレッド間でスタックにメモリを割り当てるときに競合が発生します.しかしantirezはredisがメモリ割り当てに使用する時間が極めて少ないため、このような状況は無視できると述べた.
この問題をどう考えますか.
参照先:https://software.intel.com/zh...
質問です:Redisは単一プロセスの単一スレッドモードですか?
下の図はRedis 5である.0起動後の効果.LWPはスレッドIDであり、NLWPはスレッド数である.5.0のredis serverには4つのスレッド,1つのプライマリスレッド48684,3つのbio(background IO,バックグラウンドioタスク)スレッド,3つのバックグラウンドスレッドがそれぞれ異なるioタスクを実行していることがわかり,1つのkeyを削除する際のioスレッド実行に重点を置いた.
Redisは非同期削除コマンドunlinkを追加し、大きなkeyを削除するときにプライマリスレッドがブロックされることを防止します.その原理はunlinkを実行すると、削除する必要があるデータがチェーンテーブルに掛けられ、専用のスレッドが削除を担当することです.元のdelコマンドはブロックされています.1000万個のデータの集合に対してdelとunlinkをそれぞれ実行することによってその効果を観察した.
大きなコレクションの削除を見てください
まず、スクリプトを使用して1000万要素の集合testsetを生成し、delコマンドを使用して削除します.次のようにします.
127.0.0.1:8888>info// info ：
# Memory
used_memory:857536
used_memory_human:837.44K
127.0.0.1:8888> eval "local i = tonumber(ARGV[1]);local res;math.randomseed(tonumber(ARGV[2]));while (i > 0) do res = redis.call('sadd',KEYS[1],math.random());i = i-1;end" 1 testset 10000000 2
(nil)
(18.51s)// 18.51s
127.0.0.1:8888>info//
# Memory
used_memory:681063080
used_memory_human:649.51M
127.0.0.1:8888> scard testset//
(integer) 9976638 // math.random() ， ， ， 9976638 。
127.0.0.1:8888> sscan testset 0 //
1) "3670016"
2) 1) "0.94438312106969913"
2) "0.55726669754705704"
3) "0.3246220281927949"
4) "0.51470726752407259"
5) "0.33469647464095453"
6) "0.48387842554779648"
7) "0.3680923377946449"
8) "0.34466382877187052"
9) "0.019202849370987551"
10) "0.71412580307299545"
11) "0.12846412375963484"
12) "0.10548432828182557"
127.0.0.1:8888> del testset // del ， 2.76s
(integer) 1
(2.76s)
127.0.0.1:8888>info//
# Memory
used_memory:858568
used_memory_human:838.45K上記の実験をやり直し、今回はunlinkで削除してみます.
127.0.0.1:8888> unlink testset//unlink
(integer) 1
127.0.0.1:8888>info// 。 ， testset 。 ， 1-2s,
# Memory
used_memory:326898224
used_memory_human:311.75M漸進的な削除を試みる
以下を参照してください.http://antirez.com/news/93
この問題を解決するために,Redis著者のAntirezはまず漸進的な削除によって解決することを考慮した.Redisも、lru eviction、keyの期限切れ、および漸進的なrehashのような漸進的な戦略を多くの場所で使用する.原文は以下の通り.
So this was the first thing I tried: create a new timer function, and perform the eviction there. Objects were just queued into a linked list, to be reclaimed slowly and incrementally each time the timer function was called. This requires some trick to work well. For example objects implemented with hash tables were also reclaimed incrementally using the same mechanism used inside Redis SCAN command: taking a cursor inside the dictionary and iterating it to free element after element. This way, in each timer call, we don’t have to free a whole hash table. The cursor will tell us where we left when we re-enter the timer function.削除するオブジェクトをチェーンテーブルに配置し、定期的にタスクを実行し、その一部だけを削除します.
これは何か問題がありますか.原文の例を見てみましょう.
WHILE 1
SADD myset element1 element2 … many many many elements
DEL myset
END削除が速く増加しない場合、上記の例ではメモリが急騰する.(どんな場合にこのようなケースが発生するかはわかりませんが).そこで著者らは、メモリが増加するか減少するかを判断することによって、削除タスクの実行頻度を動的に調整する適応的な削除を設計し始めた.コードの例は以下の通りである.
/* Compute the memory trend, biased towards thinking memory is raising
* for a few calls every time previous and current memory raise. */
// ， ， mem_is_raising 1， 。
// mem_is_raising mem_trend 0.1 , 0.9^22 0.1
// ，
if (prev_mem < mem) mem_trend = 1;
mem_trend *= 0.9; /* Make it slowly forget. */
int mem_is_raising = mem_trend > .1;
//
/* Free a few items. */
size_t workdone = lazyfreeStep(LAZYFREE_STEP_SLOW);
//
/* Adjust this timer call frequency according to the current state. */
if (workdone) {
if (timer_period == 1000) timer_period = 20;
if (mem_is_raising && timer_period > 3)// ，
timer_period--; /* Raise call frequency. */
else if (!mem_is_raising && timer_period < 20)
timer_period++; /* Lower call frequency. *///
} else {
timer_period = 1000; /* 1 HZ */
}この方法は、結局、1つのスレッドにおいて、回収が特に頻繁であると、redisのqpsが低下し、qpsは通常の65%にしか達しないため、欠陥がある.
when the lazy free cycle was very busy, operations per second were reduced to around 65% of the normそこでredis著者antirezは非同期スレッド回収を考慮し始めた.
非同期スレッド
共有オブジェクト
非同期スレッドはなぜ共有データが多く共有できないのか,マルチスレッド間で競合が発生する可能性が高い.そのため、パフォーマンスのためには、まず共有データを消滅させなければなりません.
ではredisはどこで共有データを使うのでしょうか
共有方法
以下のコード例は、Redis 2である.8.24.
まずsaddの実行時に下位データがどのように保存されているかを見てみましょう
sadd testset val1下層は以下のように保存される(gdbプロセスは以下の通りであり、比較的難解であり、以下の説明を参照).
254 set = lookupKeyWrite(c->db,c->argv[1]);
(gdb) n
255 if (set == NULL) {
(gdb) p c->argv[1]
$1 = (robj *) 0x7f58e3ccfcc0
(gdb) p *c->argv[1]
$2 = {type = 0, encoding = 0, lru = 1367521, refcount = 1, ptr = 0x7f58e3ccfcd8}
(gdb) p (char *)c->argv[1].ptr //client argv robj,argv[1] ptr key 'testset'
$4 = 0x7f58e3ccfcd8 "testset"
(gdb) n
254 set = lookupKeyWrite(c->db,c->argv[1]);
(gdb) n
255 if (set == NULL) {
...
(gdb) p (char *)((robj *)((dict *)set.ptr).ht[0].table[3].key).ptr
$37 = 0x7f58e3ccfcb8 "val1" // val1 dict ，dict dictEntry,dictEntry key ， robj,robj 以下の構造体で説明すると、sadd testset val 1、testset、val 1がどこに保存されているかを見ることができます.
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
int refcount;
void *ptr;
} robj;つまり、値を取得するプロセスは次のとおりです.
key -> value_obj -> hash table -> robj -> sds_string次に、2つの共有オブジェクトの典型的なシーンを見ます.
int setTypeAdd(robj *subject, robj *value) {
...
if (subject->encoding == REDIS_ENCODING_HT) {
if (dictAdd(subject->ptr,value,NULL) == DICT_OK) {
incrRefCount(value);// value ，refcount 1， robj, 1
return 1;
}
}
...
}次のコマンドを実行します.
sadd testset1 value2
sunionstore set testset1 testset2 // testset1 testset2 set 次にtestsetの要素を表示して、その参照カウントが2になったかどうかを確認します.
smembers testset
(gdb) p *(robj *)(((dict *)setobj.ptr).ht[0].table[3].key)
$88 = {type = 0, encoding = 0, lru = 1457112, refcount = 2, ptr = 0x7f58e3ccfb68} //refcount 2
(gdb) p (char *)(((robj *)(((dict *)setobj.ptr).ht[0].table[3].key)).ptr)
$89 = 0x7f58e3ccfb68 "val" // val/* Add a Redis Object as a bulk reply */
void addReplyBulk(redisClient *c, robj *obj) {
addReplyBulkLen(c,obj);
addReply(c,obj);
addReply(c,shared.crlf);
}robjオブジェクトを直接戻りパラメータとして使用します
また,クライアント転送パラメータもrobjオブジェクトであり,直接値としてオブジェクトに保存される.
共有時に削除する方法
では、共有オブジェクトは単一スレッドの場合、どのように削除されますか?
delコマンドの実装を見てみましょう
delはdictDeleteを呼び出し、最終的に各データ型の独自の構造関数を呼び出す
dictFreeKey(d, he);
dictFreeVal(d, he);集合タイプは次の関数を呼び出します.
void dictRedisObjectDestructor(void *privdata, void *val)
{
DICT_NOTUSED(privdata);
if (val == NULL) return; /* Values of swapped out keys as set to NULL */
decrRefCount(val);
}値のrefcountを1だけ減らすことがわかります
共有データの解決方法
新しいバージョンでは、共有データの解決方法
sunionstoreとsmembersコマンドを使用して、共有をどのように解決するかを見てみましょう.
次のコードはredis 5.0.3バージョンで説明されています.
void saddCommand(client *c) {
...
for (j = 2; j < c->argc; j++) {
if (setTypeAdd(set,c->argv[j]->ptr)) added++; //sadd c->argv[j]->ptr,
}
...
}
int setTypeAdd(robj *subject, sds value) {//value sds
long long llval;
if (subject->encoding == OBJ_ENCODING_HT) {
dict *ht = subject->ptr;
dictEntry *de = dictAddRaw(ht,value,NULL);
if (de) {
dictSetKey(ht,de,sdsdup(value));
dictSetVal(ht,de,NULL);
return 1;
}
}
return 0;
}値を増やしたときはsdsになりました
現在の保存構造は次のとおりです.
key -> value_obj -> hash table -> sds_stringクライアントに戻ると、次のようにsdsになります.
addReplyBulkCBuffer(c,elesds,sdslen(elesds));
void addReplyBulkCBuffer(client *c, const void *p, size_t len) {
addReplyLongLongWithPrefix(c,len,'$');
addReplyString(c,p,len);
addReply(c,shared.crlf);
}効果
効果はどうですか?
まず値をとるときにrobjの間接参照からsdsの直接参照に変わります.
次に共有を減らすとメモリの消費量が増加し、sdsを使用すると、各sdsのメモリ消費量はrobjよりも小さくなります.この修正をantirezがどのように評価するかを見てみましょう.
The result is that Redis is now more memory efficient since there are no robj structures around in the implementation of the data structures (but they are used in the code paths where there is a lot of sharing going on, for example during the command dispatch and replication).
...
But, the most interesting thing is, Redis is now faster in all the operations I tested so far. Less indirection was a real winner here. It is faster even in unrelated benchmarks just because the client output buffers are now simpler and faster.2つの意味を言いました.1つはメモリの使用がより効率的になったことです.
2つ目は、より少ない間接参照により、redisが以前よりも高速になり、クライアントの出力がより簡潔で高速になることです.
非同期スレッド非同期スレッドの実装は後で詳細に説明する
に質問
1.マルチスレッド間でスタックにメモリを割り当てるときに競合が発生します.しかしantirezはredisがメモリ割り当てに使用する時間が極めて少ないため、このような状況は無視できると述べた.
この問題をどう考えますか.
参照先:https://software.intel.com/zh...