src/java/voldemort/versioning/VectorClockUtils.java

   1 /*
   2  * Copyright 2008-2013 LinkedIn, Inc
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
   5  * use this file except in compliance with the License. You may obtain a copy of
   6  * 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, WITHOUT
  12  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  13  * License for the specific language governing permissions and limitations under
  14  * the License.
  15  */
  16 package voldemort.versioning;
  17
  18 import java.util.ArrayList;
  19 import java.util.Iterator;
  20 import java.util.List;
  21 import java.util.Set;
  22 import java.util.SortedSet;
  23
  24 import com.google.common.collect.Sets;
  25
  26 public class VectorClockUtils {
  27
  28     /**
  29      * Compare two VectorClocks, the outcomes will be one of the following: <br>
  30      * -- Clock 1 is BEFORE clock 2, if there exists an nodeId such that
  31      * c1(nodeId) <= c2(nodeId) and there does not exist another nodeId such
  32      * that c1(nodeId) > c2(nodeId). <br>
  33      * -- Clock 1 is CONCURRENT to clock 2 if there exists an nodeId, nodeId2
  34      * such that c1(nodeId) < c2(nodeId) and c1(nodeId2) > c2(nodeId2)<br>
  35      * -- Clock 1 is AFTER clock 2 otherwise
  36      *
  37      * @param v1 The first VectorClock
  38      * @param v2 The second VectorClock
  39      */
  40     public static Occurred compare(VectorClock v1, VectorClock v2) {
  41         if(v1 == null || v2 == null)
  42             throw new IllegalArgumentException("Can't compare null vector clocks!");
  43         // We do two checks: v1 <= v2 and v2 <= v1 if both are true then
  44         boolean v1Bigger = false;
  45         boolean v2Bigger = false;
  46
  47         SortedSet<Short> v1Nodes = v1.getVersionMap().navigableKeySet();
  48         SortedSet<Short> v2Nodes = v2.getVersionMap().navigableKeySet();
  49         // get clocks(nodeIds) that both v1 and v2 has
  50         SortedSet<Short> commonNodes = Sets.newTreeSet(v1Nodes);
  51         commonNodes.retainAll(v2Nodes);
  52         // if v1 has more nodes than common nodes
  53         // v1 has clocks that v2 does not
  54         if(v1Nodes.size() > commonNodes.size()) {
  55             v1Bigger = true;
  56         }
  57         // if v2 has more nodes than common nodes
  58         // v2 has clocks that v1 does not
  59         if(v2Nodes.size() > commonNodes.size()) {
  60             v2Bigger = true;
  61         }
  62         // compare the common parts
  63         for(Short nodeId: commonNodes) {
  64             // no need to compare more
  65             if(v1Bigger && v2Bigger) {
  66                 break;
  67             }
  68             long v1Version = v1.getVersionMap().get(nodeId);
  69             long v2Version = v2.getVersionMap().get(nodeId);
  70             if(v1Version > v2Version) {
  71                 v1Bigger = true;
  72             } else if(v1Version < v2Version) {
  73                 v2Bigger = true;
  74             }
  75         }
  76
  77         /*
  78          * This is the case where they are equal. Consciously return BEFORE, so
  79          * that the we would throw back an ObsoleteVersionException for online
  80          * writes with the same clock.
  81          */
  82         if(!v1Bigger && !v2Bigger)
  83             return Occurred.BEFORE;
  84         /* This is the case where v1 is a successor clock to v2 */
  85         else if(v1Bigger && !v2Bigger)
  86             return Occurred.AFTER;
  87         /* This is the case where v2 is a successor clock to v1 */
  88         else if(!v1Bigger && v2Bigger)
  89             return Occurred.BEFORE;
  90         /* This is the case where both clocks are parallel to one another */
  91         else
  92             return Occurred.CONCURRENTLY;
  93     }
  94
  95     /**
  96      * Given a set of versions, constructs a resolved list of versions based on
  97      * the compare function above
  98      *
  99      * @param values
 100      * @return list of values after resolution
 101      */
 102     public static List<Versioned<byte[]>> resolveVersions(List<Versioned<byte[]>> values) {
 103         List<Versioned<byte[]>> resolvedVersions = new ArrayList<Versioned<byte[]>>(values.size());
 104         // Go over all the values and determine whether the version is
 105         // acceptable
 106         for(Versioned<byte[]> value: values) {
 107             Iterator<Versioned<byte[]>> iter = resolvedVersions.iterator();
 108             boolean obsolete = false;
 109             // Compare the current version with a set of accepted versions
 110             while(iter.hasNext()) {
 111                 Versioned<byte[]> curr = iter.next();
 112                 Occurred occurred = value.getVersion().compare(curr.getVersion());
 113                 if(occurred == Occurred.BEFORE) {
 114                     obsolete = true;
 115                     break;
 116                 } else if(occurred == Occurred.AFTER) {
 117                     iter.remove();
 118                 }
 119             }
 120             if(!obsolete) {
 121                 // else update the set of accepted versions
 122                 resolvedVersions.add(value);
 123             }
 124         }
 125
 126         return resolvedVersions;
 127     }
 128
 129     /**
 130      * Generates a vector clock with the provided values
 131      *
 132      * @param serverIds servers in the clock
 133      * @param clockValue value of the clock for each server entry
 134      * @param timestamp ts value to be set for the clock
 135      * @return
 136      */
 137     public static VectorClock makeClock(Set<Integer> serverIds, long clockValue, long timestamp) {
 138         List<ClockEntry> clockEntries = new ArrayList<ClockEntry>(serverIds.size());
 139         for(Integer serverId: serverIds) {
 140             clockEntries.add(new ClockEntry(serverId.shortValue(), clockValue));
 141         }
 142         return new VectorClock(clockEntries, timestamp);
 143     }
 144
 145     /**
 146      * Generates a vector clock with the provided nodes and current time stamp
 147      * This clock can be used to overwrite the existing value avoiding obsolete
 148      * version exceptions in most cases, except If the existing Vector Clock was
 149      * generated in custom way. (i.e. existing vector clock does not use
 150      * milliseconds)
 151      *
 152      * @param serverIds servers in the clock
 153      */
 154     public static VectorClock makeClockWithCurrentTime(Set<Integer> serverIds) {
 155         return makeClock(serverIds, System.currentTimeMillis(), System.currentTimeMillis());
 156     }
 157
 158 }