FDB Conflict Algorithm - Warehouse Analogy

Database (Shards) The Warehouse

Shelf A-M Ver: 100

Apple Banana Grape Melon

Shelf N-Z Ver: 100

Orange Pear Strawberry Watermelon

(Click versions to edit manually for simulation)

Transaction (T_x) The Worker

Entry Time (Read Ver):

Commit Time (Write Ver): 110

1. What did I look at? (Read Set) Shelf A-M (Apple...)
Shelf N-Z (Orange...)

2. What did I change? (Write Set) Shelf A-M
Shelf N-Z

            Conflict Resolution Algorithm
        

            for each range ∈ R_r do
                ranges = lastCommit.intersect(range)
                for each r ∈ ranges do
                    if lastCommit[r] > T_x.readVersion then
                        return abort;
            
            // Commit Path
            for each range ∈ R_w do
                lastCommit[range] = T_x.commitVersion;
            return commit;
        

Execution Log

> Ready to simulate transaction...