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:

  1. People who will receive money from others. They have a positive balance.
  2. 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 the isSettled flag 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 pick A from the first category and B from 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