
Hello,我是小兔大白糖。 这篇整理面试口述与高频追问要点,方便对照站内同主题通识文。
正文
面向岗位:大型加密货币交易所 Senior Backend Developer - Risk 考察目标: Coding Interview 中高频出现的 6 大核心数据结构,要求能白板手写、可运行、能说清 trade-off。
目录
1. LRU Cache
Concept
LRU (Least Recently Used):当 cache 满时,淘汰最久未被访问的 key。核心思想是"时间局部性"——最近被访问的数据很可能再次被访问。
Analogy:就像书桌上只能放 5 本书,新拿一本上来就把最底下那本(最久没看)抽掉。
Python Implementation
"""
LRU Cache - Python implementation using OrderedDict.
Time: get/put O(1), Space O(capacity)
"""
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict() # key -> value, ordered by access time
def get(self, key: int) -> int:
if key not in self.cache:
return -1
# Move to end (most recently used)
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
# Pop first (least recently used)
self.cache.popitem(last=False)
def __repr__(self):
return f"LRUCache({list(self.cache.items())})"
# ===================== 测试代码 =====================
def test_lru_cache():
cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
assert cache.get(1) == 10 # 1 becomes MRU
cache.put(3, 30) # evicts key 2
assert cache.get(2) == -1 # 2 is evicted
assert cache.get(3) == 30
cache.put(4, 40) # evicts key 1
assert cache.get(1) == -1
assert cache.get(3) == 30
assert cache.get(4) == 40
print("All LRU Cache tests passed!")
print(cache)
if __name__ == "__main__":
test_lru_cache()Java Implementation
import java.util.LinkedHashMap;
import java.util.Map;
/**
* LRU Cache - Java implementation using LinkedHashMap.
* accessOrder=true makes it order by access time (get/put).
*/
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
// initialCapacity, loadFactor, accessOrder=true
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
// ===================== 测试代码 =====================
public static void main(String[] args) {
LRUCache<Integer, Integer> cache = new LRUCache<>(2);
cache.put(1, 10);
cache.put(2, 20);
System.out.println(cache.get(1)); // 10, 1 becomes MRU
cache.put(3, 30); // evicts key 2
System.out.println(cache.get(2)); // null (evicted)
System.out.println(cache.get(3)); // 30
cache.put(4, 40); // evicts key 1
System.out.println(cache.get(1)); // null
System.out.println(cache.get(3)); // 30
System.out.println(cache.get(4)); // 40
System.out.println("Cache contents: " + cache);
}
}Complexity Analysis
| Operation | Time | Space |
|---|---|---|
get | O(1) | O(capacity) |
put | O(1) | O(capacity) |
手写实现要点:如果不让用
LinkedHashMap/OrderedDict,需要手写 HashMap + Doubly Linked List。HashMap 存 key -> Node 的映射,Double Linked List 维护访问顺序。
大型加密货币交易所 / Risk 实际应用
- Risk Feature Local Cache:风控规则引擎在本地缓存热点用户的风控特征(如近 24h 交易笔数),减少 Redis 往返。
- Order Book Snapshot Cache:交易引擎缓存最近几档 order book snapshot,LRU 淘汰冷 snapshot。
- ** sanctions List 查询结果缓存**:制裁名单 API 返回结果缓存在本地,避免重复调用外部服务。
2. LFU Cache
Concept
LFU (Least Frequently Used):当 cache 满时,淘汰访问频率最低的 key。如果频率相同,淘汰最老的。核心思想是"频率局部性"——被频繁访问的数据更重要。
Analogy:图书馆书架只有 5 个位置,每次把被借次数最少的书下架。
Python Implementation
"""
LFU Cache - Python implementation.
Time: get/put O(1), Space O(capacity)
"""
from collections import defaultdict
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.freq = 1
self.prev = None
self.next = None
class DLinkedList:
"""Double linked list with dummy head/tail."""
def __init__(self):
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def append(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
self.size += 1
def pop(self, node=None):
if self.size == 0:
return None
if not node:
node = self.tail.prev
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
return node
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.size = 0
self.min_freq = 0
self.key_map = {} # key -> Node
self.freq_map = defaultdict(DLinkedList) # freq -> DLinkedList
def get(self, key: int) -> int:
if key not in self.key_map:
return -1
node = self.key_map[key]
self._update(node)
return node.val
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
if key in self.key_map:
node = self.key_map[key]
node.val = value
self._update(node)
return
if self.size >= self.capacity:
# Evict LFU (tail of min_freq list)
evicted = self.freq_map[self.min_freq].pop()
del self.key_map[evicted.key]
self.size -= 1
node = Node(key, value)
self.key_map[key] = node
self.freq_map[1].append(node)
self.min_freq = 1
self.size += 1
def _update(self, node):
"""Move node from freq list to freq+1 list."""
freq = node.freq
self.freq_map[freq].pop(node)
if self.min_freq == freq and self.freq_map[freq].size == 0:
self.min_freq += 1
node.freq += 1
self.freq_map[node.freq].append(node)
# ===================== 测试代码 =====================
def test_lfu_cache():
cache = LFUCache(2)
cache.put(1, 10)
cache.put(2, 20)
assert cache.get(1) == 10 # freq(1)=2
cache.put(3, 30) # evicts key 2 (freq=1)
assert cache.get(2) == -1
assert cache.get(3) == 30 # freq(3)=2
cache.put(4, 40) # evicts key 1 or 3? Both freq=2, evict older (key 1)
assert cache.get(1) == -1
assert cache.get(3) == 30
assert cache.get(4) == 40
print("All LFU Cache tests passed!")
if __name__ == "__main__":
test_lfu_cache()Java Implementation
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
/**
* LFU Cache - Java implementation using HashMap + LinkedHashSet per frequency.
* All operations O(1).
*/
public class LFUCache {
private final int capacity;
private int minFreq;
private int size;
// key -> {value, freq}
private final Map<Integer, Node> keyMap;
// freq -> set of keys (insertion order = eviction order)
private final Map<Integer, LinkedHashSet<Integer>> freqMap;
private static class Node {
int val;
int freq;
Node(int val) {
this.val = val;
this.freq = 1;
}
}
public LFUCache(int capacity) {
this.capacity = capacity;
this.minFreq = 0;
this.size = 0;
this.keyMap = new HashMap<>();
this.freqMap = new HashMap<>();
}
public int get(int key) {
if (!keyMap.containsKey(key)) return -1;
Node node = keyMap.get(key);
updateFreq(key, node);
return node.val;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (keyMap.containsKey(key)) {
Node node = keyMap.get(key);
node.val = value;
updateFreq(key, node);
return;
}
if (size >= capacity) {
evictLFU();
}
Node node = new Node(value);
keyMap.put(key, node);
freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
minFreq = 1;
size++;
}
private void updateFreq(int key, Node node) {
int freq = node.freq;
freqMap.get(freq).remove(key);
if (freq == minFreq && freqMap.get(freq).isEmpty()) {
minFreq++;
}
node.freq++;
freqMap.computeIfAbsent(node.freq, k -> new LinkedHashSet<>()).add(key);
}
private void evictLFU() {
LinkedHashSet<Integer> set = freqMap.get(minFreq);
int keyToEvict = set.iterator().next();
set.remove(keyToEvict);
keyMap.remove(keyToEvict);
size--;
}
// ===================== 测试代码 =====================
public static void main(String[] args) {
LFUCache cache = new LFUCache(2);
cache.put(1, 10);
cache.put(2, 20);
System.out.println(cache.get(1)); // 10
cache.put(3, 30); // evicts key 2
System.out.println(cache.get(2)); // -1
System.out.println(cache.get(3)); // 30
cache.put(4, 40); // evicts key 1
System.out.println(cache.get(1)); // -1
System.out.println(cache.get(3)); // 30
System.out.println(cache.get(4)); // 40
System.out.println("LFU Cache tests passed!");
}
}Complexity Analysis
| Operation | Time | Space |
|---|---|---|
get | O(1) | O(capacity) |
put | O(1) | O(capacity) |
核心设计:
key_map定位节点,freq_map[f]存储频率为 f 的所有节点(用 DLinkedList 或 LinkedHashSet 保持插入顺序),min_freq记录当前最小频率用于 O(1) 淘汰。
大型加密货币交易所 / Risk 实际应用
- Risk Rule Result Cache:高频触发的风控规则(如"大额提币检查")结果缓存,低频规则自然淘汰,避免 Redis 压力。
- Hot Wallet Address Cache:热钱包地址被高频查询,冷地址自动淘汰。
- API Response Cache for Internal Services:内部微服务间调用,缓存高频查询的 response。
3. Bloom Filter
Concept
Bloom Filter 是一个概率型数据结构,用于判断"一个元素是否可能属于某个集合"。可能误判(false positive),但绝不会漏判(false negative)。
Analogy:就像酒店前台的黑名单系统,一查"这人可能在黑名单上"就报警,但如果系统说"不在",那一定不在。
Python Implementation
"""
Bloom Filter - Python implementation using multiple hash functions.
Space efficient probabilistic membership test.
"""
import hashlib
import math
import mmh3 # pip install mmh3; fallback to hashlib if not available
class BloomFilter:
def __init__(self, expected_items: int, false_positive_rate: float):
"""
expected_items: 预期插入元素数量
false_positive_rate: 可接受的误判率 (如 0.01 = 1%)
"""
self.size = self._optimal_size(expected_items, false_positive_rate)
self.hash_count = self._optimal_hash_count(self.size, expected_items)
self.bit_array = [0] * self.size
self.item_count = 0
@staticmethod
def _optimal_size(n, p):
m = - (n * math.log(p)) / (math.log(2) ** 2)
return int(m)
@staticmethod
def _optimal_hash_count(m, n):
k = (m / n) * math.log(2)
return int(k)
def _hashes(self, item: str):
"""Generate k hash values using double hashing."""
h1 = mmh3.hash(item, 0) % self.size
h2 = mmh3.hash(item, 1) % self.size
for i in range(self.hash_count):
yield (h1 + i * h2) % self.size
def add(self, item: str):
for idx in self._hashes(item):
self.bit_array[idx] = 1
self.item_count += 1
def __contains__(self, item: str) -> bool:
return all(self.bit_array[idx] == 1 for idx in self._hashes(item))
def current_false_positive_rate(self) -> float:
return (1 - math.exp(-self.hash_count * self.item_count / self.size)) ** self.hash_count
# ===================== 测试代码 =====================
def test_bloom_filter():
bf = BloomFilter(expected_items=10000, false_positive_rate=0.01)
# Add some items
for i in range(1000):
bf.add(f"user_{i}")
# Check membership
assert "user_5" in bf
assert "user_999" in bf
assert "user_not_exist" not in bf # May be false positive!
# False positive test
fp_count = 0
test_size = 10000
for i in range(test_size):
if f"nonexistent_{i}" in bf:
fp_count += 1
print(f"Items added: {bf.item_count}")
print(f"Bit array size: {bf.size}")
print(f"Hash functions: {bf.hash_count}")
print(f"False positives: {fp_count}/{test_size} = {fp_count/test_size:.4f}")
print(f"Expected FP rate: {bf.current_false_positive_rate():.4f}")
if __name__ == "__main__":
test_bloom_filter()Java Implementation
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
/**
* Bloom Filter - Java implementation.
* Uses MD5 for multiple hash functions (double hashing technique).
*/
public class BloomFilter {
private final BitSet bitSet;
private final int bitSize;
private final int hashCount;
private int itemCount;
public BloomFilter(int expectedItems, double falsePositiveRate) {
this.bitSize = optimalSize(expectedItems, falsePositiveRate);
this.hashCount = optimalHashCount(bitSize, expectedItems);
this.bitSet = new BitSet(bitSize);
this.itemCount = 0;
}
private int optimalSize(int n, double p) {
return (int) (-(n * Math.log(p)) / (Math.log(2) * Math.log(2)));
}
private int optimalHashCount(int m, int n) {
return (int) ((m / (double) n) * Math.log(2));
}
public void add(String item) {
int[] hashes = getHashes(item);
for (int hash : hashes) {
bitSet.set(Math.abs(hash % bitSize), true);
}
itemCount++;
}
public boolean mightContain(String item) {
int[] hashes = getHashes(item);
for (int hash : hashes) {
if (!bitSet.get(Math.abs(hash % bitSize))) {
return false;
}
}
return true; // May be false positive!
}
private int[] getHashes(String item) {
int[] result = new int[hashCount];
try {
MessageDigest md = MessageDigest.getInstance("MD5");
byte[] digest = md.digest(item.getBytes(StandardCharsets.UTF_8));
int h1 = bytesToInt(digest, 0);
int h2 = bytesToInt(digest, 4);
for (int i = 0; i < hashCount; i++) {
result[i] = h1 + i * h2;
}
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException(e);
}
return result;
}
private int bytesToInt(byte[] bytes, int offset) {
return ((bytes[offset] & 0xFF) << 24) |
((bytes[offset + 1] & 0xFF) << 16) |
((bytes[offset + 2] & 0xFF) << 8) |
(bytes[offset + 3] & 0xFF);
}
// ===================== 测试代码 =====================
public static void main(String[] args) {
BloomFilter bf = new BloomFilter(10000, 0.01);
for (int i = 0; i < 1000; i++) {
bf.add("user_" + i);
}
System.out.println(bf.mightContain("user_5")); // true
System.out.println(bf.mightContain("user_999")); // true
System.out.println(bf.mightContain("not_exist")); // false (probably)
// False positive test
int fp = 0;
int testSize = 10000;
for (int i = 0; i < testSize; i++) {
if (bf.mightContain("nonexistent_" + i)) fp++;
}
System.out.println("False positives: " + fp + "/" + testSize);
System.out.println("Bit size: " + bf.bitSize + ", Hash count: " + bf.hashCount);
}
}Complexity Analysis
| Operation | Time | Space |
|---|---|---|
add | O(k) ~ O(1) (k = hash count, typically 3-7) | O(m) bits |
mightContain | O(k) ~ O(1) | O(m) bits |
空间效率公式:对于 n 个元素、误判率 p,最优 bit 数组大小
m = -n * ln(p) / (ln2)^2,最优 hash 函数数量k = m/n * ln2。 例如:n=100万, p=1% 时,只需约 1.14MB。
大型加密货币交易所 / Risk 实际应用
- Sanctions List Pre-Filter:OFAC / UN 制裁名单预过滤。Bloom Filter 放在 API Gateway 层,快速判断"用户是否在制裁名单上",false positive 再走精确查询。
- Duplicate Order Detection:防止用户重复提交订单,Bloom Filter 先过滤已存在的 order ID。
- Blacklist IP Pre-Check:IP 黑名单前置过滤,减少 Redis 查询。
- Transaction Hash Deduplication:去重已处理的交易 hash,避免重复入账。
4. Consistent Hash
Concept
Consistent Hashing 将节点和数据都映射到同一个 hash 环上,数据归属顺时针最近的节点。当节点增删时,只有相邻节点的数据需要迁移,而不是全部 rehash。
Analogy:就像一群朋友围成一个圈分糖果,每个糖果给顺时针最近的人。有人离开,只影响左右邻居。
Python Implementation
"""
Consistent Hash with Virtual Nodes.
Reduces load imbalance when node count is small.
"""
import hashlib
import bisect
from typing import List, Dict
class ConsistentHash:
def __init__(self, nodes: List[str] = None, replicas: int = 150):
self.replicas = replicas # Virtual nodes per physical node
self.ring = [] # Sorted list of hash values
self.nodes = {} # hash -> physical node
self.keys = set() # Physical nodes
if nodes:
for node in nodes:
self.add_node(node)
def _hash(self, key: str) -> int:
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def add_node(self, node: str):
self.keys.add(node)
for i in range(self.replicas):
key = self._hash(f"{node}:{i}")
self.nodes[key] = node
bisect.insort(self.ring, key)
def remove_node(self, node: str):
self.keys.discard(node)
for i in range(self.replicas):
key = self._hash(f"{node}:{i}")
del self.nodes[key]
idx = bisect.bisect_left(self.ring, key)
self.ring.pop(idx)
def get_node(self, key: str) -> str:
if not self.ring:
return None
h = self._hash(key)
idx = bisect.bisect_right(self.ring, h)
if idx == len(self.ring):
idx = 0
return self.nodes[self.ring[idx]]
def get_distribution(self, test_keys: List[str]) -> Dict[str, int]:
dist = {node: 0 for node in self.keys}
for k in test_keys:
node = self.get_node(k)
dist[node] += 1
return dist
# ===================== 测试代码 =====================
def test_consistent_hash():
ch = ConsistentHash(nodes=["node-A", "node-B", "node-C"], replicas=150)
# Generate test keys
test_keys = [f"user_{i}" for i in range(10000)]
dist = ch.get_distribution(test_keys)
print("Initial distribution:", dist)
# Add node D
ch.add_node("node-D")
dist2 = ch.get_distribution(test_keys)
print("After adding node-D:", dist2)
# Check data migration percentage
moved = sum(1 for k in test_keys if ch.get_node(k) != ConsistentHash(
nodes=["node-A", "node-B", "node-C"], replicas=150
).get_node(k))
print(f"Keys moved: {moved}/{len(test_keys)} = {moved/len(test_keys)*100:.2f}%")
# Remove node B
ch.remove_node("node-B")
dist3 = ch.get_distribution(test_keys)
print("After removing node-B:", dist3)
if __name__ == "__main__":
test_consistent_hash()Java Implementation
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
/**
* Consistent Hash with Virtual Nodes.
* Maps both nodes and data to a hash ring.
*/
public class ConsistentHash {
private final int replicas; // Virtual nodes per physical node
private final TreeMap<Long, String> ring = new TreeMap<>();
private final Set<String> nodes = new HashSet<>();
public ConsistentHash(int replicas, Collection<String> nodes) {
this.replicas = replicas;
for (String node : nodes) {
addNode(node);
}
}
public void addNode(String node) {
nodes.add(node);
for (int i = 0; i < replicas; i++) {
long hash = hash(node + ":" + i);
ring.put(hash, node);
}
}
public void removeNode(String node) {
nodes.remove(node);
for (int i = 0; i < replicas; i++) {
long hash = hash(node + ":" + i);
ring.remove(hash);
}
}
public String getNode(String key) {
if (ring.isEmpty()) return null;
long hash = hash(key);
Map.Entry<Long, String> entry = ring.ceilingEntry(hash);
if (entry == null) {
entry = ring.firstEntry();
}
return entry.getValue();
}
private long hash(String key) {
try {
MessageDigest md = MessageDigest.getInstance("MD5");
byte[] digest = md.digest(key.getBytes(StandardCharsets.UTF_8));
return ((long) (digest[3] & 0xFF) << 24) |
((long) (digest[2] & 0xFF) << 16) |
((long) (digest[1] & 0xFF) << 8) |
((long) (digest[0] & 0xFF));
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException(e);
}
}
// ===================== 测试代码 =====================
public static void main(String[] args) {
List<String> nodes = Arrays.asList("node-A", "node-B", "node-C");
ConsistentHash ch = new ConsistentHash(150, nodes);
Map<String, Integer> dist = new HashMap<>();
for (int i = 0; i < 10000; i++) {
String node = ch.getNode("user_" + i);
dist.merge(node, 1, Integer::sum);
}
System.out.println("Initial: " + dist);
ch.addNode("node-D");
dist.clear();
for (int i = 0; i < 10000; i++) {
String node = ch.getNode("user_" + i);
dist.merge(node, 1, Integer::sum);
}
System.out.println("After add node-D: " + dist);
ch.removeNode("node-B");
dist.clear();
for (int i = 0; i < 10000; i++) {
String node = ch.getNode("user_" + i);
dist.merge(node, 1, Integer::sum);
}
System.out.println("After remove node-B: " + dist);
}
}Complexity Analysis
| Operation | Time | Space |
|---|---|---|
addNode | O(replicas * log N) | O(replicas * nodes) |
removeNode | O(replicas * log N) | O(replicas * nodes) |
getNode | O(log N) | O(replicas * nodes) |
虚拟节点数量:通常每个物理节点 100-200 个虚拟节点。虚拟节点越多,负载越均衡,但 ring 越大查询越慢。
大型加密货币交易所 / Risk 实际应用
- Redis Cluster Sharding:风控特征存储在 Redis Cluster 中,使用 consistent hash 将 userId 映射到特定 Redis 节点,扩容时只迁移 1/N 数据。
- Kafka Partition Assignment:自定义 partitioner 用 consistent hash 保证相同 key 始终落到同一 partition。
- Rate Limiting Sharding:API 限流状态分散到多个 Redis 节点,consistent hash 按 userId 分片。
- Cache Cluster:本地缓存集群(如 Caffeine + Hazelcast)的 key 分布策略。
5. Token Bucket
Concept
Token Bucket 是经典的 rate limiting 算法。桶以固定速率产生 token,请求来时要消费 token,有 token 就通过,没有就拒绝或等待。允许一定程度的突发流量(burst)。
Analogy:就像游乐园的代币机,每隔几秒自动吐出 1 个代币,玩项目需要消耗代币。代币可以攒着,最多攒满一桶。
Python Implementation
"""
Token Bucket - Rate limiting algorithm.
Supports burst traffic while maintaining average rate.
"""
import time
import threading
class TokenBucket:
def __init__(self, rate: float, capacity: int):
"""
rate: tokens added per second
capacity: maximum tokens in bucket (burst size)
"""
self.rate = rate
self.capacity = capacity
self.tokens = float(capacity)
self.last_update = time.time()
self.lock = threading.Lock()
def _add_tokens(self):
now = time.time()
elapsed = now - self.last_update
self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
self.last_update = now
def consume(self, tokens: int = 1) -> bool:
with self.lock:
self._add_tokens()
if self.tokens >= tokens:
self.tokens -= tokens
return True
return False
def wait_time(self, tokens: int = 1) -> float:
"""Return seconds to wait before tokens are available."""
with self.lock:
self._add_tokens()
if self.tokens >= tokens:
return 0.0
needed = tokens - self.tokens
return needed / self.rate
# ===================== 测试代码 =====================
def test_token_bucket():
bucket = TokenBucket(rate=10.0, capacity=5) # 10/sec, burst 5
# First 5 should pass immediately (burst)
for i in range(5):
assert bucket.consume(), f"Request {i} should pass"
# 6th should fail (bucket empty)
assert not bucket.consume(), "6th request should fail"
# Wait for refill
time.sleep(0.2)
assert bucket.consume(), "Should pass after refill"
# Wait time test
bucket2 = TokenBucket(rate=2.0, capacity=1)
assert bucket2.consume()
wait = bucket2.wait_time()
print(f"Wait time: {wait:.3f}s")
assert 0.4 < wait < 0.6
print("All Token Bucket tests passed!")
if __name__ == "__main__":
test_token_bucket()Java Implementation
/**
* Token Bucket - Thread-safe rate limiter.
* Allows burst up to capacity, then throttles to steady rate.
*/
public class TokenBucket {
private final double rate; // tokens per second
private final double capacity;
private double tokens;
private long lastUpdateTimeNanos;
private final Object lock = new Object();
public TokenBucket(double rate, double capacity) {
this.rate = rate;
this.capacity = capacity;
this.tokens = capacity;
this.lastUpdateTimeNanos = System.nanoTime();
}
public boolean consume(double tokens) {
synchronized (lock) {
refill();
if (this.tokens >= tokens) {
this.tokens -= tokens;
return true;
}
return false;
}
}
public boolean consume() {
return consume(1.0);
}
public double waitTime(double tokens) {
synchronized (lock) {
refill();
if (this.tokens >= tokens) {
return 0.0;
}
double needed = tokens - this.tokens;
return needed / rate;
}
}
private void refill() {
long now = System.nanoTime();
double elapsed = (now - lastUpdateTimeNanos) / 1_000_000_000.0;
tokens = Math.min(capacity, tokens + elapsed * rate);
lastUpdateTimeNanos = now;
}
// ===================== 测试代码 =====================
public static void main(String[] args) throws InterruptedException {
TokenBucket bucket = new TokenBucket(10.0, 5.0);
// Burst 5 should pass
for (int i = 0; i < 5; i++) {
System.out.println("Request " + i + ": " + bucket.consume());
}
System.out.println("Request 5: " + bucket.consume()); // false
Thread.sleep(200);
System.out.println("After 200ms: " + bucket.consume()); // true
// Wait time
TokenBucket bucket2 = new TokenBucket(2.0, 1.0);
bucket2.consume();
System.out.println("Wait time: " + bucket2.waitTime(1.0) + "s");
}
}Complexity Analysis
| Operation | Time | Space |
|---|---|---|
consume | O(1) | O(1) |
wait_time | O(1) | O(1) |
关键设计:懒加载 refill(只在 consume 时计算),避免定时器线程。用
System.nanoTime()保证精度。
大型加密货币交易所 / Risk 实际应用
- Per-User API Rate Limit:每个用户每秒钟最多 N 次 API 调用,大型加密货币交易所 交易 API 的
X-MBX-USED-WEIGHT-1M就是这种机制。 - Withdrawal Rate Limit:提币接口按用户限流,防止机器人批量提币。
- Internal Service Throttling:风控服务调用外部数据源(如链上分析 API)时用 token bucket 限流,防止打挂对方。
- Order Placement Burst Control:允许用户短时间内下少量订单(burst),但长期平均速率受控。
6. Timing Wheel
Concept
Timing Wheel(时间轮)是 Kafka / Netty 使用的高效定时器结构。将时间划分为固定槽位(slot),每个槽位挂一个任务链表。指针每 tick 转动一格,到期就执行该槽位的所有任务。
Analogy:就像老式火车站的大钟,每个刻度(slot)下面挂着该时刻发车的列车(task)。指针每走一格,就把该刻度的所有车放行。
Python Implementation
"""
Hierarchical Timing Wheel - Multi-level timing wheel for efficient timeout management.
Level 0: tick=1ms, 20 slots -> max 20ms
Level 1: tick=20ms, 60 slots -> max 1200ms
Level 2: tick=1s, 60 slots -> max 60s
"""
import time
import threading
from collections import deque
from typing import Callable, List, Optional
class TimerTask:
def __init__(self, delay_ms: int, callback: Callable, recurring: bool = False):
self.delay_ms = delay_ms
self.callback = callback
self.recurring = recurring
self.rounds = 0 # How many rounds to wait in current slot
def run(self):
self.callback()
class TimingWheelLevel:
def __init__(self, tick_ms: int, wheel_size: int):
self.tick_ms = tick_ms
self.wheel_size = wheel_size
self.slots = [deque() for _ in range(wheel_size)]
self.current_tick = 0
self.interval = tick_ms * wheel_size
def add(self, task: TimerTask, remaining_ms: int):
"""Add task, return True if task is placed in this level."""
if remaining_ms >= self.interval:
return False
ticks = remaining_ms // self.tick_ms
task.rounds = ticks // self.wheel_size
slot_idx = (self.current_tick + ticks) % self.wheel_size
self.slots[slot_idx].append(task)
return True
def advance(self) -> List[TimerTask]:
self.current_tick = (self.current_tick + 1) % self.wheel_size
slot = self.slots[self.current_tick]
expired = []
remaining = deque()
for task in slot:
if task.rounds <= 0:
expired.append(task)
else:
task.rounds -= 1
remaining.append(task)
self.slots[self.current_tick] = remaining
return expired
class HierarchicalTimingWheel:
def __init__(self, tick_ms: int = 1, wheel_size: int = 20):
self.tick_ms = tick_ms
self.wheel_size = wheel_size
# Level 0: tick=1ms, 20 slots -> 20ms
# Level 1: tick=20ms, 60 slots -> 1200ms
# Level 2: tick=1200ms, 60 slots -> 72000ms (72s)
self.levels = [
TimingWheelLevel(tick_ms, wheel_size),
TimingWheelLevel(tick_ms * wheel_size, wheel_size),
TimingWheelLevel(tick_ms * wheel_size * wheel_size, wheel_size),
]
self.running = False
self.lock = threading.Lock()
self.thread: Optional[threading.Thread] = None
def start(self):
self.running = True
self.thread = threading.Thread(target=self._tick_loop)
self.thread.daemon = True
self.thread.start()
def stop(self):
self.running = False
if self.thread:
self.thread.join()
def schedule(self, delay_ms: int, callback: Callable, recurring: bool = False):
task = TimerTask(delay_ms, callback, recurring)
with self.lock:
self._add_task(task, delay_ms)
def _add_task(self, task: TimerTask, remaining_ms: int):
for level in self.levels:
if level.add(task, remaining_ms):
return
# Overflow: put in highest level's last slot
self.levels[-1].slots[-1].append(task)
def _tick_loop(self):
while self.running:
time.sleep(self.tick_ms / 1000.0)
with self.lock:
self._advance()
def _advance(self):
carry = True
for level in self.levels:
expired = level.advance()
for task in expired:
# Execute in thread pool (simplified: direct call)
task.run()
if task.recurring:
self._add_task(task, task.delay_ms)
if level.current_tick != 0:
carry = False
break # No carry to next level
# ===================== 测试代码 =====================
def test_timing_wheel():
results = []
def callback(name):
results.append((name, time.time()))
print(f"[{time.time():.3f}] Task '{name}' executed")
tw = HierarchicalTimingWheel(tick_ms=10, wheel_size=10)
tw.start()
tw.schedule(30, lambda: callback("A")) # 30ms
tw.schedule(50, lambda: callback("B")) # 50ms
tw.schedule(150, lambda: callback("C")) # 150ms -> goes to level 1
time.sleep(0.3)
tw.stop()
assert len(results) >= 3, f"Expected 3 tasks, got {len(results)}"
print(f"\nAll {len(results)} tasks executed successfully!")
if __name__ == "__main__":
test_timing_wheel()Java Implementation
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.*;
/**
* Hierarchical Timing Wheel - Multi-level timing wheel.
* Netty/Kafka style timer for efficient timeout management.
*/
public class HierarchicalTimingWheel {
private final long tickMs;
private final int wheelSize;
private final TimingWheelLevel[] levels;
private final ScheduledExecutorService executor;
private final ExecutorService taskExecutor;
public HierarchicalTimingWheel(long tickMs, int wheelSize) {
this.tickMs = tickMs;
this.wheelSize = wheelSize;
this.levels = new TimingWheelLevel[3];
// Level 0: tick=1ms, 20 slots -> 20ms
// Level 1: tick=20ms, 60 slots -> 1200ms
// Level 2: tick=1200ms, 60 slots -> 72000ms
this.levels[0] = new TimingWheelLevel(tickMs, wheelSize);
this.levels[1] = new TimingWheelLevel(tickMs * wheelSize, wheelSize);
this.levels[2] = new TimingWheelLevel(tickMs * wheelSize * wheelSize, wheelSize);
this.executor = Executors.newSingleThreadScheduledExecutor();
this.taskExecutor = Executors.newFixedThreadPool(4);
}
public void start() {
executor.scheduleAtFixedRate(this::tick, tickMs, tickMs, TimeUnit.MILLISECONDS);
}
public void stop() {
executor.shutdown();
taskExecutor.shutdown();
}
public void schedule(long delayMs, Runnable task) {
TimerTask timerTask = new TimerTask(delayMs, task);
addTask(timerTask, delayMs);
}
private synchronized void addTask(TimerTask task, long remainingMs) {
for (TimingWheelLevel level : levels) {
if (level.add(task, remainingMs)) return;
}
levels[levels.length - 1].slots[wheelSize - 1].add(task);
}
private synchronized void tick() {
boolean carry = true;
for (TimingWheelLevel level : levels) {
List<TimerTask> expired = level.advance();
for (TimerTask task : expired) {
taskExecutor.execute(task.runnable);
}
if (level.currentTick != 0) {
carry = false;
break;
}
}
}
private static class TimerTask {
long delayMs;
Runnable runnable;
int rounds = 0;
TimerTask(long delayMs, Runnable runnable) {
this.delayMs = delayMs;
this.runnable = runnable;
}
}
private class TimingWheelLevel {
final long tickMs;
final int wheelSize;
final Queue<TimerTask>[] slots;
int currentTick = 0;
final long interval;
@SuppressWarnings("unchecked")
TimingWheelLevel(long tickMs, int wheelSize) {
this.tickMs = tickMs;
this.wheelSize = wheelSize;
this.interval = tickMs * wheelSize;
this.slots = new Queue[wheelSize];
for (int i = 0; i < wheelSize; i++) slots[i] = new LinkedList<>();
}
boolean add(TimerTask task, long remainingMs) {
if (remainingMs >= interval) return false;
long ticks = remainingMs / tickMs;
task.rounds = (int) (ticks / wheelSize);
int slotIdx = (int) ((currentTick + ticks) % wheelSize);
slots[slotIdx].add(task);
return true;
}
List<TimerTask> advance() {
currentTick = (currentTick + 1) % wheelSize;
Queue<TimerTask> slot = slots[currentTick];
List<TimerTask> expired = new LinkedList<>();
Queue<TimerTask> remaining = new LinkedList<>();
for (TimerTask task : slot) {
if (task.rounds <= 0) {
expired.add(task);
} else {
task.rounds--;
remaining.add(task);
}
}
slots[currentTick] = remaining;
return expired;
}
}
// ===================== 测试代码 =====================
public static void main(String[] args) throws InterruptedException {
HierarchicalTimingWheel tw = new HierarchicalTimingWheel(10, 10);
tw.start();
CountDownLatch latch = new CountDownLatch(3);
tw.schedule(30, () -> {
System.out.println("Task A executed");
latch.countDown();
});
tw.schedule(50, () -> {
System.out.println("Task B executed");
latch.countDown();
});
tw.schedule(150, () -> {
System.out.println("Task C executed (level 1)");
latch.countDown();
});
latch.await(1, TimeUnit.SECONDS);
tw.stop();
System.out.println("All tasks executed!");
}
}Complexity Analysis
| Operation | Time | Space |
|---|---|---|
schedule | O(1) | O(tasks) |
tick (per tick) | O(expired_tasks) | O(tasks) |
cancel | O(1) with hashtable | O(tasks) |
层级设计:单层时间轮最大只能表示
tick * slots的延迟。层级时间轮通过多层(如毫秒级、秒级、分钟级)实现任意大的延迟,同时保持 O(1) 的插入和 tick。
大型加密货币交易所 / Risk 实际应用
- Order Timeout Management:挂单超过 N 秒未成交自动取消。交易引擎管理百万级订单的超时,Timing Wheel 比 PriorityQueue 高效得多。
- Connection Timeout:WebSocket / TCP 连接超时管理,Netty 的
HashedWheelTimer就是这种实现。 - Delayed Message Processing:Kafka 的 delayed operation(如 delayed fetch, delayed produce)使用 Timing Wheel 管理。
- Risk Alert Throttling:风控告警在触发后 N 分钟内不重复发送,Timing Wheel 管理 cooldown 时间。
- Session Expiry:用户登录 session TTL 管理,到期自动踢出。
7. 面试现场建议
7.1 30 分钟白板 LRU 的标准流程
Phase 1:理解题意 (2 min)
- 确认:
get和put都要是 O(1) - 确认:是否需要 thread-safe?(通常先写单线程,再提 thread-safe)
- 确认:capacity 是 count-based 还是 size-based?(先 count-based)
Phase 2:核心设计 (5 min)
- 在白板上画:HashMap + Doubly Linked List
- HashMap:
key -> Node,O(1) 定位 - Doubly Linked List: 维护访问顺序,head=MRU, tail=LRU
- 写 Node 结构:
key, val, prev, next
Phase 3:实现代码 (15 min)
class Node:
def __init__(self, k, v):
self.key = k
self.val = v
self.prev = self.next = None
- 先写
__init__初始化 dummy head/tail - 再写
_remove(node)和_add_to_head(node)辅助方法 - 然后写
get:如果存在,remove + add_to_head - 最后写
put:如果存在 update + move_to_head;如果不存在 add_to_head + 检查 capacity
Phase 4:测试走查 (5 min)
- 口头走一遍:
cap=2, put(1), put(2), get(1), put(3), get(2)=? - 预期:get(2) = -1,因为 2 被淘汰
Phase 5:扩展讨论 (3 min)
- "如果要 thread-safe,可以加
ReadWriteLock,读多写少场景性能更好" - "如果要 size-based(比如缓存总大小不超过 100MB),Node 里加 size 字段,总量超了就淘汰"
- "如果要 eviction callback(如淘汰时写回 DB),在
_remove里触发"
7.2 加分项(主动提及)
| 话题 | 一句话表达 |
|---|---|
| Thread Safety | "单线程版本先保证正确性,生产环境会用 ConcurrentHashMap + ReentrantReadWriteLock" |
| Size-based Eviction | "大型加密货币交易所 缓存的是 protobuf 对象,按字节数控制更合理,Node 里加 size 字段" |
| Expiration Policy | "可以加 expireAt 字段,get 时检查是否过期,类似 Caffeine 的 expireAfterWrite" |
| Eviction Callback | "淘汰时触发 onEvict(key, value),用于 write-through 或 audit log" |
| Distributed LRU | "单节点用本地缓存,集群场景用 Redis + local LRU 做 L1/L2,或用 Hazelcast/Caffeine 分布式版本" |
| Cache Warming | "服务启动时预加载热点数据,避免冷启动击穿 DB" |
7.3 避免的坑
- 不要先写
list.remove(key):链表删除需要节点引用,不是 key - 不要忘记更新 HashMap:put 新 key 时,old node 要从 HashMap 删除
- 不要写错边界条件:
self.size > self.capacity时才淘汰,不是>= - 不要过度设计:先写单线程,面试官问才加锁
8. 常见追问应对
Q1: How to make LRU thread-safe?
Model Answer:
"单线程版本用
HashMap+DoubleLinkedList。线程安全版本有两种方案:
- 粗粒度锁:
ReentrantLock保护所有操作,简单但并发度低。- 细粒度锁:Java 的
ConcurrentHashMap保证 map 安全,链表操作用ReentrantReadWriteLock,读多写少时性能更好。- Lock-free:用
ConcurrentLinkedDeque+ConcurrentHashMap,但实现复杂,容易出 bug。 生产环境我倾向方案 2,够简单且性能足够。大型加密货币交易所 的 Caffeine 缓存库内部用了Striped ReadWriteLock,分段锁减少竞争。"
Q2: What's the false positive rate of Bloom Filter?
Model Answer:
"False Positive Rate 的公式是: 假阳性率近似:
p ≈ (1 - exp(-k*n/m))^k(m 位数,n 元素数,k 哈希次数) 其中 k=hash 函数数量, n=插入元素数, m=bit 数组大小。 给定 n 和 p,最优参数是:
m = -n * ln(p) / (ln2)^2k = m/n * ln2例如 n=100万, p=0.1% 时,m ≈ 1.44MB, k=10。 False Negative 一定为 0——如果 Bloom Filter 说不在,那一定不在。"
Q3: How many virtual nodes for Consistent Hash?
Model Answer:
"虚拟节点数量是 load balance 和 metadata overhead 的 trade-off:
- 太少(<50):节点少时负载不均衡,hash 环上大片区域归一个节点。
- 太多(>500):内存开销大,查询变慢(TreeMap 的 O(log N) 中 N 变大)。
- Sweet spot:100-200 个虚拟节点/物理节点。 例如 大型加密货币交易所 的 Redis Cluster 有 10 个节点,150 个虚拟节点,ring 上共 1500 个点,
TreeMap查询完全够用。 还可以给不同权重的节点配不同数量的虚拟节点,实现 weighted consistent hash。"
Q4: Token Bucket vs Sliding Window?
Model Answer:
"两者都是限流算法,但场景不同:
维度 Token Bucket Sliding Window 突发流量 允许 burst(桶里有 token 就能用) 严格平滑(按窗口平均) 内存开销 O(1) 两个变量 O(N) 记录每个请求时间 精度 高(懒加载计算) 取决于窗口粒度 适用场景 API rate limit,允许突发 严格计数,如短信发送次数 大型加密货币交易所 API 用 Token Bucket 因为交易场景需要允许合理 burst(如开盘瞬间的下单潮)。Sliding Window 用在严格计数场景,如每日提币次数限制。"
Q5: What's the difference between Timing Wheel and Priority Queue?
Model Answer:
"两者都能管理定时任务,但 Timing Wheel 在大规模任务下性能更好:
- PriorityQueue(Min-Heap):插入 O(log N),取最小 O(1),tick 时检查堆顶是否到期。适合任务数量少(<1万)。
- Timing Wheel:插入 O(1),tick 时只检查当前 slot。适合任务数量极大(百万级)。 因为 PriorityQueue 的
O(log N)在 N=100万时约等于 20 次比较,而 Timing Wheel 永远是 O(1)。Kafka 处理百万级 delayed fetch 请求就是用的 Timing Wheel。"
Q6: How to handle memory limit in LFU?
Model Answer:
"LFU 通常有两种内存控制方式:
- Count-based:限制 key 的数量(如最多 1 万个),实现简单。
- Size-based:限制总内存大小(如最多 100MB),每个 Node 记录
size(如 value 的 byte 长度),put 时检查total_size + new_size > capacity,超了就按 LFU 淘汰直到满足。 大型加密货币交易所 场景下,value 可能是 protobuf message 或大 JSON,size-based 更合理。实现时在Node里加int size,LFUCache里维护current_size,淘汰时循环调用 evict 直到current_size + new_size <= capacity。"
Q7: Can Bloom Filter support deletion?
Model Answer:
"标准 Bloom Filter 不支持删除,因为多个 key 可能共享同一个 bit,删除会误伤其他 key。 但有两种变体支持删除:
- Counting Bloom Filter:每个 bit 改成 counter(如 4-bit),add 时 counter++,delete 时 counter--。空间开销 ×4~8。
- Cuckoo Filter:用 cuckoo hash 存储指纹,支持删除且空间效率比 Counting Bloom Filter 更好。 大型加密货币交易所 制裁名单场景是只增不减(名单只会加人),标准 Bloom Filter 就够了。如果是动态黑白名单,可以用 Cuckoo Filter 或 Redis 的 RedisBloom 模块。"
Q8: How would you implement this in a distributed setting?
Model Answer:
"分布式场景下每种结构有不同的方案:
- LRU/LFU:单节点用 Caffeine,分布式用 Redis(但 Redis 的 LRU 是近似的)。更高可用用 Hazelcast / Ignite。
- Bloom Filter:可以每个节点持有一份相同的 Bloom Filter(只读),更新时广播或定时同步。或者用 RedisBloom 模块。
- Consistent Hash:配合 virtual node 做数据分片,如 Redis Cluster 的 16384 个 slot 就是一种 consistent hash。
- Token Bucket:分布式限流用 Redis + Lua 脚本实现原子
INCR和EXPIRE,或者用专门的限流服务(如 Sentinel)。大型加密货币交易所 可能用Redis Cell模块或自研的分布式 token bucket。- Timing Wheel:单节点用本地 wheel,分布式延迟任务用 Redis
ZSET(score=执行时间戳)或 Kafkadelayed operation。"
Q9: What's the time complexity of Consistent Hash with virtual nodes?
Model Answer:
"查找是 O(log V),V = 虚拟节点总数 = 物理节点数 × replicas。因为用 TreeMap/红黑树维护有序的 hash ring。 添加/删除节点是 O(replicas × log V),因为要对每个虚拟节点做 TreeMap 的插入/删除。 如果 replicas=150,物理节点=10,V=1500,log(1500)≈11,完全可以忽略。 优化:如果 hash 函数分布均匀,可以用跳表或数组+二分查找替代 TreeMap,查找降到 O(log V) 但常数更小。"
Q10: How does Timing Wheel handle tasks with very long delays (e.g., 1 day)?
Model Answer:
"单层时间轮最大只能表示
tick × slots的延迟,比如 tick=1ms, slots=1024,最大只能表示约 1 秒。 层级时间轮(Hierarchical Timing Wheel) 解决这个问题:
- Level 0:tick=1ms, 1024 slots -> 约 1s
- Level 1:tick=1s, 1024 slots -> 约 17min
- Level 2:tick=1min, 1024 slots -> 约 17h
- Level 3:tick=1h, 1024 slots -> 约 42d 插入时从高层到低层,找到能容纳该 delay 的最底层放入。tick 时低层转一圈 carry 到高层。 Kafka 的
TimingWheel就是三层结构,Netty 的HashedWheelTimer是单层但支持大 delay(通过 rounds 计数)。"
Last Updated: 2026-05-14 Target Position: 大型加密货币交易所 Senior Backend Developer - Risk Study Tip: 先背熟 LRU 和 Token Bucket 的手写代码(考频最高),然后 Bloom Filter 和 Consistent Hash(系统 design 必考),最后 LFU 和 Timing Wheel(高级/追问)。