3万語に及ぶ記事: サーバー開発と設計のためのアルゴリズム集

[[442986]]

孫子はこう言った。「行軍と戦闘の最善の方法は戦略を使うこと、次に良いのは敵の同盟を攻撃すること、次に良いのは敵の兵士を攻撃すること、そして最悪なのは敵の都市を攻撃すること。」行軍と戦争の最善の方法は戦略を使うことであり、最悪の方法は敵と残忍な戦いをすることである。同様に、プログラミングでは、問題を解決する方法が数多くあります。論理的な直接的な戦いに巻き込まれるのは良くありません。優れた合理的なアルゴリズムを使用することが、「敵の計画を潰す」最善の方法です。

アルゴリズムのアイデアの本質は、深く研究し、注意深く評価する価値があります。このハンドブックでは、サーバーの開発と設計プロセスでよく使用されるアルゴリズムをまとめ、簡潔なテキストと図でイデオロギーの原則を説明して図示し、すべての人に何らかの考えとインスピレーションをもたらすことを目指しています。

マインドマップ

1. スケジューリングアルゴリズム

サーバーロジックの開発と設計では、スケジューリング アルゴリズムがいたるところで見られます。リソースのスケジューリング、要求の割り当て、負荷分散戦略などはすべて、スケジューリング アルゴリズムに関連しています。スケジューリング アルゴリズムに良いものも悪いものもありません。ビジネス シナリオに最も適したものが最良です。

1.1. 投票

ポーリングは非常にシンプルで、よく使用されるスケジューリング アルゴリズムです。ポーリングでは、最初のノードから順に各サービス ノードに要求を配布し、次に最後のノードに要求を配布して、次のサイクルを再開します。最終的に、すべてのリクエストは各ノードに均等に分散されます。各リクエストの消費が同じであると仮定すると、ラウンドロビン スケジューリングは最もバランスの取れたスケジューリング (負荷分散) アルゴリズムです。

1.2. 加重ラウンドロビン

サービスノードのパフォーマンス構成が異なり、処理能力が異なる場合もあります。この場合、ノードの処理能力の強さに応じて異なる重み値を設定し、重み付けラウンドロビン方式を使用してスケジューリングを行うことができます。

加重ラウンドロビンは次のように説明できます。

スケジューリング ノードは、すべてのサービス ノードの現在の重み値を記録し、それらを対応する構成値に初期化します。

リクエストをスケジュールする必要がある場合、現在の重みが最も高いノードが毎回選択され、選択されたノードの重みが 1 つ減ります。

すべてのノードの重みがゼロの場合、初期化時に構成された重みにリセットされます。

最終的に、すべてのリクエストは各ノードの重みに応じてサービス ノードに分散されます。 3 つのサービス ノード {a,b,c} があり、それぞれの重みが {2,3,4} であるとします。この場合、要求の割り当て順序は、以下に示すように {c,b,c,a,b,c,a,b,c} になります。

リクエストシーケンス番号 現在の重み 選択されたノード 調整された重み 1{2,3,4}c{2,3,3}2{2,3,3}b{2,2,3}3{2,2,3}c{2,2,2}4{2,2,2}a{1,2,2}5{1,2,2}b{1,1,2}6{1,1,2}c{1,1,1}7{1,1,1}a{0,1,1}8{0,1,1}b{0,0,1}9{0,0,1}c{0,0,0}

1.3. スムーズな重み付けポーリング

重み付けポーリング アルゴリズムでは、サービス ノードが短期間に集中的に呼び出される可能性が高く、瞬間的な圧力が過剰になります。重みの高いノードが最初に選択され、重みの数に達するまで次のノードは選択されません。要求は同じノードに連続的に割り当てられます。たとえば、3 つのサービス ノード {a、b、c} があり、重み構成がそれぞれ {5、1、1} ​​であると仮定すると、重み付けポーリング スケジューリング要求の割り当て順序は {a、a、a、a、a、b、c} になります。ノード a には、連続する複数の要求が割り当てられていることは明らかです。

この問題に対処するために、スムーズ重み付けポーリングは重みベースのスムーズポーリング アルゴリズムを実装します。いわゆるスムーズさとは、一定期間内にサービス ノードが選択される回数の分布が重みと一致するだけでなく、スケジューリング アルゴリズムによってノードがより均等に選択され、一定期間内に重みの高いサービス ノードのみを選択することに集中しないことを意味します。

平滑化重みラウンドロビン アルゴリズムは次のように記述できます。

スケジューリング ノードは、すべてのサービス ノードの現在の重み値を記録し、それらを対応する構成値に初期化します。

リクエストをスケジュールする必要がある場合、そのたびに各ノードの現在の重み値がそのノード自体に設定されている重み値に追加され、現在の重み値が最も高いノードが選択されて割り当てられます。同時に、選択されたノードの重み値が、すべてのノードの元の重み値の合計から減算されます。

すべてのノードの重みがゼロの場合、初期化時に構成された重みにリセットされます。

3 つのサービス ノード {a、b、c} があり、それらの重みがそれぞれ {5、1、1} ​​であると仮定すると、スムーズ ウェイト ポーリングの各ラウンドの割り当てプロセスは次の表に示されます。

最終的な要求割り当て順序は { a, a, b, a, c, a, a} となり、通常の重み付けポーリング アルゴリズムよりもスムーズになります。

1.4. ランダム

ランダムとは、各リクエストがサービス ノードにランダムに割り当てられることを意味します。ランダムの利点は、完全にステートレスなスケジューリングであり、スケジューリング ノードが過去のリクエスト割り当てに関するデータを記録する必要がないことです。理論的には、リクエストの数が十分に多い場合、ランダム アルゴリズムは完全にバランスのとれた負荷分散スケジューリング アルゴリズムに近づきます。

1.5. 加重ランダム

加重ラウンドロビンと同様に、加重ランダムは、サービスノードの処理能力に応じて異なる加重値の設定をサポートします。リクエストをスケジュールする必要がある場合、ノードの加重値に応じて、毎回加重ランダム割り当てが実行されます。サービスノードの加重が大きいほど、ランダム選択の確率が高くなります。最終的に、各サービス ノードに割り当てられるすべてのリクエストの数は、ノード構成の重み値に比例します。

1.6. 最小負荷

実際のアプリケーションでは、各リクエストは異種である可能性が高く、リクエストごとに消費されるサーバー リソースの量が異なります。ポーリング方式を使用する場合でも、ランダム方式を使用する場合でも、完全な負荷分散を正確に実現できない可能性があります。最小負荷アルゴリズムは、各サービス ノードの現在の実際の負荷容量に基づいて要求を分散し、現在の負荷が最も小さいノードが優先されます。

最小負荷アルゴリズムは次のように説明できます。

サービス ノードは定期的に負荷状況をスケジューリング ノードに報告し、スケジューリング ノードはすべてのサービス ノードの現在の負荷値を更新して記録します。

スケジュールする必要があるリクエストがある場合、その都度、現在の負荷が最も小さい（負荷余剰が最も大きい）サービス ノードが選択されます。

負荷ステータスでは、ノードで処理されているリクエストの数、サーバーの CPU とメモリの使用状況、過去のリクエストの応答遅延などのデータをカウントし、これらのデータに基づいて合理的な計算式を使用して負荷スコアを計算できます。

1.7. 2回のランダム選択戦略

最小負荷アルゴリズムは、リクエストが異種である場合に、より優れたバランスを実現できます。ただし、一般的に、サービス ノードの負荷データは一定の遅延がある一定の間隔でスケジューリング ノードに同期されます。遅延した負荷データをスケジューリングに使用すると、「ハーディング」動作が発生し、その時点で負荷が低いノードに要求が一括して送信され、次回負荷データが同期的に更新されたときに、そのノードがより高い位置にある可能性があり、要求が割り当てられなくなります。次回は、より多くのリクエストが低負荷ノードに割り当てられ、サーバーはこのビジーとアイドルのサイクルのままになり、サーバーの安定性に悪影響を及ぼします。

この状況に対処するために、2 つのランダム選択戦略アルゴリズムには、次のようにいくつかの改善が加えられました。

サービス ノードは定期的に負荷状況をスケジューリング ノードに報告し、スケジューリング ノードはすべてのサービス ノードの現在の負荷値を更新して記録します。

利用可能なすべてのノードのリストから 2 つのランダム選択操作を実行して、2 つのノードを取得します。

2 つのノードの負荷状況を比較し、負荷が低いノードをスケジュール ノードとして選択します。

2 回のランダム選択戦略は、ランダム アルゴリズムと最小負荷アルゴリズムの利点を組み合わせ、負荷情報を使用してノードを選択しながら、起こり得る「群集行動」を回避します。

1.8. 一貫性のあるハッシュ

順序を維持し、キャッシュを最大限に活用するために、通常、同じリクエスト キーを持つリクエストが常に同じサービス ノードに割り当てられ、リクエストの一貫性が維持されることが望まれます。そのために、一貫性のあるハッシュ スケジューリング メソッドが用意されています。

コンシステント ハッシュ アルゴリズムに関しては、著者は km に「分散システムにおけるコンシステント ハッシュ スキームの適用の比較」という特別記事を掲載しており、その長所と短所、比較データを詳細に紹介して比較しています。興味のある学生はぜひ読んでみてください。

1.8.1. セグメンテーション

最も単純な一貫性のあるハッシュ方式はセグメンテーションです。つまり、事前にリソースセグメントを計画し、リクエストのキー値マッピングに従って対応するセグメントを見つけます。たとえば、構成を通じて、ID [1-10000] のリクエストはサービスノード 1 にマッピングされ、ID [10001-20000] のリクエストはノード 2 にマッピングされます。ただし、この方法には大きなアプリケーション制限があり、バランスと安定性の点で理想的ではありません。実際のビジネスアプリケーションでは基本的に使用されません。

1.8.2. リングカット法

リングカット法を実装する方法は多数ありますが、原理は似ています。リングカット方式では、N 個のサービス ノードのアドレスを N 個の整数値のグループにハッシュします。整数のグループはサービス ノードのすべての仮想ノードであり、すべての仮想ノードはリング上に分散されます。

要求割り当てプロセス中に、指定されたオブジェクト キーも整数値にハッシュされ、その整数値より大きい値を持つ最初の仮想ノードがリング上で検索されます。仮想ノードに対応する実際のノードは、オブジェクトをマップする必要があるサービス ノードです。

下の図に示すように、オブジェクト K1 はノード 2 にマップされ、オブジェクト K2 はノード 3 にマップされます。

リングカット法は実装がやや複雑で、時間の計算量は O(log(vn)) です (ここで、n はサービスノードの数、v は各ノードが所有する仮想ノードの数)。単調性は良好ですが、バランスと安定性は主に仮想ノードの数と仮想ノードの生成ルールに依存します。たとえば、ketama ハッシュ リングカット法では、サービスノードの IP とポートで構成される文字列の MD5 値を使用して、160 グループの仮想ノードを生成します。

1.8.3. 二次係数

モジュロ ハッシュ マッピングは、単純な一貫性のあるハッシュ方式ですが、単純な 1 回限りのモジュロ ハッシュは単調性が悪く、障害回復には非常に不向きです。サービス ノードが利用できなくなると、ほとんどの要求が新しいノードに再割り当てされ、キャッシュの大規模な移行が発生します。そのため、2 回限りのモジュロ一貫性のあるハッシュ方式があります。

二次モジュロ アルゴリズムとは、スケジューリング ノードが 2 つのサービス ノード テーブル (ルーズ テーブル (すべてのノード テーブル) とコンパクト テーブル (使用可能なノード テーブル)) を維持することを意味します。要求割り当てプロセス中、最初にルーズ テーブルがモジュロ演算されます。結果のノードが使用可能な場合は、それが直接選択されます。結果のノードが使用できなくなった場合は、コンパクト テーブルで 2 回目のモジュロ演算が実行され、最終ノードが取得されます。以下のように表示されます。

二次モジュロアルゴリズムは実装が簡単で、時間計算量は O(1) であり、単調性が高く、縮小やノード障害を適切に処理できます。バランスと安定性も比較的良好ですが、これは主にオブジェクト キーの分布が十分にハッシュされているかどうかによって決まります (そうでない場合は、ハッシュ関数のレイヤーを追加してキーを分割することもできます)。

