分散ハッシュテーブルには長所と短所の両方があります。 DHTは適切にスケーリングしますが、競合の競合によるデータ損失が発生する可能性があるため、次の例を検討してください。
client a: def o-value = DHT.get("some-key");
client a: def a-value = changeValue(o-value);
client b: def o-value = DHT.get("some-key");
client a: DHT.put("some-key", a-value);
client b: def b-value = changeValue(o-value);
client b: DHT.put("some-key", b-value);
クライアントbがクライアントaのデータを書き換えたが、それについて誰も知らないことが判明した（a、bも、このキーのデータを後で読む人もいない）。
多くのNoSQLデータベースには基本的にDHTがあるため、同時アクセスの問題をどのように解決しようとするのかを見るのは興味深いです。
たとえば、MongoDBは比較とスワップ戦略を使用します：各ドキュメント（値）のバージョンが保存され、更新時に、更新時に祖先がデータベースに保存されている場合、変更されたドキュメントの「祖先」のバージョンが示されます。アップデーターはメッセージを受信し、再度アップグレードを試みます-STMの類似物。 このアプローチはシャードではうまく機能しますが、レプリケーションでは不十分です。
Riakは、バージョン管理システムのような同時アクセスの問題を解決します。つまり、競合するバージョンを異なるブランチに保存し、マージを実行する次のフェッチをプログラムに提供します。 このアプローチにより、競合するアクセスだけでなく、クラスターの一部の一時的な分離に関連する競合を解決できます（パーティションの許容範囲：マシンのクラスターは2つの部分に分割でき、両方の部分が機能し、将来問題なく団結できます）。
Riakはより多くの開発条件を課しますが、大量の情報を扱う場合、データのスケーラビリティと信頼性を提供します。 この記事では、一般的なWebアプリケーションを開発する際にRiakの制限を回避する方法について説明します。
ブログ
Riakに基づいて実装された最初のプリミティブ（小さなサイズの追加専用リスト）を検討してください。
ブログを書いているところを想像してみてください。各投稿のコメントはそれほど多くなく、追加後にコメントを変更することはできません。 この場合、コメント付きの投稿全体を値として保存するのが妥当であるため、読み取り操作はO（1）を通過します。 データのスキームを説明しましょう：
public class Post { public static class Comment implements Comparable<Comment> { public String text; public int ts; //timestamp /* equals, hashCode, compareTo*/ } public String text; public List<Comment> comments; }
次に、2人のユーザーが「同時に」コメントを追加したとします。
client a: def o-post = DHT.get("post/13");
client a: def a-post = addComment(o-value, " , ");
client b: def o-post = DHT.get("some-key");
client a: DHT.put("post/13", a-post);
client b: def b-post = addComment(o-post, " ");
client b: DHT.put("post/13", b-post);
これで、2つのエントリがID「post / 13」でデータベースに保存されます。 このキーを最初に申請した人は両方を受け取り、自分で絞め殺す必要があります。 簡単にするために、投稿を編集できないと仮定して、「ブランチ」からの投稿が適切であり、コメントしか追加できないため、両方の投稿のコメントリストに共通のプレフィックスがあるため、それを選択してプレフィックスから新しいリストを作成する必要があります。最初のリストへの追加と2番目のリストへの追加。 マージ操作は次のようになります。
public static Post merge(Post a, Post b) { Post c = new Post(); c.text = a.text; c.comments = Mergers.mergeLists(a.comments, b.comments); return c; }
mergeListsは次のように定義されています。
public static <T extends Comparable<T>> List<T> mergeLists(List<T> a, List<T> b) { List<T> result = new ArrayList<T>(); List<T> rest = new ArrayList<T>(); int max = Math.min(a.size(), b.size()); int i=0; // for(;i<max && a.get(i).equals(b.get(i));i++) { result.add(a.get(i)); } // for(int j=i;j<a.size();j++) { rest.add(a.get(j)); } for(int j=i;j<b.size();j++) { rest.add(b.get(j)); } // Collections.sort(rest); // for(T item : rest) { result.add(item); } return result; }
明らかに、mergeListsはセットの和集合に非常に類似しているため、一部の要素がaまたはbにあった場合、結果リストに含まれるため、マージ時にデータの損失はありません。 これで、競合アクセスの問題を回避しながら、Riakのリストに書き込む方法を学びました。
複数の投稿をずらす必要がある場合は、折りたたみコンビネーター内でマージを使用します。
アラート（メッセージ、更新）
次のプリミティブは、削除可能な固定サイズのリストです。 最大サイズに達すると、いくつかの要素がスローされます（たとえば、最も古いものですが、分散システムではこの概念は非常に条件付きです）。 リストのサイズは固定されているため、リスト全体を1つの値として再度保存します。
あらゆる種類の通知がこのプリミティブによく当てはまります。 まず、イベント通知はイベント自体ほど重要ではありません。 第二に、ユーザーが長時間ログインしていない場合に、ユーザーが古いイベントに関する通知を見たいとは考えにくい。 第三に、ユーザーが既にイベントに関する情報を調査している場合は、通知を削除する必要があります。
オブジェクトの1つのリストが値として保存されていた以前のスキームとは異なり、2つのリストがここに保存されます。「通知」のリストと削除された「通知」のリストです。 マージの場合、対応するリストがマージされるため、削除されたオブジェクトは削除されたオブジェクトのリストに残り、追加されたオブジェクトのリストに追加されたオブジェクトが残ります（当然、マージ後、削除されたオブジェクトは減算する必要があります）。 もっと正式に書く：
問題は、この操作の定義では、必要なプリミティブを実装しているにもかかわらず、リストが無限に大きくなることです。 これらのリストを制限してみましょう：追加されたオブジェクトのリストが最大になった場合-削除されたオブジェクトのリストにオブジェクトを転送し、削除されたオブジェクトのリストが成長した場合-オブジェクトを削除します。
追加、削除、およびマージの各操作の後、ram操作を実行する必要があります。 リストの長さを制限することで、何かを失い、ほとんどの場合、望ましくない動作を獲得したことは明らかです。 試してみましょう。 私たちの場合（オブジェクトの損失が定期的な問題である場合）、唯一の望ましくない動作は、すでにリモートアラートが表示されていることです。 この指標を測定するために、プロセスをモデル化し、一連の観察を行いました。 エラーの数がリストの長さとリクエストの処理時間とリクエストの頻度の積に依存することは明らかです（これは本当にそうです、私はチェックしました）。このパラメーターキーを呼び出します。 以下に、ダイナミクスを理解できるグラフをいくつか示します。
リストの長さによる書き込みエラーの割合
グラフはリストの変更の割合を反映し、その後、リスト内の要素の最大数に応じて、リモートの「アラート」が新しいものとして再表示されます。 キーパラメータは修正されました（0.8および2）。これは、1秒あたり約8リクエストおよび1秒あたり20リクエストに相当します。 それが見かけほど小さくないことは以下に書かれます。
キーパラメータからの書き込みエラーの割合
グラフは、固定リスト長（それぞれ30および130要素）のキーパラメーターに依存するエラーの割合のダイナミクスを示します。
1％のエラー領域
キーパラメーターは横軸に沿ってプロットされ、赤い線は値1を表します。 縦座標はリストの長さで、赤い線は100、200、300の要素に対応しています。 黒は、エラーが1％未満のパラメーターのゾーンをマークします。
毎秒10リクエストが見かけほど少なくない理由。 まず、書き込み要求のみが考慮されます。次に、これは要求の総数ではなく、1つのオブジェクトに対する要求の数です。 たとえば、Google +を設計する場合、1秒あたり10件のリクエストは、すべてのGoogleへの呼び出しの数ではなく、1つのレコードに対するコメントの予測頻度です。
ストリーム（VKontakteの壁またはTwitterのテープ）
この記事の最後のパターンは大きなリストであり、レコードを最後に追加したり、レコードを末尾と先頭の両方から読み取ったり、1回の要求で複数のレコードを受信したりできます。 リストからの削除はほとんどないと想定されています。
このプリミティブは、Twitterのフィードとソーシャルネットワークの壁をうまく説明していますが、他の用途も考えられます。
1つのキーと値のペアで記述された以前のスキームとは異なり、このパターンは、リストの開始と終了に関する情報を含むサービスキーと値のペア、およびリストからの固定サイズセグメントが格納されるデータチャンクによって記述されます。 日付モデルと、各データ型のマージ操作を定義します。
class Info { public String key; public String prefix; public int lastChunk = 0; public String getChunkKey(int chunk) { return prefix + chunk; } public Info mergeWith(Info brother) { Info info = new Info(); info.key = key; info.prefix = prefix; info.lastChunk = Math.max(lastChunk, brother.lastChunk); return info; } } class Chunk<T extends Comparable<T>> { public String key; List<T> added = new ArrayList<T>(); List<T> deleted = new ArrayList<T>(); public void add(T obj) { added.add(obj); } public void delete(T obj) { deleted.add(obj); } public Iterable<T> getData() { List<T> data = new ArrayList<T>(added); data.removeAll(deleted); return data; } public Chunk<T> mergeWith(Chunk<T> brother) { Chunk<T> chunk = new Chunk(); chunk.key = key; chunk.added = mergeLists(added, brother.added); chunk.deleted = mergeLists(deleted, brother.deleted); return chunk; } }
操作は明らかだと思います。 リストにアイテムを追加する場合：
- 各リストに対応する情報を取得します
- 最後のチャンクを決定して取得する
- 完了していない場合は、レコードを追加してチャンクを保存します
- それ以外の場合は、新しいチャンクを作成し、レコードを追加して保存します。 さらに、情報の最後のチャンクへの「ポインター」を編集し、保存します
おわりに
この記事からわかるように、Riakでは、Webで一般的なデータスキームを使用して、これらのデータを複数のノードに簡単に配布できます。 これは、Riakがプログラマーに提供する一連のプリミティブにより実現されます。
競合の解決に対する透過的なアプローチと、各リクエストの制限（CAP）を選択する柔軟性のために、Riakアプローチが好きでした。