Rate Limiting in Distributed System Using Mysql for high cardinality

Rate limiting involves limiting access to a resource x number of times in last y minutes. Lets take an example to understand definitions and implementation.

Example : A User is allowed 5 incorrect logins per minute.

Definition

  • Zone : A use case.
  • Bucket : Unique Id in a use case. E.g. Per user is given a bucket
  • Bucket-Lock : Lock applicable per bucket. E.g. Per User 1 lock is allocated.

Following rate limiting solution is a suitable solution when

  1. Rate limiting every transaction is important and unforgiving. E.g. Each Login attempt is important.
  2. High cardinality in Rate limiting buckets. E.g. User base must be large wrt. to number of login attempts i.e. 5
  3. Each transaction gets a txn id and a history.
  4. Rate limit is required for a moving window.

Solution

Mysql Tables

  • Zone Master : Each use case has an id and description. Window is in seconds. For above example Rate : 5 , window : 1 x 60
+-------------+--------+
| Field | Type |
+-------------+--------+
| id | int |
| description | text |
| rate | int |
| window | bigint |
+-------------+--------+
  • Zone Bucket Lock : Bucket_key has to be unique per bucket. E.g. for above use case , lets say zone id = 1 . Then bucket keys can be 1_<userid> . This table is used to maintain isolation and to maintain concurrency of user login attempts in a distributed system.
+-------------+---------------------+
| Field | Type |
+-------------+---------------------+
| bucket_key | unique varchar(255) |
+-------------+---------------------+
  • Zone Txn : For saving all allowed and disallowed transactions. This is used to calculate number of txns and matched against rate.
+------------+-------------+-------------------+
| Field | Type | Default |
+------------+-------------+-------------------+
| id | bigint(20) | NULL |
| zone_id | int(11) | NULL |
| bucket_key | varchar(255)| NULL |
| blocked | tinyint(1) | NULL |
| created_at | timestamp | CURRENT_TIMESTAMP |
+------------+-------------+-------------------+
  • Stored Procedure
DELIMITER //
CREATE PROCEDURE check_velocity (IN p_zone_id int(11), IN p_bucket_key varchar(255))
BEGIN
# variables
DECLARE v_rate INT;
DECLARE v_window BIGINT;
DECLARE v_blocked TINYINT;
DECLARE v_zone_txn_id BIGINT;

# get rate limit, window from zone master
SELECT `rate`, `window` INTO v_rate, v_window from `zone_master` where `id` = p_zone_id;
# insert fresh bucket Key if not already there
INSERT ignore INTO zone_bucket_lock(bucket_key) VALUES(p_bucket_key);
START TRANSACTION;
# lock
SELECT * FROM zone_bucket_lock WHERE `bucket_key` = p_bucket_key for update;
# Check zone rate limit  put it in v_blocked
SELECT IF(count(*) >= v_rate, 1,0) INTO v_blocked from `zone_txn` WHERE `bucket_key` = p_bucket_key and `zone_id` = p_zone_id and `blocked` = 0 and `created_at` >= NOW() - INTERVAL v_window SECOND;
# insert into zone_txn
INSERT INTO `zone_txn`(`zone_id`, `bucket_key`, `blocked`) VALUES(p_zone_id, p_bucket_key, v_blocked);
# return Blocked, allowed Txn Id , in case required for reference number
SET v_zone_txn_id = LAST_INSERT_ID();
COMMIT;
select v_blocked, v_zone_txn_id, p_zone_id, p_bucket_key, v_rate, v_window;
END //
DELIMITER ;
  • Implementation : Call Stored Procedure above to get 0 : for unblocked and 1 for blocked Txn. E.g. Call check_velocity(1, 1_<custid>)

Note : We cannot use zone_txn to block the concurrent attempts as well as calculate rate limit. Mysql “Select for update“ behaves unexpectedly here : http://stackoverflow.com/questions/43251975/mysql-select-for-update-blocks-1st-insert-if-using-non-primary-key-in-where-clau

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.