Object-Oriented Programming and Design Questions

To implement a thread-safe per-user token-bucket with swap-able storage, use an abstraction for the store (get/create/update bucket) and keep token checks O(1) by only updating that user's bucket on each request. Use per-bucket locks to maximize concurrency. Below is a concise Python implementation with an in-memory store and a Redis-store stub.

1. Approach

• TokenBucket holds capacity, refill_rate (tokens/sec), tokens, last_refill_time, and a Lock.
• TokenStore interface; InMemoryTokenStore implements it with a dict of buckets.
• allow_request(user_id) fetches bucket (creates if absent), refills tokens lazily, and consumes one token if available.
• O(1) per request, per-user locking for concurrency. Redis implementation would use Lua script for atomicity.

2. Code

import time
import threading
from abc import ABC, abstractmethod

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.refill_rate = refill_rate  # tokens per second
        self.tokens = capacity
        self.last = time.time()
        self.lock = threading.Lock()

    def allow(self):
        with self.lock:
            now = time.time()
            elapsed = now - self.last
            added = elapsed * self.refill_rate
            if added > 0:
                self.tokens = min(self.capacity, self.tokens + added)
                self.last = now
            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False

class TokenStore(ABC):
    @abstractmethod
    def get_or_create(self, user_id, capacity, refill_rate) -> TokenBucket:
        pass

class InMemoryTokenStore(TokenStore):
    def __init__(self):
        self.store = {}
        self.store_lock = threading.Lock()

    def get_or_create(self, user_id, capacity, refill_rate):
        bucket = self.store.get(user_id)
        if bucket:
            return bucket
        with self.store_lock:
            # double-check
            bucket = self.store.get(user_id)
            if not bucket:
                bucket = TokenBucket(capacity, refill_rate)
                self.store[user_id] = bucket
            return bucket

class RateLimiter:
    def __init__(self, capacity, refill_rate, store=None):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.store = store or InMemoryTokenStore()

    def allow_request(self, user_id) -> bool:
        bucket = self.store.get_or_create(user_id, self.capacity, self.refill_rate)
        return bucket.allow()

3. Key concepts / concurrency

• Per-bucket Lock ensures only requests for same user contend; different users proceed concurrently.
• store_lock only used on bucket creation; get is lock-free fast path.
• For Redis or cross-process correctness, implement TokenStore using Redis and a Lua script that performs refill+consume atomically.

4. Complexity

• Time per request: O(1)
• Space: O(U) for U active users

5. Edge cases

• Clock drift: use monotonic time if available.
• Bursty adds: allow fractional tokens stored as float.
• Cleanup: eviction policy for stale buckets to limit memory.

Requirements clarification:

• Read-only search over products, must be stateless, support pagination, sorting, future filters/facets, pluggable ranking, and be backward-compatible.

High-level design:

• RESTful HTTP endpoints backed by a search service (initially DB+indexes, later migrate to search engine like Elasticsearch / OpenSearch or Algolia) and a ranking layer that can be swapped without breaking API.

Endpoints:

1. GET /v1/items/search
   Query params:

• q=string (optional full-text)
• sort=price.asc|price.desc|relevance (default relevance)
• page_size=int (max 100)
• cursor=opaque-string (for cursor pagination)
• filters=key1:val1,val2;key2:range(10,50) (see shape)
• facets=category,brand (optional list to compute facet counts)
• rank_profile=standard|promoted (optional)

Example request:
GET /v1/items/search?q=phone&sort=relevance&page_size=20&cursor=eyJvZmZz...&filters=brand:Apple,Samsung;price:range(300,1000)&facets=brand,category

Response shape (JSON):
{
"items": [{ "id":"123","title":"...","price":399, "score":0.92, ... }],
"cursor": "opaque-string-or-null",
"next_page_available": true,
"total_estimate": 1240, // optional, may be approximate for scale
"facets": { "brand": [{"value":"Apple","count":120}, ...] },
"applied_filters": { "brand":["Apple"], "price":["300-1000"] },
"rank_profile": "standard"
}

Pagination strategy:

• Cursor-based pagination (opaque cursor encoding last sort key + tie-breaker + server timestamp) to be stateless and stable as dataset grows. Support page_size and cursor. server may return next cursor=null when end reached. For simple small dataset early on, also accept offset=n for management/admin use but avoid client reliance.

Filters & facets extensibility:

• Filters passed as structured string or JSON (for POST variant) to allow complex boolean expressions. Use a POST /v1/items/search with body for large/complex queries:
  {
  "q":"phone",
  "sort":"relevance",
  "page_size":20,
  "cursor": "...",
  "filters": { "brand":["Apple","Samsung"], "price": {"gte":300,"lte":1000} },
  "facets":["brand","category"],
  "rank_profile":"promoted"
  }
• Facets computed by search backend; return counts and possible buckets.

Ranking & extensibility:

