「スペースを時間で交換する」アルゴリズムはキャッシュの世界へとあなたを導きます

私たちは、アルゴリズムの時間計算量や空間計算量についてよく考えます。時間や空間が十分にある場合、そのアルゴリズムは必要ありません。残念ながら、この条件は存在しません。ただ、相対的に言えば、場合によっては、どちらか一方を考慮する必要がないのです。今日議論している「キャッシュ」は、当然ながら「スペースと時間を交換する」アルゴリズムです。キャッシュは、メモリやハードディスクなどの場所にデータを一時的に保存することです。つまり、時間のかかる特定の操作を回避することが目的です。一般的に時間のかかる操作には、データベースのクエリ、一部のデータの計算結果、またはサーバーへの負荷を軽減することが含まれます。実際、クエリや計算は短くて時間のかかる処理ですが、非常に頻繁な操作であり、累積時間も非常に長いため、サーバーが耐えられないほどの深刻なキューなどが発生するため、圧力も軽減されます。

概念的な事柄については、ほとんどが単なる物語になってしまうので、今は話しません。それでは、さまざまなキャッシュについて説明しましょう。

.NET を初めて使う友人は、まず DataSet クラスに触れます。彼らは、DataSet のサンプル プログラムをぼんやりと見て、それが何なのか気にせずにそのまま使用します。実際、DataSet はキャッシュです。データセットを読み取るときに、読み取られるデータの各部分を処理すれば、プログラムとデータベースは常に接続されます。データの処理にかかる時間がごくわずかである場合、またはデータベースを使用するのが自分だけである場合は、データベースが常に接続されているかどうかは問題ではなく、コードを書くときに DataSet クラスを使用する必要はありません。しかし、実際には、時間がかからないということは不可能です。時間がかかると、処理が完了するまでデータベース接続が占有されてしまいます。このようなクエリが多すぎると、接続数が多すぎて、データベースが特定の操作中にテーブルをロックし、他のリクエストが待機することになり、クエリのタイムアウトやプログラム例外などが発生します。したがって、最初にデータを取得し、次にデータを処理し、データベースが他の要求を処理できるように、できるだけ早くデータベース接続を閉じる必要があります。 したがって、適切なタイミングで DataSet または DataReader を選択することが重要です (注: DataReader は接続を保持する読み取り方法です)。

混乱して、気づかないうちにキャッシュ (DataSet) を使用している可能性がありますが、これは .net が実行していることです。ただし、キャッシュの使用方法や、いつキャッシュを使用するかについてはまだわからない場合があります。心配しないでください。一つずつ見ていきます。

前述のように、キャッシュするデータは、一部のデータベース クエリ、計算結果、頻繁に実行されるクエリのみです。では、実際の開発ではどのようなデータに遭遇するのでしょうか? 実際、よく考えてみると、これは非常によくあることです。たとえば、ユーザーがログインしてリンクをクリックするたびにページが更新される場合、必ずしもデータベースを再クエリできるとは限りませんよね?よく、人の情報を保存するのに Session を使用します。人がシステムからログアウトすると、Session はクリアされます。つまり、Session はキャッシュでもありますが、.NET が提供する優れたクラスでもあります。すみません、見たくない例をもう 1 つ挙げてしまいました。実際、セッションはプライベート データであり、セッション データへのアクセスは SessionID を介して行う必要があります (詳細は説明しません。Google で検索してください)。これだけでは、キャッシュの重要性を説明するには不十分です。この質問を拡張すると、マルチユーザー ブログ システムを開発していて、いずれかのブログにアクセスするたびにブロガーの情報を照会する必要があるとします。A と B が同時にブログにアクセスする場合、理想的な状況は、両方がデータベースにアクセスするのではなく、1 回だけ照会することです。これは正しいですか?実は。 。 。はい、そしていいえ！（物語の中では、はいと言えばそれははいであり、いいえと言えばそれはいいえであり、いいえと言えばそれはいいえであり、そしてまたいいえでもあります。:)。私が「いいえ」と言う理由は、ブログのウェブサイトに毎日数人しかアクセスせず、開発も進まない場合、キャッシュを使用する必要がないからです。キャッシュを使用すると開発がさらに複雑になり、ブロガーの情報を更新するたびにデータベース情報を更新するだけでなく、キャッシュも処理する必要があるためです。しかし、Blog Garden のようにブログのトラフィックが多い場合は、キャッシュしないと、データベース サーバーはずっと前にゲーム オーバーになっていたでしょう:)。そこで、キャッシュの使用方法を確認しましょう。

