System requirements

Functional:

These are the specific functionalities that the system must support:

1. User Authentication and Management
   • Registration and login for users.
   • User profile management (viewing and updating user details).
2. Real-Time Collaboration
   • Multiple users can view and edit spreadsheets simultaneously.
   • Live updates of changes (using WebSockets).
3. Spreadsheet Operations
   • Create, read, update, and delete spreadsheets.
   • Support for spreadsheet features, including cells, formulas, and data formatting.
4. Cell Management
   • Ability to get, update, and manage individual cell data.
   • Support for data validation and formula calculation.
5. Version Control
   • Tracking changes to spreadsheets over time.
   • Ability to revert to previous versions of spreadsheets.
6. Commenting System
   • Allow users to leave comments on specific cells.
   • Notifications of new comments or changes.
7. Access Control
   • Different levels of access (view and edit) for various users.

Non-Functional:

1. Scalability
   • The system should handle up to 10,000 concurrent users efficiently.
   • Database scalability to support a high volume of spreadsheet documents.
2. Performance
   • Response time for user interface actions should be under 200 ms.
   • Real-time updates for collaborative edits should reflect in less than 100 ms.
3. Availability
   • The system should have an uptime of 99.9% to ensure user access at all times.
   • Regular backups and recovery options must be in place.
4. Security
   • Data encryption in transit and at rest.
   • Secure authentication and authorization mechanisms to protect user data.
5. Cross-Platform Compatibility
   • The web application should work on various browsers (Chrome, Firefox, Safari) and devices (desktops, tablets, smartphones).
6. Usability
   • The user interface should be intuitive and easy to navigate.
   • Offer help/support resources for users as needed.
7. Maintainability
   • The application should be designed with a modular architecture to allow easy updates and maintenance.
   • Clear documentation for developers is essential.

Capacity estimation

 User Capacity Estimation

• Concurrent Users: Assume that we want to support up to 10,000 concurrent users at peak times.
• Sessions: Estimate average session length. For example, if an average user spends 1 hour working on a spreadsheet and re-visits multiple times a day, we can predict daily active users.

2. Spreadsheet Size and Data Estimation

• Average Spreadsheet Size: Assume each spreadsheet has an average of 100 rows x 10 columns with a mix of text and numbers. If each cell averages 100 bytes (considering values and metadata), the size per spreadsheet can be estimated as:

• Total Storage Requirements:
  • If each user creates an average of 5 spreadsheets, the total number of spreadsheets for 10,000 users would be:

• • Total storage needed would be:

3. Database Transactions

• Read and Write Transactions: Each user action (like opening a spreadsheet, editing a cell, etc.) generates a transaction. Assume:
  • Average transactions per user per session: 15 (creating, updating cells, loading spreadsheets, etc.)
  • Total transactions during peak hours (1-hour session with 10,000 users):

4. Network Bandwidth Estimation

• Data Transfer: Each transaction data size can vary, but let's assume:
  • Average data transfer per transaction: 1 KB (for fetching/updating spreadsheet data)
• Estimated network bandwidth required:

5. Server Resources

• Web Server:
  • If we assume each server can handle 100 concurrent users, we would need:

• Database Server:
  • For high transaction volumes and data capacity requirements, robust database resources are essential. Using multi-tenant databases with load balancing may be needed as user growth occurs.

API design

User Management

1. User Registration
   • Method: POST
   • Endpoint: /auth/signup
   • Description: Registers a new user.
   • Request Body:
   • { "name": "string", "email": "string", "password": "string"}
   • Response:
   • { "id": "string", "name": "string", "email": "string"}
2. User Login
   • Method: POST
   • Endpoint: /auth/login
   • Description: Authenticates a user and returns a token.
   • Request Body:
   • { "email": "string", "password": "string"}
   • Response:
   • { "token": "string"}
3. Get User Profile
   • Method: GET
   • Endpoint: /auth/user
   • Description: Retrieves the logged-in user's profile.
   • Response:
   • { "id": "string", "name": "string", "email": "string"}

Spreadsheet Management

1. Create Spreadsheet
   • Method: POST
   • Endpoint: /spreadsheets
   • Description: Creates a new spreadsheet.
   • Request Body:
   • { "title": "string", "access_level": "string"}
   • Response:
   • { "id": "string", "title": "string", "created_at": "date", "updated_at": "date"}
2. Get Spreadsheet
   • Method: GET
   • Endpoint: /spreadsheets/{id}
   • Description: Retrieves a specific spreadsheet by its ID.
   • Response:
   • { "id": "string", "title": "string", "cells": [ ... ], "created_at": "date", "updated_at": "date"}