• rank_profile param allows switching ranking logic without changing API. Server maps profile to ranking pipeline (ML model, business rules, boosts). Ranking config stored separately and versioned.

Versioning approach:

• URL versioning (/v1/...). Keep v1 stable; non-breaking extensions (new optional params, additional fields in response) are backwards compatible. For breaking changes (schema changes, required fields, changed semantics), introduce /v2/ with migration docs. Deprecation strategy: advertise deprecated params in responses (warning header) and keep old endpoints for at least two release cycles.

Statelessness and caching:

• API is stateless: cursor encodes server-needed state. Use cache headers (ETag/Cache-Control) for identical queries. Search service can be horizontally scaled, backed by read replicas or a search engine.

Security & best practices:

• Rate limit, authentication (API key/OAuth), validate filter inputs to avoid injection, sanitize q.

Why this design:

• Cursor-based + opaque token keeps API stateless and scalable.
• POST body option supports complex future filters without URL length limits.
• rank_profile decouples ranking implementation from API, minimizing breaking changes.
• URL versioning + additive changes minimize client breakage while enabling evolution.

Requirements:

• Call downstream service without letting its failure cascade: keep latency and availability SLAs
• Support safe retries, backoff, fallbacks, isolate failures, observable signals
• Enable incremental roll-out and quick rollback/remove with minimal production risk

High-level design:

• Client component in our microservice wraps downstream calls with a resilience library (Resilience4j/Hystrix-like) providing timeouts, retries, circuit breaker and bulkhead semantics. Surrounding code calls the wrapper, not the service directly.

Core components & responsibilities:

• HTTP client with per-request timeout (e.g., 500ms–2s depending on SLA) and connection pool limits.
• Retry policy: idempotency-aware, exponential backoff with jitter, max attempts (e.g., 3), and per-request retry budget to avoid thundering herd.
• Circuit breaker: open after N failures within sliding window, forced short-circuit for a cooldown (e.g., open for 30s), probe requests on half-open.
• Bulkheads: thread-pool or semaphore isolation per downstream to limit concurrent calls (protects event-loop/main thread).
• Fallbacks: graceful fallback path—cached stale response, default value, feature-flagged degraded behavior, or asynchronous background queue to record request for later processing.
• Monitoring/alerts: metrics emitted (latency histogram, success/failure counts, retries, circuit state, bulkhead queue length, fallback rate). Send to Prometheus/Grafana and set alerts for increased fallback rate or open circuit. Traces (distributed tracing) include downstream spans and error tags.
• Logging: structured logs for failures including request ids and circuit state.

Data flow:

1. Incoming request -> Business logic -> Downstream client wrapper
2. Wrapper checks circuit: if open -> immediate fallback or 503 to caller
3. If closed/half-open -> call HTTP client with timeout; on failure apply retry/backoff
4. After retries exhausted -> fallback and emit metric/event

Scaling and resource management:

• Use connection pools and per-service bulkheads scaled to expected QPS.
• Rate-limit calls to downstream if necessary.
• Cache common responses with TTL to reduce load.

Adding/removing dependency with minimal risk:

• Start with feature flag and dark-launch: route a small percentage of traffic to the new code path (canary). Use shadowing to send requests to downstream without affecting main response.
• Deploy circuit defaults conservative: short timeouts, small concurrency, and strong limits.
• Monitor key signals (error rate, latency, fallback rate) and roll forward when healthy.
• To remove: flip feature flag to stop calls, ensure all traffic uses fallback/alternative path, then remove code & config in controlled release. Keep monitoring for residual errors and retain tracing/logging config for a short retention period.

Trade-offs:

• Short timeouts protect availability but may reduce successful calls for slow endpoints.
• Aggressive retries increase success but risk amplification—limit retries and use jitter.
• Fallback correctness must be designed per business case (some operations cannot be degraded).

This combination ensures downstream failures are contained, observable, and reversible with low production risk.

Start with guiding heuristics, then a concrete strangler + consumer-driven contracts plan to extract the Payments domain.

Heuristics for decomposition

• Domain-first: identify bounded contexts via domain-driven design (ubiquitous language, events, subdomains). Prefer extracting a cohesive business capability (e.g., Payments).
• Cohesion > coupling: group functionality with high internal cohesion and low external coupling (data, transactions, shared logic).
• Slow-changing & independent deployability: pick domains that change at different paces and can own their release cycle.
• Data ownership: give each service its own datastore to avoid distributed transactions; prefer event-sourcing or async comms for consistency.
• API/contract surface: minimize chatty interactions; expose clear intent-based APIs.
• Operational readiness: readiness for monitoring, scaling, security, and failure isolation.

Concrete migration plan (Payments) — Strangler + Consumer-Driven Contracts

