Eventually Consistent Group Expense Manager

Authors: Abhishek Kumar Singh, Fan Yi

Email: aksingh@princeton.edu, fanyi@princeton.edu

COS518_ProjectDemo.mov

Demo Description

We provide a demo with three devices all running on the same machine and communicating over localhost. However our system can support any number of devices and can be run over a network as well.

Summary of the demo:

1. We Create Two Groups of user ((1,2,3) and (1,3)) on device 1(00:00–00:30)
2. Before sync new created groups are not visible of device 2 and 3. When device 3 syncs with device 1, groups become visible on device 3. (00:30–01:04)
3. We add two transaction on device 3 –1 owes 2, 4.5 dollars and 2 owes 3, 4.5 dollars.(01:04–01:36)
4. We demonstrate the payment minimisation feature where our application simplifies the above debts and shows all of them can be settled by just 1 payment i.e. 1 pays 3, 4.5 dollars.(01:36–01:47)
5. We see that the debt entries are visible on device 2, and we mark the transaction “2 owes 3,4.5 dollars” as settled.(01:47–02:03)
6. We see that after sync, the settled status of “2 owes 3,4.5 dollars” is visible on device 3. (02:03–02:21)
7. We see that the payment minimisation acknowledges the settlement status and shows the new payment to be made as “1 pays 2, 4.5 dollars”.(02:21–02:28).
8. Since device 1 has not synced with 2 or 3 after settlement was reflected on them, status of “2 owes 3,4.5 dollars” on device 1 is still “not settled”. (02:28–02:40)
9. We crash both backend and frontend of device 1 and relaunch them. We see that the debts records are successfully recovered.(02:40–03:02).

10. When device 1 syncs with client2 , it changes the status of “2 owes 3,4.5 dollars” to settled as it receives this information now. (03:02–03:32)

Overview

We develop a distributed application to record debts and settlements among a group of friends. Our application is primarily based on the Bayou Model for eventual consistency to maintain a ledger of debts. Our basic functionality is reimplementation of the techniques mentioned in the paper titled “Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System” (reference [1]). We also use various other techniques studied during the course to implement various features of the application e.g. Logging using Atomic rename, temporary multi versioning of logs to survive crashes during log write operation etc.

Unlike the original Bayou paper, we added a feature where an old debt entry can be marked as settled, this creates a relationship between two log entries separated in time and introduces new challenges in removing committed entries from log. The techniques used to handle this will be described later.

We further provide greedy debt simplification feature, which will try to reduce the number of payments required to settle all the debt. In terms of records of the applications, it translates to a method of merger of different records affecting the same group of friends.

In this report we will describe the implementation details of various features implemented in the app. We are supplementing the report with a demo video which demonstrates various functionality with 3 users.

Problem Statement

There is a set of people numbered 1 to N. Among them a subset S, likes to go out together and usually pay for each other. They want an application that records the debts that exist in the group and tells each one of them what payments they need to make. They further want to track the status of debts and hence want a feature that allows them to mark debts as settled (for which payments have been made).

Why eventual consistency for this problem?

We resort to an eventual consistency-based application to solve the problem as we don’t need to see a debt immediately after a someone adds it. The app should eventually reflect all the debts. Also, it might be possible that a person keeps adding debts to his instance of the app but is actually offline.

Application Architecture

Basic Execution Flow: (Bayou like functionality)

There are three kinds of records:

• Group Info Record — It contains the information about a group of users e.g. 1,2 and 3 might have a group called “LA Trip” to record debts of their LA trip
• Debt Record — contains information about who owes whom e.g. 1 owes 2, 5 dollars
• Settlement record — contains information about the debt which got settled e.g. “1 owes 2, 5 dollars” is settled. The original debt record is identified by timestamp.deviceiD (where deviceid is the id of the device that created the record) which acts as a unique marker.

1. Each RPC Server maintains a lamport clock.
2. Whenever a debt/settlement record is added by the frontend, it gets assigned a timestamp equal to current lamport clock value on that server.
3. Devices sync with each other periodically exchanging log entries of debt/settlement records and group information (what groups are known on the device)
4. One of the devices is responsible for committing the records and assign it with a commit timestamp, this device can also be an isolated, “always on” server sitting in a datacenter without any frontend. It commits records in the order in which they are present in its log.
5. There is a total ordering to the records — committed records are ordered before uncommitted records in the order of commit timestamp. Uncommitted records are ordered by timestamp.deviceiD

Settlement Functionality

Unlike the original Bayou paper where all records are created independent of each other (they might be conflicting, but one doesn’t depend on another) we provide a functionality where user can mark an old debt as settled, and hence it creates a record which references an older debt record.

We implement this functionality by identifying each debt record by its (timestamp, device id of the user that created it) hence providing a unique identifier. Whenever a user marks an old debt record as settled, it creates a new settlement record containing the identifier of the old debt record.

Key points that imply correctness –