.Net Framework には、使用できる既製のキャッシュ クラスが用意されており、最も一般的なのは System.Web.HttpRuntime.Cache です。 BlogDataProvier.GetBlogInfo() メソッドを実行するたびに (名前が示すように、このメソッドはブロガー情報を取得する方法であると想定します)、クエリを実行する前にキャッシュからデータを取得する必要があります。データが存在しない場合は、データベースからデータを取得し、結果をキャッシュに保存して、結果を返す必要があります。以下に、キャッシュを使用したことがない友人が概要を理解できるように、このメソッドの疑似コードを記述します。

公共 クラスSqlDataProvider
 {
公共 静的オブジェクト GetBlogInfo(文字列 ユーザー名)
 {
 //データベースから取得したBlogInfoは次のとおりです 
 nullを返します。
 }
 }
公共 クラスBlogDataProvider
 {
公共 静的オブジェクト GetBlogInfo(文字列 ユーザー名)
 {
 var cacheKey = "Blog_" + ユーザー名;
 var blog = CacheHelper.Get(cacheKey);
 if (ブログ == null)
 {
 blog = SqlDataProvider.GetBlogInfo(ユーザー名);
 CacheHelper.Set(キャッシュキー、ブログ);
 }
ブログに戻る;
 }
 }
公共 クラスCacheHelper
 {
公共 静的オブジェクト Get(文字列キー)
 {
 System.Web.HttpRuntime.Cache.Get(キー)を返します。
 }
公共 静的  void Set(文字列キー、オブジェクト値)
 {
 System.Web.HttpRuntime.Cache.Insert(キー、値);
 }
 } 
 

キャッシュには、その実際の意味を表す 2 つの単語があります。1 つは「保存」で、保存するだけです。もう 1 つは「遅延」で、一時的に遅延します。キャッシュは通常、一時的な保存にのみ使用され、その運命は削除または置き換えられるため、キャッシュには時間制限の問題があります。データが期限切れにならないと言うのであれば、正直に言って、コードに直接書き込むことをお勧めします。

上記の例では、HttpCache クラスについて説明しています。これを使用すると、主にパブリック データのキャッシュ (いわゆるパブリック データとは、ユーザーがアクセスできるデータと同じデータ) を中心に、ほとんどのキャッシュの問題を解決できるようです。初心者の友人は、MSDN を読んでこのクラスの使い方を注意深く勉強してほしいと思います。本当に重要ですね。

冒頭で「スペースを時間で交換する」ことについて話しましたが、これまでは頻繁に発生するクエリをキャッシュする状況についてのみ触れてきました。スペースを犠牲にして時間をキャッシュする明らかな例はありますか?問題ありません、見ることができます！

先に言っておきますが、私の会社は現在採用活動を行っているのですが、筆記試験の質問の一つに、リストと辞書の違いと使い方を紹介するものがあります。残念なことに、多くの人にインタビューした後、良い答えをくれた学生は一人だけで、他の学生はいろいろなことを言いました。どう答えるか考えましたか？ :) 以下の内容を読んで、あなたが今考えていることと一致していて、まだやりがいのある仕事を見つける必要があると感じた場合は、私に知らせてください。

実際、List と Dictionary ジェネリックは人々を混乱させるために使われます。学生の中にはジェネリックについて話して騙されてしまう人もいます。ArrayList と Hashtable を使って質問することは完全に可能です。