1.8.4. 最高ランダム重み

最高ランダム重みアルゴリズムは、リクエストキーとノードIDをパラメータとしてハッシュラウンド（MurmurHashアルゴリズムなど）を実行し、比較のためにすべてのノードの重み値を取得し、最終的に最大重み値に対応するノードをターゲットマッピングノードとして取得します。これは次の式で表すことができます。

ハッシュ操作は、各オブジェクトのランダムな値をランダムに比較して選択を行う、前述の通常のランダム スケジューリング方法と同様に、一貫性を維持するための疑似ランダムな方法と考えることもできます。

この方法は O(n) の時間計算量を必要としますが、その代わりに非常に優れた単調性とバランスを備えています。ノード数が変化しても、オブジェクトの最大重み値が変更されノードにかかった場合にのみ影響を受けます。つまり、変更されたノード上のオブジェクトの再マッピングにのみ影響します。したがって、容量の拡張、容量の削減、ノードの障害に関係なく、オブジェクトを最低コストで転送できます。この方法は、ノード数が少なく、単調性に対する要件が非常に高いシナリオで使用できます。

ジャンプ一貫性ハッシュ

ジャンプ コンシステント ハッシュは、非常に単純なジャンプ アルゴリズムを使用して、指定されたオブジェクト キーに対してオブジェクトがマップされるサービス ノードを計算します。アルゴリズムは次のとおりです。

 int JumpConsistentHash(unsigned long long key , int num_buckets)
 {
    長い長い b = -1、j = 0;
    (j < num_buckets) の間 {
        b = j;
キー=キー* 2862933555777941757ULL + 1;
        j = (b + 1) * ( double (1LL << 31) / double (( key >> 33) + 1));
    }
 bを返します。
 }

このアルゴリズムは一見理解するのが難しいように思えるかもしれませんが、実際には次のアルゴリズムのバリエーションであり、ランダム関数を線形合同法で変換するだけです。

 int ch( int  キー、 int num_buckets) {
    ランダムシード(キー)
 int b = -1; // 前回のジャンプ前のバケット番号
int j = 0; //現在のジャンプの前のバケット番号
    while(j < num_buckets){
        b = j;
ダブルr = random.next () ; // 0<r<1.0
        j = floor( (b+1) / r);
    }
 bを返します。
 }

これは、ランダム性によってバランスを確保する疑似ランダム方式でもあります。ここでのランダム関数で使用されるシードは、各リクエストのキー値であるため、一貫性が確保されます。最高のランダム重みとの違いは、ここでのランダム性はすべてのノードに対して 1 回実行される必要はなく、一部のノードの比較はランダム値によってスキップされる点です。

ジャンプ一貫性ハッシュは実装が簡単で、メモリを消費せず、時間の計算量は O(log(n)) です。拡張と縮小の単調性という点では、バランスが非常に高く、パフォーマンスも良好です。ただし、中間ノードに障害が発生した場合、理想的には障害が発生したノードを最後のノードと交換し、障害が発生したノードと最後のノードの両方のオブジェクトを転送する必要があります。 ###1.8.6. まとめ

他にも多くの種類の一貫性ハッシュ方式があり、通常はさまざまなハッシュ関数と組み合わせて実装されます。上記の方法には、使いやすさ、単調性の向上、バランスの向上などを目的として、二次ジャンプ一貫性ハッシュ法などのいくつかの変更も行われています。最小負荷方式を組み合わせたバリエーションもあります。たとえば、制限負荷コンシステントハッシュは、現在の負荷状況に基づいて、すべてのノードの最大負荷を制限します。コンシステントハッシュでハッシュをマッピングする場合、最大負荷制限に達したノードはスキップされます。実際のアプリケーションでは、ビジネス状況に応じて、より適切な調整と組み合わせを行うことができます。

2. 復元なしのランダムサンプリングアルゴリズム

非置換ランダムサンプリングとは、n 個のデータから m 個の重複しないデータを抽出することを意味します。非置換ランダムサンプリングアルゴリズムに関しては、著者は km で特別な記事を公開しており、さまざまなランダムサンプリングアルゴリズムの原理とプロセス、およびそれらの長所と短所と適用範囲を詳細に説明して実装しています。興味のある学生は読んでみてください。

2.1. クヌースシャッフルサンプリング

非置換ランダムサンプリングは、シャッフルアルゴリズムを使用してシーケンスをランダムに配置し、最初の m 個のシーケンスをサンプリング結果として選択するシャッフルアルゴリズムプロセスと見なすことができます。

Knuth シャッフル アルゴリズムは、Fisher-Yates シャッフル アルゴリズムの改良版です。削除操作を位置交換に置き換え、削除された各数字を、削除されていない最後の数字 (または削除されていない最初の数字) と交換します。

Knuth のシャッフル アルゴリズムは次のように記述できます。

1 から n までの数字のランダムな順列を生成します (配列のインデックスは 1 から始まります)

iが1からn-1までの場合、doj ← ランダムな整数値 i ≤ j < n a[j]とa[i]を入れ替える

Knuth シャッフル アルゴリズムを使用したランダム サンプリング方法は、Knuth シャッフル ランダム サンプリング アルゴリズムと呼ばれます。ランダム サンプリングでは m 個のシーケンスの抽出のみが必要なので、シャッフル プロセスでは最初の m 個のデータのみをシャッフルする必要があります。

2.2. プレースホルダーシャッフルランダムサンプリング

Knuth シャッフル アルゴリズムはインプレース シャッフルです。つまり、元の配列を直接シャッフルします。元の配列のすべての要素は保持されますが、要素間の順序は破壊されます。同じ元の配列を複数回サンプリングするという要件を満たすために、元の配列が読み取り専用 (グローバル構成テーブルなど) であり、1 回のサンプリングで破壊されないことを期待する場合があります。Knuth サンプリング アルゴリズムを使用する場合は、元の配列を最初にコピーする必要がありますが、これは明らかに最善のアプローチではありません。より良い方法は、Knuth シャッフル アルゴリズムに基づいて元の配列を交換するのではなく、追加のマップを使用して要素間の交換関係を記録することです。これをプレースホルダー シャッフル アルゴリズムと呼びます。

プレースホルダー シャッフル アルゴリズムのプロセスは次のように示されます。

最終的にシャッフルの結果は 3、5、2、4、1 になります。

プレースホルダーシャッフルアルゴリズムを使用して実装されたランダムサンプリング方法は、プレースホルダーシャッフルランダムサンプリングと呼ばれます。同様に、最初の m 個のデータのみを抽出できます。このアルゴリズムは、一時的なスペースを追加するだけで、元の配列に変更を加えません。

2.3. サンプリング手法の選択 サンプリング

シャッフル アルゴリズムは、事前に初期化されたデータ リストをシャッフルするため、データ リスト全体をメモリにキャッシュする必要があります。データの総量 n が大きく、単一レコードのデータも大きい場合、すべてのデータ レコードをメモリにキャッシュするのは非常に面倒です。事前にデータ リストの完全なキャッシュを必要としないサンプリング テクノロジ アルゴリズムが選択され、ストリーミング処理がサポートされます。

サンプリング技術アルゴリズムは次のように記述できます。

• 1からnまでの乱数Uを生成する
• U ≥ mの場合はステップ4へ進む
• このレコードをサンプルとして選択し、m から 1 を引いた値、n から 1 を引いた値にします。 m>0の場合はステップ1にジャンプし、それ以外の場合はサンプリングが完了してアルゴリズムが終了する。
• このレコードをスキップし、サンプルとして選択せず、n から 1 を引いてステップ 1 にジャンプします。

サンプリング技術を選択するアルゴリズムのプロセスは次のように示されます。

最終的に、サンプリング結果は 2.5 になります。

選択サンプリング技術アルゴリズムによって選択される各数字の確率は であることが証明できます。

サンプリング技術アルゴリズムでは、データ ストリーム全体をメモリにキャッシュする必要はありませんが、データの合計サイズ、つまり値 n を事前に正確に把握する必要があります。出力順序と入力順序を変更せずに維持でき、単一の要素が描画されるかどうかを事前に知ることができるという利点があります。

2.4. 貯留層サンプリング

多くの場合、データの総量 n はまだわかりません。前述の選択的サンプリング アルゴリズムでは、最初に n 値をカウントし、次にサンプリングを実行するために、データを 2 回スキャンする必要があります。これは、ストリーム処理シナリオでは依然として大きな制限があります。

Alan G. Waterman は、データの総量 n を事前に知らなくてもストリーム処理シナリオをサポートできる、Reservoir Sampling と呼ばれるアルゴリズムを提案しました。

貯留層サンプリングアルゴリズムは次のように記述できます。

• データカーソルi←0、i≤mのデータをすぐにリザーバに入れ、プール[i]←iを設定する
• 1からiまでの乱数jを生成する
• j>mの場合はステップ5へ進む
• このレコードをサンプルとして選択し、元のリザーバーのプール[j]のデータを削除し、プール[j]をiに設定する
• カーソルiは1ずつ増加します。iが

貯留層サンプリング アルゴリズムのプロセスは次のように示されます。

最終的に、サンプリング結果は 1.5 になります。

各データが選択されてリザーバーに残る確率は、次の式で証明できます。

2.5. ランダムスコア順サンプリング

シャッフル アルゴリズムは、データをランダムに並べ替えることとも考えられます。n 個の要素のセットから m 個の要素をランダムに選択する問題は、ランダムに並べ替えた後に上位 m 個の要素を取得することと同じです。この原理に基づいて、ランダム スコアで並べ替えることにより、ランダム サンプリングの問題を解決する方法を設計できます。

ランダムスコアソートアルゴリズムは次のように記述できます。

• システムは、mの容量を持つランキングリストを維持します。
• 各要素に（0,1]間隔でランダムスコアを与え、ランダムスコアに従ってリーダーボードに挿入します。
• すべてのデータ処理が完了すると、上位 m 個の要素がサンプリング結果になります。

ランダム スコア ソート サンプリング アルゴリズムにはリザーバー サンプリング アルゴリズムに比べて利点がなく、追加のソート消費が必要になりますが、次の加重ランダム サンプリングではそのアルゴリズムのアイデアを活用します。

2.6. 単純な重み付きサンプリング

需要シナリオの多くのデータ要素は重み付けする必要があります。各要素が抽選される確率は、要素自体の重みによって決まります。たとえば、サーバー全体の消費抽選などのアクティビティでは、一定期間のプレイヤーの合計消費量を抽選の重みとして使用する必要があります。消費量が多いほど、最終的に当選する可能性が高くなります。これには、重み付けサンプリング アルゴリズムが関係します。

ルーレット ホイール選択法とも呼ばれる単純な重み付けランダム アルゴリズムでは、データを仮想のルーレット ホイール上に配置します。個々の要素の重みが高いほど、ルーレット ホイール上で占めるスペースが大きくなり、選択される可能性が高くなります。

ルーレットホイールの1位から4位までの賞品とラッキー賞品の重みがそれぞれ5、10、15、30、40で、すべての要素の重みの合計が100であると仮定します。[1, 100]からランダムに値を取得し、その値が45であると仮定して、最初の要素から始めて重みを累積し続け、累積重みに45が含まれる要素が現れたら、その要素を選択します。以下のように表示されます。

重量45は4等賞の累積重量値内なので、最終的な抽選結果は4等賞となります。

m 個の要素を置換せずに選択する場合は、最初に 1 つの要素を選択してセットから削除し、残りの要素を同じ方法で繰り返し抽出する必要があります。

このサンプリング アルゴリズムは複雑であり、コレクションから要素を削除すると元のデータの可読性が損なわれます。さらに重要なのは、このアルゴリズムではデータを複数回走査する必要があり、ストリーム処理シナリオでのアプリケーションには適していないことです。

2.7. 加重A-Resアルゴリズムリザーバーサンプリング

単純な加重サンプリング アルゴリズムでは、すべてのデータを保持するのに十分なメモリが必要であり、元のデータの可読性が損なわれ、時間の計算量が大きいなどの欠点があります。従来のリザーバ アルゴリズムは、ストリーム処理シナリオで置換なしのビッグ データのランダム サンプリングを効率的に実装しますが、加重状況には適用できません。

A-Res (Algorithm A With a Reservoir) は、リザーバー サンプリング アルゴリズムの重み付けバージョンです。このアルゴリズムの主な考え方は、従来のリザーバー アルゴリズムと同じで、m 個の要素を含む結果セットを維持し、結果セット内の各新しい要素を置き換えようとするものです。同時に、ランダムスコアソートアルゴリズムのサンプリングの考え方を巧みに利用しています。データをランダムにスコアリングする際に、データの重みを組み合わせてランキングスコアを生成し、スコアと重みの間に正の相関関係を満たします。A-Resアルゴリズムによるランダムスコアの生成式は次のとおりです。

ここで、は i 番目のデータの重み値であり、は (0,1] の間のランダムな値です。

A-Res アルゴリズムは次のように説明できます。

• 最初のm個の数値については、特別な値を計算し、それを直接リザーバーに入れる
• m+1,m+2,...,nのi番目の数について、式で固有値を計算する。固有値がリザーバ内の最小値を超える場合は、最小値を置き換える。

このアルゴリズムの時間計算量は であり、ストリーム処理シナリオで完全に使用できます。

2.8. 加重A-ExpJアルゴリズムリザーバーサンプリング

A-Res は各要素に対して乱数を生成する必要があり、高品質の乱数を生成するとパフォーマンスのオーバーヘッドが大きくなる可能性があります。論文「リザーバーを使用した加重ランダムサンプリング」では、より最適化された指数ジャンプアルゴリズムである A-ExpJ サンプリング (指数ジャンプを使用したアルゴリズム A) が提案されており、乱数生成の量を から に削減できます。原理は、追加のランダム操作によって要素のセグメントの固有値の計算をスキップするのと似ています。

A-ExpJ アルゴリズムのリザーバー サンプリングは次のように記述できます。

• 最初の m 個の数値について、固有値を計算します。ここで、は i 番目のデータの重み値であり、(0,1] の間のランダムな値であり、リザーバーに直接入れられます。
• m+1、m+2、...、nのi番目の数については、以下の手順を実行します。
• しきい値を計算します。ここで、r は (0,1] 間のランダムな値であり、はリザーバー内の最小の固有値です。
• いくつかの要素をスキップし、i番目の要素が次を満たすまでこれらの要素の重みを累積する。
• 現在の要素の固有値を計算します。ここで、は(,1]の間のランダムな値、はリザーバ内の最小の固有値、は現在の要素の重み値です。
• リザーバー内の最小の固有値を持つ要素を現在の要素に置き換えます
• しきい値の更新、

ちょっと分かりにくいですね。コードをお見せしましょう:

関数aexpj_weight_sampling(データ配列、重み配列、n、m)
ローカル結果、ランク = {}、{}
 i=1, m の場合
ローカルrand_score = math.random() ^ (1 / weight_array[i])
ローカルidx = binary_search(rank, rand_score)
テーブルに挿入(rank, idx, {score = rand_score, data = data_array[i]})
終わり  
 
ローカルweight_sum、xw = 0、math.log(math.random()) / math.log(rank[m].score)
 i=m+1,nの場合
        重みの合計 = 重みの合計 + 重みの配列[i]
        weight_sum >= xwの場合 
ローカルtw = ランク[m].スコア^重み配列[i]
ローカルrand_score = (math.random()*(1-tw) + tw) ^ (1 / weight_array[i])
ローカルidx = binary_search(rank, rand_score)
テーブルに挿入(rank, idx, {score = rand_score, data = data_array[i]})
テーブル.remove(ランク)
            重み合計 = 0
            xw = math.log(math.random()) / math.log(rank[m].score)
終わり 
終わり  
 
 i=1, m の場合
        結果[i] = ランク[i].データ
終わり  
 
結果を返す
終わり 

3. ソートアルゴリズム

3.1. 基本的なソート

基本的なソートは、要素のソートコードの比較に基づくソートアルゴリズムです。

3.1.1. バブルソート

バブルソートはシンプルで直感的なソートアルゴリズムです。各ラウンドで隣接する要素の各ペアを比較します。隣接する要素の順序がルールに準拠していない場合、順序が入れ替わり、各ラウンドで最小 (最大) の要素が上に浮き上がります。すべてのラウンドが終了すると、順序付けられたシーケンスになります。

このプロセスは次のように示されます。

挿入ソート

挿入ソートは、順序付けられたシーケンスを構築します。最初は、最初の要素が順序付けられたシーケンスと見なされ、後続のすべての要素はソートされていないシーケンスと見なされます。ソートされていないシーケンスは、最初から最後までスキャンされます。ソートされていないデータの場合、ソートされたシーケンスは後ろから前にスキャンされ、対応する位置が見つけられ、挿入されます。

このプロセスは次のように示されます。

選択ソート

選択ソートでは、まずソートされていないシーケンス内で最小 (最大) の要素を見つけ、それをソートされたシーケンスの先頭に格納します。残りのソートされていない要素から最小 (最大) の要素を探し続け、それをソートされたシーケンスの最後に配置します。すべての要素が処理されるまで。

このプロセスは次のように示されます。

挿入ソートは各ラウンドで最初のソートされていないシーケンスの位置を処理しますが、選択ソートは各ラウンドでソートされたシーケンスの位置を固定します。バブル ソートも、各ラウンドでソートされたシーケンスの位置を固定します。選択ソートとの違いは、選択ソートが最小 (最大) の要素を直接選択するのに対し、バブル ソートはシーケンス内の隣接する要素を交換することによって最小 (最大) の要素を選択することです。

3.1.4. クイックソート

クイックソートは分割統治戦略を使用して、シーケンスを 2 つのサブシーケンスに分割します。クイックソートは、ソートアルゴリズムにおける分割統治の考え方の典型的な応用です。本質的に、クイックソートはバブルソートに基づく再帰的な分割統治法とみなされるべきです。

クイックソートは、シーケンスから「ベースライン」と呼ばれる要素を選択し、ベースラインよりも小さい値を持つすべての要素をベースラインの前に配置し、ベースラインよりも大きい値を持つ要素をベースラインの後ろに配置します。 1 ラウンド後、ベンチマークはシリーズの真ん中にあります。そして、ベンチマーク値より小さい要素のサブシーケンスとベンチマーク値より大きい要素のサブシーケンスを再帰的にソートします。

このプロセスは次のように示されます。

3.1.5. マージソート

マージソートは、マージ操作に基づく効果的なソートアルゴリズムであり、分割統治アプローチの非常に典型的な応用でもあります。マージソートでは、まずシーケンスを 2 つの最小単位に分割し、次に順序付けられたシーケンスをマージして 1 つの順序付けられたシーケンスにマージし、最終的に最終的な順序付けられたシーケンスにマージします。

このプロセスは次のように示されます。

3.1.6. ヒープソート

ヒープソートは、ヒープ データ構造を使用して設計されたソート アルゴリズムです。ヒープは、完全なバイナリ ツリーを近似し、ヒープの特性を満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードよりも小さい (または大きい) です。

ヒープソートでは、まずヒープを作成し、各ラウンドでヒープの最上位要素をポップし、次にヒープの特性を維持するためにヒープを調整します。ポップされたすべての要素のシーケンスが、最終的なソートされたシーケンスになります。

このプロセスは次のように示されます。

3.1.7. シェルソート

シェル ソートは、減少増分ソート アルゴリズムとも呼ばれ、挿入ソートのより効率的な改良版ですが、シェル ソートは不安定なソート アルゴリズムです。

挿入ソートは、ほぼすでにソートされているデータに対して操作する場合に効率的です。つまり、線形ソートの効率を実現できます。しかし、挿入ソートは一度に 1 ビットしかデータを移動できないため、一般的に非効率的です。

シェルソートでは、比較するすべての要素を複数の領域に分割することで、挿入ソートのパフォーマンスが向上します。これにより、要素を最終位置に向かって一度に大量に前進させることができます。アルゴリズムは、アルゴリズムの最後のステップを並べ替えるために小さくて小さくなりますが、このステップでは、ソートされるデータはほぼソートされています（挿入ソートは現時点では高速です）。

プロセスは次のように実証されています。

3.2

基本的なソートは、要素ソートコードの比較に基づいていますが、割り当てソートでは「割り当て」と「コレクション」の方法を使用します。

3.2.1

カウンティングソートの中核は、入力データの値をキーに変換し、それを追加の配列スペースに格納することです。線形時間計算量を持つソート方法として、カウンティングソートでは、入力データが特定の範囲の整数である必要があります。

カウントソートの特性：入力要素が0からkの間のn整数である場合、その実行時間はそうです。カウンティングソートは比較ソートではなく、そのソート速度はどの比較ソートアルゴリズムよりも高速です。

カウントに使用される配列の長さは、ソートする配列内のデータの範囲（ソートされる配列の最大値と最小値の差に等しい）に依存するため、カウントソートには、大きなデータ範囲を持つ配列には多くの時間とスペースが必要です。

プロセスは次のように実証されています。

3.2.2

Bucket Sortは、カウントソートのバージョンです。たとえば、ソートされたデータを10単位で除算し、同じ商値を持つ数値を同じバケツに配置できます。つまり、10個ごとに同じバケツに入れられます。

プロセスは次のように実証されています。

バケットソートをより効率的にするには、次の 2 つのことを行う必要があります。

十分な余裕がある場合は、バケットの数を増やしてみてください

使用されるマッピング関数は、すべての入力データをすべてのバケットに均等に配布できます。

カウントソートは、本質的に特別なバケットソートです。

3.2.3

RADIXソートの原理は、桁数に応じて整数を異なる数値にカットし、各数字を個別に比較することです。 RADIXのソートは、最初に最も有意な数字で並べ替え、同じ値を同じバケツに入れ、最低ビット値の順にそれらを積み重ねてから、次に最も有意なビットで並べ替え、すべてのビットがソートされるまでこのプロセスを繰り返し、最後に順序付けられたシーケンスを繰り返します。

プロセスは次のように実証されています。

RADIXソートもバケットソートです。バケットソートはバケツを値範囲で分割し、ラジックスのソートは数字で分割することができます。

3.3マルチウェイマージソート

マルチウェイマージソートアルゴリズムは、既に順序付けられた複数のリストを順序付けされたリストのセットにマージおよびソートするソートプロセスです。

k-wayマージソートは、次のように説明できます。

• 最初は、K-Way注文リストの最初の要素を取り出し、比較プールに入れます。
• 比較プールから最小の（最大の）要素を取り、結果リストに追加し、要素が比較プールに配置されている順序リストの次の要素を配置します（もしあれば）。
• すべてのキューのすべての要素が取り出されるまで、ステップ2を繰り返します。

比較プールから最小の（最大の）要素が取られるたびに、K値の比較操作が必要です。

敗者の木は、敗者のツリーの反対側のツリーです。

次の図は、勝者のツリーを示しています。

敗者ツリーの親ノードは、左と右の子供の比較後の敗者を表しますが、前のレベルの比較プロセスでは、前の勝者と比較されます。

次の図は、敗者の木を示しています。

葉のノードの値は次のとおりです。{7,4,2,3,5,6,1}は4、7は勝者です。 7と8のレコード4などのOD。

k = 8を仮定すると、敗者のツリーマージソートプロセスは次のように実証されています。

まず、敗者の数を構築し、最終的な勝者は1つです。1つがポップアウトされ、1が位置する8番目の列が1つの葉の位置に置かれ、敗者のツリーが調整されます。各ラウンドの最終的な勝者シーケンスは、最後のマージ順序付きシーケンスです。

勝者のツリーと敗者のツリーの本質は、補助ノードの比較結果を記録して、新しいノードを挿入した後の比較と調整性能を実現することです。

著者は、敗者のツリーを使用して、LUA言語に基づいてマルチウェイマージソートアルゴリズムを実装しています。

3.4リストのソート

