001/* 002 * Syncany, www.syncany.org 003 * Copyright (C) 2011-2016 Philipp C. Heckel <philipp.heckel@gmail.com> 004 * 005 * This program is free software: you can redistribute it and/or modify 006 * it under the terms of the GNU General Public License as published by 007 * the Free Software Foundation, either version 3 of the License, or 008 * (at your option) any later version. 009 * 010 * This program is distributed in the hope that it will be useful, 011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 013 * GNU General Public License for more details. 014 * 015 * You should have received a copy of the GNU General Public License 016 * along with this program. If not, see <http://www.gnu.org/licenses/>. 017 */ 018package org.syncany.operations.down; 019 020import java.util.AbstractMap; 021import java.util.ArrayList; 022import java.util.Collections; 023import java.util.List; 024import java.util.Map; 025import java.util.Map.Entry; 026import java.util.logging.Level; 027import java.util.logging.Logger; 028 029import org.syncany.database.DatabaseVersion; 030import org.syncany.database.DatabaseVersionHeader; 031import org.syncany.database.MemoryDatabase; 032import org.syncany.database.VectorClock; 033 034/** 035 * The database reconciliator implements various parts of the sync down algorithm (see also: 036 * {@link DownOperation}). Its main responsibility is to compare the local database to the 037 * other clients' delta databases. The final goal of the algorithms described in this class is 038 * to determine a winning {@link MemoryDatabase} (or better: a winning {@link DatabaseBranch}) of 039 * a client. 040 * 041 * <p>All algorithm parts largely rely on the comparison of a client's database branch, i.e. its 042 * committed set of {@link DatabaseVersion}s. Instead of comparing the entire database versions 043 * of the different clients, however, the comparisons solely rely on the {@link DatabaseVersionHeader}s. 044 * In particular, most of them only compare the {@link VectorClock}. If the vector clocks are 045 * in conflict (= simultaneous), the local timestamp is used as a final decision (oldest wins). 046 * 047 * <p><b>Algorithm:</b> 048 * <ol> 049 * <li>Input: Local branch, unknown remote branches</li> 050 * <li>Sort the databaseversions by vectorclocks, tiebreaking with timestamps.</li> 051 * <li>Walk through the sorted list and construct the winning branch. 052 * </ol> 053 * 054 * @see DownOperation 055 * @see VectorClock 056 * @author Philipp C. Heckel (philipp.heckel@gmail.com) 057 * @author Pim Otte (otte.pim@gmail.com) 058 * @author Steffen Dangmann (steffen.dangmann@googlemail.com) 059 */ 060public class DatabaseReconciliator { 061 private static final Logger logger = Logger.getLogger(DatabaseReconciliator.class.getSimpleName()); 062 063 /** 064 * Implements the core synchronization algorithm as described {@link DatabaseReconciliator in the class description}. 065 * 066 * @param allBranches All branches of all machines (including local) 067 * @return Returns the branch of the winning client 068 */ 069 public Map.Entry<String, DatabaseBranch> findWinnerBranch(DatabaseBranches allBranches) 070 throws Exception { 071 072 Entry<String, DatabaseBranch> winnersNameAndBranch = findWinnersNameAndBranch(allBranches); 073 074 if (winnersNameAndBranch != null) { 075 String winnersName = winnersNameAndBranch.getKey(); 076 DatabaseBranch winnersBranch = winnersNameAndBranch.getValue(); 077 078 if (logger.isLoggable(Level.INFO)) { 079 logger.log(Level.INFO, "- Winner is " + winnersName + " with branch: "); 080 081 for (DatabaseVersionHeader databaseVersionHeader : winnersBranch.getAll()) { 082 logger.log(Level.INFO, " + " + databaseVersionHeader); 083 } 084 } 085 086 return winnersNameAndBranch; 087 } 088 else { 089 return null; 090 } 091 } 092 093 public DatabaseBranch findLosersPruneBranch(DatabaseBranch losersBranch, DatabaseBranch winnersBranch) { 094 DatabaseBranch losersPruneBranch = new DatabaseBranch(); 095 096 boolean pruneBranchStarted = false; 097 098 for (int i = 0; i < losersBranch.size(); i++) { 099 if (pruneBranchStarted) { 100 losersPruneBranch.add(losersBranch.get(i)); 101 } 102 else if (i < winnersBranch.size() && !losersBranch.get(i).equals(winnersBranch.get(i))) { 103 pruneBranchStarted = true; 104 losersPruneBranch.add(losersBranch.get(i)); 105 } 106 } 107 108 return losersPruneBranch; 109 } 110 111 public DatabaseBranch findWinnersApplyBranch(DatabaseBranch losersBranch, DatabaseBranch winnersBranch) { 112 logger.log(Level.INFO, "Finding winnersApplyBranch."); 113 logger.log(Level.INFO, "Losers Branch: " + losersBranch); 114 logger.log(Level.INFO, "Winners Branch: " + winnersBranch); 115 DatabaseBranch winnersApplyBranch = new DatabaseBranch(); 116 117 boolean applyBranchStarted = false; 118 119 for (int i = 0; i < winnersBranch.size(); i++) { 120 if (!applyBranchStarted) { 121 if (i >= losersBranch.size() || !losersBranch.get(i).equals(winnersBranch.get(i))) { 122 applyBranchStarted = true; 123 } 124 } 125 126 if (applyBranchStarted) { 127 winnersApplyBranch.add(winnersBranch.get(i)); 128 } 129 } 130 131 return winnersApplyBranch; 132 } 133 134 /** 135 * Algorithm to find the winner's database branch (client name and branch). 136 * The winner's branch is used to determine the local file system actions. 137 * 138 * <p>Basic algorithm: Sort all databaseversions by vectorclocks, tiebreaking with timestamps and machinenames. 139 * Iterate over this list, adding databaseversions to the winning branch if they are not simultaneous with the 140 * winning branch up until this point. 141 * 142 * <p><b>Illustration:</b><br> 143 * Suppose the following branches exist. 144 * Naming: <em>created-by / vector clock / local time</em>. 145 * 146 * <pre> 147 * A B C 148 * --|------------------------------------------------- 149 * 0 | A/(A1)/T=10 B/(A3,B1)/T=20 C/(A1,C1)/T=14 150 * 1 | A/(A2)/T=13 C/(A1,C2)/T=15 151 * 2 | A/(A3)/T=19 152 * 3 | A/(A4)/T=23 153 * </pre> 154 * 155 * <b>Sorted Database versions:</b> 156 * <ol> 157 * <li>A[0]:A/(A1)/T=10</li> 158 * <li>A[1]:A/(A2)/T=13</li> 159 * <li>C[0]:C/(A1,C1)/T=14</li> 160 * <li>C[1]:C/(A1,C2)/T=15</li> 161 * <li>A[2]:A/(A3)/T=19</li> 162 * <li>B[0]:B/(A3,B1)/T=20</li> 163 * <li>A[3]:A/(A4)/T=23</li> 164 * </ol> 165 * 166 * <b>Iterating through the list:</b> 167 * <ol> 168 * <li>A[0] is the first version. Add it.</li> 169 * <li>A[1] > A[0]. Add it.</li> 170 * <li>C[0] is simultaneous with A[1]. Ignore it.</li> 171 * <li>C[1] is simultaneous with A[1]. Ignore it.</li> 172 * <li>A[2] > A[1]. Add it.</li> 173 * <li>B[0] > A[2]. Add it.</li> 174 * <li>A[3] is simultaneous with B[0]. Ignore it.</li> 175 * </ol> 176 * 177 * <b>Winning branch:</b> 178 * <ol> 179 * <li>A[0]:A/(A1)/T=10</li> 180 * <li>A[1]:A/(A2)/T=13</li> 181 * <li>A[2]:A/(A3)/T=19</li> 182 * <li>B[0]:B/(A3,B1)/T=20</li> 183 * </ol> 184 * 185 * Last version matches last version of B. Hence B wins. 186 * 187 * @param allBranches All branches of all machines (including local) 188 * @return Returns the name and the branch of the winning machine 189 */ 190 private Entry<String, DatabaseBranch> findWinnersNameAndBranch(DatabaseBranches allBranches) { 191 List<DatabaseVersionHeader> databaseVersionHeaders = sortBranches(allBranches); 192 193 if (databaseVersionHeaders.size() == 0) { 194 return null; 195 } 196 197 // Determine winning branch 198 DatabaseBranch winnersBranch = new DatabaseBranch(); 199 DatabaseVersionHeaderComparator databaseVersionHeaderComparator = new DatabaseVersionHeaderComparator(false); 200 201 for (DatabaseVersionHeader potentialWinner : databaseVersionHeaders) { 202 boolean emptyWinnerBranch = winnersBranch.size() == 0; 203 boolean potentialWinnerWins = !emptyWinnerBranch && databaseVersionHeaderComparator.compare(potentialWinner, winnersBranch.getLast()) > 0; 204 205 if (emptyWinnerBranch || potentialWinnerWins) { 206 logger.log(Level.INFO, "Adding database version to winning branch: " + potentialWinner); 207 winnersBranch.add(potentialWinner); 208 } 209 else { 210 logger.log(Level.INFO, "Ignoring databaseVersion: " + potentialWinner); 211 } 212 } 213 214 // Determine client name for winning branch 215 DatabaseVersionHeader winningLastDatabaseVersionHeader = winnersBranch.getLast(); 216 217 for (String currentClient : allBranches.getClients()) { 218 DatabaseBranch currentBranch = allBranches.getBranch(currentClient); 219 DatabaseVersionHeader currentBranchLastDatabaseVersionHeader = currentBranch.getLast(); 220 221 if (winningLastDatabaseVersionHeader.equals(currentBranchLastDatabaseVersionHeader)) { 222 return new AbstractMap.SimpleEntry<String, DatabaseBranch>(currentClient, winnersBranch); 223 } 224 } 225 226 return null; 227 } 228 229 private List<DatabaseVersionHeader> sortBranches(DatabaseBranches allBranches) { 230 List<DatabaseVersionHeader> databaseVersionHeaders = new ArrayList<DatabaseVersionHeader>(); 231 232 for (String client : allBranches.getClients()) { 233 databaseVersionHeaders.addAll(allBranches.getBranch(client).getAll()); 234 } 235 236 Collections.sort(databaseVersionHeaders, new DatabaseVersionHeaderComparator(true)); 237 238 return databaseVersionHeaders; 239 } 240}