Skip to content
Designing Real-Time Bus Arrival Systems: GPS Cleaning, ETA Prediction & 100k QPS Caching

Designing Real-Time Bus Arrival Systems: GPS Cleaning, ETA Prediction & 100k QPS Caching

This article details the end-to-end design of a real-time bus arrival query system, covering GPS data cleaning, map matching, ETA prediction with Kalman filtering, multi-level caching for 100k QPS, WebSocket push aggregation, and fallback strategies, with code examples and architecture diagrams.

Rain's Path to Java Mastery
Rain's Path to Java Mastery
Rain's Path to Java Mastery

1. Requirements Alignment & Capacity Estimation

The system must show real-time bus arrival info: "2 stops away, ~5 minutes". Functional scope includes querying arrivals for a route/direction/stop, displaying vehicle positions on a map, and sub-second data freshness. Explicitly excluded: route planning, payment, scheduling.

Key Metrics

GPS report frequency: 3–10 sec (vehicle terminal capability)

End-to-end latency: User-visible < 3–5 sec (perception red line)

Query response: P99 < 100 ms (read path must be ultra-light)

ETA error: Peak < 1–2 min (algorithm determines experience)

Availability: 99.9% (can be inaccurate, never unavailable)

Capacity Tiers

Single city small: 10k vehicles, write ~3,300 TPS (burst 10k), read peak 100k QPS, read/write ratio ~30:1

Tier-1 city: 30k vehicles, write 3k–6k TPS, read peak 10k+ QPS, read/write ratio ~10:1

National: 200k–1M vehicles, write peak 50k–100k TPS, read peak 100k–1M QPS

For a tier-1 city (30k vehicles, 10 sec interval): write ~3,000 TPS (6k with 2× redundancy), read peak 10k+ QPS. Annual raw GPS records ≈ 100 billion (3,300 TPS × 86,400 sec × 365 days), ~100 GB/day compressed.

Core characteristic: Write is high-frequency small-packet stream; read is bursty hotspot stream; full chain allows eventual consistency, no strong consistency required.

2. Overall Architecture

Data flow:

GPS report → MQTT ingress → Kafka buffering → Flink cleaning/ETA → Redis hot data → API sub-second response + WebSocket push

Layer Responsibilities

Ingress: Netty/MQTT gateway – auth, protocol conversion, rate limiting, stateless.

Kafka: Peak shaving, per-vehicle ordering via partition strategy.

Flink: System brain – cleaning, map matching, stop detection, ETA calculation.

Redis: Handles all read traffic, real-time hot data with second-level TTL.

Time-series DB: Historical trajectory archiving + segment duration statistics.

MySQL: Static route/stop data, rarely changed, fully cacheable.

Tech Stack

Gateway: Nginx + Spring Cloud Gateway – high performance, rate limiting, horizontal scaling

IoT Ingress: MQTT + EMQX – IoT standard, million-level long connections, auto-reconnect

Message Queue: Kafka – high throughput, persistence, suits massive GPS reports

Stream Compute: Flink – native streaming, exactly-once, strong windowing

Hot Cache: Redis Cluster – sub-ms response, native GEO/ZSET

History Storage: TDengine / ClickHouse / HBase – time-series writes, high compression, analytical queries

Relational: MySQL – route, stop, vehicle master data

Search: Elasticsearch – stop fuzzy search, geo lookup

Real-time Push: WebSocket + Netty – long-connection push, arrival alerts

3. Data Model: The dist_from_start Field Is Key

3.1 Not "Nearby Vehicles" – It's a Route-Along Distance Model

Common mistake: using Redis GEO for nearest vehicles. Buses follow fixed routes; users care about distance along the route . A vehicle 200 m straight-line but 2 km via roads – straight-line distance is meaningless.

3.2 MySQL Base Tables

-- Route-stop relation (core table)
CREATE TABLE bus_route_station (
  line_id VARCHAR(32),
  direction TINYINT COMMENT '0 outbound 1 inbound',
  station_seq INT COMMENT 'stop sequence',
  station_id VARCHAR(32),
  station_name VARCHAR(64),
  lon DECIMAL(10,7),
  lat DECIMAL(10,7),
  dist_from_start INT COMMENT 'distance from route start (meters)',
  PRIMARY KEY (line_id, direction, station_seq)
);

The dist_from_start field is the linchpin. Example: Route 302 outbound – Stop A: 0 m, B: 800 m, C: 1,500 m, D: 2,600 m. Vehicle projected at 1,300 m; user queries Stop C (1,500 m): remaining distance = 1,500 – 1,300 = 200 m. One subtraction yields "stops left" and "minutes left".

3.3 Redis Data Structures

Vehicle real-time state: Hash, key bus:live:{vehicleId} – lon/lat, speed, direction, current sequence, TTL 60s–10min, expiry = lost contact

Route vehicle progress: ZSET, key line:{lineId}:{direction}:vehicles – score = along-route distance or sequence; one command fetches vehicles not yet past stop

Route vehicle coordinates: GEO, key line:{lineId}:geo – draw vehicle positions on map

Stop coordinates: GEO, key bus:stations:geo – nearby stop queries

Arrival predictions: ZSET, key route:{lineId}:arrivals – score = predicted arrival timestamp; naturally sorted for "next few buses"

Stop arrival cache: String/Hash, key arr:{lineId}:{stopId} – pre-computed results, short TTL 3–10 sec

Highlight 1: ZSET score = vehicle along-route distance. Query uses ZREVRANGEBYSCORE to fetch all vehicles with score ≤ target stop distance – already sorted, O(log N + M), no full scan.
Highlight 2: Redis Cluster hash tags: keys like bus:{line:302:1}:* forced into same slot, enabling Lua atomic multi-key ops (cross-slot Lua fails).

4. Write Path: GPS Cleaning, Correction & Idempotency