スキップリストは、各ノードで上位レベルの補助検索ノードをランダムに確立することにより、ノードへの高速アクセスを実現する順序付けられたデータ構造です（敗者ツリーのマルチウェイマージと同様）。

スキップリストはレイヤーに組み込まれており、最下層はすべての要素を含む通常の順序付けられたリンクリストです。それぞれの高いレベルは、以下のリストの「高速トラック」として機能し、i番目のレベルの要素は、固定確率p（通常は1/2または1/4）でi+1レベルでランダムに表示されます。各要素は平均して1/（1-p）リストに表示され、トップレベルの要素がリストに表示されます。

以下は、4層スキップテーブル構造の概略図です。

ターゲット要素を検索するときは、トップレベルのリスト、ヘッド要素から開始し、ターゲット以上の要素が見つかるまで、または現在のレイヤーリストの端に到達するまで、リンクリストの各レイヤーに沿って検索します。要素がターゲット要素に等しい場合、要素がターゲット要素よりも大きい場合、またはリンクリストの端に達した場合、現在のレイヤーの前の要素に戻り、次のレイヤーに移動します。など、要素は最終的に発見されるか、下部にまだ見つかりません（存在しません）。

P値が大きくなると、占有されたスペースが小さくなりますが、逆に、占有されたスペースが大きくなり、検索速度が高くなります。

スキップリストはリンクリストを使用し、バイナリ検索方法に似た補助ノードを追加するため、クエリ、挿入、削除のパフォーマンスが理想的です。ほとんどの場合、スキップリストの効率は、バランスの取れたバランススキームに匹敵します。これは、バランスの取れたツリーよりも簡単で、RedisのZSET、LevelDB、および当社のApolloランキングがすべてスキップリストスキームを使用しています。

3.5の並べ替え

ストリーム処理シナリオでは、大容量のソートリストの場合、フルストレージとソートに必要な空間と時間は非常に高く、実用的ではありません。実際のアプリケーションでは、ロングテールデータを並べ替えるためには、通常、おおよそのパーセンテージランキングを表示するだけで、高性能と高いリアルタイムパフォーマンスと引き換えにある程度の精度を犠牲にします。

3.5.1 hdrhistogramアルゴリズム

Hdrhistogramは、ヒストグラムアルゴリズムを使用して、バケツのソートに似ています。

間隔セグメンテーション法は、線形および指数セグメンテーションにすることができます。

• 線形セグメンテーション、データは固定された長さで分割されます[1-1000000]と仮定します。
• 指数セグメンテーションは、データ範囲が[1-1000000]であると仮定して、指数関数的な倍数に基づいて分割されます。

メモリと推定の精度を考慮するために、Hdrhistogramは2層ヒストグラムアルゴリズムに相当する線形セグメンテーションと指数セグメンテーションを同時に使用します。線形間隔分割が小さいほど、結果がより正確になりますが、メモリが必要なほど、ビジネスの精度要件に応じて線形間隔のサイズを制御できます。

ヒストグラムアルゴリズムは事前にデータの最大値を知る必要があり、最大値を超えるデータは保存されません。 Hdrhistogramは、データが推定値を超えるという問題を解決するための自動容量拡張機能を提供しますが、この自動容量拡張方法にはコピーコストが高くなります。

3.5.2

Hdrhistogramは、データシーケンスが均一に分布する場合、データが実際のアプリケーションで均一ではなく、特定のバケツ株式を採用する可能性があります。

CKMSは、新しいバケツを開くかどうかを決定するときに、設定されたエラー率の概念も導入します。判断式は次のとおりです。間隔間隔=エラー率 *総データ額。

次の図は、バケツマージの例です。

上記のように、エラー率が0.1に設定されていると仮定すると、データの総数が10を超えると、間隔間隔は判断式を介して1として計算されるため、間隔間隔が1以下の隣接するバケツがマージされます。

CKMSアルゴリズムは、データの性質に応じて適切なエラーレートを予測する必要があります。

3.5.3

TDigestアルゴリズムのアイデアは、おおよそのアルゴリズムで一般的に使用されるスケッチメソッドです。それは本質的にバケツの動的な方法です。

TDigestアルゴリズムが特定のパーセンタイルを推定すると、パーセンタイルに対応する2つの重心に基づいて線形に計算されます。これは、正確なパーセンタイルの計算方法と同じです。第一に、第二に、パーセンタイルQとすべての重心に基づいて、対応するインデックスに隣接する2つの重心を計算します。 （実際の計算方法は加重平均です）。

このことから、パーセンタイルQの計算誤差が小さいほど、対応する2つの重心の平均が近づくことがわかります。 TDigestアルゴリズムの鍵は、重心の数を制御する方法です。

TDigest構造アルゴリズムバッファとマージは、次のように説明できます。

一時的な配列に新しく追加されたデータポイントを追加するか、一時的な配列を計算する必要がある場合、一時配列のデータポイントは既存の重心とともにソートされます。 （データポイントと重心はまったく同じ方法で表現されます。平均と重量、各データポイントの平均値はそれ自体、重みはデフォルトで1です）。

すべてのデータポイントと重心を繰り返し、マージ条件を満たすデータポイントと重心がマージされると、新しい重心数が作成されます。

200の重心があると仮定すると、200等部分で0から1を分割でき、各重心は0.5パーセンタイルに相当します。現在10,000のデータポイントがある場合、つまり、サイズごとに10,000ポイントを並べ替えた後、合計重量は10,000です。各重心（重心によって表されるデータポイントの数に相当）が約10,000/200 = 500であることを判断できます。

実際のアプリケーションでは、90％、95％、99％などの極端なパーセンタイルに関心がある可能性があります。そのため、TDigestアルゴリズムはQ = 0およびQ = 1に近いパーセンタイル精度を特別に最適化し、Q = 0およびQ = 1の近くの質量の中心が小さく、数が特別なマッピング関数kを介して大きくなることを保証します。

もう1つのTDigest構造アルゴリズムは、AVLツリーのクラスタリングアルゴリズムです。AVLバイナリ平衡ツリーを使用して、データポイントの最も近い重心数を検索し、最も近い重心数の質量を見つけ、2つをマージします。

4.電流制限と過負荷保護

複雑なビジネスシナリオでは、瞬間的な要求の数が突然増加することができることがよくあります。これにより、サーバーがあまりにも多くのリソースを占有し、再試行とリソースの競争が多くなり、応答速度、タイムアウト、さらにはダウンタイム、さらにはシステム全体が利用できない雪崩をもたらします。

この状況に対処するために、システムは通常、信頼できる現在の制限および過負荷の保護機能を持つ必要があり、このサービスまたはダウンストリームサービスシステムの安定性を確保するために、システムのキャリング能力を超えるリクエストを迅速に拒否および破棄する必要があります。

4.1

カウンターアルゴリズムは、現在の制限アルゴリズムに実装する最も簡単で簡単なアルゴリズムです。カウンターアルゴリズムは、特定のユーザーのリクエスト、特定のタイプのインターフェイス要求、またはグローバルな合計リクエストを制限できます。

たとえば、単一のプレーヤーにログインプロトコルを設定します。これは、3秒ごとにプレーヤーのログイン時間を記録できます。

別の例では、特定のタイプのプロトコルについては、同じ秒で合計ログインプロトコルリクエストを設定するように設定すると、カウンターが100を超えると、カウンターが100を超え、現在のリクエスト間の間隔が1秒以内にある場合は、1つのリクエストが依存しています。カウンターは0にリセットされ、もう一度カウントされます。

カウンターアルゴリズムは、瞬時のトラフィックに重大な問題を抱えています。つまり、タイムウィンドウを切り替えると、最悪の場合に次のウィンドウのリクエストが集中しています。

この目的では、異なる間隔を持つ複数のカウンターを使用して、たとえば、ログイン要求を1秒以内に100回以下、1分以内に1,000回以下に制限できます。

4.2リークバケツ

漏れているバケツアルゴリズムの原理は非常に単純です。漏れやすいバケットアルゴリズムは、システムが固定レート全体でリクエストを処理することを保証できます。

次の図に示すように:

4.3トークンバケット

多くのアプリケーションシナリオでは、リクエストの固定処理レートを要求することに加えて、この時点でバーストリクエストの数を許可する必要があります。

トークンバケットアルゴリズムの原則は、システムがバケツを一定の速度で入れる必要がある場合、バケツにトークンがない場合は、サービスを拒否する必要があります。

トークンバケットアルゴリズムは、おおよそ次のように説明されています。

すべてのリクエストは、処理される前に利用可能なトークンを取得する必要があります。

現在の制限サイズに応じて、一定の速度でトークンをバケットに追加するように設定します。

バケットは最大トークンの配置制限を設定し、バケットがいっぱいになると、新しく追加されたトークンが破棄されます。

リクエストに到達した後、トークンを保持して、ビジネスロジックを処理した後にのみ取得する必要があります。

次の図に示すように:

4.4スライドウィンドウ

カウンター、漏れやすいバケットアルゴリズムは、上流のノードでの電流制限操作です。

スライディングウィンドウは、現在同時に最大のリクエストを設定しますエンドポイントと左のエンドポイントは、最大ウィンドウサイズを超え、サービスの送信または拒否を待ちます。

次の図に示すように:

4.5 STRE適応電流制限

スライディングウィンドウは、固定されたウィンドウサイズでリクエストを制限しますが、Googleは動的なウィンドウに相当します。

SRE適応電流制限アルゴリズムでは、アプリケーションレイヤーで過去2分間に2つのデータ情報を記録する必要があります。

リクエスト：リクエストの総数、アプリケーションレイヤーによって試されたリクエストの数

受け入れ：バックエンドによって正常に処理されるリクエストの数

拒否される要求の確率pの計算式は次のとおりです。

1. ここで、kはユーザーによって設定されています（2など）。
2. 通常の状況では、リクエストは受け入れに等しく、新しい要求が決定される確率は0です。つまり、すべての要求は通常渡されます
3. バックエンドで例外が発生すると、アプリケーションレイヤーが徐々にリクエストを送信することができます。
4. バックエンドが徐々に回復し、徐々に増加し、確率が増加し、より多くのリクエストがリクエスト以上に復元されると、確率Pは0に等しく、現在の制限は終了します。

さまざまなシナリオでより多くのリクエストを処理することによって引き起こされるリスクコストと、より多くのリクエストを拒否することによって引き起こされるサービスの損失コストを比較検討することにより、K値サイズを調整できます。

• K値を減らすと、適応電流制限アルゴリズムがより積極的になります（より多くの要求を拒否し、サービスの損失コストの増加、リスクコストの削減）。
• K値を増やすと、適応電流制限アルゴリズムが積極的ではなくなります（より多くの要求を節約し、サービスの損失コストを削減し、リスクコストを増加させます）。

たとえば、リクエストの処理コストがリクエストを拒否するコストに近い場合がある場合、システムの高い負荷操作により、多くのリクエスト処理がタイムアウトします。

4.6

ヒューズアルゴリズムの原則は、過去の要求の障害（タイムアウト）比を定期的に確認することです。このサイクルは繰り返されます。

次の図に示すように:

4.7 Hystrixハーフオープンヒューズ

Hystrixの半分のヒューズは、単純なヒューズと比較して半分の状態を追加します。開いた場合、その後のリクエストは切り捨てられます。その後、一定期間、オープン状態を開くと、サービスの健康チェックを実施することに相当します。

次の図に示すように:

5。シリアル化とエンコーディング

データ構造のシリアル化とは、データ構造またはオブジェクトの状態を検索形式（たとえば、ファイルとして保存、バッファーに保存する、またはネットワーク上に送信される）に変換するプロセスを指し、同じまたは別のコンピューター環境での元の状態のその後の回復を可能にします。シリアル化された形式でバイトの結果を取得する場合、元のオブジェクトと同じセマンティクスのコピーを作成するために使用できます。

5.1マークアップ言語

マークアップ言語は、テキストとその他のテキスト関連情報を組み合わせて、ドキュメント構造とデータ処理の詳細を示すコンピューターテキストエンコードです。

5.1.1

