EMMA Coverage Report (generated Tue Oct 27 11:32:50 PDT 2009)
[all classes][net.spy.memcached]

COVERAGE SUMMARY FOR SOURCE FILE [KetamaNodeLocator.java]

nameclass, %method, %block, %line, %
KetamaNodeLocator.java100% (2/2)100% (15/15)94%  (392/415)98%  (60.6/62)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class KetamaNodeLocator100% (1/1)100% (10/10)94%  (304/322)98%  (44.9/46)
getPrimary (String): MemcachedNode 100% (1/1)52%  (13/25)82%  (2.5/3)
<static initializer> 100% (1/1)75%  (6/8)75%  (0.8/1)
KetamaNodeLocator (List, HashAlgorithm, KetamaNodeLocatorConfiguration): void 100% (1/1)97%  (145/149)98%  (16.7/17)
KetamaNodeLocator (List, HashAlgorithm): void 100% (1/1)100% (8/8)100% (2/2)
KetamaNodeLocator (SortedMap, Collection, HashAlgorithm, KetamaNodeLocatorCon... 100% (1/1)100% (15/15)100% (6/6)
getAll (): Collection 100% (1/1)100% (3/3)100% (1/1)
getMaxKey (): long 100% (1/1)100% (6/6)100% (1/1)
getNodeForKey (long): MemcachedNode 100% (1/1)100% (36/36)100% (7/7)
getReadonlyCopy (): NodeLocator 100% (1/1)100% (63/63)100% (7/7)
getSequence (String): Iterator 100% (1/1)100% (9/9)100% (1/1)
     
class KetamaNodeLocator$KetamaIterator100% (1/1)100% (5/5)95%  (88/93)98%  (15.7/16)
next (): MemcachedNode 100% (1/1)67%  (10/15)83%  (1.7/2)
KetamaNodeLocator$KetamaIterator (KetamaNodeLocator, String, int): void 100% (1/1)100% (21/21)100% (7/7)
hasNext (): boolean 100% (1/1)100% (7/7)100% (1/1)
nextHash (): void 100% (1/1)100% (45/45)100% (5/5)
remove (): void 100% (1/1)100% (5/5)100% (1/1)

1package net.spy.memcached;
2 
3import java.util.ArrayList;
4import java.util.Collection;
5import java.util.Iterator;
6import java.util.List;
7import java.util.Map;
8import java.util.SortedMap;
9import java.util.TreeMap;
10 
11import net.spy.memcached.compat.SpyObject;
12import net.spy.memcached.util.DefaultKetamaNodeLocatorConfiguration;
13import net.spy.memcached.util.KetamaNodeLocatorConfiguration;
14 
15/**
16 * This is an implementation of the Ketama consistent hash strategy from
17 * last.fm.  This implementation may not be compatible with libketama as
18 * hashing is considered separate from node location.
19 *
20 * Note that this implementation does not currently supported weighted nodes.
21 *
22 * @see <a href="http://www.last.fm/user/RJ/journal/2007/04/10/392555/">RJ's blog post</a>
23 */
24public final class KetamaNodeLocator extends SpyObject implements NodeLocator {
25 
26 
27        final SortedMap<Long, MemcachedNode> ketamaNodes;
28        final Collection<MemcachedNode> allNodes;
29 
30        final HashAlgorithm hashAlg;
31    final KetamaNodeLocatorConfiguration config;
32 
33 
34        public KetamaNodeLocator(List<MemcachedNode> nodes, HashAlgorithm alg) {
35        this(nodes, alg, new DefaultKetamaNodeLocatorConfiguration());
36        }
37 
38    public KetamaNodeLocator(List<MemcachedNode> nodes, HashAlgorithm alg, KetamaNodeLocatorConfiguration conf) {
39                super();
40                allNodes = nodes;
41                hashAlg = alg;
42                ketamaNodes=new TreeMap<Long, MemcachedNode>();
43        config= conf;
44 
45        int numReps= config.getNodeRepetitions();
46                for(MemcachedNode node : nodes) {
47                        // Ketama does some special work with md5 where it reuses chunks.
48                        if(alg == HashAlgorithm.KETAMA_HASH) {
49                                for(int i=0; i<numReps / 4; i++) {
50                                        byte[] digest=HashAlgorithm.computeMd5(config.getKeyForNode(node, i));
51                                        for(int h=0;h<4;h++) {
52                                                Long k = ((long)(digest[3+h*4]&0xFF) << 24)
53                                                        | ((long)(digest[2+h*4]&0xFF) << 16)
54                                                        | ((long)(digest[1+h*4]&0xFF) << 8)
55                                                        | (digest[h*4]&0xFF);
56                                                ketamaNodes.put(k, node);
57                                        }
58 
59                                }
60                        } else {
61                                for(int i=0; i<numReps; i++) {
62 
63                                        ketamaNodes.put(hashAlg.hash(config.getKeyForNode(node, i)), node);
64                                }
65                        }
66                }
67                assert ketamaNodes.size() == numReps * nodes.size();
68    }
69 
70        private KetamaNodeLocator(SortedMap<Long, MemcachedNode> smn,
71                        Collection<MemcachedNode> an, HashAlgorithm alg, KetamaNodeLocatorConfiguration conf) {
72                super();
73                ketamaNodes=smn;
74                allNodes=an;
75                hashAlg=alg;
76        config=conf;
77        }
78 
79        public Collection<MemcachedNode> getAll() {
80                return allNodes;
81        }
82 
83        public MemcachedNode getPrimary(final String k) {
84                MemcachedNode rv=getNodeForKey(hashAlg.hash(k));
85                assert rv != null : "Found no node for key " + k;
86                return rv;
87        }
88 
89        long getMaxKey() {
90                return ketamaNodes.lastKey();
91        }
92 
93        MemcachedNode getNodeForKey(long hash) {
94                final MemcachedNode rv;
95                if(!ketamaNodes.containsKey(hash)) {
96                        // Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5
97                        // in a lot of places, so I'm doing this myself.
98                        SortedMap<Long, MemcachedNode> tailMap=ketamaNodes.tailMap(hash);
99                        if(tailMap.isEmpty()) {
100                                hash=ketamaNodes.firstKey();
101                        } else {
102                                hash=tailMap.firstKey();
103                        }
104                }
105                rv=ketamaNodes.get(hash);
106                return rv;
107        }
108 
109        public Iterator<MemcachedNode> getSequence(String k) {
110                return new KetamaIterator(k, allNodes.size());
111        }
112 
113        public NodeLocator getReadonlyCopy() {
114                SortedMap<Long, MemcachedNode> smn=new TreeMap<Long, MemcachedNode>(
115                        ketamaNodes);
116                Collection<MemcachedNode> an=
117                        new ArrayList<MemcachedNode>(allNodes.size());
118 
119                // Rewrite the values a copy of the map.
120                for(Map.Entry<Long, MemcachedNode> me : smn.entrySet()) {
121                        me.setValue(new MemcachedNodeROImpl(me.getValue()));
122                }
123                // Copy the allNodes collection.
124                for(MemcachedNode n : allNodes) {
125                        an.add(new MemcachedNodeROImpl(n));
126                }
127 
128                return new KetamaNodeLocator(smn, an, hashAlg, config);
129        }
130 
131        class KetamaIterator implements Iterator<MemcachedNode> {
132 
133                final String key;
134                long hashVal;
135                int remainingTries;
136                int numTries=0;
137 
138                public KetamaIterator(final String k, final int t) {
139                        super();
140                        hashVal=hashAlg.hash(k);
141                        remainingTries=t;
142                        key=k;
143                }
144 
145                private void nextHash() {
146                        // this.calculateHash(Integer.toString(tries)+key).hashCode();
147                        long tmpKey=hashAlg.hash((numTries++) + key);
148                        // This echos the implementation of Long.hashCode()
149                        hashVal += (int)(tmpKey ^ (tmpKey >>> 32));
150                        hashVal &= 0xffffffffL; /* truncate to 32-bits */
151                        remainingTries--;
152                }
153 
154                public boolean hasNext() {
155                        return remainingTries > 0;
156                }
157 
158                public MemcachedNode next() {
159                        try {
160                                return getNodeForKey(hashVal);
161                        } finally {
162                                nextHash();
163                        }
164                }
165 
166                public void remove() {
167                        throw new UnsupportedOperationException("remove not supported");
168                }
169 
170        }
171}

[all classes][net.spy.memcached]
EMMA 2.0.5312 (C) Vladimir Roubtsov