blob: b5ea52e06014663b8550a0d04a8847ef5acac9f4 [file] [log] [blame]
Jonathan Hartdb3af892015-01-26 13:19:07 -08001/*
2 * Copyright 2015 Open Networking Laboratory
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
Jonathan Hart77bdd262015-02-03 09:07:48 -080016package org.onosproject.store.ecmap;
Jonathan Hartdb3af892015-01-26 13:19:07 -080017
Madan Jampani4f1f4cd2015-07-08 23:05:35 -070018import com.google.common.collect.Collections2;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080019import com.google.common.collect.ImmutableList;
Madan Jampani4f1f4cd2015-07-08 23:05:35 -070020import com.google.common.collect.ImmutableMap;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080021import com.google.common.collect.Lists;
22import com.google.common.collect.Maps;
Madan Jampani3d76c942015-06-29 23:37:10 -070023import com.google.common.collect.Sets;
Jonathan Hartf9108232015-02-02 16:37:35 -080024import org.apache.commons.lang3.tuple.Pair;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080025import org.onlab.util.AbstractAccumulator;
Jonathan Hartdb3af892015-01-26 13:19:07 -080026import org.onlab.util.KryoNamespace;
Jonathan Hart233a18a2015-03-02 17:24:58 -080027import org.onlab.util.SlidingWindowCounter;
Jonathan Hartdb3af892015-01-26 13:19:07 -080028import org.onosproject.cluster.ClusterService;
Jonathan Hartaaa56572015-01-28 21:56:35 -080029import org.onosproject.cluster.ControllerNode;
Jonathan Hartdb3af892015-01-26 13:19:07 -080030import org.onosproject.cluster.NodeId;
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -070031import org.onosproject.persistence.PersistenceService;
Jonathan Hartdb3af892015-01-26 13:19:07 -080032import org.onosproject.store.Timestamp;
33import org.onosproject.store.cluster.messaging.ClusterCommunicationService;
Jonathan Hartdb3af892015-01-26 13:19:07 -080034import org.onosproject.store.cluster.messaging.MessageSubject;
Madan Jampani3e033bd2015-04-08 13:03:49 -070035import org.onosproject.store.impl.LogicalTimestamp;
Madan Jampani3d76c942015-06-29 23:37:10 -070036import org.onosproject.store.serializers.KryoNamespaces;
Jonathan Hartdb3af892015-01-26 13:19:07 -080037import org.onosproject.store.serializers.KryoSerializer;
Jonathan Hart6ec029a2015-03-24 17:12:35 -070038import org.onosproject.store.service.EventuallyConsistentMap;
39import org.onosproject.store.service.EventuallyConsistentMapEvent;
40import org.onosproject.store.service.EventuallyConsistentMapListener;
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -070041import org.onosproject.store.service.Serializer;
Jonathan Hart4a29c592015-09-23 17:55:07 -070042import org.onosproject.store.service.WallClockTimestamp;
Jonathan Hartdb3af892015-01-26 13:19:07 -080043import org.slf4j.Logger;
44import org.slf4j.LoggerFactory;
45
Jonathan Hartdb3af892015-01-26 13:19:07 -080046import java.util.Collection;
Madan Jampani3d76c942015-06-29 23:37:10 -070047import java.util.Collections;
Jonathan Hartdb3af892015-01-26 13:19:07 -080048import java.util.List;
49import java.util.Map;
Madan Jampanid13f3b82015-07-01 17:37:50 -070050import java.util.Objects;
Madan Jampani43e9c9c2015-06-26 14:16:46 -070051import java.util.Optional;
Jonathan Hartdb3af892015-01-26 13:19:07 -080052import java.util.Set;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080053import java.util.Timer;
Jonathan Hartdb3af892015-01-26 13:19:07 -080054import java.util.concurrent.ExecutorService;
55import java.util.concurrent.Executors;
56import java.util.concurrent.ScheduledExecutorService;
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -080057import java.util.concurrent.TimeUnit;
Madan Jampani3d76c942015-06-29 23:37:10 -070058import java.util.concurrent.atomic.AtomicBoolean;
Madan Jampani43e9c9c2015-06-26 14:16:46 -070059import java.util.concurrent.atomic.AtomicReference;
Brian O'Connor5eb77c82015-03-02 18:09:39 -080060import java.util.function.BiFunction;
Jonathan Hartdb3af892015-01-26 13:19:07 -080061import java.util.stream.Collectors;
62
63import static com.google.common.base.Preconditions.checkNotNull;
64import static com.google.common.base.Preconditions.checkState;
65import static java.util.concurrent.Executors.newSingleThreadScheduledExecutor;
Brian O'Connorc6713a82015-02-24 11:55:48 -080066import static org.onlab.util.BoundedThreadPool.newFixedThreadPool;
Brian O'Connor4b2ba5f2015-02-18 20:54:00 -080067import static org.onlab.util.Tools.groupedThreads;
Jonathan Hart4a29c592015-09-23 17:55:07 -070068import static org.onosproject.store.service.EventuallyConsistentMapEvent.Type.PUT;
69import static org.onosproject.store.service.EventuallyConsistentMapEvent.Type.REMOVE;
Jonathan Hartdb3af892015-01-26 13:19:07 -080070
71/**
72 * Distributed Map implementation which uses optimistic replication and gossip
73 * based techniques to provide an eventually consistent data store.
74 */
75public class EventuallyConsistentMapImpl<K, V>
76 implements EventuallyConsistentMap<K, V> {
77
78 private static final Logger log = LoggerFactory.getLogger(EventuallyConsistentMapImpl.class);
79
Madan Jampani3d76c942015-06-29 23:37:10 -070080 private final Map<K, MapValue<V>> items;
Jonathan Hartdb3af892015-01-26 13:19:07 -080081
Jonathan Hartdb3af892015-01-26 13:19:07 -080082 private final ClusterService clusterService;
83 private final ClusterCommunicationService clusterCommunicator;
84 private final KryoSerializer serializer;
Madan Jampani3d76c942015-06-29 23:37:10 -070085 private final NodeId localNodeId;
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -070086 private final PersistenceService persistenceService;
Jonathan Hartdb3af892015-01-26 13:19:07 -080087
Madan Jampanibcf1a482015-06-24 19:05:56 -070088 private final BiFunction<K, V, Timestamp> timestampProvider;
Jonathan Hartdb3af892015-01-26 13:19:07 -080089
90 private final MessageSubject updateMessageSubject;
Jonathan Hartaaa56572015-01-28 21:56:35 -080091 private final MessageSubject antiEntropyAdvertisementSubject;
Jonathan Hartdb3af892015-01-26 13:19:07 -080092
Jonathan Hartaaa56572015-01-28 21:56:35 -080093 private final Set<EventuallyConsistentMapListener<K, V>> listeners
Madan Jampani3d76c942015-06-29 23:37:10 -070094 = Sets.newCopyOnWriteArraySet();
Jonathan Hartdb3af892015-01-26 13:19:07 -080095
96 private final ExecutorService executor;
Jonathan Hartdb3af892015-01-26 13:19:07 -080097 private final ScheduledExecutorService backgroundExecutor;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080098 private final BiFunction<K, V, Collection<NodeId>> peerUpdateFunction;
Jonathan Hartdb3af892015-01-26 13:19:07 -080099
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700100 private final ExecutorService communicationExecutor;
101 private final Map<NodeId, EventAccumulator> senderPending;
Madan Jampani28726282015-02-19 11:40:23 -0800102
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700103 private final String mapName;
104
Jonathan Hartdb3af892015-01-26 13:19:07 -0800105 private volatile boolean destroyed = false;
Jonathan Hart539a6462015-01-27 17:05:43 -0800106 private static final String ERROR_DESTROYED = " map is already destroyed";
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800107 private final String destroyedMessage;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800108
Jonathan Hart4f397e82015-02-04 09:10:41 -0800109 private static final String ERROR_NULL_KEY = "Key cannot be null";
110 private static final String ERROR_NULL_VALUE = "Null values are not allowed";
111
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700112 private final long initialDelaySec = 5;
113 private final boolean lightweightAntiEntropy;
114 private final boolean tombstonesDisabled;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800115
Jonathan Hart233a18a2015-03-02 17:24:58 -0800116 private static final int WINDOW_SIZE = 5;
117 private static final int HIGH_LOAD_THRESHOLD = 0;
118 private static final int LOAD_WINDOW = 2;
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700119 private SlidingWindowCounter counter = new SlidingWindowCounter(WINDOW_SIZE);
Jonathan Hart233a18a2015-03-02 17:24:58 -0800120
Jonathan Hartca335e92015-03-05 10:34:32 -0800121 private final boolean persistent;
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -0700122
123 private static final String PERSISTENT_LOCAL_MAP_NAME = "itemsMap";
124
Jonathan Hartca335e92015-03-05 10:34:32 -0800125
Jonathan Hartdb3af892015-01-26 13:19:07 -0800126 /**
127 * Creates a new eventually consistent map shared amongst multiple instances.
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800128 * <p>
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700129 * See {@link org.onosproject.store.service.EventuallyConsistentMapBuilder}
130 * for more description of the parameters expected by the map.
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800131 * </p>
Jonathan Hartdb3af892015-01-26 13:19:07 -0800132 *
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700133 * @param mapName a String identifier for the map.
134 * @param clusterService the cluster service
135 * @param clusterCommunicator the cluster communications service
136 * @param serializerBuilder a Kryo namespace builder that can serialize
137 * both K and V
Madan Jampanibcf1a482015-06-24 19:05:56 -0700138 * @param timestampProvider provider of timestamps for K and V
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700139 * @param peerUpdateFunction function that provides a set of nodes to immediately
140 * update to when there writes to the map
141 * @param eventExecutor executor to use for processing incoming
142 * events from peers
143 * @param communicationExecutor executor to use for sending events to peers
144 * @param backgroundExecutor executor to use for background anti-entropy
145 * tasks
146 * @param tombstonesDisabled true if this map should not maintain
147 * tombstones
148 * @param antiEntropyPeriod period that the anti-entropy task should run
Jonathan Hartca335e92015-03-05 10:34:32 -0800149 * @param antiEntropyTimeUnit time unit for anti-entropy period
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700150 * @param convergeFaster make anti-entropy try to converge faster
Jonathan Hartca335e92015-03-05 10:34:32 -0800151 * @param persistent persist data to disk
Jonathan Hartdb3af892015-01-26 13:19:07 -0800152 */
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700153 EventuallyConsistentMapImpl(String mapName,
154 ClusterService clusterService,
155 ClusterCommunicationService clusterCommunicator,
156 KryoNamespace.Builder serializerBuilder,
Madan Jampanibcf1a482015-06-24 19:05:56 -0700157 BiFunction<K, V, Timestamp> timestampProvider,
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700158 BiFunction<K, V, Collection<NodeId>> peerUpdateFunction,
159 ExecutorService eventExecutor,
160 ExecutorService communicationExecutor,
161 ScheduledExecutorService backgroundExecutor,
162 boolean tombstonesDisabled,
163 long antiEntropyPeriod,
164 TimeUnit antiEntropyTimeUnit,
Jonathan Hartca335e92015-03-05 10:34:32 -0800165 boolean convergeFaster,
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -0700166 boolean persistent,
167 PersistenceService persistenceService) {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700168 this.mapName = mapName;
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -0700169 this.serializer = createSerializer(serializerBuilder);
170 this.persistenceService = persistenceService;
171 this.persistent =
172 persistent;
173 if (persistent) {
174 items = this.persistenceService.<K, MapValue<V>>persistentMapBuilder()
175 .withName(PERSISTENT_LOCAL_MAP_NAME)
176 .withSerializer(new Serializer() {
177
178 @Override
179 public <T> byte[] encode(T object) {
180 return EventuallyConsistentMapImpl.this.serializer.encode(object);
181 }
182
183 @Override
184 public <T> T decode(byte[] bytes) {
185 return EventuallyConsistentMapImpl.this.serializer.decode(bytes);
186 }
187 })
188 .build();
189 } else {
190 items = Maps.newConcurrentMap();
191 }
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800192 senderPending = Maps.newConcurrentMap();
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700193 destroyedMessage = mapName + ERROR_DESTROYED;
Madan Jampani28726282015-02-19 11:40:23 -0800194
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700195 this.clusterService = clusterService;
196 this.clusterCommunicator = clusterCommunicator;
Madan Jampani3d76c942015-06-29 23:37:10 -0700197 this.localNodeId = clusterService.getLocalNode().id();
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700198
Madan Jampanibcf1a482015-06-24 19:05:56 -0700199 this.timestampProvider = timestampProvider;
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700200
201 if (peerUpdateFunction != null) {
202 this.peerUpdateFunction = peerUpdateFunction;
203 } else {
204 this.peerUpdateFunction = (key, value) -> clusterService.getNodes().stream()
205 .map(ControllerNode::id)
Madan Jampani3d76c942015-06-29 23:37:10 -0700206 .filter(nodeId -> !nodeId.equals(localNodeId))
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700207 .collect(Collectors.toList());
208 }
209
210 if (eventExecutor != null) {
211 this.executor = eventExecutor;
212 } else {
213 // should be a normal executor; it's used for receiving messages
214 this.executor =
215 Executors.newFixedThreadPool(8, groupedThreads("onos/ecm", mapName + "-fg-%d"));
216 }
217
218 if (communicationExecutor != null) {
219 this.communicationExecutor = communicationExecutor;
220 } else {
221 // sending executor; should be capped
222 //TODO this probably doesn't need to be bounded anymore
223 this.communicationExecutor =
224 newFixedThreadPool(8, groupedThreads("onos/ecm", mapName + "-publish-%d"));
225 }
226
Jonathan Hartca335e92015-03-05 10:34:32 -0800227
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700228 if (backgroundExecutor != null) {
229 this.backgroundExecutor = backgroundExecutor;
230 } else {
231 this.backgroundExecutor =
232 newSingleThreadScheduledExecutor(groupedThreads("onos/ecm", mapName + "-bg-%d"));
233 }
Jonathan Hartdb3af892015-01-26 13:19:07 -0800234
Jonathan Hartaaa56572015-01-28 21:56:35 -0800235 // start anti-entropy thread
Madan Jampani3d76c942015-06-29 23:37:10 -0700236 this.backgroundExecutor.scheduleAtFixedRate(this::sendAdvertisement,
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700237 initialDelaySec, antiEntropyPeriod,
238 antiEntropyTimeUnit);
Jonathan Hartaaa56572015-01-28 21:56:35 -0800239
Jonathan Hartdb3af892015-01-26 13:19:07 -0800240 updateMessageSubject = new MessageSubject("ecm-" + mapName + "-update");
241 clusterCommunicator.addSubscriber(updateMessageSubject,
Madan Jampani3d76c942015-06-29 23:37:10 -0700242 serializer::decode,
243 this::processUpdates,
244 this.executor);
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800245
Jonathan Hartaaa56572015-01-28 21:56:35 -0800246 antiEntropyAdvertisementSubject = new MessageSubject("ecm-" + mapName + "-anti-entropy");
247 clusterCommunicator.addSubscriber(antiEntropyAdvertisementSubject,
Madan Jampani3d76c942015-06-29 23:37:10 -0700248 serializer::decode,
249 this::handleAntiEntropyAdvertisement,
250 this.backgroundExecutor);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800251
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700252 this.tombstonesDisabled = tombstonesDisabled;
253 this.lightweightAntiEntropy = !convergeFaster;
Madan Jampanie1356282015-03-10 19:05:36 -0700254 }
255
Jonathan Hartdb3af892015-01-26 13:19:07 -0800256 private KryoSerializer createSerializer(KryoNamespace.Builder builder) {
257 return new KryoSerializer() {
258 @Override
259 protected void setupKryoPool() {
260 // Add the map's internal helper classes to the user-supplied serializer
261 serializerPool = builder
Madan Jampani3d76c942015-06-29 23:37:10 -0700262 .register(KryoNamespaces.BASIC)
Madan Jampanidb5d06a2015-06-30 11:16:48 -0700263 .nextId(KryoNamespaces.BEGIN_USER_CUSTOM_ID)
Madan Jampani3e033bd2015-04-08 13:03:49 -0700264 .register(LogicalTimestamp.class)
Jonathan Hartdb3af892015-01-26 13:19:07 -0800265 .register(WallClockTimestamp.class)
Jonathan Hartaaa56572015-01-28 21:56:35 -0800266 .register(AntiEntropyAdvertisement.class)
Madan Jampani3d76c942015-06-29 23:37:10 -0700267 .register(UpdateEntry.class)
268 .register(MapValue.class)
269 .register(MapValue.Digest.class)
Jonathan Hartdb3af892015-01-26 13:19:07 -0800270 .build();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800271 }
272 };
273 }
274
275 @Override
276 public int size() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800277 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700278 // TODO: Maintain a separate counter for tracking live elements in map.
279 return Maps.filterValues(items, MapValue::isAlive).size();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800280 }
281
282 @Override
283 public boolean isEmpty() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800284 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700285 return size() == 0;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800286 }
287
288 @Override
289 public boolean containsKey(K key) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800290 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800291 checkNotNull(key, ERROR_NULL_KEY);
Madan Jampani3d76c942015-06-29 23:37:10 -0700292 return get(key) != null;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800293 }
294
295 @Override
296 public boolean containsValue(V value) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800297 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800298 checkNotNull(value, ERROR_NULL_VALUE);
Madan Jampani3d76c942015-06-29 23:37:10 -0700299 return items.values()
300 .stream()
301 .filter(MapValue::isAlive)
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700302 .anyMatch(v -> value.equals(v.get()));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800303 }
304
305 @Override
306 public V get(K key) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800307 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800308 checkNotNull(key, ERROR_NULL_KEY);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800309
Madan Jampani3d76c942015-06-29 23:37:10 -0700310 MapValue<V> value = items.get(key);
311 return (value == null || value.isTombstone()) ? null : value.get();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800312 }
313
314 @Override
315 public void put(K key, V value) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800316 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800317 checkNotNull(key, ERROR_NULL_KEY);
318 checkNotNull(value, ERROR_NULL_VALUE);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800319
Madan Jampani3d76c942015-06-29 23:37:10 -0700320 MapValue<V> newValue = new MapValue<>(value, timestampProvider.apply(key, value));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700321 if (putInternal(key, newValue)) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700322 notifyPeers(new UpdateEntry<>(key, newValue), peerUpdateFunction.apply(key, value));
Madan Jampanicab114c2015-07-23 00:14:19 -0700323 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, PUT, key, value));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800324 }
325 }
326
Jonathan Hartdb3af892015-01-26 13:19:07 -0800327 @Override
Madan Jampani43e9c9c2015-06-26 14:16:46 -0700328 public V remove(K key) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800329 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800330 checkNotNull(key, ERROR_NULL_KEY);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700331 return removeAndNotify(key, null);
332 }
333
334 @Override
335 public void remove(K key, V value) {
336 checkState(!destroyed, destroyedMessage);
337 checkNotNull(key, ERROR_NULL_KEY);
338 checkNotNull(value, ERROR_NULL_VALUE);
339 removeAndNotify(key, value);
340 }
341
342 private V removeAndNotify(K key, V value) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700343 Timestamp timestamp = timestampProvider.apply(key, value);
344 Optional<MapValue<V>> tombstone = tombstonesDisabled || timestamp == null
345 ? Optional.empty() : Optional.of(MapValue.tombstone(timestamp));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700346 MapValue<V> previousValue = removeInternal(key, Optional.ofNullable(value), tombstone);
Madan Jampania0ac4872015-07-02 11:23:49 -0700347 if (previousValue != null) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700348 notifyPeers(new UpdateEntry<>(key, tombstone.orElse(null)),
349 peerUpdateFunction.apply(key, previousValue.get()));
Madan Jampania0ac4872015-07-02 11:23:49 -0700350 if (previousValue.isAlive()) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700351 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, REMOVE, key, previousValue.get()));
Madan Jampania0ac4872015-07-02 11:23:49 -0700352 }
353 }
Madan Jampanid13f3b82015-07-01 17:37:50 -0700354 return previousValue != null ? previousValue.get() : null;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800355 }
356
Madan Jampani483d0a22015-08-19 17:33:00 -0700357 private MapValue<V> removeInternal(K key, Optional<V> value, Optional<MapValue<V>> tombstone) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700358 checkState(!destroyed, destroyedMessage);
359 checkNotNull(key, ERROR_NULL_KEY);
360 checkNotNull(value, ERROR_NULL_VALUE);
Madan Jampani483d0a22015-08-19 17:33:00 -0700361 tombstone.ifPresent(v -> checkState(v.isTombstone()));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700362
363 counter.incrementCount();
Madan Jampani3d76c942015-06-29 23:37:10 -0700364 AtomicBoolean updated = new AtomicBoolean(false);
Madan Jampanid13f3b82015-07-01 17:37:50 -0700365 AtomicReference<MapValue<V>> previousValue = new AtomicReference<>();
Madan Jampani3d76c942015-06-29 23:37:10 -0700366 items.compute(key, (k, existing) -> {
Madan Jampanid13f3b82015-07-01 17:37:50 -0700367 boolean valueMatches = true;
368 if (value.isPresent() && existing != null && existing.isAlive()) {
369 valueMatches = Objects.equals(value.get(), existing.get());
Madan Jampani3d76c942015-06-29 23:37:10 -0700370 }
Brian O'Connor6325dad2015-07-07 15:36:29 -0700371 if (existing == null) {
Jonathan Hart4a29c592015-09-23 17:55:07 -0700372 log.trace("ECMap Remove: Existing value for key {} is already null", k);
Brian O'Connor6325dad2015-07-07 15:36:29 -0700373 }
Madan Jampani483d0a22015-08-19 17:33:00 -0700374 if (valueMatches) {
375 if (existing == null) {
376 updated.set(tombstone.isPresent());
377 } else {
378 updated.set(!tombstone.isPresent() || tombstone.get().isNewerThan(existing));
379 }
Madan Jampanid13f3b82015-07-01 17:37:50 -0700380 }
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700381 if (updated.get()) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700382 previousValue.set(existing);
383 return tombstone.orElse(null);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700384 } else {
385 return existing;
386 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700387 });
Madan Jampanid13f3b82015-07-01 17:37:50 -0700388 return previousValue.get();
Jonathan Hart5ec32ba2015-02-05 13:33:58 -0800389 }
390
391 @Override
Madan Jampani4727a112015-07-16 12:12:58 -0700392 public V compute(K key, BiFunction<K, V, V> recomputeFunction) {
393 checkState(!destroyed, destroyedMessage);
394 checkNotNull(key, ERROR_NULL_KEY);
395 checkNotNull(recomputeFunction, "Recompute function cannot be null");
396
397 AtomicBoolean updated = new AtomicBoolean(false);
398 AtomicReference<MapValue<V>> previousValue = new AtomicReference<>();
399 MapValue<V> computedValue = items.compute(key, (k, mv) -> {
400 previousValue.set(mv);
401 V newRawValue = recomputeFunction.apply(key, mv == null ? null : mv.get());
402 MapValue<V> newValue = new MapValue<>(newRawValue, timestampProvider.apply(key, newRawValue));
403 if (mv == null || newValue.isNewerThan(mv)) {
404 updated.set(true);
405 return newValue;
406 } else {
407 return mv;
408 }
409 });
410 if (updated.get()) {
411 notifyPeers(new UpdateEntry<>(key, computedValue), peerUpdateFunction.apply(key, computedValue.get()));
412 EventuallyConsistentMapEvent.Type updateType = computedValue.isTombstone() ? REMOVE : PUT;
413 V value = computedValue.isTombstone()
414 ? previousValue.get() == null ? null : previousValue.get().get()
415 : computedValue.get();
416 if (value != null) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700417 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, updateType, key, value));
Madan Jampani4727a112015-07-16 12:12:58 -0700418 }
419 }
420 return computedValue.get();
421 }
422
423 @Override
Jonathan Hartdb3af892015-01-26 13:19:07 -0800424 public void putAll(Map<? extends K, ? extends V> m) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800425 checkState(!destroyed, destroyedMessage);
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800426 m.forEach(this::put);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800427 }
428
429 @Override
430 public void clear() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800431 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700432 Maps.filterValues(items, MapValue::isAlive)
433 .forEach((k, v) -> remove(k));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800434 }
435
436 @Override
437 public Set<K> keySet() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800438 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700439 return Maps.filterValues(items, MapValue::isAlive)
440 .keySet();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800441 }
442
443 @Override
444 public Collection<V> values() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800445 checkState(!destroyed, destroyedMessage);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700446 return Collections2.transform(Maps.filterValues(items, MapValue::isAlive).values(), MapValue::get);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800447 }
448
449 @Override
450 public Set<Map.Entry<K, V>> entrySet() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800451 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700452 return Maps.filterValues(items, MapValue::isAlive)
453 .entrySet()
454 .stream()
455 .map(e -> Pair.of(e.getKey(), e.getValue().get()))
456 .collect(Collectors.toSet());
457 }
Jonathan Hartdb3af892015-01-26 13:19:07 -0800458
Madan Jampani3d76c942015-06-29 23:37:10 -0700459 /**
460 * Returns true if newValue was accepted i.e. map is updated.
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -0700461 *
Madan Jampani3d76c942015-06-29 23:37:10 -0700462 * @param key key
463 * @param newValue proposed new value
464 * @return true if update happened; false if map already contains a more recent value for the key
465 */
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700466 private boolean putInternal(K key, MapValue<V> newValue) {
467 checkState(!destroyed, destroyedMessage);
468 checkNotNull(key, ERROR_NULL_KEY);
469 checkNotNull(newValue, ERROR_NULL_VALUE);
470 checkState(newValue.isAlive());
471 counter.incrementCount();
Madan Jampani3d76c942015-06-29 23:37:10 -0700472 AtomicBoolean updated = new AtomicBoolean(false);
473 items.compute(key, (k, existing) -> {
474 if (existing == null || newValue.isNewerThan(existing)) {
475 updated.set(true);
Madan Jampani3d76c942015-06-29 23:37:10 -0700476 return newValue;
477 }
478 return existing;
479 });
Madan Jampani3d76c942015-06-29 23:37:10 -0700480 return updated.get();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800481 }
482
483 @Override
Jonathan Hart539a6462015-01-27 17:05:43 -0800484 public void addListener(EventuallyConsistentMapListener<K, V> listener) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800485 checkState(!destroyed, destroyedMessage);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800486
487 listeners.add(checkNotNull(listener));
488 }
489
490 @Override
Jonathan Hart539a6462015-01-27 17:05:43 -0800491 public void removeListener(EventuallyConsistentMapListener<K, V> listener) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800492 checkState(!destroyed, destroyedMessage);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800493
494 listeners.remove(checkNotNull(listener));
495 }
496
497 @Override
498 public void destroy() {
499 destroyed = true;
500
501 executor.shutdown();
502 backgroundExecutor.shutdown();
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800503 communicationExecutor.shutdown();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800504
Jonathan Hart584d2f32015-01-27 19:46:14 -0800505 listeners.clear();
506
Jonathan Hartdb3af892015-01-26 13:19:07 -0800507 clusterCommunicator.removeSubscriber(updateMessageSubject);
Jonathan Hart584d2f32015-01-27 19:46:14 -0800508 clusterCommunicator.removeSubscriber(antiEntropyAdvertisementSubject);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800509 }
510
Jonathan Hartaaa56572015-01-28 21:56:35 -0800511 private void notifyListeners(EventuallyConsistentMapEvent<K, V> event) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700512 listeners.forEach(listener -> listener.event(event));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800513 }
514
Madan Jampani3d76c942015-06-29 23:37:10 -0700515 private void notifyPeers(UpdateEntry<K, V> event, Collection<NodeId> peers) {
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800516 queueUpdate(event, peers);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800517 }
518
Madan Jampani3d76c942015-06-29 23:37:10 -0700519 private void queueUpdate(UpdateEntry<K, V> event, Collection<NodeId> peers) {
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800520 if (peers == null) {
521 // we have no friends :(
522 return;
523 }
524 peers.forEach(node ->
Jonathan Hart9a426f82015-09-03 15:43:13 +0200525 senderPending.computeIfAbsent(node, unusedKey -> new EventAccumulator(node)).add(event)
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800526 );
527 }
528
Jonathan Hart233a18a2015-03-02 17:24:58 -0800529 private boolean underHighLoad() {
530 return counter.get(LOAD_WINDOW) > HIGH_LOAD_THRESHOLD;
531 }
532
Madan Jampani3d76c942015-06-29 23:37:10 -0700533 private void sendAdvertisement() {
534 try {
Thomas Vachuska152f9fd2015-04-02 16:28:13 -0700535 if (underHighLoad() || destroyed) {
Jonathan Hart233a18a2015-03-02 17:24:58 -0800536 return;
537 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700538 pickRandomActivePeer().ifPresent(this::sendAdvertisementToPeer);
539 } catch (Exception e) {
540 // Catch all exceptions to avoid scheduled task being suppressed.
541 log.error("Exception thrown while sending advertisement", e);
Jonathan Hartaaa56572015-01-28 21:56:35 -0800542 }
543 }
544
Madan Jampani3d76c942015-06-29 23:37:10 -0700545 private Optional<NodeId> pickRandomActivePeer() {
546 List<NodeId> activePeers = clusterService.getNodes()
547 .stream()
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700548 .map(ControllerNode::id)
549 .filter(id -> !localNodeId.equals(id))
Madan Jampani3d76c942015-06-29 23:37:10 -0700550 .filter(id -> clusterService.getState(id) == ControllerNode.State.ACTIVE)
551 .collect(Collectors.toList());
552 Collections.shuffle(activePeers);
553 return activePeers.isEmpty() ? Optional.empty() : Optional.of(activePeers.get(0));
554 }
555
556 private void sendAdvertisementToPeer(NodeId peer) {
557 clusterCommunicator.unicast(createAdvertisement(),
558 antiEntropyAdvertisementSubject,
559 serializer::encode,
560 peer)
561 .whenComplete((result, error) -> {
562 if (error != null) {
Madan Jampania0ac4872015-07-02 11:23:49 -0700563 log.debug("Failed to send anti-entropy advertisement to {}", peer, error);
Madan Jampani3d76c942015-06-29 23:37:10 -0700564 }
565 });
566 }
567
Jonathan Hartaaa56572015-01-28 21:56:35 -0800568 private AntiEntropyAdvertisement<K> createAdvertisement() {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700569 return new AntiEntropyAdvertisement<K>(localNodeId,
570 ImmutableMap.copyOf(Maps.transformValues(items, MapValue::digest)));
Jonathan Hartaaa56572015-01-28 21:56:35 -0800571 }
572
573 private void handleAntiEntropyAdvertisement(AntiEntropyAdvertisement<K> ad) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700574 if (destroyed || underHighLoad()) {
575 return;
576 }
577 try {
Jonathan Hart9a426f82015-09-03 15:43:13 +0200578 if (log.isTraceEnabled()) {
579 log.trace("Received anti-entropy advertisement from {} for {} with {} entries in it",
580 mapName, ad.sender(), ad.digest().size());
581 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700582 antiEntropyCheckLocalItems(ad).forEach(this::notifyListeners);
Jonathan Hartaaa56572015-01-28 21:56:35 -0800583
Madan Jampani3d76c942015-06-29 23:37:10 -0700584 if (!lightweightAntiEntropy) {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700585 // if remote ad has any entries that the local copy is missing, actively sync
586 // TODO: Missing keys is not the way local copy can be behind.
587 if (Sets.difference(ad.digest().keySet(), items.keySet()).size() > 0) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700588 // TODO: Send ad for missing keys and for entries that are stale
589 sendAdvertisementToPeer(ad.sender());
Jonathan Hartf893be82015-02-24 17:35:51 -0800590 }
Jonathan Hartaaa56572015-01-28 21:56:35 -0800591 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700592 } catch (Exception e) {
593 log.warn("Error handling anti-entropy advertisement", e);
HIGUCHI Yuta00c3f572015-02-25 07:33:50 -0800594 }
Jonathan Hartaaa56572015-01-28 21:56:35 -0800595 }
596
597 /**
Madan Jampani3d76c942015-06-29 23:37:10 -0700598 * Processes anti-entropy ad from peer by taking following actions:
599 * 1. If peer has an old entry, updates peer.
600 * 2. If peer indicates an entry is removed and has a more recent
601 * timestamp than the local entry, update local state.
Jonathan Hartaaa56572015-01-28 21:56:35 -0800602 */
Jonathan Hartaaa56572015-01-28 21:56:35 -0800603 private List<EventuallyConsistentMapEvent<K, V>> antiEntropyCheckLocalItems(
604 AntiEntropyAdvertisement<K> ad) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700605 final List<EventuallyConsistentMapEvent<K, V>> externalEvents = Lists.newLinkedList();
Jonathan Hartaaa56572015-01-28 21:56:35 -0800606 final NodeId sender = ad.sender();
Madan Jampani3d76c942015-06-29 23:37:10 -0700607 items.forEach((key, localValue) -> {
608 MapValue.Digest remoteValueDigest = ad.digest().get(key);
609 if (remoteValueDigest == null || localValue.isNewerThan(remoteValueDigest.timestamp())) {
Jonathan Hartaaa56572015-01-28 21:56:35 -0800610 // local value is more recent, push to sender
Madan Jampani3d76c942015-06-29 23:37:10 -0700611 queueUpdate(new UpdateEntry<>(key, localValue), ImmutableList.of(sender));
Madan Jampanid13f3b82015-07-01 17:37:50 -0700612 }
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700613 if (remoteValueDigest != null
614 && remoteValueDigest.isNewerThan(localValue.digest())
615 && remoteValueDigest.isTombstone()) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700616 MapValue<V> tombstone = MapValue.tombstone(remoteValueDigest.timestamp());
Madan Jampanid13f3b82015-07-01 17:37:50 -0700617 MapValue<V> previousValue = removeInternal(key,
618 Optional.empty(),
Madan Jampani483d0a22015-08-19 17:33:00 -0700619 Optional.of(tombstone));
Madan Jampanid13f3b82015-07-01 17:37:50 -0700620 if (previousValue != null && previousValue.isAlive()) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700621 externalEvents.add(new EventuallyConsistentMapEvent<>(mapName, REMOVE, key, previousValue.get()));
Jonathan Hartaaa56572015-01-28 21:56:35 -0800622 }
623 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700624 });
Jonathan Hartaaa56572015-01-28 21:56:35 -0800625 return externalEvents;
626 }
627
Madan Jampani3d76c942015-06-29 23:37:10 -0700628 private void processUpdates(Collection<UpdateEntry<K, V>> updates) {
629 if (destroyed) {
630 return;
Jonathan Hartaaa56572015-01-28 21:56:35 -0800631 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700632 updates.forEach(update -> {
633 final K key = update.key();
634 final MapValue<V> value = update.value();
Madan Jampani483d0a22015-08-19 17:33:00 -0700635 if (value == null || value.isTombstone()) {
636 MapValue<V> previousValue = removeInternal(key, Optional.empty(), Optional.ofNullable(value));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700637 if (previousValue != null && previousValue.isAlive()) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700638 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, REMOVE, key, previousValue.get()));
Madan Jampanid13f3b82015-07-01 17:37:50 -0700639 }
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700640 } else if (putInternal(key, value)) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700641 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, PUT, key, value.get()));
Jonathan Hartaaa56572015-01-28 21:56:35 -0800642 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700643 });
Jonathan Hartdb3af892015-01-26 13:19:07 -0800644 }
645
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800646 // TODO pull this into the class if this gets pulled out...
647 private static final int DEFAULT_MAX_EVENTS = 1000;
648 private static final int DEFAULT_MAX_IDLE_MS = 10;
649 private static final int DEFAULT_MAX_BATCH_MS = 50;
650 private static final Timer TIMER = new Timer("onos-ecm-sender-events");
Jonathan Hartdb3af892015-01-26 13:19:07 -0800651
Madan Jampani3d76c942015-06-29 23:37:10 -0700652 private final class EventAccumulator extends AbstractAccumulator<UpdateEntry<K, V>> {
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800653
654 private final NodeId peer;
655
656 private EventAccumulator(NodeId peer) {
657 super(TIMER, DEFAULT_MAX_EVENTS, DEFAULT_MAX_BATCH_MS, DEFAULT_MAX_IDLE_MS);
658 this.peer = peer;
659 }
660
661 @Override
Madan Jampani3d76c942015-06-29 23:37:10 -0700662 public void processItems(List<UpdateEntry<K, V>> items) {
663 Map<K, UpdateEntry<K, V>> map = Maps.newHashMap();
664 items.forEach(item -> map.compute(item.key(), (key, existing) ->
Madan Jampani92c64eb2015-07-23 15:37:07 -0700665 item.isNewerThan(existing) ? item : existing));
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800666 communicationExecutor.submit(() -> {
Madan Jampani3d76c942015-06-29 23:37:10 -0700667 clusterCommunicator.unicast(ImmutableList.copyOf(map.values()),
Madan Jampani175e8fd2015-05-20 14:10:45 -0700668 updateMessageSubject,
669 serializer::encode,
670 peer)
671 .whenComplete((result, error) -> {
672 if (error != null) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700673 log.debug("Failed to send to {}", peer, error);
Madan Jampani175e8fd2015-05-20 14:10:45 -0700674 }
675 });
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800676 });
Jonathan Hartdb3af892015-01-26 13:19:07 -0800677 }
678 }
Jonathan Hart4a29c592015-09-23 17:55:07 -0700679}