This post originated from an RSS feed registered with Java Buzz
by Talip Ozturk.
Original Post: Hazelcast Internals 4: Distributed Map
Feed Title: Shared Memory
Feed URL: http://www.jroller.com/talipozturk/feed/entries/rss
Feed Description: about java, jcache, jini, javaspaces, distributed data structures and a little bit of me and life.
Hazelcast distributed map is a peer to peer, partitioned implementation so entries put into the map will be almost evenly partitioned onto the existing members. Entries are partitioned according to their keys.
Every key is owned by a member. So every key-aware operation, such as put, remove, get is routed to the member owning the key.
How does Hazelcast determine the owner of a key?
Hazelcast creates fixed number of virtual blocks (segments). Block count is set to 271 by default. Each key fall into one of these blocks. Each block is owned/managed by a member. Oldest member of the cluster will assign the ownerships of the blocks and let every member know who owns which blocks. So at any given time, each member knows the owner member of a each block. Hazelcast will convert your key object to com.hazelcast.nio.Data then calculate the block of the owner: block-of-the-key = hash(keyData) % BLOCK_COUNT. Since each member(JVM) knows the owner of each block, each member can find out which member owns the key.
Can I get the owner of a key?
Hazelcast internally knows the owner of each key but it is exposed to the developer. So there is no getKeyOwner (key) like API available yet. The reason is that key ownership is dynamic; the key owner might change right after you looked up for it so you might end up working with the wrong key and/or the owner.
Key ownership might change when a member joins or leaves the cluster due to recovery or load balancing. So 99.9% of the time, the owner of a key will not change but it is still not 100%.
Since it is highly requested, we are looking to provide a way to work with the locally owned keys.
What happens when a new member joins?
Just like any other member in the cluster, the oldest member also knows who owns which block and what the oldest member knows is always right. The oldest member is also responsible for redistributing the block ownerships when a new member joins. Since there is new member, oldest member will take ownership of some of the blocks and give them to the new member. It will try to move the least amount of data possible. New ownership information of all blocks is then sent to all members.
Notice that the new ownership information may not reach each member at the same time and the cluster never stops responding to user map operations even during joins so if a member routes the operation to a wrong member, target member will tell the caller to re-do the operation.
If a member's block is given to the new member, then the member will send all entries of that block to the new member (Migrating the entries). Eventually every member in the cluster will own almost same number of blocks, and almost same number of entries. Also eventually every member will know the owner of each block (and each key).
How about distributed set and list?
Both distributed set and list are implemented on top of distributed map. The underlying distributed map doesn't hold value; it only knows the key. Items added to both list and set are treated as keys. Unlike distributed set, since distributed list can have duplicate items, if an existing item is added again, copyCount of the entry (com.hazelcast.impl.ConcurrentMapManager.Record) is incremented. Also note that index based methods of distributed list, such as List.get(index) and List.indexOf(Object), are not supported because it is too costly to keep distributed indexes of list items so it is not worth implementing.
Check out the com.hazelcast.impl.ConcurrentMapManager class for the implementation. As you will see, the implementation is lock-free because ConcurrentMapManager is a singleton and processed by only one thread, the ServiceThread.
Previous Topic
