Carpe Diem

備忘録

アルゴリズム

重み付き乱択を行う

概要 重み付き乱択アルゴリズムは結果に偏りのある抽選で ソシャゲのガチャのようにレアリティによって出現確率を変えたい リクエストを重み付けして分散したり、A/Bテストで99:1のように振り分けたい といった用途で使えます。 今回はその説明と実装方法の…

Consistent Hashing (コンシステントハッシュ法)

Consistent Hashingとは Consistent Hashingはハッシュテーブルアルゴリズムの1つです。 ハッシュテーブルのサイズの変更をしても柔軟にマッピングできるため、ノードの追加・削除が発生する分散データベースやキャッシュの保存先を決定するといった用途に…

check digitを使った誤り検出

概要 クレジットカード・シリアルナンバーなど、長くなるほど入力ミスはしやすくなります。 そんな時に毎回DBに問い合わせて正しい値かをチェックするのではなくアルゴリズムによって正しいものかどうかチェックする仕組みがcheck digit(チェックディジット…

様々なrate limitアルゴリズム

概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると…

B TreeとB+ Treeの違い

概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう?と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフ…