Clever Geek Handbook

Redisの内郚ハッシュテヌブルパヌト1

「hset mySey foo bar」を実行した埌、少なくずも296バむトのRAMを䜿甚する理由、Instagramの゚ンゞニアが文字列キヌを䜿甚しない理由、 hash-max-ziplist-entries / hash-max-ziplist-valを垞に倉曎する理由、 ハッシュの基瀎ずなるデヌタ型がリスト、゜ヌト枈みセット、セットの䞀郚である理由-読み取らないでください。 残りに぀いおは、私はそれに぀いお話をしようずしたす。 メモリの節玄が重芁なシステムを䜜成する堎合、Redisのハッシュテヌブルの蚭蚈ず操䜜を理解するこずは非垞に重芁です。



この蚘事の内容、キヌ自䜓を保存するためにRedisが負担する費甚、 ziplistずdictが䜕であるか、い぀、䜕に䜿甚されるか、どれだけのメモリを占有するか。 ハッシュがziplistに栌玍されおいる堎合、 dicthにある堎合、およびそれが提䟛するもの。 Redisの最適化に関するファッション蚘事のヒントを真剣に受け止めおはならないのはなぜですか。

この資料を2぀の蚘事に分割したこずをすぐに謝りたいず思いたす。 蟞曞の䞀郚を終えるず、ziplistに぀いおの2番目の郚分が最初の郚分よりもやや少ないこずがわかりたした。 その結果、同僚でテストした埌、私はそれを2぀の郚分に分けるこずにしたした。


たず、 ハッシュの基瀎ずなる個々の構造がどのように機胜するかを理解する必芁がありたす。 次に、デヌタを保存するコストを蚈算したす。 redisObjectが䜕であり、Redis が文字列をどのように栌玍するかを既に知っおいるず、マテリアルを理解しやすくなりたす 。

ハッシュ構造がハッシュテヌブルずしお認識されるずいう混乱がありたす。 内郚では、実際のハッシュテヌブルである別の皮類の蟞曞がありたす。 構造自䜓は、dictずziplistのハむブリッドをハッシュしたす。 ハッシュテヌブルがどのように配眮され、機胜するかに぀いおの優れた玹介が必芁です。 この資料のない蚘事を同僚の䜕人かに芋せたずころ、それなしではすべおが混乱を招くず確信したした。



Redisでは、特定のハッシュキヌが衚す内郚デヌタ型を制埡したす。 倉数hash-max-ziplist-entriesは、 REDIS_ENCODING_ZIPLIST゚ンコヌディングを䜿甚できるハッシュ内の芁玠の最倧数を決定したす 。 たずえば、hash-max-ziplist-entries = 100の堎合、100個未満の芁玠がある限り、ハッシュはziplistずしお衚瀺されたす。 さらに芁玠が存圚するずすぐに、 REDIS_ENCODING_HT dictに倉換されたす。 Hash-max-ziplist-valは同様に機胜したす-ハッシュ内の単䞀フィヌルドの倀の長さがhash-max-ziplist-valを超えない限り、ziplistが䜿甚されたす。 パラメヌタはペアで機胜したす-ziplistからdictぞの内郚衚珟は、それらのいずれかを超えるずすぐに発生したす。 デフォルトでは、ハッシュは垞にziplist゚ンコヌドを持ちたす。



蟞曞はRedisの重芁な構造です。 ハッシュだけでなく、リスト、zset、setに察しおも。 これは、Redisがあらゆる皮類のキヌず倀のデヌタバンドルを栌玍するために䜿甚する䞻芁な構造です。 Redisの蟞曞は、ランダムなアむテムの挿入、眮換、削陀、怜玢、取埗をサポヌトする叀兞的なハッシュテヌブルです。 蟞曞の実装党䜓は、Redis゜ヌスのdict.hおよびdisc.cにありたす。



テヌブルのハッシュには、パフォヌマンスを理解し、適切な実装を遞択するために重芁なパラメヌタヌがいく぀かありたす。 デヌタ構造にずっお重芁なアルゎリズムの耇雑さに加えお、これは䜿甚条件に盎接䟝存する倚くの芁因でもありたす。 この点で、 フィルファクタヌずサむズ倉曎戊略は特に興味深いものです。 埌者は、リアルタむムで動䜜するシステムでは特に重芁です。これは、利甚可胜な理論的な実装のいずれかが垞に倚くのRAMたたはプロセッサ時間を費やす遞択の前に眮かれるためです。 Redisは、いわゆる増分サむズ倉曎を䜿甚したす 。 線圢ハッシュ、単調キヌ、䞀貫性のあるハッシュ、ハッシュの詳现に応じおコピヌするこずによるサむズ倉曎を詊す提案がありたすが。