4.1 Ingress: Don't Write Directly – Push to Kafka

@PostMapping("/location")
public Result<Void> reportLocation(@RequestBody BusLocationDTO dto) {
  if (dto.getVehicleId() == null || dto.getLineId() == null) return Result.error("params");
  kafkaTemplate.send("bus-location-topic", JSON.toJSONString(dto));
  return Result.success();
}

Why not direct DB? 10k vehicles × 3 sec = 3,300+ TPS, burst ×3. Kafka buffers, downstream batch consumes, ingress stays ms-level.

4.2 Kafka Partition Strategy: Ordering First

Partition key vehicleId : same vehicle messages strictly ordered; most common, consumer processes per vehicle

Partition key lineId : same route data co-located; Flink aggregates per route

Per-vehicle ordering is hard requirement (out-of-order = stale overwriting fresh). Hash by vehicleId is safest.

4.3 Outlier Filtering & Coordinate Correction

@Component
public class GpsCleanProcessor {
  private static final double MAX_SPEED_KMH = 120.0;
  private static final double MAX_JUMP_METERS = 500.0;

  @KafkaListener(topics = "gps_raw", groupId = "clean-group")
  public void onMessage(GpsReport report, Acknowledgment ack) {
    GpsReport last = RedisUtil.get("gps:last:" + report.getBusId());
    if (last != null && isWildPoint(last, report)) {
      metrics.increment("gps.wild.point");
      ack.acknowledge();
      return; // discard outlier
    }
    // Coordinate correction: domestic maps use GCJ-02, GPS chip outputs WGS84
    double[] wgs84 = CoordTransform.gcj02ToWgs84(report.getLng(), report.getLat());
    report.setLng(wgs84[0]).setLat(wgs84[1]);
    kafkaTemplate.send("gps_clean", report.getBusId(), report);
    RedisUtil.setex("gps:last:" + report.getBusId(), 300, report);
    ack.acknowledge();
  }

  private boolean isWildPoint(GpsReport last, GpsReport cur) {
    long dtSec = Math.max(1, (cur.getTs() - last.getTs()) / 1000);
    double dist = GeoUtils.distance(last.getLng(), last.getLat(), cur.getLng(), cur.getLat());
    double speedKmh = dist / dtSec * 3.6;
    return speedKmh > MAX_SPEED_KMH || (dist > MAX_JUMP_METERS && dtSec < 5);
  }
}

Speed jump > 120 km/h or 500 m within 5 sec → outlier. Outlier rate drops from 3% to 0.1%.

Pitfall: Coordinate correction is mandatory. GCJ-02 vs WGS84 can shift positions by hundreds of meters – once spent half a day debugging a "whole fleet shifted one block" issue.

4.4 Deduplication & Idempotency: Three Layers

Consumer-side idempotent dedup: Redis SETNX on gps:dedup:{vehicleId}:{ts} (2 min TTL).

Stale data discard: Messages > 30 sec behind current time dropped – real-time system only cares about "now".

Timestamp version optimistic lock (key): 4G retransmission causes "new packet arrives first, old later" → vehicle appears to move backward. Use timestamp as version, Lua atomic write:

-- KEYS[1]=vehicle:{id}  ARGV=[ts,lng,lat,speed]
local ts = tonumber(ARGV[1])
local old = tonumber(redis.call('HGET', KEYS[1], 'ts') or '0')
if ts <= old then return 0 end -- stale packet discarded
redis.call('HMSET', KEYS[1], 'ts', ts, 'lng', ARGV[2], 'lat', ARGV[3], 'speed', ARGV[4])
redis.call('EXPIRE', KEYS[1], 300) -- lost-contact auto-expire
return 1
Highlight: Timestamp version optimistic lock – 10× faster than distributed locks. One Lua script handles out-of-order discard, atomic update, and lost-contact expiry.

4.5 Real-time State Write: Hash Tag + ZSET

@Service
public class BusGpsConsumer {
  private final RouteMatcher routeMatcher;
  private final SpeedSmoother speedSmoother;
  private final StringRedisTemplate redis;

  @KafkaListener(topics = "bus.gps.cleaned", groupId = "eta-writer")
  public void onGps(BusGps gps) {
    if (System.currentTimeMillis() - gps.getTs() > 30_000) return; // stale
    String hashTag = String.format("{line:%s:%d}", gps.getLineId(), gps.getDirection());
    String lineKey = String.format("bus:%s:zset", hashTag);
    String vehicleKey = String.format("bus:%s:veh:%s", hashTag, gps.getVehicleId());

    RouteProjection projection = routeMatcher.project(gps);
    double smoothSpeed = speedSmoother.update(gps.getVehicleId(), gps.getSpeed(), gps.getTs());

    Map<String, String> pos = Map.of(
      "dist", String.valueOf(projection.getDistFromStart()),
      "speed", String.valueOf(smoothSpeed),
      "ts", String.valueOf(gps.getTs()),
      "seg", String.valueOf(projection.getSegmentId())
    );
    redis.opsForHash().putAll(vehicleKey, pos);
    redis.opsForZSet().add(lineKey, gps.getVehicleId(), projection.getDistFromStart());
    redis.expire(vehicleKey, Duration.ofSeconds(90));
    redis.expire(lineKey, Duration.ofMinutes(30));
  }
}

4.6 Batch Historical Persistence

@Async
public void batchSave(List<BusLocationDTO> batch) {
  if (batch.isEmpty()) return;
  SqlSession sqlSession = sqlSessionFactory.openSession(ExecutorType.BATCH);
  try {
    BusLocationMapper mapper = sqlSession.getMapper(BusLocationMapper.class);
    for (BusLocationDTO dto : batch) mapper.insert(convert(dto));
    sqlSession.commit();
  } finally { sqlSession.close(); }
}

