Created
March 4, 2024 23:58
-
-
Save deemp/0830bd7e77dc4e955f78a820859b30ad to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Light version | |
| Works well when the maximum number of requests per 30 minutes can be sorted with 1 GB of RAM. | |
| On each node, there is an FE and an MSD. | |
| Nodes are indexed from 0 to 99. | |
| MSD | |
| Begin | |
| SLOWEST_USERS: HashSet[UID] := {} | |
| thread1: | |
| provide endpoint for POST requests with payload containing beacon call data | |
| while true: | |
| CURRENT_TIME: Time := current time in seconds from 00:00 | |
| ITERATION: Uint := [CURRENT_TIME / 60] | |
| LEADERS: [Uint] := [ITERATION % 100, (ITERATION + 1) % 100, (ITERATION + 2) % 100] | |
| while true | |
| CURRENT_TIME: Time := current time in seconds from 00:00 | |
| NEW_ITERATION: Uint := [CURRENT_TIME / 60] | |
| (UID, TS1, TS2): (UID, Time, Time) := await a POST request with beacon call data from FE | |
| for LEADER in LEADERS: | |
| send (UID, TS1, TS2) to LEADER | |
| thread2: | |
| provide endpoint for POST requests with payload containing a list of slowest users | |
| while true: | |
| SLOWEST_USERS_LIST: [UID] := await a request from any leader | |
| SLOWEST_USERS := hashset constructed from SLOWEST_USERS_LIST | |
| End | |
| Leader | |
| Begin | |
| type UID = Uint | |
| REQUESTS_WINDOW: [(UID, Time, Time)] := empty array of triples (UID: Uint, Average time: Time, TS2: Time) | |
| TIME_WINDOW: Time := 30 * 60 * 1000 * 1000 | |
| SLOWEST_USERS: [UID] := empty array of UID | |
| MSDS: [Uint] := indices of MSD, or numbers from 1 to 100 | |
| while true: | |
| CURRENT_TIME: Time := current time in seconds from 00:00 of the current day | |
| ITERATION: Uint := CURRENT_TIME // 60, where `//` denotes integer division with rounding down | |
| while true: | |
| (UID, TS1, TS2): (Uint, Time, Time) := await a request with beacon call data from a MSD | |
| REQUESTS_WINDOW := append (UID, TS2-TS1, TS2) to REQUESTS_WINDOW | |
| NEW_ITERATION: Uint := [CURRENT_TIME / 60] | |
| if NEW_ITERATION != ITERATION: | |
| ITERATION := NEW_ITERATION | |
| REQUESTS_FILTERED: [(Uint, Time, Time)] := | |
| from REQUESTS_WINDOW filter out values (_, _, TS2) where TS2 > (CURRENT_TIME - TIME_WINDOW) | |
| USER_DATA: Map[UID, (Time, Uint)] := {} with default value equal to (0, 0) | |
| for REQUEST in REQUESTS_FILTERED: | |
| (UID, AVERAGE_TIME, _) := REQUEST | |
| (AVERAGE_TIME, NUMBER_OF_PROCESSED_REQUESTS) := USER_DATA[UID] | |
| NEW_NUMBER_OF_PROCESSED_REQUESTS: Uint := NUMBER_OF_PROCESSED_REQUESTS + 1 | |
| NEW_AVERAGE_TIME: Uint := (AVERAGE_TIME * NUMBER_OF_PROCESSED_REQUESTS + AVERAGE_TIME) / NEW_NUMBER_OF_PROCESSED_REQUESTS | |
| USER_DATA[UID] := (NEW_AVERAGE_TIME, NEW_NUMBER_OF_PROCESSED_REQUESTS) | |
| USER_DATA: [(UID, Time)] := empty array | |
| for (UID, (AVERAGE_TIME, _)) in items(USER_DATA): | |
| append (UID, AVERAGE_TIME) to USER_DATA | |
| THRESHOLD: Time := | |
| find via binary search the max time | |
| for which in USER_DATA there are no more than 10% users with larger average time | |
| SLOWEST_USERS := users that have larger than Average time in USER_DATA | |
| for MSD in MSDS: | |
| send SLOWEST_USERS to MSD | |
| break | |
| End |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment