scale out の技術 〜 consistent hashing 編 (cloud 研究会, December 19, 2008)
scale out の技術 〜 consistent hashing 編 首藤 一幸 2008年 12月 19日 cloud 研究会 (丸山不二夫氏主宰) スライド: shudo-cloud-scaleout-20081219.pdf (PDF ファイル, 840 KB) 関連資料: オーバレイによる分散キャッシュ: ウェブページ (21 pages, HTML) Unstructured overlay と Sturectured overlay: ウェブページ (34 pages, HTML) Back to Publications のページ 首藤のページ scale out の方策
Consistent Hashing は、 複数のノードにレコードを分散させる方法として、 Amazon Dynamo や Cache::Memcached::Fast などで使われているアルゴリズムです。 この文章では、Perl で実際に Consistent Hashing を実装し、 その特徴を理解することを目的とします。 更新履歴 2008-06-01: 公開 サーバー台数で割った余り (mod) を使用する まず Consistent Hashing と比較するために、レコードに対して整数のハッシュ値を求め、 ハッシュ値をノード数で割った余り (mod) で、ノードを選択するという方法を書いてみます。 ここでは、ハッシュ値の算出に CRC (Cyclic Redundancy Check) を使用しています。 use strict; use String::CRC; use Pe
Node.js から Key Value Store などを利用する際に、キーを複数のノードに分散させる汎用的なライブラリがあったら便利なのではと思い実装してみました。 ソースコードはGitHubで公開しています。ライセンスはMIT Licenseとします。 git clone git://github.com/dakatsuka/node-consistent-hashing.git また、npmでもインストール出来るようにしました。 npm install consistent-hashing 使い方# 基本的な使い方は下記の通りです。 var ConsistentHashing = require('consistent-hashing'); var cons = new ConsistentHashing(["node1", "node2", "node3"]); console.
Consistent Hashing を使うべきケース、使う必要がないケース - kazuhoのメモ置き場
Consistent Hashing が便利なのは、頻繁にノードが上がったり落ちたりする環境で、ネットワークレベルで可用性を保証する必要がある場合。逆に RDBMS のシャーディング等で ノード毎に高可用性を確保している ノード追加／削除は頻繁じゃない 場合は、値域分割が有力な選択肢になる。値域分割であれば、 範囲を指定したイテレーション 障害の影響範囲の局所化 (特定のユーザーが入っているノードだけが落ちるとか) 値域毎の負荷に応じた分割 といったことが可能。Pacific は、このアプローチです。
Consistent Hashingについては以下を参照。要は「キャッシュを分散させた場合で分散させる数が変わったときに、「orz」とならないようにするための仕組みの1つ」な感じです（多分）。 http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashing mixi engineer blog で、それを実現するためのCライブラリとしてlibketamaがあります。 API – Last.fm このlibketamaのソースにはPython、Java、PHPの各バインディングが含まれているようなので、ちょっと使ってみました。 まずは、ソースをcheckout。使用リビジョンは398です。 $ svn co svn://svn.audioscrobbler.net/misc/ketama $ build手順は以下の通り。Makefileを置換
RJ のジャーナル - libketama - a consistent hashing algo for memcache clients | Last.fm
2007年 04月 11日 水曜日 02:36 We wrote ketama to replace how our memcached clients mapped keys to servers. Previously, clients mapped keys->servers like this: server = serverlist; 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 enough t
libmemcached でconsistent hashing id:kazeburoさんのYAPCでの話でlibmemcachedがconsistent hashing使えないと言われてしまったのを知らなかったのだけど、先週の金曜Brian Akerのセッションでそのことを知ったので調べてみたよ！ テストはこのように書いてみました。 するとようやく現象が確認できました。で、問題はどこかと調べてみたところ・・・libmemcached C ライブラリでした＞＜ libmemcached 0.20以降でこの現象は直ってるはず。 なお、これを調べてる時にMemcached::libmemcached + Cache::Memcached::libmemcachedでマスターキー付きのget/setがうまくできないことが判明。これは次のリリースで直る予定。近々リリース予定の0.2101では、
Consistent Hashing with Clojure
Consistent Hashing with Clojure Let's say you want to distribute some objects to a number of nodes. The Naive approach to this problem would be to hash the object you want to store, then using the modulus operator pick a node and store it there, (mod (hash obj) n) This scheme would work until you add or remove nodes from the cache, now because you pick nodes from a pool of (+ n 1) or (- n 1) nodes
Consistent hashing - Wikipedia
In computer science, consistent hashing[1][2] is a special kind of hashing technique such that when a hash table is resized, only keys need to be remapped on average where is the number of keys and is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped because the mapping between the keys and the slots is de
Consistent Hashing:
Slide 1 of 37
Consistent Hashingとは Consistent Hashingはハッシュテーブルアルゴリズムの１つです。 ハッシュテーブルのサイズの変更をしても柔軟にマッピングできるため、ノードの追加・削除が発生する分散データベースやキャッシュの保存先を決定するといった用途に使われます。 アルゴリズムの説明 ハッシュ化 例えば入力値を0~99の値に変換するハッシュ関数を用意します。 ノードのIDをそのハッシュ関数で変換すると以下のように配置されたとします。 次にデータも同じようにハッシュ関数で変換し、以下のように配置されたとします。 マッピング データのハッシュ値と同じorより大きな値の中で最も近いノードにマッピングします。 自分よりも大きなハッシュ値を持つノードが存在しない場合は、最小のハッシュ値のノードにマッピングします。 これがConsistent Hashingです。 ノードの追加
GitHub - debasishg/scala-redis: A scala library for connecting to a redis server, or a cluster of redis nodes using consistent hashing on the client side.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
あ、どうも、マタノ兄弟商会のマタノです。 んで、ここのところmemcachedでconsistent hashingを実現する方法についてあれこれ調べているのですが、いったん整理しました。 ◆libmemcached memcacheのクライアントライブラリ ◆libketama memcacheのconsistent hashingアルゴリズムライブラリ ◆php_ketama ketamaに同梱のPHP版ketamaインターフェース（PHP拡張モジュール） ◆PECL memcached PHP本家がリリースしているlibmemcachedインターフェース（PHP拡張モジュール） で、それぞれのconsistent hashingの動作とマッピングの互換性を検証してみました。 ■consistent hashingについて ▼libmemcached memcached_behavio
RJ’s Journal – libketama - a consistent hashing algo for memcache clients – Last.fm
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 eno
あ、どうも、マタノ兄弟商会のマタノです。 PHPでmemcachedのconsistent hashingを実現する方法をば。 というか、PHPの拡張モジュール「Memcached」を使えば、簡単に実現可能なのですが、その導入手順についてもう少し詳しく書いてみます。 以下、必要ライブラリ等のインストール手順です。 （実施環境はCentOS5.2 x86_64、memcached自体はすでにインストール済みという前提で） ■libketamaのインストール consistent hashingのアルゴリズム用ライブラリです。 『libketama – a consistent hashing algo for memcache clients』 ◆SVNリポジトリから、最新リビジョンをチェックアウト svn://svn.audioscrobbler.net/misc/ketama/ READ
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
"Dynamo-style" に学ぶ Replication, Partitioning, Consistent Hashing の気持ち 先日、DynamoDB設計の背景にあった可用性とスケーラビリティの両立に対するAmazonのアツい想いについて書いた： AmazonのDynamoDB論文を眺めた 背景だけだと寂しいので、ここではもう少し詳しく、DynamoDBの実装を支える Replication と Partitioning の基本、そして Consistent Hashing について、"Designing Data-Intensive Applications" (DDIA) の解説も踏まえてまとめておく。 Replication DynamoDB（分散DB）が考えるべき問題の1つに、データのコピーをネットワーク上の複数のマシン（ノード）で保持する Replication（レプ
Consistent Hashing
Tom White's Blog: Consistent Hashing(翻訳: ConsistentHashing - コンシステント・ハッシュ法)でconsistent hashingというアルゴリズムを知った。大略こういうことらしい。 問題 複数台のキャッシュサーバがあり、オブジェクトのキャッシュをどのサーバに配置するかを決めたい。 普通のハッシュ利用法だとどうなるか オブジェクトのハッシュ値 mod N (Nはキャッシュサーバの台数)で決める。 しかし、これではキャッシュサーバを追加したり削除したりすると全てのオブジェクトのキャッシュ配置先が変わってしまう。 望ましいのは キャッシュサーバを追加すれば既存のサーバから少しずつ分担が新しいサーバに移動し、キャッシュサーバが取り除かれれば残りのサーバに負担が分散、それ以外のオブジェクトのキャッシュ先は変わらない、というのがよい。 Con
Consistent Hashing
I've bumped into consistent hashing a couple of times lately. The paper that introduced the idea (Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web by David Karger et al) appeared ten years ago, although recently it seems the idea has quietly been finding its way into more and more services, from Amazon's Dynamo to memcached (courtesy
GitHub - 3rd-Eden/memcached: A fully featured Memcached client build on top of Node.js. Build with scaling in mind so it will support Memcached clusters and consistent hashing.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
自作 memcached-client に必要だったので、ConsistentHashing - コンシステント・ハッシュ法 の解説を参考に Erlang で Consisten Hashing を実装した。 環状の配置は ETS の orderd_set を利用している。 レプリカを挿入しているところと get_node で next, first を使っているあたりが肝。 -module(chash). %% API -export([new/1, delete/1, add_node/3, remove_node/2, get_node/2]). -define(NUMBER_OF_REPLICAS, 100). %%==================================================================== %% API %%======
Improving load balancing with a new consistent-hashing algorithm
We run Vimeo’s dynamic video packager, Skyfire, in the cloud, serving almost a billion DASH and HLS requests per day. That’s a lot! We’re very happy with the way that it performs, but scaling it up to today’s traffic and beyond has been an interesting challenge. Today I’d like to talk about a new algorithmic development, bounded-load consistent hashing, and how it eliminates a bottleneck in our vi
GitHub - dchiji/Cradle: Consistent Hashing とあるプロジェクトの一環で作ったプログラムで、突然あるノードが落ちても一瞬でネットワーク再構成/データ復旧することが可能な程度の耐障害性が特徴です。 Consistent Hashingということで、当然のことながらデータ保持時の負荷分散もサポートしています。 実用に耐えるのは難しいかもしれませんが、簡易KVSとして試用しても良いレベルだと思っています。 利用するにはErlang処理系をインストールしておく必要があり、テストにはR12B-5を使用しました。 使用方法 準備 src/dssg.erlをダウンロードして $ erlc dssg.erl を実行しておきます。 新規ノードを立ち上げる start関数を引数無しで呼び出すことにより、新規ノードを立ち上げることができます。 また、ノード追加時に必要なノ
Philosophy We strive to create an environment conducive to many different types of research across many different time scales and levels of risk. Learn more about our Philosophy Learn more
Consistent Hashing
Slide 19 of 37
memcache_servers = ['192.168.0.246:11212', '192.168.0.247:11212', '192.168.0.249:11212'] ring = HashRing(memcache_servers) server = ring.get_node('my_key') The motivation behind hash_ring Consistent hashing is really neat and can be used anywhere where you have a list of servers and you need to map some keys (objects) to these servers. An example is memcached or a distributed system. A problem whe
Today I get back into my post series about the Google Technology Stack, with a more detailed look at distributed dictionaries, AKA distributed key-value stores, AKA distributed hash tables. What we’d like to do is store a dictionary of key-value pairs [tex](k_1,v_1),(k_2,v_2),\ldots[/tex] across a cluster of computers, preferably in a way that makes it easy to manipulate the dictionary without hav
GitHub - RJ/ketama: C library for consistent hashing, and langauge bindings
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
GitHub - acrosa/scala-redis: A scala library for connecting to a redis server, or a cluster of redis nodes using consistent hashing on the client side.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
In recent years, with the advent of concepts such as cloud computing and big data, distributed systems have gained popularity and relevance. One such type of system, distributed caches that power many high-traffic dynamic websites and web applications, typically consist of a particular case of distributed hashing. These take advantage of an algorithm known as consistent hashing. What is consistent
Consistent hashing vs order-preserving partitioning in distributed databases
The Cassandra distributed database supports two partitioning schemes now: the traditional consistent hashing scheme, and an order-preserving partitioner. The reason that almost all similar systems use consistent hashing (the dynamo paper has the best description; see sections 4.1-4.3) is that it provides a kind of brain-dead load balancing from the hash algorithm spreading keys across the ring. Bu
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Consistent Hashing を試す
Consistent HashingをNode.jsで実装してみた
Consistent Hashingな拡張モジュール - Do You PHP はてブロ
libmemcached でconsistent hashing - D-6 [相変わらず根無し]
Consistent Hashing （コンシステントハッシュ法） - Carpe Diem
» [memcached]consistent hashingの動作とマッピングの互換性手間を惜しまず
» PHPでmemcachedのconsistent hashingを実現する手間を惜しまず
"Dynamo-style" に学ぶ Replication, Partitioning, Consistent Hashing の気持ち
Erlang で Consistent Hashing 実装 - higepon blog
耐障害性の高いConsistent Hashingを実装してみる - kyeeva blog!
Consistent Hashing with Bounded Loads
Consistent hashing implemented simply in Python - amix blog
Consistent hashing – Michael Nielsen
A Guide to Consistent Hashing | Toptal®