At higher volumes, write directly to time-series DB (TDengine/ClickHouse), bypass MySQL.

5. Map Matching & Stop Detection: Pinning Drifting GPS to Route

5.1 Map Matching: GPS → Route Projection

double mileage = RouteProjector.project(polyline, p); // projected mileage (meters)
int nextIdx = upperBound(line.stationMileages(), mileage); // binary search next stop

Principle: for each polyline segment find nearest projection point, pick best, accumulate preceding segment lengths. Production often uses Hidden Markov Model (HMM) map matching – better for parallel roads, elevated highways.

Haversine formula for point-to-point distance (must-know basics):

static double dist(double la1, double lo1, double la2, double lo2) {
  final double R = 6_371_000, rad = Math.PI / 180;
  double dLat = (la2 - la1) * rad, dLon = (lo2 - lo1) * rad;
  double a = Math.pow(Math.sin(dLat/2),2) + Math.cos(la1*rad)*Math.cos(la2*rad)*Math.pow(Math.sin(dLon/2),2);
  return 2 * R * Math.asin(Math.sqrt(a));
}
Why not straight-line? Buses follow fixed routes; straight-line error can be multiples. ETA must use along-route arc-length projection distance.

5.2 Stop Detection: Hysteresis Dual-Threshold State Machine

Hidden trap: GPS drift + red-light stops cause vehicle to oscillate at stop boundary. Simple "within 50 m = arrived" flickers between arrived/not-arrived.

Solution: Hysteresis dual-threshold + state machine . Enter threshold strict (40 m + low speed), exit threshold loose (80 m + high speed), middle = hysteresis zone preserving previous state.

public enum StopState { APPROACHING, ARRIVED, DEPARTED }

static StopState transit(StopState cur, GpsPoint p, Station s) {
  double d = dist(p.lat(), p.lng(), s.lat(), s.lng());
  if (cur != StopState.DEPARTED && d < 40 && p.speed() < 2.0) return StopState.ARRIVED;
  if (cur == StopState.ARRIVED && d > 80 && p.speed() > 5.0) return StopState.DEPARTED;
  return cur; // hysteresis zone: keep state
}

Asymmetric enter/exit thresholds naturally immune to edge jitter – more stable than any filter.

5.3 Speed Smoothing: Don't Let Instantaneous Speed Ruin ETA

Sliding window avg: mean of last N speeds – low cost, most common

Exponential weighted: new×0.3 + old×0.7 – low cost, memory-efficient

Kalman filter: state estimation + noise model – medium cost, best effect

Min/max clamp: clamp outliers to reasonable range – low cost, must-have fallback

Flink often uses exponential weighted: smoothSpeed = lastSmooth * 0.7 + instantSpeed * 0.3.

High-frequency writes: use lock-free ring buffer to avoid contention:

public class SpeedRingBuffer {
  private final double[] buf = new double[60]; // 5-min window
  private final AtomicInteger idx = new AtomicInteger();
  public void offer(double speed) { buf[idx.getAndIncrement() % buf.length] = speed; }
  public double avg() { return Arrays.stream(buf).filter(v -> v > 0).average().orElse(0); }
}

When window speed too low (severe congestion), fall back to historical same-hour speed for that segment – crawling instantaneous speed has no reference value.

6. ETA Prediction Algorithm: The System's Soul

6.1 Why "Distance ÷ Speed" Fails

Curves: straight-line distance << actual travel distance

Rush hour: same segment speed varies 3× between 8 AM and 2 PM

Dwell time: 20–40 sec per stop for boarding/alighting

Traffic lights: 15–60 sec per intersection

GPS jitter: instantaneous speed unreliable

Correct approach: Segmented baseline + real-time correction .

6.2 V2: Segmented Prediction + Historical Baseline

ETA = current_segment_remaining_time
    + Σ(intermediate_segment_historical_median_duration)
    + stop_count × dwell_time
    × traffic_factor

Locate vehicle's current stop interval, accumulate each segment's duration to target stop. Historical baselines pre-computed offline from trajectories, stored in Redis keyed bus:avg_speed:{lineId}:{direction}:{hour}, default 15 km/h if missing – cold start uses baseline, no wild guesses .

Real-time correction factor clamped to [0.7, 1.5] to prevent jitter:

int segmentTime(String vehicleId, String line, int dir, int from, int to) {
  int base = historyCache.get(line, dir, from, to, timeSlot(now()));
  double factor = clamp(avgSpeed(vehicleId) / baseSpeed(line, dir, from, to), 0.7, 1.5);
  return (int) (base / factor);
}

6.3 V3: Three-Layer Weighted Speed Model

Each segment speed = weighted blend of:

Real-time measured (weight 0.5)

Historical same-period (weight 0.3)

City-wide congestion (weight 0.2)

@Service
public class EtaCalculator {
  private static final double W_REAL = 0.5, W_HISTORY = 0.3, W_GLOBAL = 0.2;
  private static final double SMOOTH = 0.3; // exponential smoothing

  public EtaResult predict(BusLiveStatus bus, Station target) {
    List<Segment> segments = routeService.getRemainingSegments(bus.getRouteId(), bus.getNextStationId(), target.getStationId());
    long totalSec = 0;
    for (Segment seg : segments) {
      double vReal = bus.getSpeed();
      double vHistory = historySpeedDao.avgSpeed(seg.getId(), bus.getTimestamp());
      double vGlobal = congestionCache.getRoadSpeed(seg.getRoadId());
      double vPredict = W_REAL * vReal + W_HISTORY * vHistory + W_GLOBAL * vGlobal;
      vPredict = Math.max(vPredict, 3.0); // floor 3 km/h
      totalSec += (long) (seg.getLengthKm() / vPredict * 3600);
      totalSec += seg.getStopDwellSec();
    }
    // Exponential smoothing: avoid ETA number jumping
    Long prev = etaCache.get(bus.getBusId() + ":" + target.getStationId());
    if (prev != null) totalSec = (long) (SMOOTH * totalSec + (1 - SMOOTH) * prev);
    etaCache.put(bus.getBusId() + ":" + target.getStationId(), totalSec);
    return EtaResult.of(bus.getBusId(), totalSec);
  }
}

