## Design a Multi-Dimensional Job Rate Limiter Design and implement a rate limiter for jobs. A decision may depend on the job's effort, a per-user limit, a per-hour limit, and a per-day limit. The meaning of job effort and the scope of the hourly and daily limits are not specified. Clarify them before choosing an algorithm. For a concrete discussion, you may model effort as a positive quota cost and require every applicable bucket to have enough capacity before admitting a job. ### Part 1 — Define the Admission Contract Specify the request fields, limit configuration, window boundaries, time zone, response, and whether rejected jobs consume quota. Explain whether hour and day quotas are per user, global, or both. #### What This Part Should Cover - An exact interpretation of job effort and every quota scope. - Atomic all-or-nothing consumption across applicable limits. - Boundary, clock, and configuration-change semantics. - A retry or idempotency policy for repeated job submissions. ```hint Name every bucket a decision touches The request is allowed only after the design identifies all quota keys and the amount that each one would consume. ``` ### Part 2 — Implement the State Transitions Choose fixed windows, sliding windows, token buckets, or another policy and give pseudocode for one admission decision. Address concurrent requests for the same user and cleanup of inactive state. #### What This Part Should Cover - State and invariants for hour, day, user, and effort accounting. - One atomic compare-and-update path or equivalent transaction. - Deterministic handling at an exact window boundary. - Bounded memory and cleanup work. ```hint Check before committing If one quota fails after two others were decremented, the limiter needs a rollback or an atomic conditional update. ``` ### Part 3 — Distribute and Operate the Limiter Extend the design across many service instances and regions. Discuss strict versus approximate global enforcement, hot users, store failure, observability, and tests. #### What This Part Should Cover - Key partitioning and coordination for one user's decisions. - The consistency and overshoot cost of local quota leasing. - Fail-closed or fail-open behavior chosen from job risk. - Metrics for admission, rejection reason, latency, overshoot, and state growth. ```hint Quantify any local allowance Caching quota near workers improves availability and latency, but the maximum overshoot must be derived from lease size and worker count. ``` ### What a Strong Answer Covers - Resolves the four dimensions into a precise, testable policy. - Prevents partial quota consumption and double charging on retries. - Separates exact enforcement from deliberately bounded approximation. - Includes window-boundary, concurrency, failure, and configuration tests. ### Follow-up Questions 1. How would a limit decrease take effect without accepting a burst under the old value? 2. What happens when one job's effort exceeds the remaining daily quota? 3. How would you reconcile counters after a regional partition heals? 4. Which limits could safely be approximate, and which must remain strict?