Khi băm 1.000 ID khác nhau vào bảng embedding 256 ô, mô phỏng dưới đây có 980 ID phải dùng chung vector với ít nhất một ID khác. Với bảng ánh xạ giữ đầy đủ khóa ID, mỗi ID có vector riêng. Đánh đổi nằm ở số vector cần lưu và cách quản lý ID xuất hiện ít hoặc đã ngừng hoạt động. Ta có thể quan sát trực tiếp cả việc cập nhật chung vector lẫn việc tạo lại embedding sau khi hết hạn bằng một chương trình Python nhỏ.
Collisionless embedding giữ riêng thông tin của ID
Bài báo Monolith dùng bảng key–value dựa trên Cuckoo Hashmap để lưu embedding riêng theo ID. Bài báo còn mô tả lọc ID theo tần suất, lọc xác suất và hết hạn sau thời gian ID ngừng hoạt động. Ngưỡng tần suất được điều chỉnh theo mô hình, còn thời hạn hết hoạt động được điều chỉnh theo embedding table. Bài báo Monolith, bản v2, mục 2.1
Trong mô phỏng này, bảng cố định chọn vector bằng bucket = digest(ID) % B. Mọi ID rơi vào cùng ô đều truy cập đúng một vector. Cách thứ hai dùng dict với nguyên chuỗi ID làm khóa và cấp một vector riêng cho mỗi ID. Dictionary của Python cũng dùng hashing để tìm khóa, đồng thời so sánh khóa để giữ các mục khác nhau. Tính chất cần quan sát là các ID khác nhau vẫn truy cập các giá trị riêng. Quy tắc khóa và hashing trong Python
Mã Python dưới đây mô phỏng việc ánh xạ ID và vòng đời trạng thái embedding. Với hệ thống gợi ý đầy đủ, còn cần các bước huấn luyện, phân phối tham số và đồng bộ sang serving. Có thể đọc phần kiến trúc đó trong bài tổng quan Monolith đã có trên blog. Kiến trúc gợi ý thời gian thực của Monolith
Đếm va chạm bằng cùng một bộ ID
Lần chạy dùng Python 3.9.6 trên macOS arm64 và thư viện chuẩn. Chạy đối chiếu với Python 3.10.11 cho cùng số đếm và trạng thái vector. random.Random(20261113) chọn 1.000 số khác nhau từ range(1_000_000), sau đó thêm tiền tố item: để tạo ID. Hàm băm là hashlib.blake2b(..., digest_size=8), chuyển 8 byte thành số nguyên theo thứ tự byte big rồi lấy phần dư theo kích thước bảng. Với chuỗi đầu vào và cấu hình này, digest được xác định bởi BLAKE2b. Tài liệu BLAKE2 trong Python
Mã kiểm tra cả 1.000 digest 64 bit đều khác nhau trong bộ dữ liệu này. Các lần dùng chung ô được đếm ở bước lấy phần dư theo B. Ta phân biệt ba cách đếm.
- ID vượt số ô đã dùng bằng số ID trừ số ô có dữ liệu. Nếu một ô chứa ba ID, ô đó đóng góp hai vào số này.
- ID trong ô dùng chung đếm tất cả ID nằm trong ô có từ hai ID trở lên. Ô chứa ba ID đóng góp ba.
- Cặp ID cùng ô đếm từng cặp ID khác nhau. Ô chứa ba ID đóng góp ba cặp.
Gọi $c_b$ là số ID ở ô $b$, tổng số cặp cùng ô là
$$ C=\sum_{b=1}^{B}\frac{c_b(c_b-1)}{2} $$Nếu coi mỗi ID được ánh xạ độc lập và đều vào $B$ ô, mỗi cặp có xác suất $1/B$ dùng chung ô. Với $n$ ID, số cặp kỳ vọng theo giả thiết đó là
$$ \mathbb{E}[C]=\frac{n(n-1)}{2B} $$Cột cuối của bảng là giá trị tính từ giả thiết phân bố đều. Cột số cặp đo được đến từ một bộ ID và một hàm băm đã cố định.
| Số ô B | Ô đã dùng | ID vượt số ô đã dùng | ID trong ô dùng chung | Cặp ID cùng ô | Cặp kỳ vọng |
|---|---|---|---|---|---|
| 256 | 251 | 749 | 980 | 1.966 | 1.951,172 |
| 1.024 | 643 | 357 | 610 | 495 | 487,793 |
| 4.096 | 889 | 111 | 208 | 127 | 121,948 |
Nếu triển khai bảng cố định bằng mảng dense cấp trước B vector hai chiều, phần giá trị cần 2B vị trí. Dictionary trong mô phỏng giữ 1.000 vector hai chiều, tương đương 2.000 vị trí chứa giá trị vô hướng. Với B=256, dictionary giữ nhiều vector hơn. Với B=4096, thiết kế mảng dense cần dự trù 4.096 vector nhưng vẫn có 208 ID nằm trong ô dùng chung. Đây là so sánh dung lượng giá trị theo thiết kế. Dung lượng RAM thực tế còn bao gồm khóa, cấu trúc dictionary và các đối tượng Python.
Hai ID cập nhật cùng vector như thế nào?
Trong bộ dữ liệu này, item:115040 và item:41657 cùng vào ô 0 khi B=256. Mã cộng 1 vào tọa độ đầu của ID thứ nhất, rồi cộng 2 vào tọa độ thứ hai của ID thứ hai. Kết quả đọc lại là
| Cách ánh xạ | item:115040 |
item:41657 |
|---|---|---|
| Bảng băm 256 ô | [1.0, 2.0] |
[1.0, 2.0] |
| Dictionary giữ khóa ID | [1.0, 0.0] |
[0.0, 2.0] |
Với bảng cố định, cập nhật qua một ID làm thay đổi giá trị đọc được qua ID còn lại vì cả hai cùng truy cập một vector. Với dictionary, hai cập nhật nằm ở hai vector riêng. Các phép cộng được đặt sẵn để theo dõi thay đổi trạng thái. Muốn đo ảnh hưởng tới chất lượng gợi ý, cần huấn luyện và đánh giá mô hình trên dữ liệu có nhãn.
Thử lọc tần suất và hết hạn
Phần tiếp theo chọn ngưỡng nhận ID là 3 lần xuất hiện và thời hạn không hoạt động là 5 đơn vị thời gian giả lập. Đây là các giá trị do ví dụ đặt ra. Mô phỏng dùng những quy tắc cụ thể sau.
- Trước mỗi sự kiện, xóa embedding có
time - last_seen >= 5. - Tăng bộ đếm xuất hiện của ID. Nếu ID có từ ba lần xuất hiện và chưa có embedding, cấp một vector
[0.0, 0.0]. - Nếu ID đang có embedding, cộng 1 vào tọa độ đầu và cập nhật
last_seen. - Giữ bộ đếm tần suất suốt dòng sự kiện, kể cả sau khi xóa embedding. ID quay lại có thể được nhận ngay và bắt đầu bằng một vector mới.
| Thời điểm | Sự kiện | Thay đổi quan sát được |
|---|---|---|
| 0 | rare |
Lần đầu, chờ đủ ngưỡng |
| 1, 2 | hot |
Hai lần đầu, chờ đủ ngưỡng |
| 3 | hot |
Được nhận, giá trị thành [1.0, 0.0] |
| 4, 5 | warm |
Hai lần đầu, chờ đủ ngưỡng |
| 6 | warm |
Được nhận, có hai embedding đang hoạt động |
| 7 | hot |
Giá trị thành [2.0, 0.0], cập nhật thời điểm hoạt động |
| 11 | Kiểm tra hết hạn | Xóa warm vì đã ngừng hoạt động 5 đơn vị |
| 12 | hot |
Xóa embedding cũ của hot trước khi xử lý sự kiện, rồi tạo lại và cập nhật thành [1.0, 0.0] |
Kết thúc dòng sự kiện có ba lần cấp embedding, hai lần hết hạn và nhiều nhất hai embedding hoạt động cùng lúc. Bộ đếm vẫn giữ ba ID rare, hot và warm. Quy tắc giữ bộ đếm sau khi hết hạn giúp thấy rõ khác biệt giữa tuổi của embedding và lịch sử xuất hiện. Khi quản lý bộ nhớ của hệ thống thực, cần tính cả nơi lưu bộ đếm và chính sách dọn dữ liệu đó.
Mã chạy lại
Lưu đoạn mã thành experiment.py rồi chạy python3 experiment.py. Chương trình in phiên bản Python, seed, toàn bộ số đếm và diễn biến vòng đời. Các assert kiểm tra ID khác nhau, vector riêng và trạng thái cuối của ví dụ.
1import hashlib
2import platform
3import random
4from collections import Counter, defaultdict
5
6SEED = 20261113
7ID_COUNT = 1000
8DIMENSION = 2
9THRESHOLD = 3
10TTL = 5
11
12
13def bucket_index(feature_id, size):
14 digest = hashlib.blake2b(feature_id.encode("utf-8"), digest_size=8).digest()
15 return int.from_bytes(digest, "big") % size
16
17
18def group_ids(feature_ids, size):
19 groups = defaultdict(list)
20 for feature_id in feature_ids:
21 groups[bucket_index(feature_id, size)].append(feature_id)
22 return groups
23
24
25def simulate_lifecycle():
26 events = [
27 (0, "rare"), (1, "hot"), (2, "hot"), (3, "hot"),
28 (4, "warm"), (5, "warm"), (6, "warm"), (7, "hot"),
29 (11, None), (12, "hot"),
30 ]
31 counts = Counter()
32 embeddings = {}
33 last_seen = {}
34 admissions = expirations = peak_active = 0
35 print(f"Lifecycle: threshold={THRESHOLD}, idle_ttl={TTL}; counters retained after expiry")
36 print("time | event | status | expired | active values")
37 for time, feature_id in events:
38 expired = sorted(key for key, seen in last_seen.items() if time - seen >= TTL)
39 for key in expired:
40 del embeddings[key]
41 del last_seen[key]
42 expirations += len(expired)
43 status = "tick"
44 if feature_id is not None:
45 counts[feature_id] += 1
46 if feature_id in embeddings:
47 status = "update"
48 elif counts[feature_id] >= THRESHOLD:
49 embeddings[feature_id] = [0.0] * DIMENSION
50 admissions += 1
51 status = "admit"
52 else:
53 status = "filtered"
54 if feature_id in embeddings:
55 embeddings[feature_id][0] += 1.0
56 last_seen[feature_id] = time
57 peak_active = max(peak_active, len(embeddings))
58 active = {key: embeddings[key] for key in sorted(embeddings)}
59 print(f"{time} | {feature_id or '-'} | {status} | {expired} | {active}")
60 assert admissions == 3 and expirations == 2 and peak_active == 2
61 assert embeddings == {"hot": [1.0, 0.0]}
62 assert dict(counts) == {"rare": 1, "hot": 5, "warm": 3}
63 print(f"Final: admissions={admissions}, expirations={expirations}, "
64 f"peak_active={peak_active}, counter_ids={len(counts)}")
65
66
67def main():
68 print(f"Python {platform.python_version()} | {platform.system()} {platform.machine()} | stdlib only")
69 print(f"seed={SEED}, IDs={ID_COUNT}, dimension={DIMENSION}, BLAKE2b digest_size=8")
70 rng = random.Random(SEED)
71 feature_ids = [f"item:{value}" for value in rng.sample(range(1_000_000), ID_COUNT)]
72 digests = {hashlib.blake2b(key.encode("utf-8"), digest_size=8).digest() for key in feature_ids}
73 assert len(digests) == ID_COUNT
74 keyed = {feature_id: [0.0] * DIMENSION for feature_id in feature_ids}
75 assert len(keyed) == ID_COUNT
76 assert len({id(value) for value in keyed.values()}) == ID_COUNT
77 print("buckets | occupied | extra_IDs | IDs_in_shared_buckets | colliding_pairs | expected_pairs")
78 for size in (256, 1024, 4096):
79 groups = group_ids(feature_ids, size)
80 extra_ids = ID_COUNT - len(groups)
81 aliased_ids = sum(len(group) for group in groups.values() if len(group) > 1)
82 pairs = sum(len(group) * (len(group) - 1) // 2 for group in groups.values())
83 expected = ID_COUNT * (ID_COUNT - 1) / (2 * size)
84 assert sum(map(len, groups.values())) == ID_COUNT
85 print(f"{size} | {len(groups)} | {extra_ids} | {aliased_ids} | {pairs} | {expected:.3f}")
86 print(f"ID-keyed dictionary: {len(keyed)} vectors, {len(keyed) * DIMENSION} scalar slots")
87
88 size = 256
89 groups = group_ids(feature_ids, size)
90 shared_bucket = min(index for index, group in groups.items() if len(group) > 1)
91 first, second = sorted(groups[shared_bucket])[:2]
92 dense = [[0.0] * DIMENSION for _ in range(size)]
93 dense[bucket_index(first, size)][0] += 1.0
94 dense[bucket_index(second, size)][1] += 2.0
95 keyed[first][0] += 1.0
96 keyed[second][1] += 2.0
97 assert dense[bucket_index(first, size)] is dense[bucket_index(second, size)]
98 assert keyed[first] == [1.0, 0.0] and keyed[second] == [0.0, 2.0]
99 print(f"Shared bucket {shared_bucket}: {first}, {second}")
100 print(f"Fixed table lookups: {dense[shared_bucket]}, {dense[shared_bucket]}")
101 print(f"Keyed lookups: {keyed[first]}, {keyed[second]}")
102 simulate_lifecycle()
103
104
105if __name__ == "__main__":
106 main()
Trong ứng dụng có nhiều loại đặc trưng, khóa cần chứa đủ thông tin để phân biệt chúng. Chẳng hạn user:42 và item:42 biểu diễn hai ID khác nhau. Khi thử bảng băm, giữ cùng một bộ ID, ghi rõ số ô và chọn cách đếm trước khi diễn giải tỷ lệ va chạm. Các hàm băm và ví dụ trong thư viện chuẩn được giới thiệu thêm trong bài Python trên blog. Các hàm hash có sẵn trong Python
Bình luận