Congestion factor by time-of-day (simple, low-cost, quick win):

private double getCongestionFactor(Date reportTime) {
  int hour = Calendar.getInstance().get(Calendar.HOUR_OF_DAY);
  if ((hour >= 7 && hour <= 9) || (hour >= 17 && hour <= 19)) return 1.5; // rush hour 1.5×
  if (hour >= 11 && hour <= 13) return 1.2; // lunch mild
  return 1.0;
}

Add ~15 sec per intersection from historical stats.

Results:

Error distribution (left better)
Pure distance/speed  ████████████████████████░░░░  avg 180s
+ Historical speed   ██████████████░░░░░░░░░░░░░░  avg 75s
Three-layer+smooth   █████████░░░░░░░░░░░░░░░░░░  avg 28s

From 180 s to 28 s – algorithm value proven.

6.4 V3+: Kalman Incremental Correction (High-Value Design)

Three-layer weighting solves accuracy, but full recompute per GPS causes number jumps (5 min → 2 min → 4 min). Better: no global recompute, only incremental correction . Kalman filter estimates a "duration bias coefficient" k (1.0 = normal). After each completed segment, update k with "actual_duration / baseline_duration".

public final class EtaPredictor {
  private double k = 1.0; // state estimate
  private double p = 1.0; // estimate covariance
  private static final double Q = 0.02; // process noise: traffic change rate
  private static final double R = 0.35; // observation noise: GPS/stop jitter

  public void update(double observed) { // observed = actual / baseline
    p += Q;
    double gain = p / (p + R); // Kalman gain
    k += gain * (observed - k);
    p *= (1 - gain);
    k = Math.max(0.4, Math.min(3.0, k)); // clamp extremes
  }

  public long predict(List<Segment> remain) {
    double runSec = remain.stream().mapToDouble(Segment::baselineSec).sum();
    double stopSec = remain.stream().filter(Segment::isStation).mapToDouble(Segment::dwellSec).sum();
    return (long) (runSec * k + stopSec);
  }
  public record Segment(long id, double baselineSec, double dwellSec, boolean isStation) {}
}
Two clever points: ① Cold start safe : new vehicle/route, k=1.0 uses baseline directly. ② Only corrects remaining segments : as vehicle approaches target, more corrections applied, result converges smoothly. User sees a monotonic converging curve, not jumping numbers.

Interview gold sentence: "Users watch the convergence trend of 'minutes left'; a sudden jump from 5 to 2 minutes is far worse than steadily showing 4 minutes." Pair with frontend monotonic decreasing display (numbers only decrease, reset at arrival) – complaints drop 70%.

6.5 Flink Implementation: Stateful Processing + Smoothed Speed

public class ArrivalTimePredictFunction extends KeyedProcessFunction<String, GpsReport, ArrivalPrediction> {
  private transient ValueState<GpsReport> lastGpsState;
  private transient ValueState<Integer> currentStationIndexState;

  @Override
  public void open(Configuration parameters) {
    lastGpsState = getRuntimeContext().getState(new ValueStateDescriptor<>("last-gps", GpsReport.class));
    currentStationIndexState = getRuntimeContext().getState(new ValueStateDescriptor<>("station-idx", Integer.class));
  }

  @Override
  public void processElement(GpsReport gps, Context ctx, Collector<ArrivalPrediction> out) throws Exception {
    GpsReport lastGps = lastGpsState.value();
    Integer currentIdx = currentStationIndexState.value();
    if (currentIdx == null) currentIdx = 0;

    double speedKmh;
    if (lastGps != null) {
      double distanceMeter = GeoUtils.calculateDistance(lastGps.getLat(), lastGps.getLon(), gps.getLat(), gps.getLon());
      long timeDiffSec = (gps.getTimestamp() - lastGps.getTimestamp()) / 1000;
      double instantSpeed = timeDiffSec > 0 ? (distanceMeter / timeDiffSec) * 3.6 : 0;
      speedKmh = lastGps.getSmoothSpeed() * 0.7 + instantSpeed * 0.3;
    } else speedKmh = gps.getSpeed();
    gps.setSmoothSpeed(speedKmh);

    BusLine line = LineCache.getLine(gps.getLineId());
    List<BusStation> stations = line.getStations();
    for (int i = currentIdx; i < Math.min(currentIdx + 10, stations.size()); i++) {
      BusStation station = stations.get(i);
      double distToStation = GeoUtils.calculateDistance(gps.getLat(), gps.getLon(), station.getLat(), station.getLon());
      int trafficLightCount = countTrafficLights(currentIdx, i, line);
      double predictSeconds = (distToStation / 1000.0) / Math.max(speedKmh, 5) * 3600 + trafficLightCount * 15;
      ArrivalPrediction prediction = new ArrivalPrediction();
      prediction.setLineId(gps.getLineId());
      prediction.setBusId(gps.getBusId());
      prediction.setStationId(station.getStationId());
      prediction.setStationsAway(i - currentIdx);
      prediction.setArrivalSeconds((long) predictSeconds);
      out.collect(prediction);
    }
    lastGpsState.update(gps);
    currentStationIndexState.update(currentIdx);
  }
}

Only predict next 3–10 stops, not all. Full pre-computation would explode write amplification; limiting range balances performance and cost.

6.6 Quantifying Accuracy

Offline trajectory replay: compute MAE/MAPE, bucketed by 0–3 min / 3–10 min / 10+ min.

New model runs shadow mode one week (compute only, no display), compare with old, then gradual rollout.

