Raven Split is a website dedicated to solving the daily troubles of split expenses within a group.
We developed an algorithm to help simplify the payback relationship.
Having trouble with calculating shared expenses with friends after dining together?
Tired of taking out wallet or opening LINE Pay ever time after joining an order at UBER EAT with colleagues?
Don’t worry! With Raven Split service, you can release yourself from those bothering mathematic trivialities!
- Track balance: Track self-balances as well as debt details across groups on the dashboard clearly.
- Organize expenses: Split expenses easily with friends, colleagues, family, or anyone.
- Add expenses: Record shared expenses quickly with split/customized mode and calculate helper.
- Pay friends back: Settle up with a friend and record the payment anytime.
- Simplify payback relations: Settle up with the whole group by simplized way calculating by Raven Split algorithm.
- Raw Data: the expense data come from client input, including who paid and who were involved in this expense.
- Balance: the current owe amount and owe relationship between two people, which is calculated by all the previous expense records.
- Best Settle Solution: the simplier payback solution which took all the balances in the group, and then use the algorithm to reduct the total number of repayments between group members, but still keep everyone get there full owed amount back.
1. Pick up two nodes (people) as start and end in the graph.
2. Pick up one path that can go from start to end, which might pass through couple of nodes (other people).
3. Find the bottleneck capacity, which is minimum debt amount on this path (the minimun debt).
4. For each edge, minus bottleneck capacity to get residual (remaining debts).
5. Add this capacity to the shortest path (which is edge of start to end in our definition).
Note: In this algorithm, we will not build a new payback relation if there is no current debt relation between the two people. (In real world cases, it is probably that the two people are not knowing each other but just join the same group.)
0. Prepare data: Calcuate balance with raw data. Make sure only one edge between two nodes.
1. Origin debt: Adam owes Euli $100, Adam owes Tim $50, and Tim owes Euli $50.
2. Process with algorithm: Adam owes Tim $50, and Tim owes Euli $50 => This can change to Adam paying Euli $50 directly
3. Get simplified solution: Adam pays Euli $100 + $50 = $150.
-
1. Having 30 debts between group members 2. Reduced to 9 debts after calculating by Raven Split algorithm
- Applied both relational database and graph database RDS MySQL is used for saving raw data, balances as well as user and group datas. On the other hand, Neo4j is used to save the best settle solutions. With this structure, we can: - Guarantee the consistency of user data with the trait of relational database. - Take advantage of the graph database's relation base structure to fasten algorithm calculation.
-
Implement Lambda and SQS to handle best settle calculation when needed Considering the resouce-consuming by best settle calculation and the complexity of calculation itself influenced by the number of edges(payment relationships), it is not good either to conduct calculations per modification or wait until user requests. Hence, implement the following design for improvement:
- Counting the amount of expense modification, conduct best settle calculation once per 5 modifications. - Implement AWS Lambda for best settle calculation to ease the system loading. Produce job to AWS SQS to trigger Lambda when needed. - Separate prioritized queue to deal with immediate requests for checking the best settle solution from users. - Design check and lock system to avoid race-condition.
- Server: NodeJS, Express
- Database: RDS MySQL, Neo4j
- AWS Serverless Service: Lambda, SQS
- Client: React (Front-End Repo), Bootstrap, Material-UI
Euli Liao
If any question or feedback, feel free to contact me by the following:
- GitHub
- Email: tina5ps93@gmail.com