HTMLは、Webページを作成するために使用される標準のマークアップ言語です。 HTMLは、Webページ、Webアプリケーション、モバイルアプリケーション用のユーザーインターフェイスを設計するために、CSSおよびJavaScriptでよく使用される基本テクノロジーです。 WebブラウザはHTMLファイルを読み取り、Visual Webページにレンダリングできます。 HTMLは、手がかりが表示されるときにWebサイトの構造的セマンティクスを説明し、プログラミング言語ではなくマークアップ言語になります。

5.1.2拡張マークアップ言語（XML）

XMLは、データ情報を送信および伝達するように設計されたマークアップ言語です。各XMLドキュメントはXML宣言から始まり、前のコードの最初の行はXML宣言です。このコード行は、パーサーまたはブラウザに、XMLルールに従ってファイルを解析する必要があることを指示します。

XMLドキュメントの文字は、マークアップとコンテンツの2つのカテゴリに分かれています。タグは通常、<、>で終了します。タグ付き文字またはコンテンツのいずれか。タグは、<で始まり、>で終わるタグ構造に属します。

要素は、スタートタグとマッチングエンドタグの間、または空のエレメントタグの間のドキュメントの論理コンポーネントです。

属性は、タグ構造、スタートタグまたは空のエレメントタグ内の「名前値ペア」です。たとえば、各要素では、1つの属性がせい​​ぜい1回表示され、1つの属性には1つの値しか表示されません。

5.1.3

Markdownは、John Gruberによって設立された軽量のマークアップ言語です。これにより、読みやすく書くのが簡単な単純なテキスト形式でドキュメントを作成し、有効なXHTML（またはHTML）ドキュメントに変換することができます。この言語は、メールですでに入手可能なプレーンテキストタグの多くの機能を吸収します。

マークダウンの軽量で読みやすく、簡単に作られやすい機能があり、写真、チャート、数学の公式をサポートしているため、多くのWebサイトは現在、マークダウンを使用してヘルプドキュメントを作成したり、フォーラムにメッセージを投稿したりしています。 Github、Reddit、Diaspora、Stack Exchange、OpenstreetMap、SourceForge、Jianshuなど、電子書籍の作成にも使用できます。もちろん、KMプラットフォームも非常に強力です。

マークダウン構文形式は次のとおりです。

5.1.4

JSONは、XMLと比較して、データの線形化を目的とした軽量のマークアップ言語です。

JSONの基本的なデータ型とエンコーディングルール：

• 値：10進数は、先頭の0を持つことができず、負の数になり、小数を持つことができます。 EまたはEを使用して指数関数的な部分を表すこともできます。 NANなどの非数字を含めることはできません。整数や浮動小数点数と区別できません。
• 文字列：二重引用符で囲まれたゼロ以上のユニコードコードビット ""。バックスラッシュから始まる脱出された文字シーケンスをサポートします。
• Boolean：TrueまたはFalseとして表現されています。
• 配列：ゼロ以上の値を順序付けます。各値は任意のタイプにすることができます。シーケンスリストは、四角い括弧で囲まれています[、]。要素はコンマで分割されます。示されているように：[値、値]
• オブジェクト：キーが文字列のみになることができるいくつかの順序付けられていない「キー価値ペア」。オブジェクト内のキーが一意であることは推奨されますが、必須ではありません。オブジェクトは、巻き毛のブレースで始まります{および}で終わります。キー価値のペアは、コンマで分離されます。キーはコロンで分割されます。
• ヌル値：値はnullとして記述されます

5.2 TLVバイナリシリアル化

多くの効率的なデータのシリアル化方法は、TLV（TAG+LENGTH+値）を使用してデータをシリアル化して脱出します。タグはデータタグであり、次のデータ型が何であるかを識別します。

5.2.1

プロトコルバッファー（略してプロトブフ）は、XMLおよびJSONよりも小さく、より速く、シンプルで、柔軟で効率的で自動化された構造データシリアル化方法です。

プロトコルバッファーには、これらの説明に基づいて定義する必要があるデータ構造を説明するインターフェイスの説明言語が含まれています。

プロトコルバッファーは、キーの値の形式です。

Field_Numberセクションでは、現在のデータメンバーが現在どのデータメンバーであるかを示し、現在のキー値を使用してCCおよびHファイルのデータメンバーに対応するように使用します。

ワイヤタイプは、次のカテゴリを備えたフィールドエンコーディングタイプです。

機能をエンコードするプロトコルバッファ：

• 整数データはVARINT（セクション5.4.1を参照）でエンコードされ、シリアル化されたデータサイズを保存します。
• 署名された整数の場合、最初にzigzagエンコードを実行し（セクション5.4.2を参照）、次に否定的な整数シリアル化後のデータサイズを削減するためにVarintデータエンコードを実行します。
• エンコーディングタイプの文字列、ネストされた構造、および詰め込まれた反復フィールドは長さが識別され、それらのエンコード方法は均一にタグ+長さ+値です。

5.2.2

TDRは、主にデータのシリアル化と脱派化とデータストレージに使用されているTencent Interactive Entertainive R＆D Departmentの自己開発のクロスプラットフォーム多言語データ表現コンポーネントです。 TDRは、XMLファイルを介したインターフェイスと構造の説明を定義し、これらのデータ構造をシリアル化および脱isizeに使用するために使用されるプログラムツールを介したこれらの説明に基づいて.TDRおよび.Hファイルコードを生成します。

TDR1.0のバージョンは、バージョンのバージョン番号を事前に維持する必要があります。

TDR2.0は、一般に、TDR2.0がメッセージプロトコルの前後の双方向の互換性をサポートしています。

プロトコルバッファとTDRにはインターフェイス説明言語があり、シリアル化がより効率的になり、データシリアル化がよりコンパクトになります。

5.2.3 Lunaのシリアル化

LUNAライブラリは、C ++ 17に基づくオープンソースLUA/C ++バインディングライブラリであり、LUAデータ構造のシリアル化および脱滑り機能も実装しています。

LUA言語に送信および保存する必要があるデータの主なタイプは、nil、boolean、number、string、およびtableです。したがって、シリアル化プロセス中に、Lunaはタイプを次の9型として定義します。

シリアル化方法は次のとおりです。

全体として、これはプロトコルバッファーとTDRと同様のTLVエンコード方法でもあり、同時に、LUA型構造の特性に対していくつかの効率の最適化がなされています。

主な機能は次のとおりです。

• ブールタイプは、2種類の値を追加することでそれを解くことができます。
• Integerは、記録長に追加のバイトを必要とせずに、Varint圧縮エンコードも使用します。
• 署名された整数の場合、Zigzag調整が最初に実行され、次にVarintデータエンコードが実行されます。
• 字符串类型分为string 和string_idx，编码过程中会缓存已经出现过的字符串，对于后续重复出现的字符串记录为string_idx 类型，value 值记录该字符串第一次出现的序号，节约字符串占用的空间。
• 对于小于246(255 减去类型数量9)的小正整型数，直接当成不同类型处理，加上数值9 之后记录在type 中，节约空间。
• Table 为嵌套结构，用table_head 和table_tail 两种类型表示开始和结束。key 和value 分别进行嵌套编码。

5.2.4. Skynet 序列化

Skynet 是一个应用广泛的为在线游戏服务器打造的轻量级框架。但实际上它也不仅仅使用在游戏服务器领域。skynet 的核心是由C 语言编写，但大多数skynet 服务使用lua 编写，因此它也实现了针对lua 数据结构的序列化和反序列化功能。

序列化方式如下：

主な機能は次のとおりです。

• Type 类型通过低3 位和高5 位来区分主类型和子类型。
• Boolean 单独主类型，子类型字段用1 和0 区分true 和false。
• 整型使用number 主类型，子类型分为number_zero(0 值)，number_byte(小于8 位的正整数)，number_word(小于16 位的正整数)，number_dword(小于32 位的正负整数)，number_qword(其他整数)，number_real(浮点数)。
• 字符串类型分为短字符串short_string 和长字符串long_string，小于32 字节长度的字符串记录为short_string 主类型，低5 位的子类型记录长度。long_string 又分为2 字节(长度小于0x1000)和4 字节(长度大于等于0x1000)长字符串，分别用2 字节length 和4 字节length 记录长度。
• Table 类型会区分array 部分和hash 部分，先将array 部分序列化，array 部分又分为小array 和大array，小array(0-30 个元素)直接用type 的低5 位的子类型记录大小，大array 的子类型固定为31，大小通过number 类型编码。Hash 部分需要将key 和value 分别进行嵌套编码。
• Table 的结束没有像luna 一样加了专门的table_tail 标识，而是通过nil 类型标识。

5.3. 压缩编码

压缩算法从对数据的完整性角度分有损压缩和无损压缩。

有损压缩算法通过移除在保真前提下需要的必要数据之外的其小细节，从而使文件变小。在有损压缩里，因部分有效数据的移除，恢复原文件是不可能的。有损压缩主要用来存储图像和音频文件，通过移除数据达到比较高的压缩率。

无损压缩，也能使文件变小，但对应的解压缩功能可以精确的恢复原文件，不丢失任何数据。无损数据压缩被广泛的应用于计算机领域，数据的传输和存储系统中均使用无损压缩算法。

接下来我们主要是介绍几种无损压缩编码算法。

5.3.1. 熵编码法

一种主要类型的熵编码方式是对输入的每一个符号，创建并分配一个唯一的前缀码，然后，通过将每个固定长度的输入符号替换成相应的可变长度前缀无关(prefix-free)输出码字替换，从而达到压缩数据的目的。每个码字的长度近似与概率的负对数成比例。因此，最常见的符号使用最短的码。

霍夫曼编码和算术编码是两种最常见的熵编码技术。如果预先已知数据流的近似熵特性(尤其是对于信号压缩)，可以使用简单的静态码。

5.3.2. 游程编码

又称行程长度编码或变动长度编码法，是一种与资料性质无关的无损数据压缩技术，基于“使用变动长度的码来取代连续重复出现的原始资料”来实现压缩。举例来说，一组资料串"AAAABBBCCDEEEE"，由4 个A、3 个B、2 个C、1 个D、4 个E 组成，经过变动长度编码法可将资料压缩为4A3B2C1D4E(由14 个单位转成10 个单位)。

5.3.3. MTF 变换

MTF(Move-To-Front)是一种数据编码方式，作为一个额外的步骤，用于提高数据压缩技术效果。MTF 主要使用的是数据“空间局部性”，也就是最近出现过的字符很可能在接下来的文本附近再次出现。

过程可以描述为：

首先维护一个文本字符集大小的栈表，“recently used symbols”(最近访问过的字符)，其中每个不同的字符在其中占一个位置，位置从0 开始编号。

扫描需要重新编码的文本数据，对于每个扫描到的字符，使用该字符在“recently used symbols”中的index 替换，并将该字符提到“recently used symbols”的栈顶的位置(index 为0 的位置)。重复上一步骤，直到文本扫描结束。

5.3.4. 块排序压缩

当一个字符串用该算法转换时，算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串，那么转换过的字符串上就会有一些连续重复的字符，这对压缩是很有用的。

块排序变换(Burrows-Wheeler Transform)算法能使得基于处理字符串中连续重复字符的技术(如MTF 变换和游程编码)的编码更容易被压缩。

块排序变换算法将输入字符串的所有循环字符串按照字典序排序，并以排序后字符串形成的矩阵的最后一列为其输出。

5.3.5. 字典编码法

由Abraham Lempel 和Jacob Ziv 独创性的使用字典编码器的LZ77/78 算法及其LZ 系列变种应用广泛。

LZ77 算法通过使用编码器或者解码器中已经出现过的相应匹配数据信息替换当前数据从而实现压缩功能。这个匹配信息使用称为长度-距离对的一对数据进行编码，它等同于“每个给定长度个字符都等于后面特定距离字符位置上的未压缩数据流。”编码器和解码器都必须保存一定数量的缓存数据。保存这些数据的结构叫作滑动窗口，因为这样所以LZ77 有时也称作滑动窗口压缩。编码器需要保存这个数据查找匹配数据，解码器保存这个数据解析编码器所指代的匹配数据。