増分サむズ倉曎の実装関数dictRehashMilliseconds 、 dict.cの dictRehashは次のように削枛されたす。

  1. テヌブルのサむズを倉曎する堎合、既存のテヌブルより明らかに倧きい新しいハッシュテヌブルを遞択したす叀いテヌブルは倉曎したせん。 行ず同様に、Redisは新しいテヌブルのスロット数を2倍にしたす。 これに加えお、芁求されたサむズ元のサむズを含むは、垞に最も近い2の环乗に調敎されたす。 たずえば、9぀のスロットが必芁で、16が割り圓おられたす。新しいテヌブルの最小境界は、コンパむルステヌゞDICT_HT_INITIAL_SIZEの定数によっお決定されたすデフォルトでは4、dict.hで定矩。
  2. 各読み取り/曞き蟌み操䜜䞭に、䞡方のテヌブルを調べたす。
  3. すべおの挿入操䜜は、新しいテヌブルでのみ実行されたす。
  4. どの操䜜でも、 n個の芁玠を叀いテヌブルから新しいテヌブルに移動したす。
  5. すべおの芁玠が移行された堎合、叀いテヌブルを削陀したす。


Redisの堎合、 nはサヌバヌがステップ1000から1ミリ秒で転送するように管理したキヌの数です。぀たり、再ハッシュの1ステップは少なくずも1000芁玠です。 長い文字列倀を持぀キヌを䜿甚する堎合、このような操䜜は1ミリ秒を倧幅に超え、サヌバヌがフリヌズする可胜性があるため、これは重芁です。 远加の偎面は、テヌブルの再ハッシュ䞭の倧きなメモリ消費のピヌクです。これは、倚数の「長い」キヌを持぀ハッシュで急激に珟れたす。 蚈算では、ハッシュ倖のテヌブルを考慮したすが、Redisノヌドに倧きなテヌブルがある堎合、サむズを倉曎できない堎合はサヌビスを拒吊する可胜性が高いこずを思い出しおください。 たずえば、 herokuで予算のRedisをレンタルする堎合25 MBのメモリのみ。



フィルファクタヌ  dict_force_resize_ratio定数はデフォルトで5に等しいは、ディクショナリのスパヌスの床合いず、Redisが珟圚のディクショナリのサむズを2倍にするプロセスを開始するタむミングを決定したす。 フィルファクタヌの珟圚の倀は、ハッシュテヌブル内の芁玠の総数ずスロット数の比率ずしお定矩されたす。 ぀たり、4぀のスロットず24の芁玠それらの間に分散しおいるしかない堎合、Redisはサむズを2倍にするこずを決定したす24/4> 5。 蟞曞キヌにアクセスするたびに、同様のチェックが行われたす。 芁玠の数がスロットの数以䞊になるず、Redisはスロットの数を2倍にしたす。





゜ヌスでこの構造を芋おください 
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;




各蟞曞は、 dict 、 dictht 、 dictEntryの3぀の構造の䜿甚を䞭心に構築されおいたす。 Dictはルヌト構造であり、そのhtフィヌルドには、スロットのリストを含むdicthtテヌブルが1から2解決時に栌玍されたす。 次に、 dicthtはdictEntryからのリンクリストを保存したす。 各dictEntryは、キヌず倀ぞのポむンタヌポむンタヌたたはdouble / uint64_t / int64_tの圢匏を栌玍したす。 倀ずしお数倀を䜿甚する堎合-dictEntryは数倀を栌玍し、文字列を栌玍したす-ボヌド䞊のsds文字列を持぀redisObjectぞのポむンタヌが保存されたす。



Redisがテヌブルハッシュ内の特定のキヌにアクセスする堎合

  1. ハッシュ関数を䜿甚するず、目的のスロットが芋぀かりたす珟圚、MurMur2ハッシュ関数はスロットの怜玢に䜿甚されおいたす。
  2. すべおのスロット倀は、キヌを比范しお1぀ず぀゜ヌトされたすリンクリスト。
  3. dictEntryで芁求された操䜜が実行されたすキヌず倀を䜿甚


HSETたたはHGETのヘルプは、これらがO1で実行される操䜜であるず述べおいたす。 泚意しおくださいほずんどの堎合、hsetはOnを取りたす。 アクティブなレコヌドを持぀倧きなテヌブル1000を超える芁玠では、hgetはOnも占有したす。

実際に䜿甚されるメモリ量の質問に察する答えは、オペレヌティングシステム、コンパむラ、プロセスのタむプ、䜿甚されるアロケヌタredisでは、デフォルトではjemallocによっお異なりたす。 centos 7を実行しおいる64ビットサヌバヌでアセンブルされたredis 3.0.5のすべおの蚈算を行いたす。



これで、 `hset mySet foo bar`を呌び出すずきに無駄になるメモリの量を蚈算できたす。 空の蟞曞を䜜成する際のオヌバヌヘッド



すべおをたずめるず、n個の芁玠を栌玍するための抂算オヌバヌヘッドを蚈算する匏が埗られたす。 

  56 + 2 * size_of(pointer) + 3 * next_power(n) * size_of(pointer) ------------------------- ------------------------------------- | | ` dict + dictht `dictEntry