1. Discovery & design (1–2 sprints)

   • Map current flows touching payments, DB schemas, side effects, latency, and consumers.
   • Define Payments bounded context, data model, invariants, and APIs (sync + events).
   • Capture existing integration points and consumers; list critical SLAs.

2. Introduce façade / proxy (strangler)

   • Deploy an API gateway or adapter that initially routes all payment calls to the monolith.
   • Implement feature flagging to switch specific operations to the new service gradually.

3. Build Payments service behind contract-first APIs (2–4 sprints)

   • Write consumer-driven contracts (Pact or similar) for each consumer interaction (charge, refund, status).
   • Implement service with its own DB and idempotent endpoints; emit domain events (PaymentCreated, PaymentSettled).
   • Add monitoring, retries, and circuit-breakers.

4. Verify via contract testing and integration

   • Consumers run contract tests against a mock Payments provider in CI; Payments service verifies consumer contracts.
   • Deploy consumer mocks in integration environments to validate behaviour.

5. Incremental cutover

   • Start routing non-critical traffic or one consumer to Payments service using feature flags.
   • Gradually increase coverage, run canary deploys, monitor errors/latency, rollback if needed.

6. Data migration & synchronization

   • For state: backfill payments data into new store using idempotent scripts; or handle reads via dual-write initially.
   • Use event publishing from monolith (or change-data-capture) to bootstrap service state.

7. Deprecation

   • Remove payment logic from monolith once all consumers rely on Payments service; delete DB tables and deprecated APIs.

Why this works

• Strangler minimizes risk by routing through a façade, enabling progressive replacement.
• Consumer-driven contracts ensure backward-compatible behavior and fast feedback between teams.
• Owning data and events isolates faults and allows independent scaling.

Risks & mitigations

• Distributed transactions: avoid them; prefer eventual consistency and compensating actions.
• Latency/availability: add timeouts, retries, circuit breakers, and SLA monitoring.
• Teams alignment: enforce contracts, shared runbooks, and cross-team testing windows.

This approach lets new payment features be implemented and deployed independently with minimal refactor of the monolith.

Requirements & goals:

• Preserve synchronous system correctness while introducing an event-sourced async pipeline.
• Minimize user-visible disruption, ensure observability, enable safe rollback, and support incremental consumer migration.

Migration plan (phased):

1. Prep & infra

• Add an append-only event store (Kafka / Kinesis / Pulsar) and a durable schema registry (Avro/Protobuf/JSON Schema).
• Implement idempotent event producers and a CDC or event-emitter library used by services.

2. Dual-write strategy (safe-start)

• On each synchronous transaction, write to the existing datastore first, then synchronously produce an event to the event store before committing the response (or use outbox pattern to guarantee atomicity).
• Prefer outbox table + reliable publisher to avoid distributed transaction across DB + event bus.
• Make writes idempotent (include unique event-id, version, and source).

3. Event schema evolution

• Use a schema registry and enforce backward/forward compatibility rules (recommend backward compatible additions; avoid breaking removals).
• Version events via a "type" + "schemaVersion" field. For non-compatible changes: emit both vN and vN+1 while migrating producers, or use a translator service for the old events.

4. Onboard & version consumers

• Start consumers reading from event store in parallel but in "read-only" mode or writing to a shadow downstream store.
• Use feature flags / consumer config to route reads: old synchronous reads remain primary; new consumers update shadow stores.
• Consumers should handle multiple schema versions; provide adapter/translator layer. Gradually flip consumers to use event-driven reads once parity is confirmed.

5. Reconciliation & data parity

• Periodically materialize projections from events and compare to the source-of-truth DB (hashes, row counts, checksums, sample audits).
• Run full reconciliation jobs during low traffic: compare per-entity state by ID, log diffs, and provide automated repair scripts that rehydrate entity state from event stream.
• Monitor business metrics (e.g., order counts, balances) for drift.

6. Observability & correctness checks

• Trace correlation IDs across write path, provide metrics (lag, publish failures), dead-letter queues, and alerts for reconciliation drift thresholds.
• Implement contract tests between producers and consumers using schema registry and CI gating.

7. Rollback & cutover

• Rollback: if parity or correctness fails, stop event publishing or switch consumers back to DB reads. Because of outbox guarantees, you can pause publisher or replay corrected events.
• Cutover: once parity stable and consumers validated, flip routing to make event-driven projections primary and remove dual-write. Keep the outbox for a while to allow fast rollback.
• Final cleanup: deprecate unused fields, prune old schema versions after all consumers updated.

Trade-offs & risks

• Dual-write increases write path complexity; outbox mitigates atomicity risk.
• Replays require deterministic event handlers; non-determinism must be removed before relying on replay for repair.
• Rolling back after consumers start mutating external state is harder—ensure idempotency and use compensating transactions.

This approach enables incremental migration, strong correctness guarantees through reconciliation and idempotency, and safe rollback paths while evolving event schemas and onboarding consumers safely.