リストはどのようなデータ構造ですか?配列です！しかも動的配列です。なぜ動的かというと、状況に応じて動的にスペースを適用できるからです。辞書の構造は何ですか?辞書だと答えた生徒もいました。辞書はどのようなデータ構造ですか? ハッシュ テーブル! ハッシュは、その名前が示すように、分散データのテーブルです。どうやって「分散」するのでしょうか？ 当然、それらはキーに応じて分散されており、各キーは値に対応しているため、「キーと値のペア」と呼ばれることが多く、キーと値はペアになっています。 Dictionary を配列と見なすと、各 Key のハッシュ値 (ハッシュ値とは何ですか? .net では、どの型にも int 値を返す GetHashCode メソッドがありますよね?) が配列の添え字となり、配列の要素値が値となります。したがって、Dictionary 内の Key の値を取得する場合、速度は非常に速く、既知の添え字を通じて直接値を取得でき、時間の計算量は O(1) です。速いですか？とても早いですね。しかし、すべてのキーのハッシュ値が正しいと考えたことはありますか?明らかにそうではありません。どのキーを使用するかは誰にもわからないため、辞書の配列は非常に長くなり、多くの空の位置が無駄になります。そのため、スペースと時間をトレードオフすることになります。もちろん、GetHashCode アルゴリズムは異なり、キーに対応する値の分布も異なります。比較的タイトなものもあれば、比較的ルーズなものもあります。一般的なアルゴリズムには、コンシステント ハッシュ アルゴリズムが含まれます。

辞書の実際のメモリ配分

上図に示すように、dict の分布はコンパクトではなく、多くのスペースを犠牲にしますが、最も速くデータを見つけることができるため、dict や hash や map など、名前やクラスに関係なく、すべてハッシュテーブルであり、主な目的はクエリです。したがって、ユーザー名をキーとしてブログをキャッシュすると、ユーザーはブログにアクセスするときにユーザー名を使用するため、データベースをまったく経由せずにブロガーの情報を取得するために blogId も必要ありません。

リストなどのコンパクトなデータ セットは、通常、バッチ処理に使用されます。もちろん、スペースと速度の両方を考慮したデータ構造、つまりツリー構造もあります。検索時にすべてのデータをトラバースする必要はありません。時間計算量は一般に O(logn) で、スペースはコンパクトです。コンパクトな配列ではなく、リンクされたリスト構造を使用します。したがって、前の 2 つほど時間とスペースを消費しませんが、その用途は非常に広範囲です。私たちが使用するデータベースのインデックスは基本的にツリーです。これにより、占有されるスペースが小さくなり、クエリ速度が遅くなることがなくなります。

上の段落では、ハッシュ テーブルの基本原理を紹介しました。これで、キャッシュの利点がわかりました。実際のプロジェクトでは、システムが提供する Cache クラスを使用するだけでなく、自分で Cache クラスを作成することもできます。なぜそうしないのでしょうか?へへ。変数を静的にしてパブリックにすると、グローバル変数と同じになります。どこからでもアクセスでき、十分に高速なため dict も使用します。今すぐ 1 つ書いて、戻って続行してみませんか。

先ほど「遅い」という言葉を述べました。速度を落とすにはさまざまな戦略があります。たとえば、最も一般的なのは時間キャッシュです。データは一定時間内で有効です。データにアクセスするたびに、キャッシュされたデータが期限切れかどうかを確認してから、取得するか削除するかを決定する必要があります。時間戦略に加えて、熱戦略もあります。メモリが限られているため、キャッシュは無限に適用されないため、長さを制限する必要があります。長さを制限するということは、誰かが入ることができる場合、他の誰かが出なければならないことを意味します。これは削除戦略です。すべてのキャッシュに人気度をマークし、キャッシュを追加するたびに (制限に達した場合) 最も人気のあるキャッシュを削除することができます。キャッシュが取得されるたびに、キャッシュ温度は 1 ずつ増加します。とてもユーザーフレンドリーなデザインですね。 このタイプのコードは以前のブログ投稿に掲載しました。興味のある友達にはポータルをあげます。

