Before Real-Time Behavior
The foundation of Kanban Flow and the required real-time behavior, is having all the required RESTful API endpoints, these endpoints are what we build on them the real-time behavior, they are the main way to access the data in the system and manipulate it.
The real-time behavior exists in viewing the details of boards, so we will use it mainly in viewing updates, but the create, update and delete operations will be done over HTTP via REST.
Why WebSockets Protocol
One solution rather than WebSockets is continuous polling, it is simply using the same restful API and just repeatedly send requests to check any changes happen, and if a change is detected then new data is rendered to the client, this introduces delay by the time between each poll. This delay is structural as in standard HTTP only the client can initiate a request, so the server has no way to notify a client of a change and the client must keep asking. Polling can give the real-time feel by polling very aggressively, but this consumes resources heavily.
Furthermore, polling for every connected user that makes the cost grows at scale when users increase due to continuous processing for requests to determine whether there is a change or not.
Also with continuous polling you're holding a TCP socket open (opened connection to avoid continuous handshakes and tearing down on every single polling request) on the server per client (HTTP/1.1 Persistent Connections), which is same resource cost as a WS connection, but now you're polling pointless empty responses across it instead of only sending data when something actually changes. So continuous keep-alive polling pays WebSockets TCP connection cost and still wastes bandwidth and CPU on empty "nothing changed" round trips. WebSockets is strictly better: same held-open TCP connection cost, but zero waste. It gives the ability for the server to push the changes to the client just when something is changed.
Preserving State
The WebSocket connections are saved in memory as object per every connection per single user, so I pushed the connection objects to a dictionary that binds every connection with the user that opened it, and the same is made for boards, to know when board is changed, which users to push for them the change.
Also till now I focus on building the system to work as one instance with no distributed states that are centralized and can be accessed from multiple instances.
A single connection can be subscribed in at most one board, and single user can have many connections.
Problem of Database Connections
WebSockets is stateful, so unlike REST, a session-scoped database session object would hold one DB connection open per WS connection for its entire lifetime which may exhaust the connection pool and the connections run out. I fixed this by scoping the session to just the auth-time DB lookup instead and delete it after usage, releasing the DB connection.
Pushed Changes To Clients
Refetching the boards on every change is bad idea, as if there are N concurrent users connected to the board and are viewing it, one change will trigger N requests to reload the board. The right decision here is to just broadcast deltas and every user build on the version that he has already loaded.
Regarding how users are connected to the boards, I decided at first to close and reopen a WS connection every time the user navigates to a different board. Downsides: every navigation now pays a full handshake + auth-frame/auth-message round trip again. At scale, users switching boards frequently = exhausting the TCP sockets which are the underlying of websocket connections.
Then I ruled out that, and decided to keep only one WS connection open for the whole session (from login to logout/tab-close). When the user navigates to Board 1, client sends a small message over the existing connection: {"type": "subscribe", "board_id": 1}. Server adds that connection to a "Board 1 room." Navigate to Board 2, then client sends {"type": "unsubscribe", "board_id": 1} then {"type": "subscribe", "board_id": 2}. Same connection, just changes which "room" it's in. So, one persistent connection + "rooms"/subscriptions that are the users that any change on the subscribed board will be pushed for them.
Securing Endpoints with WebSockets Protocol
With WebSockets, the browser's WebSocket API gives you no way to set custom headers on the handshake request unlike traditional RESTful endpoints, so I considered 3 choices, ruled out 2 and landed on the 3rd:
1. Sending the JWT as a query param: then discovered that this may leak the JWT into server/proxy logs and browser history.
2. Persisting the JWT as a cookie on the client side: but since the browser auto-attaches cookies on every request to the domain regardless of origin, this option opens CSRF vulnerability, which is simply a malicious link can have JS script that requests the server and then it connects with the server and can do anything on behalf of the client. I believe that this can be mitigated but I decided not to continue with this solution.
3. Sending the JWT as the first frame/message after the upgrading the protocol: this solution avoids the pitfalls in the previous two, here the JWT only travels once, as an explicit message/frame over an encrypted channel (via wss protocol), never touching a URL or relying on credentials that browsers send automatically. It has only one downside that is potentially exhausting resources, as a buggy or malicious client can open many upgraded connections and each connection consumes server resources and they remain unauthenticated, so it may cause DoS problem but this can be avoided by setting a timeout after the server accepts and upgrades the protocol from HTTP to WS and during this allowed period the client should send their JWT and authenticate, otherwise the connection automatically closes releasing the resources allocated for it.
Rate Limiting
The system should have defense line against the buggy or malicious clients that sends too many messages, as messages mostly means queries that run on the database and resources consumption, so to prevent resource exhaustion we should maintain a limit for messages that a single client can send and after it, a rate limited message should be sent.
I decided to set the limit on the user not the connection, so it can not get bypassed by simply opening multiple connections for the same user.
The Algorithm
My idea depends on tokens, each token represents a unit that the client can spend for sending a message to the server.
Fixed time window: tokens are refreshed every X seconds. The client can send 5 messages right before X, the tokens are refreshed at second X, and it sends 5 more messages right after. So there are 10 messages in small window.
Token bucket (capacity 5, +1 token every 0.2s till reaches 5 tokens): The system adds 1 token for the user every 0.2s, until reaches the limit of 5 tokens which is the bucket's capacity (this prevents accumulating tokens and flooding the server with messages by a malicious or buggy client). This solution can still allow bursts (up to the bucket capacity) but it doesn't have the fixed-window boundary problem, here you can not send 10 messages in a small window.
Concurrent Updating and Lost Updates
Two users open the same task, and one saves. The other user's screen never receives that update, because their connection dropped, they left an edit form open, or both saves were sent at the same moment. The second user then saves from the stale copy and overwrite the first user's change. No error is raised and the first user's work is lost silently while the change was intended to be on the stale version before updates of the first user.
Approaches to Fix
Optimistic concurrency control: that is allowing everyone edit freely and concurrently and only pays when a conflict actually occurs.
Pessimistic concurrency control: that is locking the updates, so no user can edit a task while there is another user is editing it. If edit stays for minutes due to any problem so others have to wait. It requires more handling to mitigate this like timeouts.
Conflicts are rare, in pessimistic concurrency control the system pays that cost on every edit to prevent something that seldom happens. I chose to never make anyone wait, just update and if there is a conflict happened then notify that error happened and the user will try again, instead of waiting long time
Implementing Optimistic Concurrency Control
Each task carries a version, and every edit sends back the version it was based on. The server applies the update only if that version still matches, then increments it. If it doesn't match, the edit was based on stale data, so the server rejects it with 409 Conflict and the client knows that he was editing a stale version.
The check and the write happen in a single atomic SQL update statement that locks the database row for the duration of executing the update statement, so two simultaneous requests can never both pass (this is the Isolation principle in ACID principles that relational DBMS follow, which is update statements for the same data are not interfered).
I decided to make only title and description edits are versioned. A move is a complete instruction ("put it in Done"), so last-write-wins is acceptable as there is no data loss. One known limitation in my idea is when two tasks are dropped into the same gap they get the same index, so their relative order becomes ambiguous. A unique constraint on (column, index) with retry would solve this, but I decided to not solve this problem as I want to focus on more important things in this project.
I tested the concurrency via 20 requests overlapping once. So the server is flooded by 20 requests at the same time, and it only makes one update request passes and all the others get 409 Conflict. So I succeeded in controlling the concurrency.
Top comments (0)