1. Since the user who creates the settlement record has already seen the original record the timestamp associated with settlement record will always be higher than original record (because timestamps are assigned using lamport clocks) and hence settlement will always be ordered after the original record
2. Since the user who creates the settlement record has both original and settlement records in its log, both original and settlement record will be part of gossips together and hence no device can end up with a log that has only the settlement record.
3. Following from 1 and 2, the settlement record will always be committed after the original record.

Crash Tolerance

To make the application crash tolerant, application acknowledges requests from the frontend only after it has added the corresponding record to the log on the disk.

Applications also log lamport clock values and group information. In order to make writing log on the disk crash tolerant we employ two techniques: atomic rename, and temporary versioning. The latter is required because some OS might not allow rename operation to replace an already existing file.

We use following steps for logging:

1. Write the new log to a temporary log file.
2. Atomically rename the already present logfile to logfile_old
3. Atomically rename the already temporary log file to logfile
4. Delete logfile_old

When the application restarts after crash, the RPC server will try to recover from logfile. If logfile is not present (certain crash scenarios can lead to this) then it recovers from logfile_old. We recover the old lamport clock values, and offset them by some fixed constant before use. We also recover largest assigned commit timestamp and all the records(debt, groupInfo and settlement).

This procedure ensures that no matter the time of crash, the applications is always able to at least recover the records that were acknowledged to the front end.

If it happens that server crashes after the record has been added to the log and before the record was acknowledged to the front end, when the app restarts the frontend will display that record is already present and hence the user will not add it again.

Log Cleanup

It seems a logical requirement for the user to be able to remove settled records (debt record and settlement record). The commit device might need to retain all the transactions till it confirms that a certain settled record has been removed by all users (we have not implemented this functionality).

For other users, they should be able to remove settled transactions from the log in order to shorten it and limit its size.

To ensure correctness, a log can be removed when both the debt record and settlement record have been committed and are present in the log of commit device. This is necessary to make sure that both debt record and settlement record are present in the full log residing on the commit device. This way we don’t end up in a scenario where a record gets deleted from the system without reaching the commit device.

However, if a device removes records it should make sure that if it receives that record again during further syncs, it should not add it to the log. We solve this problem by maintaining a “latestTs” table which contains, for every device (including self), the highest timestamp for a record that was created by that device and was seen. E.g. latestTs[2] on device 1 will contain the highest timestamp value of the records created by device 2 that have been seen by device 1. We use this table to identify duplicate records received during syncs.

Minimising payments required for debt settlements

We try to provide a simplified view of the debts involved by reducing the number of payments that will be required to clear all debts.

For e.g. if A owes B 5 dollars and B owes C 5 dollars it should be possible to settle both debts by just one payment which is A pays C 5 dollars.

We model this problem as follows:

Every User is a node in a directed Graph G. A directed edge between two users, say 1 and 2, of weight w, corresponds to a payment of w dollars.

We need to find a graph with minimum number of edges such that if payments are made as per the edges of the graph, then all debts get settled.

This is a well-studied problem in literature which has an optimal solution using min-cost max flow algorithm.

However due to implementation complexity of min-cost max flow algorithm, we use a sub-optimal greedy algorithm for solving the problem and implemented that.

Algorithm Description:

Note: We have not done enough literature survey on this algorithm and hence do not claim any novelty as of now.

1. Compute net debt or net credit for each user.
2. Remove all users with 0 net debt/credit from computation
3. Create two sets (SDebt and SCred) of users, one with net debt >0 and other with net credit > 0
4. We call val of user as the net debt/credit amount for him.
5. Create a graph G with a node corresponding to each user and no edges.
6. Remove the maximum value users from SDebt and SCred, let’s call them u1 and u2 respectively.
7. Add and edge between u1 and u2 in G with weight(w) = min (value of u1, value of u2)
8. Reduce the values of u1 and u2 by w.
9. If value of u1 > 0, add u1 back to Sdebt
10. If value of u2 >0, add u2 back to SCred
11. Note: Only one of u1 and u2 will be added back due to the way w is selected in step 7.
12. Repeat step 6–12, until no nodes remain in SDebt and SCred.

Future work for problem of reducing number of payments:

1. Do more literature survey about the problem.
2. We will benchmark the given algorithm against the theoretically optimal algorithm.
3. We will also try to establish the degree of sub-optimality in terms of relative performance to the optimal algorithms (empirically and theoretically).

Implementation

We implemented the application in python using the python xml-rpc library and wxpython library. The code will be available on Github later. Please contact the authors to get access to the code.

Paper References

1. Terry, Douglas B., et al. “Managing update conflicts in Bayou, a weakly connected replicated storage system.” SOSP. Vol. 95. 1995.
2. Ladin, Rivka, et al. “Providing high availability using lazy replication.” ACM Transactions on Computer Systems (TOCS) 10.4 (1992): 360–391.

Code References

Note: Template codes from the references has been reused for basic XML RPC Server and UI. All the project related functionalities have been implemented by us without any code reuse.

1. https://docs.python.org/3/library/xmlrpc.server.html#module-xmlrpc.server
2. https://wxpython.org/Phoenix/docs/html/index.html