3. Update Spreadsheet
   • Method: PUT
   • Endpoint: /spreadsheets/{id}
   • Description: Updates a specific spreadsheet.
   • Request Body:
   • { "title": "string", "access_level": "string"}
   • Response:
   • { "id": "string", "title": "string", "updated_at": "date"}
4. Delete Spreadsheet
   • Method: DELETE
   • Endpoint: /spreadsheets/{id}
   • Description: Deletes a specific spreadsheet.
   • Response:
   • { "message": "Spreadsheet deleted successfully."}

Cell Management

1. Get Cells
   • Method: GET
   • Endpoint: /spreadsheets/{id}/cells
   • Description: Retrieves all cells for a specific spreadsheet.
   • Response:
   • { "cells": [ ... ]}
2. Update Cell
   • Method: POST
   • Endpoint: /spreadsheets/{id}/cells
   • Description: Updates a specific cell's content.
   • Request Body:
   • { "row": "int", "column": "int", "value": "string", "formula": "string"}
   • Response:
   • { "id": "string", "row": "int", "column": "int", "value": "string"}

Version Control

1. Get Versions
   • Method: GET
   • Endpoint: /spreadsheets/{id}/versions
   • Description: Retrieves version history for a specific spreadsheet.
   • Response:
   • { "versions": [ ... ]}
2. Revert to Version
   • Method: POST
   • Endpoint: /spreadsheets/{id}/versions/revert
   • Description: Reverts the spreadsheet to a specified version.
   • Request Body:
   • { "version_id": "string"}
   • Response:
   • { "message": "Reverted to version successfully."}

Comment Management

1. Add Comment
   • Method: POST
   • Endpoint: /cells/{cell_id}/comments
   • Description: Adds a comment to a specific cell.
   • Request Body:
   • { "content": "string"}
   • Response:
   • { "id": "string", "cell_id": "string", "content": "string", "created_at": "date"}
2. Get Comments
   • Method: GET
   • Endpoint: /cells/{cell_id}/comments
   • Description: Retrieves all comments for a specific cell.
   • Response:
   • { "comments": [ ... ]}

Database design

1. User:
   • Stores basic information like ID, name, email, and a hashed password for security.
2. Spreadsheet:
   • Contains details about each spreadsheet such as its owner, title, creation date, last updated date, and access level for sharing.
3. Cell:
   • Each record represents individual cells within a spreadsheet, noting their position (row, column), value (either static or formula), and links to the spreadsheet they belong to.
4. Version:
   • Keeps track of different versions of the spreadsheets. Each version comprises a serialized representation of the spreadsheet content, allowing users to revert back if necessary.
5. Comment:
   • Allows users to add comments to individual cells. Each comment has a reference to its respective cell and the user who created it.

Relationships:

• User to Spreadsheet: A user can create multiple spreadsheets (1-to-many).
• Spreadsheet to Cell: A spreadsheet consists of many cells (1-to-many).
• Spreadsheet to Version: A spreadsheet has multiple versions (1-to-many).
• Cell to Comment: A cell can have multiple comments (1-to-many).

High-level design

User Interface (Client Application)

• Description: The front-end provides the user interface for the application, enabling users to interact with spreadsheets.
• Technologies: Built using frameworks like React, Angular, or Vue.js.
• Key Features: User authentication, spreadsheet management, real-time editing, commenting, notifications.

Backend Services

• Real-time Collaboration Service
  • Manages the WebSocket connections for real-time collaboration.
  • Synchronizes changes made by users in real-time.
• API Gateway
  • Acts as a single entry point for all client requests.
  • Handles routing to appropriate microservices and provides load balancing.
• Authentication Service
  • Responsible for user authentication and authorization.
  • Issues JWT tokens for secure communication.
• Spreadsheet Service
  • Manages business logic related to creating, reading, updating, and deleting spreadsheets.
  • Interacts with the database to store and retrieve spreadsheet data.
• Cell Management Service
  • Handles operations related to individual cells (updates, formulas, validations).
• Version Control Service
  • Keeps track of all versions of spreadsheets.
  • Allows users to revert to previous versions.
• Notification Service
  • Sends notifications related to real-time updates and comments on spreadsheets.

Database Layer

• Relational Database (e.g., PostgreSQL)
  • Stores user information, spreadsheet data, cell values, version history, and comments.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Real-time Collaboration Service Flow

Here's a high-level overview of the steps involved in the operation of the Real-time Collaboration Service:

1. Establishing WebSocket Connections