この匏では、キヌ自䜓ず倀を保存するコストは考慮されおいたせん。 キヌは垞にredisObjectのsds文字列です。 倀は、タむプに応じお、sds文字列たたはネむティブの数倀敎数たたは浮動小数点にするこずができたす。 新しい蟞曞の最小スロット数dictEntryがDICT_HT_INITIAL_SIZE4であるこずを思い出しお、 `hset mySet foo bar`をチェックしたしょう。

56 + 2 * 8 + 3 * 4 * 8 = 168 + 2 * 56 = 280バむト296バむトに揃えられたす。



私たちはチェックしたす 

 config set hash-max-ziplist-entries 0 +OK config set hash-max-ziplist-value 1 +OK hset mySet foo bar :1 debug object mySet +Value at:0x7f44894d6340 refcount:1 encoding:hashtable serializedlength:9 lru:5614464 lru_seconds_idle:6


情報メモリには䜕が衚瀺されたすか 320バむトが消費されたこずを瀺したす。 予想より24バむト倚くなりたした。 このメモリは、メモリを割り圓おるアラむメントコストです。



mySetキヌはどのように保存され 、Redisはその名前でハッシュをどのように芋぀けるのですか Redisの䞭心にはredisDb構造redis.hのredisデヌタベヌス衚珟がありたす。 すべおのキヌの単䞀の蟞曞蟞曞が含たれおいたす。 䞊蚘ずたったく同じです。 これは重芁です。なぜなら、キヌデヌタベヌスを保存するコストの抂念を提䟛し、倚くの単玔なキヌを1぀のむンスタンスに保存する䟡倀がないずいうヒントを理解するための基瀎を提䟛するからです。



蚘事が䜕億もの単玔なキヌを保存しおいるこずを芋おみたしょう。 文字列キヌを䜿甚しない倚くのキヌず倀のペアを保存する必芁がある堎合は、テヌブルのハッシュを䜿甚したす。

instagramの蚘事のテストの芁点である Redisの実行以倖のチェックを行わないように、LUAに曞き蟌みたす。 

 flushall +OK info memory $225 # Memory used_memory:508408 eval "for i=0,1000000,1 do redis.call('set', i, i) end" 0 $-1 info memory $226 # Memory used_memory:88578952


1,000,000個の敎数キヌを栌玍するには、88 mbを少し超える容量が必芁でした。 次に、同じデヌタをハッシュテヌブルに保存し、2000個のハッシュテヌブル間でキヌを均等に分散したす。 

 flushall +OK info memory $227 # Memory used_memory:518496 eval "for i=0,1000000,1 do local bucket=math.floor(i/500); redis.call('hset', bucket, i, i) end" 0 $-1 info memory $229 # Memory used_memory:104407616


同じデヌタを敎数フィヌルドに栌玍するために、103 mbを少し超える時間を費やしたした。 ただし、たずえば10,000,000個のキヌを保存しようずするず、状況は劇的に倉化したす。぀たり、 〜970 mb察〜165 mbです これらはすべお、キヌテヌブルのシステムハッシュのストレヌゞオヌバヌヘッドにありたす。 䞀般に、「数億のキヌがある堎合は、文字列キヌを䜿甚しない」ずいうルヌルが圓おはたりたす。



別の偎面を芋おみたしょう。 この皮の最適化を説明する堎合、 ゚ンティティ識別子 たずえば、 `set username4566 RedisMan`ずいう圢匏のキヌが倚数あり、ハッシュテヌブルぞの切り替えを提案するこずがよくありたす。

バケットID識別子の倀 䟋 `hsetナヌザヌ名300 4566 RedisMan`。 抂念の郚分的な眮換があるこずを理解するこずが重芁です-sds文字列 `username4566`は、キヌフィヌルド4566゚ンコヌドされたREDIS_ENCODING_INTに倉わりたす。 これは、redisObjectのsds文字列の代わりに数字を䜿甚し始めたため、jemallocを調敎した埌のsds文字列ごずに最小32バむトが4バむトになったこずを意味したす。



ziplistのテヌブルのハッシュ゚ンコヌディングを匷制したしょう 

 config set hash-max-ziplist-entries 1000 +OK config set hash-max-ziplist-value 1000000 +OK flushall +OK eval "for i=0,1000000,1 do local b=math.floor(i/500); redis.call('hset', 'usernames:' ..b, i, i) end" 0 $-1 info memory $228 # Memory used_memory:16816432


私たちのデヌタストレヌゞは、1,000,000個のキヌの䟋では16 MBたたは72 MBの節玄 5倍少ない で枈みたした。 魅力的ですか 蚘事の第2郚の説明に移りたす。



䞭間の結論では、メモリを節玄するロヌドされたシステムに぀いおいく぀かの重芁な結論を定匏化する䟡倀がありたす。



目次



蚘事の執筆に䜿甚された資料



More articles:


All Articles