Low Level Design of Splitwise
Low-Level Design for Payment tracking app like Splitwise
Prioritized Requirements
- Users can add expenses.
- Users can edit expenses.
- Also, users can settle expenses.
- Allow users to make groups and add, edit and settle expenses in the group.
Requirements not a part of our design
- Comments for records.
- Activity log for every event.
- Authentication service.
Objects definition
-
User object
struct User{ userID uid; string ImageURI; string bio; } -
Balance object
There are 2 types of people:
- People who will receive money from others. They have a positive balance.
- People who will pay money to others. They have a negative balance.
So our balance object should be able to handle both positive and negative values.
struct Balance{ string currency; int amount; //For simplicity we are using integers here. // We can also use float or double but in that case, we also need to handle precision errors. } -
Expense object
Expense objects must map each user to their balance.
struct Expense{ ExpenseID eid; bool isSettled; map<User,Balance>; GroupID gid; //This expense belongs to which group //Metadata string title; int timestamp; string imageURI; } -
Group object
struct Group{ GroupID gid; List<User> users; //metadata string ImageURI; string title; string description; }
Behavior definition
-
Add Expense
We have user and balance objects, and then we can persist them in the database. -
Edit Expense
Each expense object has a unique ID. We can use the ID to change the mapping or other metadata. -
Settle Expense
We make theisSettledflag true. We will use a balancing algorithm to settle expenses. -
Add, Settle and Edit expenses in group
Each expense object has a groupID. So we can add, settle and edit expenses in a group.
Balancing algorithm
-
Problem
Let us denote each user as a node and each payment as an edge in a graph.So we need to minimize the number of edges in the graph
It means A paid x amount to B.
-
Solution
Note: When we talk about balance we are talking about the sum of all transactions for a user.
First, let's divide the user into two categories
- People who have a positive balance.
- People who have a negative balance.
If at the point any user has 0 balance that means his/her expenses are settled, and we can remove that node from the graph.
At each step we will pick the largest absolute value from each category and add an edge between them.
Let's say we pickAfrom the first category andBfrom the second category. So will add an edge from B to A (because B will pay and A will receive) and then update the balances. If the new balance of any node becomes 0 then we will not consider the node again.
To implement this we can use heap data structure.
Pseudocode
struct Node{ UserID uid; int finalBalance; } struct PaymentNode{ UserID from; UserID to; int amount; } List<PaymentNode> makePaymentGraph(){ Max_Heap<Node> firstCategory; Max_Heap<Node> secondCategory; //We are storing the absoulte value List<PaymentNode> graph; //The sum of balance of all users always results in 0 so if first heap is empty then second heap will also have no elements. loop(firstCategory.isNotEmpty()){ receiver = firstCategory.top(); sender = secondCategory.top(); //Removing the element firstCategory.pop(); secondCategory.pop(); amountTransferred = min(sender.finalBalance , receiver.finalBalance); graph.insert(PaymentNode(sender.uid, receiver.uid, amountTransferred)); sender.finalBalance -= amountTransfered; receiver.finalBalance -= amountTransfered; if(sender.finalBalance != 0) secondCategory.push(sender); if(receiver.finalBalance != 0) firstCategory.push(receiver); } return PaymentGraph; } -
Edge case
Let us consider a case
A B C D E F G 80 25 -25 -20 -20 -20 -20 If we use our approach then the payments will be
- C will pay $25 to A
- D will pay $20 to A
- E will pay $20 to A
- F will pay $20 to B
- G will pay $15 to A
- G will pay $5 to B
So there are 6 transactions.
But it can be done in only 5 transactions
- C will pay $25 to B
- D will pay $20 to A
- E will pay $20 to A
- F will pay $20 to A
- G will pay $20 to A