LZ77 算法针对过去的数据进行处理，而LZ78 算法却是针对后来的数据进行处理。LZ78 通过对输入缓存数据进行预先扫描与它维护的字典中的数据进行匹配来实现这个功能，在找到字典中不能匹配的数据之前它扫描进所有的数据，这时它将输出数据在字典中的位置、匹配的长度以及找不到匹配的数据，并且将结果数据添加到字典中。

5.3.6. 霍夫曼(Huffman)编码

霍夫曼编码把文件中一定位长的值看作是符号，比如把8 位长的256 种值，也就是字节的256 种值看作是符号。根据这些符号在文件中出现的频率，对这些符号重新编码。对于出现次数非常多的，用较少的位来表示，对于出现次数非常少的，用较多的位来表示。这样一来，文件的一些部分位数变少了，一些部分位数变多了，由于变小的部分比变大的部分多，所以整个文件的大小还是会减小，所以文件得到了压缩。

要进行霍夫曼编码，首先要把整个文件读一遍，在读的过程中，统计每个符号(我们把字节的256 种值看作是256 种符号)的出现次数。然后根据符号的出现次数，建立霍夫曼树，通过霍夫曼树得到每个符号的新的编码。对于文件中出现次数较多的符号，它的霍夫曼编码的位数比较少。对于文件中出现次数较少的符号，它的霍夫曼编码的位数比较多。然后把文件中的每个字节替换成他们新的编码。

5.3.7. 其他压缩编码

• deflate 是同时使用了LZ77 算法与霍夫曼编码的一个无损数据压缩算法。
• gzip 压缩算法的基础是deflate。
• bzip2 使用Burrows-Wheeler transform 将重复出现的字符序列转换成同样字母的字符串，然后用move-to-front 变换进行处理，最后使用霍夫曼编码进行压缩。
• LZ4 着重于压缩和解压缩速度，它属于面向字节的LZ77 压缩方案家族。
• Snappy(以前称Zippy)是Google 基于LZ77 的思路用C++语言编写的快速数据压缩与解压程序库，并在2011 年开源，它的目标并非最大压缩率或与其他压缩程序库的兼容性，而是非常高的速度和合理的压缩率。

转自网络的压缩率和性能对比：

 FormatSize Before(byte) Size   After (byte)Compress Expend(ms)UnCompress Expend(ms) MAX CPU(%)bzip235984867711591236229.5gzip359848804217938926.5deflate35984970468034420.5lzo359841306958123022lz4359841635532714712.6snappy35984136024248811

5.4. 其他编码

5.4.1. Varint

前文所提到的Varint 整型压缩编码方式，它使用一个或多个字节序列化整数的方法，把整数编码为变长字节。

Varint 编码将每个字节的低7bit 位用于表示数据，最高bit 位表示后面是否还有字节，其中1 表示还有后续字节，0 表示当前是最后一个字节。当整型数值很小时，只需要极少数的字节进行编码，如数值9，它的编码就是00001001，只需一个字节。

如上图所示，假设要编码的数据123456，二进制为：11110001001000000，按7bit 划分后，每7bit 添加高1 位的是否有后续字节标识，编码为110000001100010000000111，占用3 个字节。

对于32 位整型数据经过Varint 编码后需要1~5 个字节，小的数字使用1 个字节，大的数字使用5 个字节。64 位整型数据编码后占用1~10 个字节。在实际场景中小数字的使用率远远多于大数字，因此通过Varint 编码对于大部分场景都可以起到很好的压缩效果。

5.4.2. ZigZag

zigzag 编码的出现是为了解决varint 对负数编码效率低的问题。对于有符号整型，如果数值为负数，二进制就会非常大，例如-1 的16 进制：0xffff ffff ffff ffff，对应的二进制位全部是1，使用varint 编码需要10 个字节，非常不划算。

zigzag 编码的原理是将有符号整数映射为无符号整数，使得负数的二进制数值也能用较少的bit 位表示。它通过移位来实现映射。

由于补码的符号位在最高位，对于负数，符号位为1，这导致varint 压缩编码无法压缩，需要最大变长字节来存储，因此首先将数据位整体循环左移1 位，最低位空出留给符号位使用，另外，对于实际使用中，绝对值小的负数应用场景比绝对值大的负数应用场景大的多，但绝对值小的负数的前导1 更多(如-1，全是1)，因此对于负整数，再把数据位按取反规则操作，将前导1 置换为0，以达到可以通过varint 编码能有效压缩的目的。

最终经过zigzag 编码后绝对值小的正负整数都能编码为绝对值相对小的正整数，编码效果如下：

5.4.3. Base 系列

有的字符在一些环境中是不能显示或使用的，比如&, =等字符在URL 被保留为特殊作用的字符，比如一些二进制码如果转成对应的字符的话，会有很多不可见字符和控制符(如换行、回车之类)，这时就需要对数据进行编码。Base 系列的就是用来将字节编码为ASCII 中的可见字符的，以便能进行网络传输和打印等。

Base 系列编码的原理是将字节流按固定步长切片，然后通过映射表为每个切片找一个对应的、可见的ASCII 字符，最终重组为新的可见字符流。

Base16 也称hex，它使用16 个可见字符来表示二进制字符串，1 个字符使用2 个可见字符来表示，因此编码后数据大小将翻倍。

Base32 使用32 个可见字符来表示二进制字符串，5 个字符使用8 个可见字符表示，最后如果不足8 个字符，将用“=”来补充，编码后数据大小变成原来的8/5。

Base64 使用64 个可见字符来表示二进制字符串， 3 个字符使用4 个可见字符来表示，编码后数据大小变成原来的4/3。

Base64 索引表如下：

笔者曾经用lua 实现过Base64 算法，有兴趣可以前往阅读。

5.4.4. 百分号编码

百分号编码又称URL 编码(URL encoding)，是特定上下文的统一资源定位符(URL)的编码机制，实际上也适用于统一资源标志符(URI)的编码。

百分号编码同样也是为了使URL 具有可传输性，可显示性以及应对二进制数据的完整性而进行的一种编码规则。

百分号编码规则为把字符的ASCII 的值表示为两个16 进制的数字，然后在其前面放置转义字符百分号“%”。

URI 所允许的字符分作保留与未保留。保留字符是那些具有特殊含义的字符，例如：斜线字符用于URL(或URI)不同部分的分界符;未保留字符没有这些特殊含义。

以下是RFC3986 中对保留字符和未保留字符的定义：

百分号编码可描述为：

• 未保留字符不需要编码
• 如果一个保留字符需要出现在URI 一个路径成分的内部, 则需要进行百分号编码
• 除了保留字符和未保留字符(包括百分号字符本身)的其它字符必须用百分号编码
• 二进制数据表示为8 位组的序列，然后对每个8 位组进行百分号编码

6. 加密与校验

6.1. CRC

CRC 循环冗余校验(Cyclic redundancy check)是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。

CRC 是两个字节数据流采用二进制除法(没有进位，使用XOR 来代替减法)相除所得到的余数。其中被除数是需要计算校验和的信息数据流的二进制表示;除数是一个长度为(n+1)的预定义(短)的二进制数，通常用多项式的系数来表示。在做除法之前，要在信息数据之后先加上n 个0。CRC 是基于有限域GF(2)(即除以2 的同余)的多项式环。简单的来说，就是所有系数都为0 或1(又叫做二进制)的多项式系数的集合，并且集合对于所有的代数操作都是封闭的。

6.2. 奇偶校验

奇偶校验(Parity Check)是一种校验代码传输正确性的方法。検証は、送信されたバイナリコードセットの「1」の数に基づいて実行されます。奇数を使用する人は奇数チェックと呼ばれ、その逆も同様です。通常、パリティビットが特別に設定されており、このコードのセットの「1」の数を奇数または偶数数にするために使用されます。奇妙な検証が使用される場合、受信者がこのコードのセットを受信すると、「1」の数が奇数であるかどうかを確認し、それによって伝送コードの正確性を決定します。

以偶校验位来说，如果一组给定数据位中1 的个数是奇数，补一个bit 为1，使得总的1 的个数是偶数。例：0000001, 补一个bit 为1 即00000011。

以奇校验位来说，如果给定一组数据位中1 的个数是奇数，补一个bit 为0，使得总的1 的个数是奇数。例：0000001, 补一个bit 为0 即00000010。

偶校验实际上是循环冗余校验的一个特例，通过多项式x + 1 得到1 位CRC。

6.3. MD 系列

MD 系列算法(Message-Digest Algorithm)用于生成信息摘要特征码，具有不可逆性和高度的离散性，可以看成是一种特殊的散列函数(见8.1 节)，一般认为可以唯一地代表原信息的特征，通常用于密码的加密存储，数字签名，文件完整性验证等。

MD4 是麻省理工学院教授Ronald Rivest 于1990 年设计的一种信息摘要算法，它是一种用来测试信息完整性的密码散列函数的实现，其摘要长度为128 位。它是基于32 位操作数的位操作来实现的。这个算法影响了后来的算法如MD5、SHA 家族和RIPEMD 等

MD5 消息摘要算法是一种被广泛使用的密码散列函数，可以产生出一个128 位(16 个字符)的散列值，用于确保信息传输完整一致。MD5 由美国密码学家罗纳德·李维斯特(Ronald Linn Rivest)设计，于1992 年公开，用以取代MD4 算法。MD5 是输入不定长度信息，输出固定长度128-bits 的算法。经过程序流程，生成四个32 位数据，最后联合起来成为一个128-bits 散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算，得出结果。

MD6 消息摘要算法使用默克尔树形式的结构，允许对很长的输入并行进行大量散列计算。该算法的Block size 为512 bytes(MD5 的Block Size 是512 bits), Chaining value 长度为1024 bits, 算法增加了并行机制，适合于多核CPU。相较于MD5，其安全性大大改进，加密结构更为完善，但其有证明的版本速度太慢，而效率高的版本并不能给出类似的证明。

6.4. SHA 系列

SHA(Secure Hash Algorithm)是一个密码散列函数家族，是FIPS 所认证的安全散列算法。

SHA1 是由NISTNSA 设计为同DSA 一起使用的，它对长度小于264 的输入，产生长度为160bit 的散列值，因此抗穷举性更好。SHA-1 设计时基于和MD4 相同原理,并且模仿了该算法。SHA-1 的安全性在2010 年以后已经不被大多数的加密场景所接受。2017 年荷兰密码学研究小组CWI 和Google 正式宣布攻破了SHA-1。

SHA-2 由美国国家安全局研发，由美国国家标准与技术研究院(NIST)在2001 年发布。属于SHA 算法之一，是SHA-1 的后继者。包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。SHA-256 和SHA-512 是很新的杂凑函数，前者以定义一个word 为32 位元，后者则定义一个word 为64 位元。它们分别使用了不同的偏移量，或用不同的常数，然而，实际上二者结构是相同的，只在循环执行的次数上有所差异。SHA-224 以及SHA-384 则是前述二种杂凑函数的截短版，利用不同的初始值做计算。

SHA-3 第三代安全散列算法之前名为Keccak 算法，Keccak 使用海绵函数，此函数会将资料与初始的内部状态做XOR 运算，这是无可避免可置换的(inevitably permuted)。在最大的版本，算法使用的内存状态是使用一个5×5 的二维数组，资料类型是64 位的字节，总计1600 比特。缩版的算法使用比较小的，以2 为幂次的字节大小w 为1 比特，总计使用25 比特。除了使用较小的版本来研究加密分析攻击，比较适中的大小(例如从w=4 使用100 比特，到w=32 使用800 比特)则提供了比较实际且轻量的替代方案。

6.5. 对称密钥算法

对称密钥算法(Symmetric-key algorithm)又称为对称加密、私钥加密、共享密钥加密，是密码学中的一类加密算法。这类算法在加密和解密时使用相同的密钥，或是使用两个可以简单地相互推算的密钥。事实上，这组密钥成为在两个或多个成员间的共同秘密，以便维持专属的通信联系。与公开密钥加密相比，要求双方获取相同的密钥是对称密钥加密的主要缺点之一。

