Split-ordered linked list: lock free hash table - くまメモ
ロックを使わず共有できるハッシュテーブル http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.7132&rep=rep1&type=pdf の論文のスライド資料を作りました。 Hashmapは大きく分けてオープンアドレッシングとクローズドアドレッシングの2種類に分かれ、こちらは後者です。 Linear-probingなどを行う物と異なり、ハッシュ値が必ず1つのバケットのみと対応するからでしょうか？ Lock-free linked-listを利用することでバケット内部での競合を解決すると共にバケットの拡張でお互いを邪魔することもありません。 Split-ordered linked list: lock free hash tableView more presentations from Kumazaki Hiroki
Scalable, Distributed Data Structures for Internet Service Construction
Next: 1. Introduction Scalable, Distributed Data Structures for Internet Service Construction Steven D. Gribble, Eric A. Brewer, Joseph M. Hellerstein, and David Culler The University of California at Berkeley {gribble,brewer,jmh,culler}@cs.berkeley.edu Abstract This paper presents a new persistent data management layer designed to simplify cluster-based Internet service construction. This self-ma
P2Pと分散ハッシュテーブル〜その１
さて、P2Pでは最近「分散ハッシュテーブル」というキーワードをよく聞きます。分散ハッシュテーブルついては後で紹介しますが、これを用いるとルーティング、検索が高速に、しかもP2Pネットワーク全体に対して適用することができます。例えば既にeMuleと呼ばれるファイル共有システムでは分散ハッシュテーブルの一種であるkademliaが使われています。ではそもそも分散ハッシュテーブルとはどういうものなのでしょうか？それを説明するにはまず検索で使われるハッシュ法を説明する必要があります。 [お知らせ]分散ハッシュテーブル（ＤＨＴ）についてわかりやすく解説したページを作りました。 ＤＨＴに興味のある方はまずこちらをご覧下さい。 分散ハッシュテーブル（ＤＨＴ）入門〜その１ ハッシュ法 今、あるデータベースを考えてください。ここには人の名前と身長が書いてあるテーブルとしましょう。例えば table_1={
libketama - a consistent hashing algo for memcache clients - Amarok Blog
We wrote ketama to replace how our memcached clients mapped keys to servers. Previously, clients mapped keys->servers like this: server = serverlist[hash(key)%serverlist.length]; This meant that whenever we added or removed servers from the pool, everything hashed to different servers, which effectively wiped the entire cache. We add (and sometimes remove) servers from the memcached pool often
最小完全ハッシュ関数の作り方
■順列型の最小完全ハッシュ関数 ０から４までの５個の数字が下のように並んでいる場合を例にして説明します。 ５個の数字の並べ方は５！通りありますので５！(=120)通りの並べ方の総てに対して0から119までの数値を一意に割り付けることが目的となります。 ３４１０２ ここでは左側から順に数字を見ていくことにします。最初の数字は３で残りの数字の個数は４個ですね。 この残れさた数字の個数分の総順列数は４！ですが、この数量を基数と言います。 つまり左端の数字が何であるかを完全に識別する為に最低限必要な基本となる重みのことです。 従って先ず最初の数字３に基数である４！を掛け算してはじき出します。 [３]４１０２ → ３＊４！ 次に左から２番目の数字ですが、ここから先はとても注意が必要です。 ２番目の数字は４で残りの数字の個数は３個です。残りの数字の個数が３個なので基数は３！になります。つまり基数が変化
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Groups
Google Code Archive - Long-term storage for Google Code Project Hosting.
http://www.inf.unibz.it/dis/teaching/DMS/lecturenotes/dms03.pdf
