Low-Level Design (LLD) of Splitwise
3.1: Defining Objects | Splitwise LLD
Here we will be having below objects that are as follows:
- User object: This class consists tells how every user is defined.
Java
class User { // User default id, with user profile image and their // bio. userID uid; string ImageURI; string bio; } |
- Group object: Now let us define the class for the group object.
Java
class Group { // Group id of this group GroupID gid; // List of all users List<User> users; // image of the group string ImageURI; // title of the group string title; // group description string description; } |
- Expense object: These objects must map each user to their balance.
Java
class Expense { ExpenseID expenseId; bool isSettled = false ; // flag to determine whether this expense is settled or // not. // Creating map of Users and their balances map<User, Balance>; GroupID gid; // This expense belongs to which group - // optional // metadata string title; int timestamp; string imageURI; } |
- Balance object: There are 2 types of users:
- Users who are receiving the money. They owe. They have a positive balance.
- Users who are paying the money. They lent. They have a negative balance.
Java
class Balance { string currency; // Note: Here we are bound that all // transactions are happening across // same currency. long amount; // We are using long as expense reported // can be large. } |
3.2: System Behavior Definition | Splitwise LLD
- Add Expense: We have user and balance objects, and then we can persist them in the database.
- Edit Expense: Each expense possesses a unique ID and we can use the ID to change mappings or other metadata.
- Settle Expense: We will make isSettled to true. We will use the balancing algorithm to settle the expenses.
- Add, settle, and edit expenses in a group: Each expense object has a groupID. So we can add, settle and edit expenses in a group.
3.3: Generating a Problem Statement | Splitwise LLD
After glancing through the above objects and behavioral characteristics, the Problem Statement generated is as follows:
Input: Input given to us is a list of transcations as transactions[from, to, transAmount]
Output: Number of minimum transactions to settle the debt
Sample Example: [ User2, User1, 100K], [ User 1, User2, 80K ], [ User1, User2, 20K]
Explanation:
- The first transaction occurs, here User2 gives 100 K to User 1 which means User2 owes 100K to User2 and User1 lent 100K.
- Again a transaction is made where- User2 repays to User1 a sum of 80K which means now User1 only lent 20K.
- Again, a transaction occurs in which User2 pays 20K to User1, meaning nobody owes anyone’s money. It means the accounting is set up.
We could have done the transaction in a lesser number to settle the debt which indeed is the goal of our system.
Consider the below graph in order to examine the net change in cash of each person in the group which can be determined by using the below formula:
Net Change in Cash(A) = (Sum of Cash Inflow(A) — Sum of Cash Outflow(A))
= (5) – (10)
= -5As depicted from the above graph, A has a net change in cash of 5 rupees, whereas A lent 4 rupees as there is a negative sign representing debt. Similarly, if we do calculate cash flow for node C(user C) it is as follows:
Net Change in Cash(C) = (5) – (5) = 0
It means user C is already settled up.
Now we are good to go with defining Node.java and paymentMode.java after having a good understanding:
Java
class Node { UserID user_ID; int final_balance; } |
Now let us also define a class for PaymentMode as seen above in the illustration:
Java
class PaymentNode { // Specific unique ID- that is our UserID UserID from; UserID to; // It is the amount that is been transefered long amount; } |
3.6: Complete LLD Implementation of Expense Sharing Application – Splitwise
Low-level design of a Splitwise system can be implemented with the usage of heap structure. Here, Nodes in graphs represent ‘Users’ and edges represent ‘transaction amount’
Pseudocode:
Java
List<PaymentNode> makePaymentGraph() { // Step 1: Let us first store the absoulte value Max_Heap<Node> type1; Max_Heap<Node> type2; 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(type1.isNotEmpty()) { // Accessing element at the top of container receiver = type1.top(); sender = type2.top(); // Step 2: Removing the element // using pop() method type1.pop(); type2.pop(); // Step 3: Getting the amount transferred by getting // minimum of sender and receiver final balance // As we need minimal edges amountTransferred = min(sender.finalBalance, receiver.finalBalance); // Step 4: Here we are creating the graph as // discussed in illustration graph.insert(PaymentNode(sender.uid, receiver.uid, amountTransferred)); // Step 5: Settling the balance as amount is being // trasfered sender.finalBalance -= amountTransfered; receiver.finalBalance -= amountTransfered; // Step 6: Checking for the edge cases if (sender.finalBalance != 0 ) type2.push(sender); if (receiver.finalBalance != 0 ) type1.push(receiver); } // Step 7: Returning the payment graph return PaymentGraph; } |
Now we can propose out API design which is as follows:
3.7: API Design:
Users –> Balance –> Expense –> Group –> Payment
User getUser(UserID user_id)
User[] getUsersInGroup(GroupID group_ID)
ExpenseID addExpense(GroupID group_id, UserID user_id, long amount, string currency)
ExpenseID editExpense(GroupID group_id, UserID user_id, long amount, string currency)
void settleExpense(ExpenseID expense_id)
Expense getExpense(ExpenseID expense_id)
ExpenseID [] getGroupExpenses(Group group_id)
GroupID makeGroup(Users[] users, string name, string imageURI, string description)
GroupID getGroup(GroupID)
PaymentGraph getGroupPaymentGraph(GroupID group_ID)
Conclusion: Splitwise can be further scaled by invoking the concept of caching as the in-real time we are making it
System Design of Backend for Expense Sharing Apps like Splitwise
In this post, we will look into the System Design of Expense Sharing Applications such as Splitiwse. We will deep dive into the LLD of Splitwise, the Happy Flow of Splitwise, and also how to design the backend for Splitwise or such Expense Sharing Applications.
Table of Content
- About Expense-Sharing Applications
- System Design of Splitwise
- Step 1: Defining Happy Flow for Splitwise
- Step 2: Requirement Analysis/Gathering Requirements of Splitwise
- Step 3: Low-Level Design (LLD) of Splitwise
- Scaling Splitwise- How It Is Achievable Invoking Caching
Contact Us