Examples of org.syncany.operations.down.DatabaseReconciliator

org.syncany.operations.down.DatabaseReconciliator
The database reconciliator implements various parts of the sync down algorithm (see also: {@link DownOperation}). Its main responsibility is to compare the local database to the other clients' delta databases. The final goal of the algorithms described in this class is to determine a winning {@link MemoryDatabase} (or better: a winning database {@link DatabaseBranch}) of a client.
All algorithm parts largely rely on the comparison of a client's database branch, i.e. its committed set of {@link DatabaseVersion}s. Instead of comparing the entire database versions of the different clients, however, the comparisons solely rely on the {@link DatabaseVersionHeader}s. In particular, most of them only compare the {@link VectorClock}. If the vector clocks are in conflict (= simultaneous), the local timestamp is used as a final decision (oldest wins).
Because there are many ways to say it, there are a few explanations to the algorithms:
Algorithm (short explanation):
1. Go back to the first conflict of all versions
2. Determine winner of this conflict; follow the winner(s) branch
3. If another conflict occurs, go to step 2
Algorithm (medium long explanation):
1. Determine last versions per client A B C
2. Determine if there are conflicts between last versions of client, if yes continue
3. Determine last common versions between clients
4. Determine first conflicting versions between clients (= last common version + 1)
5. Compare first conflicting versions and determine winner
6. If one client has the winning first conflicting version, take this client's history as a winner
7. If more than 2 clients are based on the winning first conflicting version, compare their other versions
  1. Iterate forward (from conflicting to newer!), and check for conflicts
  2. If a conflict is found, determine the winner and continue the branch of the winner
  3. This must be done until the last (newest!) version of the winning branch is reached
8. If the local machine loses (= winning first conflicting database version is NOT from the local machine) and there is a first conflicting database version from the local machine (and possibly more database versions),
Algorithm (long explanation):
- {@link #stitchBranches(DatabaseBranches,String,DatabaseBranch) stitchBranches()}: Due to the fact that Syncany exchanges only delta databases, but the algorithms require a full branch for the winner-determination, the full per-client branches must be created/derived from all the downloaded branches.
- {@link #findLastCommonDatabaseVersionHeader(DatabaseBranch,DatabaseBranches) findLastCommonDatabaseVersionHeader()}: Once the full database branches have been stitched together, the algorithm must determine whether there are any conflicts between the clients' branches. As a first step, a last common {@link DatabaseVersionHeader} is determined, i.e. a header that all clients share.
- {@link #findFirstConflictingDatabaseVersionHeader(DatabaseVersionHeader,DatabaseBranches) findFirstConflictingDatabaseVersionHeader()}: By definition, the first conflicting database version between the clients is the database version following the last common version (= last common database version + 1).
- {@link #findWinningFirstConflictingDatabaseVersionHeaders(TreeMap) findWinningFirstConflictingDatabaseVersionHeaders()}: Comparing the vector clocks of the first conflicting database version headers, the winners can be determined. This is done using the local timestamps of the database version headers (earliest wins).
- {@link #findWinnersLastDatabaseVersionHeader(TreeMap,DatabaseBranches) findWinnersWinnersLastDatabaseVersionHeader()}: Having found one or many winning branches (candidates), the last step is to walk forward and compare the winning branches with each other -- comparing their database version headers. If a set does not match, a winner is determined until only one client branch remains. This client branch is the final winning branch.
@see DownOperation @see VectorClock @author Philipp C. Heckel @author Steffen Dangmann

      "C/(C1)/T=1376074225383",
      "C/(C2)/T=1376074225399",
      "C/(C3)/T=1376074225416",
    }));    
    
    DatabaseReconciliator databaseVersionUpdateDetector = new DatabaseReconciliator();
    DatabaseBranches actualStitchedRemoteBranches = databaseVersionUpdateDetector.stitchBranches(allBranches, "D", new DatabaseBranch());
    
    DatabaseBranches expectedStitchedBranches = new DatabaseBranches();
    
    expectedStitchedBranches.put("A", TestDatabaseUtil.createBranch(new String[] {
      "A/(A1)/T=1376074225169",

View Full Code Here

      "C/(A5,B1,C2)/T=8",
      // --> B
      "C/(A5,B2,C3)/T=10",
    }));    
    
    DatabaseReconciliator databaseVersionUpdateDetector = new DatabaseReconciliator();
    DatabaseBranches actualStitchedRemoteBranches = databaseVersionUpdateDetector.stitchBranches(allBranches, "D", new DatabaseBranch());
    
    DatabaseBranches expectedStitchedBranches = new DatabaseBranches();
    
    expectedStitchedBranches.put("A", TestDatabaseUtil.createBranch(new String[] {
        "A/(A1)/T=1",

View Full Code Here

    printBranches(allBranches);
      
  
    System.out.println("----------");
    
    DatabaseReconciliator databaseReconciliator = new DatabaseReconciliator();
    TestResult actualTestResult = new TestResult();
    
    // Get 'local' branch
    DatabaseBranch localBranch = allBranches.getBranch(localMachineName);
    
    // Get all the other ones (clone 'all', and remove local)
    DatabaseBranches unstitchedRemoteBranches = allBranches.clone();
    unstitchedRemoteBranches.remove(localMachineName);


    DatabaseBranches stitchedRemoteBranches = databaseReconciliator.stitchBranches(unstitchedRemoteBranches, localMachineName, localBranch);
    
    System.out.println("Before Orchestration : Remote");
    printBranches(unstitchedRemoteBranches);
    System.out.println("Before Orchestration : Local");
    printBranch(localBranch);
    System.out.println("BEGIN Branch Orchestration!! ----------");
    printBranches(stitchedRemoteBranches);        
    System.out.println("END Branch Orchestration ----------");
        
    actualTestResult.lastCommonHeader = databaseReconciliator.findLastCommonDatabaseVersionHeader(localBranch, stitchedRemoteBranches);
    actualTestResult.firstConflictingDatabaseVersionHeaders = databaseReconciliator.findFirstConflictingDatabaseVersionHeader(actualTestResult.lastCommonHeader, stitchedRemoteBranches);
    actualTestResult.winningFirstConflictingDatabaseVersionHeaders = databaseReconciliator.findWinningFirstConflictingDatabaseVersionHeaders(actualTestResult.firstConflictingDatabaseVersionHeaders);
    actualTestResult.winnersWinnersLastDatabaseVersionHeader = databaseReconciliator.findWinnersLastDatabaseVersionHeader(actualTestResult.winningFirstConflictingDatabaseVersionHeaders, stitchedRemoteBranches);
    
    System.out.println("Actual lastCommonDatabaseVersionHeader = " +actualTestResult.lastCommonHeader);
    System.out.println("Expect lastCommonDatabaseVersionHeader = " +expectedTestResult.lastCommonHeader);


    System.out.println("Actual firstConflictingDatabaseVersionHeaders = "); printMap(actualTestResult.firstConflictingDatabaseVersionHeaders);

View Full Code Here

TOP

Related Classes of org.syncany.operations.down.DatabaseReconciliator

org.syncany.database.DatabaseVersionHeader

org.syncany.database.VectorClock

org.syncany.database.VectorClock.VectorClockComparison

org.syncany.tests.database.DatabaseReconciliatorTest

All source code are property of their respective owners. Java is a trademark of Sun Microsystems, Inc and owned by ORACLE Inc. Contact coftware#gmail.com.