hayashierMemcachedMemcachedは以下の特徴を持ったインメモリのKVSとなります。シンプルマルチスレッド処理ロジックの半分はサーバで、半分はクライアントサーバ同士では通信は行わず、互いに独立コマンドはO(1)TTLに従った失効と、LRUによるevictionlibeventによるイベント駆動処理なお、合わせてMemcachedのソースコードの各種ファイルの概要についての詳細は以下の記事をご覧ください。–https://hayashier.com/redis-memcached-code-reading/MemcachedのSETコマンド実行時のソースコード中のフローの詳細については、以下の記事をご覧ください。~https://hayashier.com/dive-deep-memcached/レポジトリは以下のURLとなります。15samplefuga2testENDincr/decrは引数で与えた数値の分だけ値を増加/減少させる。IDを添えて実行することで、書き換えられてないことを確認しながら値を設定できる。Compare-and-Swap)の略。13piyo2STOREDMemcachedのflush_allは、TTLを付与するだけなので、サーバーに影響は与えない。Touch)コマンド、gets、touchコマンドはTTLの更新。ASCIIモードでは1.5.3で追加されました。バイナリモードでは1.4.8(1.6からのバックポート)で利用できるようになっています。class毎に決められた大きさをChunkとして分割していきます。classに保存されます。class用にページ(-Iで指定したバイト数)を確保する動作となります。確保したメモリは基本的に解放せずにchunkを再利用する挙動になります。Chunkの様子は、memcachedコマンドの-vvオプション、もしくは-vvvオプションで確認することができます。付属のmemcached-toolを利用することでも確認することができます。Classが変わる毎に、前のクラスの大きさからchunk_size_growth_factorを掛けた大きさとなっていきます。Chunkのサイズがmax_item_sizeの値を超えない最も大きいところまでクラスが用意されることになります。データとして利用できるメモリー量は、Memcached全体として利用できるメモリー(max_cache_memory)と接続に伴うオーバーヘッド(memcached_connections_overhead)を除いた分となり、そちらも考慮されます。Allocation導入前のメモリ確保では、アイテムの保存の度に、mallocとfreeを行うもので、メモリーフラグメンテーションを引き起こしやすいものでした。そのため、フラグメンテーションの対策として、アプリケーションレイヤーでメモリーの管理しながらメモリーを再利用するようになりました。上記より、メリット/デメリットとして以下のことが挙げられます。Allocationで予め用意したスラブのメモリにデータを保存するので、レスポンスに安定感が期待できます。allocationとは別に、より小さな単位でメモリを管理を行うものとなっております。allocatorがデフォルトで使用されるようになっています。Allocatorhttps://www.kernel.org/doc/gorman/html/understand/understand011.htmlLinuxカーネル4.1のSLUBアローケータ(ドラフト)https://kernhack.hatenablog.com/entry/2019/05/10/001425LRUMemcachedには、Redis同様にアイテムの削除はActive/Passiveな方法があり、以下の方法となります。Crawlerただし、メモリーの再利用が間に合わず、メモリー確保の際に不足した場合には、削除対象としてLRUの挙動に従ってevictionする挙動となります。class単位となるため、全体としてみるとLRUの挙動から離れることもあります。MemcachedはTTLの切れたキーをevictionするようにベストエフォートで行われますが、キューの末尾の削除されることもあります。intensiveな状況で48スレッドまででLRUロックの都合上スケールの限界。一度に数百のキーを取り出すと、mutex競合や、不均一なレイテンシー、CPUを多く使用する状況が発生した。最適化として60秒に1回、アイテムをbumpさせ、頻繁にアクセスするアイテムのmutexロックやmutationを避ける工夫がされていました。それ以降サブLRUとしてHOT/WARM/COLDのようにセグメント化されたLRUを使用。各セグメントが自身のmutexロックを持ちます。各アイテムの状態は、以下の2つに分類されます。キーがリクエストされたことがある。1秒以内にアクセスされ、アイテムがはじき出されたか移動するときに取り除かれる各セグメントの状態は、以下の通りとなります。Maintainerが1つのバックグラウンドスレッドとして実行します。新規アイテムが最初に分類される状態。アイテムは強い局所性と短いTTLを持つことが多いので、一度キューの最後まで達すると、WARMでアイテムがbumpされず、アイテムがACTIVEであればWARMへ移動し、INACTIVEであればCOLDに移動する。確率的なキューとして振る舞う。ワークロードをスキャンするバッファとして振る舞う。2度以上アクセスされた場合にこの状態になる。ロックの競合を減らしている状態であればTTLだけ生き残る。キューの末尾まで移動したアイテムがACTIVEであればキューの先頭に移動。INACTIVEなアイテムを含む。HOT/WARMの状態から移動してくる。メモリーがいっぱいのときはevictされる。TEMPセグメントもあります。新規アイテムが分類できる状態。TEMPに入れられたアイテムは指定した時間だけbumpさせないように設定することができる。上記のままでは、アクセスパターンに一貫性がない場合、キューの真ん中の状態のアイテムが失効しているとサイズが特に大きな場合にはスペースが無駄になり、サイジングが難しい。Crawlerというバックグラウンドスレッドにより、非同期にアイテムを一通り確認し、失効しているものはreclaimする。Classが大きいほど、アイテム数が少ないので、すばやくスキャンできる。CrawlerはHOT状態はスキャンする価値がないことを知っていることもある一方で、HOTに大量の短いTTLのキーがあれば、比較的大きなCOLDをスキャンすることを避けている間は、消去することもある。Crawlerは見ない動作をします。アイテムが直接取り出したときにLRUのキューから他のアイテムがdumpされない。一度に数百のキーでも取り出せる。reclaim”モードが発生する。HOTやWARMからアイテムを移動している間、ワーカースレッドがブロックされる。Dummieshttps://work.tinou.com/2011/04/memcached-for-dummies.htmlmemcachedを知り尽くすhttp://gihyo.jp/dev/feature/01/memcachedキー分散Memcachedでは、クラスター内の各ノードはそれぞれ独立しており、互いにレプリケーションといった挙動はしません。キャッシュノード間で、対象のキーが保存されたノードの指定は、クライアント側に依存しています。クライアント側からのキーの分散方法としては、主に以下の2つの方法が考えられます。よりノードを決めます。Hashing円上の0から2^32までの均等な点に対して、各キャッシュノードのハッシュ値を求め、配置します。キーに対しても同様にハッシュ値を求め、キーの保存の際には最も近いサーバのところに保存されます。ノードの追加、削除の際には、そのノードに入れ替えに伴い、アイテムを移動させます。イベント駆動処理Memcachedのイベント駆動処理には、libeventが利用されています。使われており、以下の種類の関数が利用されています。APIを利用する前にはこの関数を実行する必要がある。タイマーイベントの設定。event構造体の準備。現在は、新規コードでは多くは安全に利用するためにはevent_base_setが必要となり推奨されていない。event_new()を使うことが推奨されている。イベント設定オブジェクトの割当て。libraryhttps://libevent.org/Memcachedのマルチスレッド処理POSIXスレッド(pthread)Memcachedではマルチスレッド処理にpthreadが利用されており、以下の関数が使用されています。処理内容デフォルト状態でworkerスレッドの起動数が4つのため、以下のようにスレッドIDが順番に割り当てられていき、workerスレッド間はリクエストをラウンドロビンで割り当てられます。3で実行されることが多いことを確認しています。slab_maintenanceRedisのリクエストのシングルスレッドで処理する性質とは対照的に、Memcachedではリクエストをマルチスレッドで処理を行い、デフォルトでは4つのworkerスレッド(memcached_thread)を起動するようになっています。ワーカースレッドが多すぎてもロックの取り合いで、パフォーマンスが上がるわけではありません。Tableでデータを管理しているが、拡張の際に、assoc_maintenanceスレッドが使用されている。それ以外のスレッドについては後述。memcached.c:8154ロック種類Memcachedではスレッドセーフな実装のために以下のロックを使い分けています。_lru_bump_bufbump_buf_lock以下も参考にしていただけるかと存じます。class間でメモリを移動するバックグラウンドスレッド。以下のコマンドで実行。slab_maintenanceスレッドで実行。class中で、空きchunkが3ページ以上あるときに、ページをグローバルプールに返す。classに再割当てが行われるようになる。evictionがある度にメモリを移動するという非常にアグレッシブな方法。ワークロードのアクセスパターンをよく理解していない限り、こちらを有効にしたままにすることは推奨されない。class間でメモリの再分散させることも可能。有効にしておく必要がある。Listにより、末尾からLRUで追い出される対象。LRUをHOT,WARM,COLDのセグメントに分割して、lru_maintainerがバックグラウンドスレッドで、アイテムをセグメント間で移動させる。COLDがevictionの対象となります。HOT/WARMのセグメントの領域の割合はチューニング可能。lru_crawlerがデフォルトで有効temporary_ttlで4つ目のTEMP領域を作ることも可能。crawlerの問題や負荷を減らす。詳細は以下をご覧ください。classの末尾から先頭に向けてアイテムを確認していき、失効したものがあればメモリを解放します。TTLで長いものと短いものが混在している状況だが滅多にアクセスされない場合に特に有効です。こちらの機能を使用するとレイテンシーやCPU使用量が増加する可能性があります。Crawlerは有効になります。ソースコード中では、スレッド名はitem_crawlerという名前が使われています。ActiveにTTLが切れたアイテムのメモリーを解放することができる。レイテンシーとCPU使用率の増加WatchersMemcachedへ接続し内部で起こっていることの調査に利用できる。以下のようにして有効化する。loggerスレッドで実行されている。アイテムを内部でfetchする度にログ出力。setコマンドでもアイテムの置き換え前にitem_getするので出力する。キャッシュからアイテムがevictionされたときに情報を出力。baseがあり、処理が行われます。Slabという低レイヤーでのメモリー管理とItemという高レイヤーでの管理の層に分けて管理を行い、それらをコネクションを管理する部分を通してこれらを扱います。Memcachedでは処理中、内部で状態遷移の仕組みを使って各状態における処理完了後に別の状態に遷移して条件に応じた処理を行っています。状態遷移Memcachedで利用される状態遷移の各状態は以下のものがあります。conn_listeningconn_new_cmdconn_waitingconn_readconn_parse_cmdconn_writeconn_nreadconn_swallowconn_closingconn_mwriteconn_closedconn_watchconn_max_statehttps://github.com/memcached/memcached/blob/master/memcached.h#L171-L191上記状態は、conn_statesのenumとして、memcached.hで定義されています。処理の流れとしては以下の通りとなります。Threadにコネクションを渡します。Threadのコネクションのキューへと入れます。Thread上でコールバック関数(event_handler)が呼ばれます。event_handler関数からdrive_machine関数が実行され、ここでコネクションにおける状態遷移等を管理しながら、各種コマンドの実行の呼び出し等を行います。Thread上でも複数のコネクションを処理することができます。baseでのイベントループの処理について、リクエストを受け付ける際には、最初にdrive_machine関数が実行し、コネクションの状態(conn_state)がconn_listeningになっています。threadの1つのコネクションキューへタスクの追加を行います。Threadのbaseでの処理ここではGETコマンド処理の例とします。Thread上では、ソケット受付時のreadイベント作成時、コネクションキューからタスクを取り出し後、conn_stateの状態をconn_new_cmdに変更します。その後、コネクションの枯渇を避けるために少しずつ様子を見ながら、conn_stateをconn_waitingへ変更。conn_stateをconn_readへと変更します。conn_stateがconn_readへと変更されたら、ソケットからの読み込みを行い、conn_stateをconn_parse_cmdへと変更します。conn_stateがconn_parse_cmdと変更されたら、入力されたコマンドのパース処理を行い、入力された命令毎に関数の実行を行います。その後、conn_stateがconn_mwriteへ遷移し、クライアントへリクエストされたアイテムを返す準備ができる状態となります。conn_stateがconn_mwriteへ変更されたらsendmsgのシステムコール関数を使ってクライアントへ結果を返します。conn_stateをconn_new_cmdへ変更し、新規コマンドを受け付ける状態となります。SETコマンド処理も類似した内容となります。読み込み完了時にはcomplete_nread関数から(ASCIIモードを利用時には)complete_nread_ascii関数が実行され、ここでout_string関数を通して"STORED"の文字が返される挙動となります。フローリクエスト受付処理TCP/UDP利用時ソケット処理時にはserver_socket関数を通してソケット関数の初期化が実行されます。具体的には以下の流れとなります。Socketを利用する場合は、server_socket_unix関数を通して初期化が実行されます。クライアントとサーバが同一ホスト上にある場合はこちらを利用することで効率よく処理ができます。古いソケットファイルが残っている場合は、unlink関数を実行して削除flag変数の値がゼロ以外の場合は、setsockopt関数を実行して、アドレスをbindで再利用し、定期的なKeep_aliveメッセージを再送信し、送信されていないメッセージがある場合には、ソケットがクローズさせないようにするbind関数listen関数conn_new関数コマンド実行時conn_stateがconn_read時には以下のフローで関数が実行されます。quitconn_stateをconn_closingへ変更O(1)Memcachedのコマンドは計算量がO(1)、すなわちキーの数によらず実行時間が一定になるようにされています。一方で、全キーを操作することが出来ないデメリットもありました(*)。取得することができます。用意されており取得可能ですが、スラブクラスを指定して取得する形となります。部分的な取得(上限2MB)で、かつメモリーをロックする上に取得も重いものとなります。reply/QuietオプションはASCIIコマンドで利用すると、リクエストに対するエラーが適切に表示されないため使うべきではないとされています。mutativeなコマンドでパケットが返ってくるのを待つのを避ける必要がある場面で利用することはできます。バイナリモードでは適切に実装されています。Commandshttps://github.com/memcached/memcached/wiki/CommandsstatsMemcachedでは、サーバ内部の状態を調査するツールとしてstatsコマンドを提供しています。以下コマンドの実行結果の例となります。sizes各アイテムのサイズとそれに対応する数。sizes_enableを実行しておく必要があります。パラメータでtrack_sizesを指定することでも可能です。class中で無駄なメモリー量となります。Unixソケットファイルを指定した際に値が入る。itemsなどで確認可能)と取得数を指定します。cachedumpは指定したスラブクラスの表示件数だけ出力しますが、最大で2MBでのレスポンスの制限があります。https://github.com/memcached/memcached/blob/master/items.c#L596また、実行時間が長く、キャッシュをロックする挙動となります。Class単位でしか取得できない制約もあります。allはサイズ制限もなくキャッシュをロックせずに全キーをリスト化して出力します。process./testappテストコード。0dumpオプションを指定すると以下のようになります。以下に以下のようなコマンドがあります。damemtopmemcached-automovememcached-automove-extstorememcached-initmemcached.sysvstart-memcachedベンチマークベンチマークには、memslap/memaslap/mcperf/memtier_benchmarkなどのものがあります。--key-maximum=100000memslap/memaslapはlibmemcachedで提供されています。libmemcachedを実行後に利用できるようになります。twemperf(mcperf)は以下のコマンドでインストールすることが可能です。installmemtier_benchmarkのインストール方法は以下の記事をご覧ください。内容確認)バイナリプロトコルテキストプロトコルのパース処理の省略による処理の高速化とテキスト形式である脆弱性の問題に対応するものとなっています。24バイトの固定長を利用します。+---------------+---------------+---------------+---------------+ASCIIモードでは、キー長の制限が250バイトでしたが、バイナリモードでは、2^16(=65,536)バイトまで扱えるようになっています。コマンドの種類増加など拡張性も上がっています。