引き続き Blog Garden を例に挙げてみましょう。Blog Garden への訪問数はすでに非常に多いことがわかっています (正確にはどれくらい多いかはわかりませんが、過去にはコメントがタイムアウトになることがよくありました。公式チームが問題を解決した後、解決方法を説明したブログ記事を公開しました。その結果、コメントで多くの学生がなぜキャッシュが必要ないのかと質問しました:)。

ウェブサイトのトラフィックが一定レベルに達すると、1 台のマシンで大量の http リクエストを処理することが難しくなります。このとき、複数のマシンを使用する必要があります。プログラムが複数のマシンで同時に実行されていない場合は、おそらくキャッシュについて深く理解していないでしょう。なぜなら、誰もが次のような経験をしたことがあるからです。「おっと、sessio は分散できないの?」 ああ、キャッシュを 2 台のマシンに置くことはできません。どうすればいいでしょうか? ！

実際、これはあなたのせいではありません。誰かを責めたいなら、Microsoft を責めてください。 IIS のおかげで、Web プログラムは 1 つのプロセスに常駐し、各 httprequest は 1 つのスレッドで処理されるため、複数のスレッドを使用する必要もありません。それは人にとって有害で​​す、ハハ。しかし、プロジェクト経験が増え、特に大規模プロジェクトを経験すると、それは大した問題ではなくなります。これが Microsoft のせいである理由は、PHP、Ruby、およびそれらのサーバー (Apache、Nginx など) がすべてマルチプロセスであるためです。各 httprequest には 1 つのプロセスがあり、同時実行を処理するために合計で数十のプロセスが開かれます。複数のプロセスは、複数のマシンがある場合と同様に、データ共有の問題を意味します。 このとき、他の Web サービス プロセスがキャッシュにアクセスするには、共有キャッシュ プロセスが必要です。 これが、これから説明する分散キャッシュです。

2、3 年前に memcached が何であるか知らなかったとしても、当時は独自の Windows サービスを作成することがまだ一般的だったため、理解できるかもしれません。しかし、今や世界には NoSQL、MongoDB、Memcached、Redis が溢れています。まだこれらを知らないのであれば、もっとブログを読んで新しいテクノロジーを調べてください。あなたはすでに時代遅れになっています。

上記の用語はすべてキャッシュに関するものです。 NoSQL は新しいテクノロジーです。現在、NoSQL DB には多くの種類があり、MongoDB もその 1 つです。MongoDB は、従来のリレーショナル データベースとインメモリ データベースのハイブリッド データベースです。現在、非常に人気のあるデータベースでもあります。 MemCached は有名な分散キャッシュサービスですが、Redis (Remoting Dictionary Service) はご存知ですか? !当社のキャッシュ サーバーは、memcached または redis を使用できます。memcached は純粋なメモリであり、プロセスを再起動するとすべてのキャッシュが失われますが、redis はデータをハード ディスクに書き込むことができます。それぞれに利点があります。計算されたデータを保存するには、Redis の方が適しています。さらに、Redis は豊富なデータ型 (list\set\hash\string) をサポートしており、memcached よりも柔軟性があります。 これらすべてには .net ドライバーと、関連するサンプルおよびユニット テストが含まれており、公式 Web サイトからダウンロードできます。

Redis の使用に関する詳細については、Dai Zhenjun のブログ http://www.cnblogs.com/daizhj/archive/2011/02/21/1959511.html を参照してください。

ハードウェアの発展とメモリの継続的な増加により、ますます多くのキャッシュ アプリケーションが使用されるようになりました。現在、さまざまな NoSQL データベース アプリケーションが登場しています。私たちもそのペースに追いつき、新しい概念を学ばなければなりません。 上記の記事がお役に立てば幸いです。

【編集者のおすすめ】

1. PHP エンタープライズ アプリケーション向けの一般的なキャッシュ技術の詳細な解説
2. LAMP アプリケーションをチューニングする 5 つの簡単な方法: オペコード キャッシュを使用する
3. 13.1 キャッシュ
4. 7.2 データソースコントロールキャッシュ