常见的对称加密算法有AES、ChaCha20、3DES、Salsa20、DES、Blowfish、IDEA、RC5、RC6、Camellia 等。

对称加密的速度比公钥加密快很多，在很多场合都需要对称加密。

6.6. 非对称加密算法

非对称式密码学(Asymmetric cryptography)也称公开密钥密码学(Public-key cryptography)，是密码学的另一类加密算法，它需要两个密钥，一个是公开密钥，另一个是私有密钥。公钥用作加密，私钥则用作解密。使用公钥把明文加密后所得的密文，只能用相对应的私钥才能解密并得到原本的明文，最初用来加密的公钥不能用作解密。由于加密和解密需要两个不同的密钥，故被称为非对称加密，不同于加密和解密都使用同一个密钥的对称加密。

公钥可以公开，可任意向外发布，私钥不可以公开，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供，也不会透露给被信任的要通信的另一方。

常用的非对称加密算法是RSA 算法。

6.7. 哈希链

哈希链是一种由单个密钥或密码生成多个一次性密钥或密码的一种方法。哈希链是将密码学中的哈希函数循环地用于一个字符串。(即将所得哈希值再次传递给哈希函数得至其哈希值)。

例：，是一个长度为4 哈希链，记为：。

相比较而言，一个提供身份验证的服务器储存哈希字符串，比储存纯文本密码，更能防止密码在传输或储存时被泄露。举例来说，一个服务器一开始存储了一个由用户提供的哈希值。进行身份验证时，用户提供给服务器。服务器计算即，并与已储存的哈希值进行比较。然后服务器将存储以用来对用户进行下次验证。

窃听者即使嗅探到送交服务器，也无法将用来认证，因为现在服务器验证算法传入的参数是。由于安全的哈希函数有一种单向的加密属性，对于想要算出前一次哈希值的窃听者来说它的值是不可逆的。在本例中，用户在整个哈希链用完前可以验证1000 次之多。每次哈希值是不同的，不能被攻击者再次使用。

7. 缓存淘汰策略

服务器常用缓存提升数据访问性能，但由于缓存容量有限，当缓存容量到达上限，就需要淘汰部分缓存数据挪出空间，这样新数据才可以添加进来。好的缓存应该是在有限的内存空间内尽量保持最热门的数据在缓存中，以提高缓存的命中率，因此如何淘汰数据有必要进行一番考究。缓存淘汰有多种策略，可以根据不同的业务场景选择不同淘汰的策略。

7.1. FIFO

FIFO(First In First Out)是一种先进先出的数据缓存器，先进先出队列很好理解，当访问的数据节点不在缓存中时，从后端拉取节点数据并插入在队列头，如果队列已满，则淘汰最先插入队列的数据。

假设缓存队列长度为6，过程演示如下：

7.2. LRU

LRU(Least recently used)是最近最少使用缓存淘汰算法，可它根据数据的历史访问记录来进行淘汰数据，其核心思想认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。最近ほとんど使用されていないデータは、次回も使用されなくなる可能性があります。因此当缓存容量的满时候，优先淘汰最近很少使用的数据。因此它与FIFO 的区别是在访问数据节点时，会将被访问的数据移到头结点。

假设缓存队列长度为6，过程演示如下：

LRU 算法有个缺陷在于对于偶发的访问操作，比如说批量查询某些数据，可能使缓存中热门数据被这些偶发使用的数据替代，造成缓存污染，导致缓存命中率下降。

7.3. LFU

LFU 是最不经常使用淘汰算法，其核心思想认为如果数据过去被访问多次，那么将来被访问的频率也更高。LRU 的淘汰规则是基于访问时间，而LFU 是基于访问次数。LFU 缓存算法使用一个计数器来记录数据被访问的次数，最低访问数的条目首先被移除。

假设缓存队列长度为4，过程演示如下：

LFU 能够避免偶发性的操作导致缓存命中率下降的问题，但它也有缺陷，比如对于一开始有高访问率而之后长时间没有被访问的数据，它会一直占用缓存空间，因此一旦数据访问模式改变，LFU 可能需要长时间来适用新的访问模式，即LFU 存在历史数据影响将来数据的"缓存污染"问题。另外对于对于交替出现的数据，缓存命中不高。

7.4. LRU-K

无论是LRU 还是LFU 都有各自的缺陷，LRU-K 算法更像是结合了LRU 基于访问时间和LFU 基于访问次数的思想，它将LRU 最近使用过1 次的判断标准扩展为最近使用过K 次，以提高缓存队列淘汰置换的门槛。LRU-K 算法需要维护两个队列：访问列表和缓存列表。LRU 可以认为是LRU-K 中K 等于1 的特化版。

LRU-K 算法实现可以描述为：

数据第一次被访问，加入到访问列表，访问列表按照一定规则(如FIFO，LRU)淘汰。

当访问列表中的数据访问次数达到K 次后，将数据从访问列表删除，并将数据添加到缓存列表头节点，如果数据已经在缓存列表中，则移动到头结点。

若缓存列表数据量超过上限，淘汰缓存列表中排在末尾的数据，即淘汰倒数第K 次访问离现在最久的数据。

假设访问列表长度和缓存列表长度都为4，K=2，过程演示如下：

LRU-K 具有LRU 的优点，同时能够降低缓存数据被污染的程度，实际应用可根据业务场景选择不同的K 值，K 值越大，缓存列表中数据置换的门槛越高。

7.5. Two queues

Two queues 算法可以看做是LRU-K 算法中K=2，同时访问列表使用FIFO 淘汰算法的一个特例。次の図に示すように:

7.6. LIRS

LIRS(Low Inter-reference Recency Set)算法将缓存分为两部分区域：热数据区与冷数据区。LIRS 算法利用冷数据区做了一层隔离，目的是即使在有偶发性的访问操作时，保护热数据区的数据不会被频繁地被置换，以提高缓存的命中。

LIRS 继承了LRU 根据时间局部性对冷热数据进行预测的思想，并在此之上LIRS 引入了两个衡量数据块的指标：

• IRR(Inter-Reference Recency)：表示数据最近两次访问之间访问其它数据的非重复个数
• R (Recency)：表示数据最近一次访问到当前时间内访问其它数据的非重复个数，也就是LRU 的维护的数据。

如下图，从左往右经过以下8 次访问后，A 节点此时的IRR 值为3，R 值为1。

IRR 可以由R 值计算而来，具体公式为：IRR=上一时刻的R-当前时刻的R，如上图当前时刻访问的节点是F，那么当前时刻F 的R 值为0，而上一个F 节点的R 值为2，因此F 节点的IRR 值为2。

LIRS 动态维护两个集合：

• LIR(low IRR block set)：具有较小IRR 的数据块集合，可以将这部分数据块理解为热数据，因为IRR 低说明访问的频次高。
• HIR(high IRR block set)：具有较高IRR 的数据块集合，可以将这部分数据块理解为冷数据。

LIR 集合所有数据都在缓存中，而HIR 集合中有部分数据不在缓存中，但记录了它们的历史信息并标记为未驻留在缓存中，称这部分数据块为nonresident-HIR，另外一部分驻留在缓存中的数据块称为resident-HIR。

LIR 集合在缓存中，所以访问LIR 集合的数据是百分百会命中缓存的。而HIR 集合分为resident-HIR 和nonresident-HIR 两部分，所以会遇到未命中情况。当发生缓存未命中需要置换缓存块时，会选择优先淘汰置换resident-HIR。如果HIR 集合中数据的IRR 经过更新比LIR 集合中的小，那么LIR 集合数据块就会被HIR 集合中IRR 小的数据块挤出并转换为HIR。

LIRS 通过限制LIR 集合的长度和resident-HIR 集合长度来限制整体大小，假设设定LIR 长度为2，resident-HIR 长度为1 的LIRS 算法过程演示如下：

• 所有最近访问的数据都放置在称为LIRS 堆栈的FIFO 队列中(图中的堆栈S)，所有常驻的resident-HIR 数据放置在另一个FIFO 队列中(图中的堆栈Q)。
• 当栈S 中的一个LIR 数据被访问时，被访问的数据会被移动到堆栈S 的顶部，并且堆栈底部的任何HIR 数据都被删除，因为这些HIR 数据的IRR 值不再有可能超过任何LIR 数据了。例如，图(b)是在图(a)上访问数据B 之后生成的。
• 当栈S 中的一个resident-HIR 数据被访问时，它变成一个LIR 数据，相应地，当前在栈S 最底部的LIR 数据变成一个HIR 数据并移动到栈Q 的顶部。例如，图(c)是在图(a)上访问数据E 之后生成的。
• 当栈S 中的一个nonresident-HIR 数据被访问时，它变成一个LIR 数据，此时将选择位于栈Q 底部的resident-HIR 数据作为替换的牺牲品，降级为nonresident-HIR，而栈S 最底部的LIR 数据变成一个HIR 数据并移动到栈Q 的顶部。例如，图(d)是在图(a)上访问数据D 之后生成的。
• 当访问一个不在栈S 中的数据时，它会成为一个resident-HIR 数据放入栈Q 的顶部，同样的栈Q 底部的resident-HIR 数据会降级为nonresident-HIR。例如，图(e)是在图(a)上访问数据C 之后生成的。

解释一下当栈S 中的一个HIR 数据被访问时，它为什么一定会变成一个LIR 数据：这个数据被访问时，需要更新IRR 值(即为当前的R 值)，使用这个新的IRR 与LIR 集合数据中最大的R 值进行比较(即栈S 最底部的LIR 数据)，新的IRR 一定会比栈S 最底部的LIR 数据的IRR 小(因为栈S 最底部的数据一定是LIR 数据，步骤2 已经保证了)，所以它一定会变成一个LIR 数据。

7.7. MySQL InnoDB LRU

MySQL InnoDB 中的LRU 淘汰算法采用了类似的LIRS 的分级思想，它的置换数据方式更加简单，通过判断冷数据在缓存中存在的时间是否足够长(即还没有被LRU 淘汰)来实现。数据首先进入冷数据区，如果数据在较短的时间内被访问两次或者以上，则成为热点数据进入热数据区，冷数据和热数据部分区域内部各自还是采用LRU 替换算法。

MySQL InnoDB LRU 算法流程可以描述为：

访问数据如果位于热数据区，与LRU 算法一样，移动到热数据区的头结点。

访问数据如果位于冷数据区，若该数据已在缓存中超过指定时间，比如说1s，则移动到热数据区的头结点;若该数据存在时间小于指定的时间，则位置保持不变。

访问数据如果不在热数据区也不在冷数据区，插入冷数据区的头结点，若冷数据缓存已满，淘汰尾结点的数据。

8. 基数集与基数统计

基数集即不重复元素的集合，基数统计即统计基数集中元素的个数。比如说18 号晚微信视频号西城男孩直播夜的累积观看人数统计就是一个基数统计的应用场景。

8.1. 哈希表

哈希表是根据关键码(Key)而直接进行访问的数据结构，它把关键码映射到一个有限的地址区间上存放在哈希表中，这个映射函数叫做散列函数。哈希表的设计最关键的是使用合理的散列函数和冲突解决算法。

好的散列函数应该在输入域中较少出现散列冲突，数据元素能被更快地插入和查找。常见的散列函数算法有：直接寻址法，数字分析法，平方取中法，折叠法，随机数法，除留余数法等。

然而即使再好的散列函数，也不能百分百保证没有冲突，因此必须要有冲突的应对方法，常见的冲突解决算法有：

• 开放定址法：从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。而查询一个对象时，则需要从对应的位置开始向后找，直到找到或找到空位。根据探查步长决策规则不同，开放定址法中一般有：线行探查法(步长固定为1，依次探查)、平方探查法(步长为探查次数的平方值)、双散列函数探查法(步长由另一个散列函数计算决定)。
• 拉链法：在每个冲突处构建链表，将所有冲突值链入链表(称为冲突链表)，如同拉链一般一个元素扣一个元素。
• 再哈希法：就是同时构造多个不同的哈希函数，当前面的哈希函数发生冲突时，再用下一个哈希函数进行计算，直到冲突不再产生。
• 建立公共溢出区：哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

使用哈希表统计基数值即将所有元素存储在一个哈希表中，利用哈希表对元素进行去重，并统计元素的个数，这种方法可以精确的计算出不重复元素的数量。

但使用哈希表进行基数统计，需要存储实际的元素数据，在数据量较少时还算可行，但是当数据量达到百万、千万甚至上亿时，使用哈希表统计会占用大量的内存，同时它的查找过滤成本也很高。如18 号晚微信视频号西城男孩直播夜有2000 万多的用户观看，假设记录用户的id 大小需要8 字节，那么使用哈希表结构至少需要152.6M 内存，而为了降低哈希冲突率，提高查找性能，实际需要开辟更大的内存空间。

8.2. 位图(Bitmap)

位图就是用每一比特位来存放真和假状态的一种数据结构，使用位图进行基数统计不需要去存储实际元素信息，只需要用相应位置的1bit 来标识某个元素是否出现过，这样能够极大地节省内存。

如下图所示，假设要存储的数据范围是0-15，我们只需要使用2 个字节组建一个拥有16bit 位的比特数组，所有bit 位的值初始化为0，需要存储某个值时只需要将相应位置的的bit 位设置为1，如下图存储了{2,5,6,9,11,14}六个数据。

假设观看西城男孩直播的微信id 值域是[0-2000 万]，采用位图统计观看人数所需要的内存就只需2.38M 了。

位图统计方式内存占用确实大大减少了，但位图占用的内存和元素的值域有关，因为我们需要把值域映射到这个连续的大比特数组上。实际上观看西城男孩直播的微信id 不可能是连续的2000 万个id 值，而应该按微信的注册量级开辟长度，可能至少需要20 亿的bit 位(238M 内存)。

8.3. 布隆过滤器

位图的方式有个很大的局限性就是要求值域范围有限，比如我们统计观看西城男孩直播的微信id 总计2000 万个，但实际却需要按照微信id 范围上限20 亿来开辟空间，假如有一个完美散列函数，能正好将观看了直播的这2000 万个微信id 映射成[0-2000 万]的不重复散列值，而其余没有观看直播的19.8 亿微信id 都被映射为超过2000 万的散列值，那事情就好办了，但事实是我们无法提前知道哪2000 万的微信号会观看直播，因此这样的散列函数是不可能存在的。

但这个思想是对的，布隆过滤器就是类似这样的思想，它能将20 亿的id 值映射到更小数值范围内，然后使用位图来记录元素是否存在，因为值域范围被压缩了，必然会存在大面积的冲突，为了降低冲突导致的统计错误率，它通过K 个不同的散列函数将元素映射成一个位图中的K 个bit 位，并把它们都置为1，只有当某个元素对应的这K 个bit 位同时为1，才认为这个元素已经存在过。

假设K=3，3 个哈希函数将数据映射到0-15 的位图中存储，过程演示如下：

类似百分比近似排序，布隆过滤器也是牺牲一定的精确度来换取高性能的做法。它仍然存在一定的错误率，不能保证完全准确，比如上图示例中，假设接下来要插入数据123，它通过3 个哈希函数分别被映射为：{2,3,6}，此时会误判为123 已经存在了，将过滤掉该数据的统计。

但实际上只要K 值和位图数组空间设置合理，就能保证错误率在一定范围，这对于大数据量的基数统计，完全能接受这样的统计误差。

8.4. 布谷鸟过滤器

布谷鸟过滤器是另外一种通过牺牲一定的精确度来换取高性能的做法，也是非常之巧妙。在解释布谷鸟过滤器之前我们先来看下布谷鸟哈希算法。

布谷鸟哈希算法是8.1 节中讲到的解决哈希冲突的另一种算法，它的思想来源于布谷鸟“鸠占鹊巢”的生活习性。布谷鸟哈希算法会有两个散列函数将元素映射到哈希表的两个不同位置。如果两个位置中有一个位置为空，那么就可以将元素直接放进去。但是如果这两个位置都满了，它就随机踢走一个，然后自己霸占了这个位置。

被踢走的那个元素会去查看它的另外一个散列值的位置是否是空位，如果是空位就占领它，如果不是空位，那就把受害者的角色转移出去，挤走对方，让对方再去找安身之处，如此循环直到某个元素找到空位为止。布谷鸟哈希算法有个缺点是当空间本身很拥挤时，出现“鸠占鹊巢”的现象会很频繁，插入效率很低，一种改良的优化方案是让每个散列值对应的位置上可以放置多个元素。

8.1 节讲到，哈希表可以用来做基数统计，因此布谷鸟哈希表当然也可以用来基数统计，而布谷鸟过滤器基于布谷鸟哈希算法来实现基数统计，布谷鸟哈希算法需要存储数据的整个元素信息，而布谷鸟过滤器为了减少内存，将存储的元素信息映射为一个简单的指纹信息，例如微信的用户id 大小需要8 字节，我们可以将它映射为1 个字节甚至几个bit 的指纹信息来进行存储。

由于只存储了指纹信息，因此谷鸟过滤器的两个散列函数的选择比较特殊，当一个位置上的元素被挤走之后，它需要通过指纹信息计算出另一个对偶位置(布谷鸟哈希存储的是元素的完整信息，必然能找到另一个散列值位置)，因此它采用异或的方式达到目的，公式如下：

 h1(x) = hash(x)
 h2(x) = h1(x) ⊕ hash(x的指纹)

位置h2 可以通过位置h1 和h1 中存储的指纹信息计算出来，同样的位置h1 也可以通过h2 和指纹信息计算出来。

布谷鸟过滤器实现了哈希表过滤和基数统计的能力，同时存储元素信息改为存储更轻量指纹信息节约了内存，但它损失了一些精确度，比如会出现两个元素的散列位置相同，指纹也正好相同的情况，那么插入检查会认为它们是相等的，只会统计一次。但同样这个误差率是可以接受的。

8.5. HyperLogLog

说到基数统计，就不得不提Redis 里面的HyperLogLog 算法了，前文所说的哈希表，位图，布隆过滤器和布谷鸟过滤器都是基于记录元素的信息并通过过滤(或近似过滤)相同元素的思想来进行基数统计的。

而HyperLogLog 算法的思想不太一样，它的基础是观察到可以通过计算集合中每个数字的二进制表示中的前导零的最大数目来估计均匀分布的随机数的多重集的基数。如果观察到的前导零的最大数目是n，则集合中不同元素的数量的估计是。

怎么理解呢?其实就是运用了数学概率论的理论，以抛硬币的伯努利试验为例，假设一直尝试抛硬币，直到它出现正面为止，同时记录第一次出现正面时共尝试的抛掷次数k，作为一次完整的伯努利试验。那么对于n 次伯努利试验，假设其中最大的那次抛掷次数为。结合极大似然估算的方法，n 和中存在估算关联关系即：。

对应于基数统计的场景，HyperLogLog 算法通过散列函数，将数据转为二进制比特串，从低位往高位看，第一次出现1 的时候认为是抛硬币的正面，因此比特串中前导零的数目即是抛硬币的抛掷次数。因此可以根据存入数据中，转化后的二进制串集中最大的首次出现1 的位置来估算存入了多少不同的数据。

这种估算方式存在一定的偶然性，比如当某次抛硬币特别不幸时，抛出了很大的值，数据会偏差的厉害，为了降低这种极端偶然性带来的误差影响，在HyperLogLog 算法中，会将集合分成多个子集(分桶计算)，分别计算这些子集中的数字中的前导零的最大数量，最后使用调和平均数的计算方式将所有子集的这些估计值计算为全集的基数。例如redis 会分为16384 个子集进行分桶求平均统计。

9. 其他常用算法

9.1. 时间轮定时器

定时器的实现方式有很多，比如用有序链表或堆都可以实现，但是他们或插入或运行或删除的性能不太好。时间轮定时器是一种插入，运行和删除都比较理想的定时器。

时间轮定时器将按照到期时间分桶放入缓存队列中，系统只需按照每个桶到期顺序依次执行到期的时间桶节点中的所有定时任务。

次の図に示すように:

而针对定时任务时间跨度大，且精度要求较高的场景，使用单层时间轮消耗的内存可能比较大，因此还可以进一步优化为采用层级时间轮来实现，层级时间轮就类似我们的时钟，秒针转一圈后，分针才进一格的原理，当内层时间轮运转完一轮后，外层时间轮进一格，接下来运行下一格的内层时间轮。

9.2. 红包分配

算法很简洁，该算法没有预先随机分配好红包金额列表，而是在每个用户点击抢红包时随机生成金额，该算法只需传入当前剩余的总金额和剩余需要派发的总人数，算法的基本原理是以剩余单个红包的平均金额的2 倍为上限，随机本次分配的金额。

这个算法的公平性在于每个领红包的人能领取到的金额是从0 到剩余平均金额的2 倍之间的随机值，所以期望就是剩余平均金额，假设100 元发给5 个人，那么第一个人领取到的期望是20 元，第2 个人领取到的期望是(100-20)/ 4 = 20 元，通过归纳法可以证明每个人领取到的期望都是20 元。但是由于每个人领取到的金额随机范围是不一样的，如第一个人能领取到的范围是0 到40 元，而最后一个人能领取到的范围是0 到100 元，因此方差跟领取的顺序是有关系。这也告诉我们抢微信红包想稳的人可以先抢，想博的人可以后抢。

这种分配算法的好处是无状态化，不需要在创建红包时预先分配并存储金额列表，在某些场景可能会对性能带来好处。

9.3. 有缘再续

优秀的算法还有很多，有缘再续。

10. 总结

笔者曾经写过一篇《服务器开发设计词汇宝典》，讲述了一些后台程序架构和系统方面的设计知识，如果把架构设计比做程序员的内功修炼的话，那么算法就是战斗中的招式，选择合适的算法能让你的代码化繁为简，或高效或优雅，见招拆招，起到四两拨千斤的效果的同时震撼心灵。

很多算法的思想都有一些共通性，他们用到的基础思想都有相似之处，如随机，分治递归，多策略相结合，一次不行再来一次等思想。比如随机，这个在服务器开发设计中随处可见的策略，yyds，随机带来的是一种个体偶然性与总体必然性的结合，在jump consistent hash 算法，跳表排序算法、带权重的A-ExpJ 算法蓄水池抽样等算法中都使用了随机跳跃的思想，实现了在无需统计状态数据的情况下，利用随机的整体均衡性来保证算法正确性的同时极大的简化了算法和提高了效率。

学习和研究优秀的算法目的是希望能在实际应用场景中做到灵活运用，取长补短，甚至能结合不同算法思想启发创造出适合各种问题场景的算法策略。

由于个人水平有限，文中难免有所纰漏，欢迎指正。

参考文章

《The Power of Two Random Choices》

《The Art of Computer Programming (vol. 2_ Seminumerical Algorithms) (3rd ed.)》

《Fisher–Yates shuffle》wikipedia

《Random Sampling with a Reservoir》JEFFREY SCOTT VITTER

《Weighted Random Sampling》(Efraimidis, Spirakis)

《Weighted random sampling with a reservoir》(Efraimidis, Spirakis)

《Reservoir sampling》wikipedia

《十大经典排序算法》菜鸟教程

《多路平衡归并排序算法》

《TDigest 算法原理》

《ElasticSearch 如何使用TDigest 算法计算亿级数据的百分位数?》

《分位数算法总结》

《Handling Overload》

《zigzag 算法详解》

《数据序列化格式》wikipedia

《markdown》百度百科

《拥抱protobuf，迎接TDR 2.0 时代》 km 文章

《Compress》https://gitee.com/yu120/compress

《无损压缩算法》wikipedia

《LZ77 与LZ78》 wikipedia

《公开密钥加密》wikipedia

《哈希链》wikipedia

《常用缓存淘汰算法LFU/LRU/ARC/FIFO/MRU》

《LIRS caching algorithm》wikipedia

《缓存淘汰算法LIRS 原理与实现》

《MySQL 5.7 Reference Manual》

《布隆过滤器过时了，未来属于布谷鸟过滤器?》

《HyperLogLog 算法的原理讲解以及Redis 是如何应用它的》

《关于基数统计》

《算法导论(第2 版)》