After enough data, upgrade from statistical model to XGBoost/LSTM with weather, weekday, holiday features.

Baseline first, then optimize. Don't start with deep learning; rule-based model first, let data speak.

7. Query Path: Multi-Level Cache Survives 100k QPS

7.1 Strategy: Compute-for-Query, Cache Is King

Read path principle: as light as possible, layer-by-layer interception .

L1: Caffeine local cache, TTL 1–3 sec – blocks 80–90% hotspot repeats, P99 < 1 ms

L2: Redis, TTL 3–10 sec – absorbs remaining traffic, DB near-zero load

L3: Timetable/historical fallback – returns fallback copy when caches fail

1 sec local cache seems stale? ETA refreshes every 5–10 sec; 1–3 sec cache latency is imperceptible. Ultra-short TTL trades 90% traffic offload – great deal. Static assets (route maps, stop lists) can add Nginx pre-cache.

7.2 Lua Batch Query: One Script Replaces N Requests

Naive: ZSET fetch vehicle list → loop HMGET per vehicle → N+1 round trips, RT spikes.

-- KEYS[1]: route vehicle ZSet, score = along-route distance
-- KEYS[2]: vehicle Hash prefix, e.g. bus:{line:302:1}:veh:
-- ARGV[1]: target stop distance from route start
-- ARGV[2]: max vehicles to return

