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.
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 pushLayer 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 1Highlight: 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 stopPrinciple: 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_factorLocate 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 28sFrom 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 resWhy 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-excludedQuery 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.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