• User Action: When a user opens the application and accesses a spreadsheet, the client application initiates a WebSocket connection to the Real-time Collaboration Service.
• WebSocket Handshake: The service handles the handshake, establishing a persistent connection that remains open for real-time communication.

2. User Presence Management

• User Connection: The service registers the new user in the system, updating the list of active users currently editing the spreadsheet.
• Broadcast Notification: The service sends a notification to all connected clients, informing them about the user’s presence (e.g., "User X has joined").

3. Listening for Events

• Event Subscriptions: The service listens to incoming events from connected users, such as cell updates, new rows, or comments.
• Message Structure: Each event sent to the service contains metadata, including the user ID, spreadsheet ID, action type, and relevant data (e.g., cell position, new value).

4. Handling User Actions

• Cell Updates: When a user updates a cell, the client application sends a message to the Real-time Collaboration Service indicating the cell that was changed and its new value.
  • Example of an update message:
  • { "type": "cell_update", "spreadsheet_id": "12345", "cell": { "row": 2, "column": 3, "value": "New Value" }, "user_id": "user123"}
• Processing Updates: The service receives the update message and processes the change:
  • It may first validate the update (e.g., check for conflicts or locks).
  • Update the state of the spreadsheet in the backend (if necessary).

5. Broadcasting Updates

• Notify All Clients: After processing the update, the Real-time Collaboration Service broadcasts this change to all other users connected to the same spreadsheet.
  • Sends the updated cell data and the ID of the user who made the change.
• Example Broadcast Message:
• { "type": "cell_update", "spreadsheet_id": "12345", "cell": { "row": 2, "column": 3, "value": "New Value" }, "user_id": "user123"}

6. Updating Clients

• Client Handling: Each connected client listens for broadcast messages.
• UI Update: Upon receiving an update message, the client updates the corresponding cell in the user interface to reflect the change in real-time.

7. Conflict Resolution

• Handling Conflicts: In case of simultaneous edits on the same cell by multiple users, the service needs to implement a conflict resolution strategy.
  • Possible strategies include:
    • Last Write Wins: The last update received overrides previous ones.
    • Locking: Temporarily lock the cell for edits until the first user's changes are saved.

8. User Disconnection

• Handling Disconnects: If a user disconnects from the WebSocket (e.g., closes the browser), the service needs to clean up:
  • Remove the user from the active users list.
  • Optionally, broadcast a message to other users informing them of the user’s exit.

9. Notifications Service Integration

• Commenting Notifications: If users comment on cells, the Real-time Collaboration Service can also communicate with the Notification Service to send alerts to users about new comments.

Data Retrieval Caching

• Use Case: Frequently accessed data, such as user profiles, spreadsheet metadata (titles, creation dates), or commonly used formulas.
• Implementation:
  • Use an in-memory cache (such as Redis or Memcached) to store the responses from the database that are frequently requested.
  • When a user requests information, the system first checks the cache. If the information is present (cache hit), it is returned immediately. If not (cache miss), the application retrieves it from the database, stores it in the cache for subsequent requests, and then returns the result.
• Benefits: Reduces database load and improves response time for end-users, especially in high-traffic scenarios.

2. Cell Value and Formula Caching

• Use Case: In cases where spreadsheets contain computed values based on complex formulas that do not change frequently or where values can be reused.
• Implementation:
  • Cache the results of formulas in memory or utilize a caching layer to store recent computations/batches of cell values.
  • This is particularly useful for keeping user interfaces responsive during collaborative editing.
• Benefits: Minimizes the need for repeated computation of the same formulas, enhancing performance for users editing the same or similar data simultaneously.

3. Session Caching

• Use Case: Store user authentication tokens and session state information.
• Implementation:
  • Use a cache to manage the user’s session state more efficiently, avoiding the need to hit the database for every operation that requires user context.
  • Upon successful authentication, user-related data can be stored temporarily for quicker access throughout their interaction with the application.
• Benefits: Reduces latency associated with user authentication processes and session validation, improving user experience.

4. Real-time Collaboration Caching

• Use Case: Cache the active users list and their associated statuses for the spreadsheets they are currently editing.
• Implementation:
  • Maintain an in-memory cache of active sessions or users in the Real-time Collaboration Service to ensure quick updates and notifications when a user joins or leaves.
• Benefits: Enables quick lookups and updates, reducing the overhead of continuously querying the data store for user presence information.

5. Notification Caching

• Use Case: Store notifications related to updates and comments temporarily before sending them to the clients.
• Implementation:
  • Implement a caching layer to hold notifications, allowing for efficient grouping and sending instead of immediate, repetitive requests to the database.
• Benefits: Reduces load on database queries while also making it easier to manage and group notifications for bulk sending.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?