local buses = redis.call('ZREVRANGEBYSCORE', KEYS[1], ARGV[1], '-inf', 'LIMIT', 0, tonumber(ARGV[2]))
local res = {}
for i, bus in ipairs(buses) do
  local vals = redis.call('HMGET', KEYS[2] .. bus, 'dist', 'speed', 'ts')
  if vals[1] then
    res[#res + 1] = bus .. '|' .. vals[1] .. '|' .. vals[2] .. '|' .. vals[3]
  end
end
return res

Why ZREVRANGEBYSCORE? Target stop at 1,500 m:

Vehicle A: 1,300 m → not passed, nearest
Vehicle B: 900 m   → not passed
Vehicle C: 200 m   → not passed
Vehicle D: 1,700 m → passed, score > 1,500 auto-excluded

Query score <= 1500 descending, already filtered & sorted. One command, clean.

7.3 Complete Query Service

@Service
public class ArrivalQueryService {
  private final StringRedisTemplate redis;
  private final RouteMetaService routeMeta;
  private final Cache<String, List<ArrivalVO>> localCache = Caffeine.newBuilder()
    .maximumSize(20_000).expireAfterWrite(Duration.ofSeconds(1)).build();
  private static final DefaultRedisScript<List> ARRIVAL_SCRIPT = new DefaultRedisScript<>(LUA_SCRIPT, List.class);

  public List<ArrivalVO> query(String lineId, int direction, String stationId) {
    String cacheKey = lineId + ":" + direction + ":" + stationId;
    return localCache.get(cacheKey, k -> load(lineId, direction, stationId));
  }

  private List<ArrivalVO> load(String lineId, int direction, String stationId) {
    double stationDist = routeMeta.distFromStart(lineId, direction, stationId);
    String hashTag = String.format("{line:%s:%d}", lineId, direction);
    String lineKey = String.format("bus:%s:zset", hashTag);
    String vehiclePrefix = String.format("bus:%s:veh:", hashTag);
    List<String> raw = redis.execute(ARRIVAL_SCRIPT, List.of(lineKey, vehiclePrefix), String.valueOf(stationDist), "5");
    if (raw == null || raw.isEmpty()) return List.of();
    return raw.stream().map(item -> parse(lineId, direction, item, stationDist)).filter(this::fresh).toList();
  }

  private ArrivalVO parse(String lineId, int direction, String raw, double stationDist) {
    String[] arr = raw.split("\\|");
    double dist = Double.parseDouble(arr[1]);
    double speed = Double.parseDouble(arr[2]);
    long ts = Long.parseLong(arr[3]);
    double remainDistance = stationDist - dist;
    speed = Math.max(speed, 3.0); // speed floor: congestion/stop/red-light low speed → ETA explosion
    int remainStations = routeMeta.countStationsBetween(lineId, direction, dist, stationDist);
    double etaSeconds = remainDistance / speed + remainStations * 20; // 20 sec per stop dwell+approach+lights
    int etaMinutes = Math.max(1, (int) Math.ceil(etaSeconds / 60));
    return new ArrivalVO(arr[0], remainDistance, remainStations, etaMinutes, ts);
  }

  private boolean fresh(ArrivalVO vo) {
    return System.currentTimeMillis() - vo.ts() < 20_000; // >20 sec stale → degrade with delay hint
  }
  public record ArrivalVO(String vehicleId, double remainDistanceM, int remainStations, int etaMinutes, long ts) {}
}

Key details: speed floor, freshness filter, dwell compensation, minimum 1 min display.

7.4 Alternative: Sequence ZSET + Top 3 Only

If ZSET score = currentSeq, fetch nearest 20 vehicles before target sequence, compute ETA, sort, return top 3.

public List<Eta> query(String lineId, int direction, int targetSeq) {
  String cacheKey = "eta:" + lineId + ":" + direction + ":" + targetSeq;
  return caffeine.get(cacheKey, k -> {
    String zKey = "line:" + lineId + ":" + direction + ":vehicles";
    Set<String> ids = redis.opsForZSet().rangeByScore(zKey, targetSeq - 20, targetSeq - 0.01);
    return ids.stream().map(id -> calcEta(id, targetSeq)).filter(e -> e.seconds() >= 0)
      .sorted(Comparator.comparingInt(Eta::seconds)).limit(3).toList();
  });
}
private Eta calcEta(String vehicleId, int targetSeq) {
  VehicleState s = getState(vehicleId);
  int eta = 0;
  for (int seq = s.currentSeq(); seq < targetSeq; seq++) eta += segmentTime(vehicleId, s.lineId(), s.direction(), seq, seq + 1);
  eta += (targetSeq - s.currentSeq()) * STOP_SECONDS;
  return new Eta(vehicleId, eta);
}

Both implementations same essence: ZSET scopes vehicles, cache absorbs queries, segmented ETA calc. Difference only in score design.

7.5 Cache Breakdown Defense: SingleFlight + Logical Expiry

Hot stop cache expiry → thousands of concurrent rebuilds = breakdown. Two weapons:

SingleFlight request merging: Same key, only one rebuild request; others wait for result.

private final LoadingCache<String, List<ArrivalVO>> localCache = Caffeine.newBuilder()
  .maximumSize(10_000).expireAfterWrite(2, TimeUnit.SECONDS).build(this::loadFromRedis);
private final ConcurrentHashMap<String, CompletableFuture<List<ArrivalVO>>> inFlightRequests = new ConcurrentHashMap<>();

private List<ArrivalVO> loadFromRedis(String stationId) {
  CompletableFuture<List<ArrivalVO>> future = inFlightRequests.computeIfAbsent(stationId, k ->
    CompletableFuture.supplyAsync(() -> { /* rebuild from Redis */ }));
  try { return future.get(300, TimeUnit.MILLISECONDS); }
  catch (Exception e) { return Collections.emptyList(); }
}

Logical expiry: Cache never physically expires; value carries "logical expiry" flag. On read, if expired, return stale value immediately , spawn async thread to rebuild.

public ArrivalVO query(long stationId) {
  String key = "arrival:" + stationId;
  CacheObj v = localCache.get(key); // L1
  if (v == null) v = redis.get(key); // L2
  if (v == null) return timetableFallback(stationId); // L3
  if (v.logicExpired() && tryLock(key)) {
    taskPool.submit(() -> { try { redis.setex(key, 10, rebuild(stationId)); } finally { unlock(key); } });
  }
  return v.data();
}

Philosophy: "Slightly stale data" far better than "no data" or "queue for rebuild". Can also use Redisson tryLock(50, 10, TimeUnit.MILLISECONDS) – fail fast, return fallback (previous bus estimate).

7.6 Cache Trio Full Defense

Avalanche (mass simultaneous expiry): TTL + random jitter

Penetration (query non-existent stop): Empty-value cache + Bloom filter

Breakdown (hot key expiry): SingleFlight / Logical expiry / Hot key never expires + async refresh

Cache-DB consistency: Update DB then delete cache (delayed double delete) + short TTL fallback

// Anti-avalanche random offset
long baseTTL = 300;
long randomOffset = ThreadLocalRandom.current().nextLong(60);
redisTemplate.opsForValue().set(key, value, baseTTL + randomOffset, TimeUnit.SECONDS);
// Anti-penetration empty cache
List<VehicleLocationVO> locations = locationMapper.selectRealtimeByLineId(lineId);
if (locations != null && !locations.isEmpty()) {
  redisTemplate.opsForValue().set(cacheKey, JSON.toJSONString(locations), LOCATION_TTL, TimeUnit.SECONDS);
} else {
  redisTemplate.opsForValue().set(cacheKey, "[]", 60, TimeUnit.SECONDS); // empty cache
}

7.7 Rate Limiting: Final Brake

Entry: Sentinel (per-user 10 QPS). API-level: Guava token bucket per route:

private final Map<Long, RateLimiter> rateLimiters = new ConcurrentHashMap<>();
@GetMapping("/realtime")
public Result<List<VehicleLocationVO>> getRealtime(@RequestParam Long lineId) {
  RateLimiter limiter = rateLimiters.computeIfAbsent(lineId, k -> RateLimiter.create(100));
  if (!limiter.tryAcquire()) return Result.error("Too frequent, retry later");
  return Result.success(busLocationService.getRealtimeLocations(lineId));
}

7.8 GEO Bonus: Nearby Stops

User opens app → "stops near me" – Redis GEO's home turf:

@Service
public class NearbyStationService {
  private static final String GEO_KEY = "bus:stations:geo";
  public void initStationsToGeo(List<BusStation> stations) {
    GeoOperations<String, String> geoOps = redisTemplate.opsForGeo();
    stations.forEach(s -> geoOps.add(GEO_KEY, new Point(s.getLongitude(), s.getLatitude()), s.getStationId()));
  }
  public List<StationDistanceVO> queryNearbyStations(double lon, double lat, double radius) {
    Circle circle = new Circle(new Point(lon, lat), new Distance(radius, Metrics.METERS));
    GeoResults<GeoLocation<String>> results = geoOps.radius(GEO_KEY, circle,
      RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs().includeDistance().includeCoordinates().sortAscending().limit(20));
    if (results == null) return Collections.emptyList();
    return results.getContent().stream().map(r -> {
      StationDistanceVO vo = new StationDistanceVO();
      vo.setStationId(r.getContent().getName());
      vo.setDistance(r.getDistance().getValue());
      return vo;
    }).collect(Collectors.toList());
  }
}

Redis GEO = GeoHash + ZSET, radius query O(log N), vastly outperforms MySQL ST_Distance_Sphere full-table scan. Same pattern for vehicle positions per route: GEOADD to line:{lineId}:geo, GEOSEARCH for map rendering.

Query summary: 99% requests intercepted at cache layer, 1% rebuilds merged to one, extreme cases have fallback. Complete defense-in-depth for high-concurrency reads.

8. Real-time Push: Push-Pull Hybrid, Surviving Push Storms

8.1 Why Not Client Polling?

10k QPS users, each polling every 3 sec → actual 100k QPS, 90% wasted (positions unchanged). Polling amplifies useless traffic. Correct: push-pull hybrid .

First entry: HTTP pull – full fetch once, immediate display

Page stay: WebSocket push – push only on real change, traffic drops order of magnitude

Low-demand: 5-sec short poll – early stage, don't over-engineer

Bus scenario tolerates 5–10 sec refresh (unlike ride-hailing). Start with 5-sec poll, upgrade to WebSocket when UX demands.

8.2 Aggregated Subscription: Push Volume from "User Count" to "Combination Count"

Per-user push → million connections = push storm. Key optimization: merge users subscribing to same "route + stop" into one channel .

String channel = "line:" + lineId + ":stop:" + stopId;
channelSessions.computeIfAbsent(channel, k -> new CopyOnWriteArraySet<>()).add(session);
// Timer every 5s: batch read Redis → broadcast per channel → push volume from "users" to "combinations"

Push volume drops from user-count to route×stop combinations – millions to thousands. Most valuable push-path optimization.

Subscription map kept locally in gateway; timer batch-reads Redis and broadcasts:

@Component
public class BusArrivalWebSocketHandler extends TextWebSocketHandler {
  private final RedisTemplate<String, Object> redisTemplate;
  private final ConcurrentHashMap<String, Set<WebSocketSession>> subscribeMap = new ConcurrentHashMap<>();

  @Override
  protected void handleTextMessage(WebSocketSession session, TextMessage message) {
    String payload = message.getPayload();
    if (payload.startsWith("subscribe:")) {
      String stationId = payload.split(":")[1];
      subscribeMap.computeIfAbsent(stationId, k -> ConcurrentHashMap.newKeySet()).add(session);
    }
  }

  @Scheduled(fixedDelay = 3000)
  public void pushArrivalInfo() {
    subscribeMap.forEach((stationId, sessions) -> {
      if (sessions.isEmpty()) return;
      Object arrivalInfo = redisTemplate.opsForValue().get("bus:arrival:" + stationId);
      if (arrivalInfo == null) return;
      TextMessage msg = new TextMessage(JSON.toJSONString(arrivalInfo));
      sessions.forEach(s -> {
        try { if (s.isOpen()) s.sendMessage(msg); }
        catch (IOException e) { sessions.remove(s); }
      });
    });
  }
}

8.3 Cluster Push: MQ Broadcast + Local Fan-out

Cluster deployment: subscriptions scattered across gateway nodes. Use MQ (Redis Pub/Sub or Kafka) to broadcast change events; each node pushes only its local connections.

static final Map<Long, Set<Session>> TOPIC = new ConcurrentHashMap<>();
static void fanout(long stationId, String payload) {
  for (Session s : TOPIC.getOrDefault(stationId, Set.of())) {
    if (s.isOpen()) s.getAsyncRemote().sendText(payload); // async, non-blocking Netty thread
  }
}

If Flink computes arrival events, add a Sink to push to gateway:

@Component
public class ArrivalPushSink implements SinkFunction<ArrivalEvent> {
  @Override
  public void invoke(ArrivalEvent value, Context ctx) {
    wsGateway.broadcast("station:" + value.getStationId(), JsonUtil.toJson(ArrivalPushVO.from(value)));
  }
}

8.4 Push Engineering Checklist

Push merging: Batch push every 5 sec, prevent N GPS updates → N pushes.

Push timing: Intensive push only 1 stop or 2 min before arrival; otherwise low frequency.

Heartbeat: 30 sec, auto-evict dead connections.

Reconnect: Client exponential backoff, avoid reconnect storm.

Horizontal scaling: Gateway shards by stationId, consistent hashing minimizes connection migration during scale.

Connection reuse: Single long connection supports multi-stop subscriptions.

Push failure fallback: Degrade to in-app message or show on next query.

9. Storage & Hot/Warm/Cold Separation: Storing Trillions of Trajectories Without Bankruptcy

9.1 Data Characteristics Drive Selection

Trajectory data: write-once, rarely updated, queries always time-range bounded – time-series DB territory. MySQL burns money.

TDengine: super-table design, high compression, storage cost -70% – vehicle trajectories, cost-sensitive

InfluxDB: mature ecosystem, low learning curve – small/medium time-series

ClickHouse: columnar, strong analytical queries – historical trajectory analysis, segment duration stats

HBase: massive KV, proven horizontal scaling – 100B+ trajectory archival, high-throughput random R/W

Recommendation: Real-time compute on Redis, trajectory storage TDengine/ClickHouse, 100B+ archival HBase + object storage . Shard by "route + time" for query efficiency.

9.2 Three-Tier Hot/Warm/Cold

Hot: Redis, retention sec–min, purpose real-time queries

Warm: TDengine/ClickHouse, retention 7 days, purpose recent trajectory replay, baseline training

Cold: OSS/S3 compressed archive, retention forever, purpose offline analysis, compliance

Expired data auto-archived to object storage – overall storage cost -60% to -70%. Historical data not waste – ETA segment baselines trained from them , closing the data loop.

10. Fallback & Disaster Recovery: System Can Be Inaccurate, Never Unavailable

Iron law of real-time systems: Users tolerate "data delay", not "blank screen".

Three-level fallback:

Redis down: local Caffeine holds 60 sec + return "no real-time data, refer to schedule"

Flink/Kafka failure: return historical schedule ETA, frontend badge "data delayed"

Query timeout: return only nearest 1 vehicle, no sorting

Push failure: degrade to in-app message / show on next query

Tunnel GPS loss: last known position + time decay, mark "weak signal"

City-wide GPS outage: three-level: real-time → last-position projection → schedule

Position stale >30 sec: don't force compute, return delay notice

Consistency model: Eventual consistency + timestamp version compare + TTL expiry fallback , accept ≤3 sec delay.

Fallback copy is part of UX:

{
  "lineId": "302",
  "stationId": "1001",
  "status": "DELAY",
  "message": "Vehicle data may be delayed, please refer to actual arrival"
}

Better show "~5 min (schedule)" than blank screen; better inaccurate than unavailable.

HA infrastructure: Redis Sentinel/Cluster, Kafka cluster + persistence, MySQL master-slave + read-write split, health checks + auto-restart, Sentinel rate limiting/circuit breaking. Target 99.95% availability.

11. Difficulty Panorama & Interview Follow-ups

11.1 14 Difficulties & Solutions

GPS drift/outliers: position jumps across river → speed jump filter + jump detection + Kalman smoothing + map matching constraint; outlier rate 3% → 0.1%

Tunnel satellite loss: minutes without reports → last valid position + time decay, mark "weak signal"

Coordinate system chaos: fleet offset hundreds of meters → unified GCJ-02/WGS84 correction

Message disorder/dupes: 4G retransmit → vehicle "moves backward" → Kafka partition ordering + timestamp version Lua idempotency + monotonic timestamp discard

Stop state jitter: boundary flicker → hysteresis dual-threshold 40m/80m + state machine

ETA inaccurate: pure distance/speed error 180s → segmented baseline + three-layer weighting + Kalman correction → 28s

Prediction jumps: 3 min → 1 min → 4 min → exponential smoothing + frontend monotonic decreasing display → complaints -70%

Hotspot read amplification: peak hot stop tens of thousands QPS → Caffeine + Redis multi-level + SingleFlight + logical expiry + hot key split → P99 < 20ms

Cache trio: breakdown/avalanche/penetration → TTL random jitter + empty cache + Bloom filter + hot key never expires

Write flood: 100k TPS crushes MySQL → Kafka buffer + Flink streaming + Redis incremental write + batch insert → write latency < 200ms

Push storm: million long connections → aggregate by route+stop + 5-sec merge + consistent hash sharding → gateway handles 500k connections

Direction misjudgment: bidirectional platforms confused → continuous displacement direction + stop sequence order validation + GeoHash direction features

Route change consistency: cache-DB inconsistency → binlog CDC broadcast + versioning + short TTL fallback, route data versioned + gradual update

History data bloat: 100B trajectories storage cost → hot/warm/cold three-tier separation → cost -60% to -70%

11.2 Anticipated Follow-ups

Q: Why not query DB directly for ETA? Real-time query needs <100 ms; DB single query takes tens of ms, can't handle 100k QPS. Pre-compute in Flink asynchronously, query only reads results – classic compute-for-query .

Q: User queries all routes for a stop? station → lines mapping, concurrent queries with timeout + partial failure degradation – one slow route must not drag down whole API.

List<CompletableFuture<List<ArrivalVO>>> futures = lineIds.stream()
  .map(lineId -> CompletableFuture.supplyAsync(() -> arrivalQueryService.query(lineId, direction, stationId), executor))
  .toList();

Q: Guarantee last-bus reminder? Arrival event + schedule last-bus rule → delayed message (RocketMQ scheduled).

Q: Redis totally down? Local Caffeine 60 sec + static schedule page, "~5 min (schedule)" not blank screen .

Q: Direction detection? Same road, two platforms. Three-layer: consecutive GPS displacement direction + stop sequence order (after A comes B) + route GeoHash direction features. Wrong direction shows opposite buses – must plug this hole.

11.3 What Interviewers Really Test

High-concurrency system design (cache, rate limit, fallback)

Real-time compute architecture understanding (Kafka/Flink streaming)

Middleware deep usage (Redis GEO, ZSET, Lua)

Real business problem abstraction (GPS drift, prediction inaccuracy – not in textbooks)

Interview tip: Draw architecture while explaining, dive deep into 2–3 highlight difficulties – beats superficial broad coverage.

12. Evolution Roadmap

V1 launch isn't the end; clear evolution path:

1. Read-time Compute → Write-time Pre-compute

Early: compute on query for fast launch. When QPS grows, shift compute to write path – on vehicle position update, also update its next 3–5 stops' arrival predictions; query reads stop cache directly.

// station:arrival:1001:302:1
[
  {"vehicleId":"粤B12345","remainStations":2,"etaMinutes":5,"ts":1730000000000},
  {"vehicleId":"粤B67890","remainStations":4,"etaMinutes":11,"ts":1730000000000}
]

Query path: read-time compute vs cache read direct

Write pressure: low vs write amplification (limit to next 3–5 stops)

Fit: early, small/medium scale vs high QPS, heavy peak

Complexity: low vs handle expired vehicles, route change cache refresh

2. Rule Model → Machine Learning

After data accumulates, upgrade ETA to XGBoost/LSTM with weather, weekday, holiday, real-time traffic features; validate via A/B testing framework.

3. More Extensions

Edge computing: deploy edge nodes at bus stops, pre-compute hot routes.

GIS visualization: map engine renders real-time trajectories.

Scenario reuse: swap "route model" – ride-hailing ETA, subway arrival, food-delivery courier tracking all fit same architecture.

Closing Summary

Vehicle GPS stream → cleaning & map matching → along-route distance ; based on route stop distances & segmented baselines compute ETA, Kalman incremental correction; query side multi-level cache + Lua scripts + fallback survives high concurrency; push side aggregated subscription survives storms.

Four mantras:

Quantify first, design later – no QPS numbers = amateur design.

Compute for query – shift compute to write path, keep read path feather-light.

Along-route distance, not straight-line – this question's first cognitive gate.

Fallback defines floor – system can be inaccurate, never unavailable.

Tech highlights recap: ZSET score = along-route distance → one command fetches unpassed vehicles; timestamp version Lua idempotency → 10× faster than distributed locks; hysteresis dual-threshold state machine → immune to all edge jitter; Kalman incremental correction → ETA converges smoothly; aggregated push → million-level push volume compressed to thousands.

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

Kalman filterRedis cachingreal-time systemssystem design interviewbus arrival predictionETA calculationFlink stream processingGPS data cleaning
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.