forked from infinispan/infinispan
/
ReplicatedConsistentHash.java
232 lines (203 loc) · 7.5 KB
/
ReplicatedConsistentHash.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
package org.infinispan.distribution.ch.impl;
import org.infinispan.commons.hash.Hash;
import org.infinispan.commons.marshall.InstanceReusingAdvancedExternalizer;
import org.infinispan.distribution.ch.AffinityTaggedKey;
import org.infinispan.distribution.ch.ConsistentHash;
import org.infinispan.marshall.core.Ids;
import org.infinispan.remoting.transport.Address;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.util.*;
/**
* Special implementation of {@link org.infinispan.distribution.ch.ConsistentHash} for replicated caches.
* The hash-space has several segments owned by all members and the primary ownership of each segment is evenly
* spread between members.
*
* @author Dan Berindei
* @author anistor@redhat.com
* @since 5.2
*/
public class ReplicatedConsistentHash implements ConsistentHash {
private final Hash hashFunction;
private final int[] primaryOwners;
private final List<Address> members;
private final Set<Address> membersSet;
private final Set<Integer> segments;
public ReplicatedConsistentHash(Hash hashFunction, List<Address> members, int[] primaryOwners) {
this.hashFunction = hashFunction;
this.members = Collections.unmodifiableList(new ArrayList<Address>(members));
this.membersSet = Collections.unmodifiableSet(new HashSet<Address>(members));
this.primaryOwners = primaryOwners;
Set<Integer> segmentIds = new HashSet<Integer>(primaryOwners.length);
for (int i = 0; i < primaryOwners.length; i++) {
segmentIds.add(i);
}
segments = Collections.unmodifiableSet(segmentIds);
}
@Override
public int getNumSegments() {
return primaryOwners.length;
}
@Override
public int getNumOwners() {
return members.size();
}
@Override
public List<Address> getMembers() {
return members;
}
@Override
public Hash getHashFunction() {
return hashFunction;
}
@Override
public int getSegment(Object key) {
if (key instanceof AffinityTaggedKey) {
AffinityTaggedKey tagged = (AffinityTaggedKey) key;
int segment = tagged.getAffinitySegmentId();
//The check for [segment < numSegments] should generally not be needed, but let's be safe as the entry
//might have been stored when a different configuration or version of Infinispan was used
if (segment != -1 && segment < primaryOwners.length) {
return segment;
}//Else: use normal hashing, which is always safe as AffinityTaggedKey is meant only as performance boost
}
// The result must always be positive, so we make sure the dividend is positive first
return (hashFunction.hash(key) & Integer.MAX_VALUE) % primaryOwners.length;
}
@Override
public List<Address> locateOwnersForSegment(int segmentId) {
Address primaryOwner = locatePrimaryOwnerForSegment(segmentId);
List<Address> owners = new ArrayList<Address>(members.size());
owners.add(primaryOwner);
for (Address member : members) {
if (!member.equals(primaryOwner)) {
owners.add(member);
}
}
return owners;
}
@Override
public Address locatePrimaryOwnerForSegment(int segmentId) {
return members.get(primaryOwners[segmentId]);
}
@Override
public Set<Integer> getSegmentsForOwner(Address owner) {
if (owner == null) {
throw new IllegalArgumentException("owner cannot be null");
}
if (!membersSet.contains(owner)) {
throw new IllegalArgumentException("The node is not a member : " + owner);
}
return segments;
}
@Override
public Set<Integer> getPrimarySegmentsForOwner(Address owner) {
int index = members.indexOf(owner);
if (index == -1) {
throw new IllegalArgumentException("The node is not a member : " + owner);
}
Set<Integer> primarySegments = new HashSet<Integer>();
for (int i = 0; i < primaryOwners.length; ++i) {
if (primaryOwners[i] == index) {
primarySegments.add(i);
}
}
return primarySegments;
}
@Override
public String getRoutingTableAsString() {
return Arrays.toString(primaryOwners);
}
@Override
public Address locatePrimaryOwner(Object key) {
return locatePrimaryOwnerForSegment(getSegment(key));
}
@Override
public List<Address> locateOwners(Object key) {
return locateOwnersForSegment(getSegment(key));
}
@Override
public Set<Address> locateAllOwners(Collection<Object> keys) {
return membersSet;
}
@Override
public boolean isKeyLocalToNode(Address nodeAddress, Object key) {
return membersSet.contains(nodeAddress);
}
@Override
public String toString() {
OwnershipStatistics stats = new OwnershipStatistics(this, members);
StringBuilder sb = new StringBuilder("ReplicatedConsistentHash{");
sb.append("ns = ").append(segments.size());
sb.append(", owners = (").append(members.size()).append(")[");
boolean first = true;
for (Address a : members) {
if (first) {
first = false;
} else {
sb.append(", ");
}
int primaryOwned = stats.getPrimaryOwned(a);
sb.append(a).append(": ").append(primaryOwned);
}
sb.append("]}");
return sb.toString();
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((hashFunction == null) ? 0 : hashFunction.hashCode());
result = prime * result + ((members == null) ? 0 : members.hashCode());
result = prime * result + Arrays.hashCode(primaryOwners);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
ReplicatedConsistentHash other = (ReplicatedConsistentHash) obj;
if (hashFunction == null) {
if (other.hashFunction != null)
return false;
} else if (!hashFunction.equals(other.hashFunction))
return false;
if (members == null) {
if (other.members != null)
return false;
} else if (!members.equals(other.members))
return false;
if (!Arrays.equals(primaryOwners, other.primaryOwners))
return false;
return true;
}
public static class Externalizer extends InstanceReusingAdvancedExternalizer<ReplicatedConsistentHash> {
@Override
public void doWriteObject(ObjectOutput output, ReplicatedConsistentHash ch) throws IOException {
output.writeObject(ch.hashFunction);
output.writeObject(ch.members);
output.writeObject(ch.primaryOwners);
}
@Override
@SuppressWarnings("unchecked")
public ReplicatedConsistentHash doReadObject(ObjectInput unmarshaller) throws IOException, ClassNotFoundException {
Hash hashFunction = (Hash) unmarshaller.readObject();
List<Address> members = (List<Address>) unmarshaller.readObject();
int[] primaryOwners = (int[]) unmarshaller.readObject();
return new ReplicatedConsistentHash(hashFunction, members, primaryOwners);
}
@Override
public Integer getId() {
return Ids.REPLICATED_CONSISTENT_HASH;
}
@Override
public Set<Class<? extends ReplicatedConsistentHash>> getTypeClasses() {
return Collections.<Class<? extends ReplicatedConsistentHash>>singleton(ReplicatedConsistentHash.class);
}
}
}