Mời bạn thưởng thức Newsletter #135.

Git at any scale

Vicent Martí giải thích vì sao host Git tập trung ở quy mô lớn rất khó: packfile là file nhị phân lớn, phải nằm trên filesystem và bị đọc theo kiểu truy cập rải rác. Thời kỳ đầu, việc bỏ packfile để lưu object trong key-value store phân tán thì git clone quá chậm, vì mỗi bước duyệt đồ thị commit/tree tốn một round trip. Distributed filesystem như NFS, GFS hay DRBD thì chậm, nhiều lỗi và khó vận hành. Spokes của GitHub nhân bản ở tầng ứng dụng, chạy three-phase commit cho reference transaction, nhưng tốc độ push bị giới hạn bởi replica chậm nhất. Mỗi repo cố định ba bản sao là thừa với repo nhỏ, thiếu với monorepo nặng CI, lại cần routing database lớn.

Continuity của Cursor lấy write-ahead log (WAL) trên object storage tương thích S3 làm nguồn sự thật. Mỗi push được ghi vào WAL trước khi xác nhận, và chỉ hiển thị sau khi reference transaction thành công cùng với việc cập nhật WAL index, nhờ đó mọi push đều linearizable. Repo Git thường trên NVMe chỉ đóng vai trò cache, được dựng lại từ WAL khi thiếu, nên hệ thống stateless, không cần consensus. Node được chọn bằng rendezvous hashing, còn an toàn ghi dựa vào compare-and-swap của S3. Replica nhận thông báo qua UDP gossip rồi kiểm tra độ mới bằng conditional GET với ETag, thường dưới 10 ms. Chỉ primary chạy compaction, replica tải pack đã nén từ S3. Thử nghiệm trên monorepo của Cursor cho thấy read scale tuyến tính tới 100 replica, S3 Standard đạt khoảng 120 push/s, S3 Express One Zone vượt 300 push/s. Đây là nền móng cho Origin, nền tảng Git hosting cho workload của agent.

Regressive JPEGs

Maurycy khám phá một mẹo vui với progressive JPEG, định dạng cho phép lưu các thành phần tần số thấp trước để ảnh tải dở vẫn hiện ở độ phân giải thấp thay vì bị cắt ngang. Trong file, dữ liệu nén được chia thành nhiều “scan”, mỗi scan có header riêng cho biết kênh màu nào (Y, Cb, Cr), khoảng DCT bin nào và độ chính xác bao nhiêu. Scan đầu thường chứa bin DC của cả ba kênh, các scan sau bổ sung dần chi tiết. Vì mỗi scan tự khai báo phạm vi phổ của nó, tác giả nhận ra có thể tạo file JPEG mà scan sau ghi đè lên dữ liệu đã render. Chỉ cần nối nhiều ảnh cùng độ phân giải và bỏ các marker start-of-image, start-of-frame, end-of-image. Khi tải qua mạng chậm, file này sẽ chuyển qua lại giữa nhiều ảnh.

Vấn đề là đa số decoder bỏ cuộc sau một số scan nhất định (có lẽ để tránh kiểu zip bomb), nên chỉ được khoảng chín frame. Để làm animation thật, cần giảm số scan mỗi frame. Progressive mode không cho phép một scan chứa cả dữ liệu AC lẫn DC, nên frame nhỏ nhất là một scan chỉ có DC, cho ảnh độ phân giải thấp hơn nhiều so với gốc. Với cách này, Chrome render được khoảng 90 frame trước khi dừng, Firefox còn kiên nhẫn hơn, và hiện tượng bóng mờ cũng biến mất vì không còn scan AC tinh chỉnh dữ liệu cũ. Kết quả là cả một video nằm trong một file ảnh. Ngoài việc rickroll hay troll, mẹo này không có ứng dụng thực tế, vì không thể thêm thông tin thời gian và tốc độ phát phụ thuộc hoàn toàn vào độ trễ mạng.

A quick look at zero-knowledge proofs

Max Bernstein và Chris Gregory tìm hiểu zero-knowledge proof (ZKP) qua một ví dụ không dính dáng gì tới tiền mã hóa: bài toán tô ba màu cho đồ thị theo paper của Goldreich, Micali, Wigderson. Trong ZKP có hai bên, prover tuyên bố biết lời giải của một bài toán khó, còn verifier cần bị thuyết phục mà không được biết lời giải đó. Tô ba màu là gán màu cho mỗi node sao cho hai node kề nhau không trùng màu, tìm thì chậm nhưng kiểm tra rất nhanh. Mỗi vòng của giao thức gồm bốn bước: prover hoán vị ngẫu nhiên ba màu rồi “khóa” màu từng node vào hộp và gửi các hộp đi; verifier chọn ngẫu nhiên một cạnh; prover gửi chìa khóa của hai hộp ở hai đầu cạnh; verifier mở hộp, kiểm tra màu hợp lệ và khác nhau.

Trong code, “hộp khóa” là hash của màu kèm một nonce ngẫu nhiên, vì nếu chỉ hash màu thì các node cùng màu sẽ có hash giống nhau và lộ cấu trúc lời giải. Thực tế nên dùng hashlib.sha256 và secrets thay cho hash và random. Một vòng chỉ bắt được prover gian lận với xác suất khoảng 1/m, với m là số cạnh, nên giao thức lặp m² vòng. Với đồ thị 1.000 cạnh, khoảng 4.600 vòng đưa xác suất gian lận lọt lưới xuống chừng 1%, còn 10.000 vòng chỉ còn 0,0045%. Nhóm tác giả còn dựng demo client-server. Cách làm tương tự áp dụng được cho Sudoku, và về lý thuyết cho mọi bài toán NP-complete nhờ phép quy dẫn, dù đồ thị có thể phình to rất nhanh, chẳng hạn bài toán phân tích thừa số một số có hai chữ số đã cần hàng nghìn node.

The Pulse: We need to talk about migrations with AI

Số The Pulse miễn phí này của The Pragmatic Engineer cho rằng công cụ AI coding đã biến những cuộc migration lớn, từng bị gác lại vì quá tốn kém, thành việc khả thi. Ví dụ nổi bật là Asana: theo case study của OpenAI, Codex giúp gỡ bỏ Enzyme, chuyển sang React Testing Library trong khoảng 1,5 tuần công kỹ sư, chi phí model và hạ tầng chừng 12 nghìn USD, trong khi kế hoạch trước đó ước tính 6 triệu USD và năm năm. Airbnb chuyển 3.500 file test Enzyme trong sáu tuần, so với ước tính thủ công 1,5 năm công. Uber chuyển 600 nghìn unit test từ JUnit 4 sang JUnit 5 trong bốn tháng với hai kỹ sư. Bun chuyển 530 nghìn dòng từ Zig sang Rust trong hai tuần, tốn 165 nghìn USD tiền API. Để so sánh, năm 2021 Sentry mất 1,5 năm với khoảng mười kỹ sư để chuyển 95 nghìn dòng JavaScript sang TypeScript.

Các kỹ thuật lặp lại ở nhiều nơi gồm vòng retry tự động cho file thất bại, pipeline nhiều phase cho từng file, vòng kiểm chứng do kỹ sư thiết kế, ưu tiên file dễ hoặc thay đổi thường xuyên trước, và chuẩn bị codebase trước khi chạy LLM. Tuy vậy, con số 6 triệu USD có lẽ bị thổi phồng, vì ước tính thủ công bỏ qua việc tốc độ làm từng file tăng dần theo kinh nghiệm. Mọi ví dụ đều cần kỹ sư lập kế hoạch, thiết kế kiểm chứng và theo sát. Kết luận là bài toán chi phí và lợi ích của migration đã thay đổi, các team nên xem lại những dự án từng né tránh.

The Accidental Application Runtime

Michael F. Bryan kể về một service Go quản lý trang trại máy in 3D nhỏ. Ban đầu nó chỉ là dashboard: HTTP server khởi động một goroutine để poll máy in. Dần dần, việc nhận job từ backend, lưu job vào SQLite, lập lịch, chạy G-code và báo trạng thái ngược lên đều được thêm vào cùng đoạn setup đó, cho tới khi NewServer khởi chạy năm goroutine chạy dài hạn. Khi cần graceful shutdown lúc nhận SIGTERM, muốn biết goroutine nào đang chạy, dừng theo thứ tự nào, ai đóng channel thì phải đọc hết đoạn setup. Tác giả gọi đây là “accidental application runtime”: ứng dụng có kiến trúc thật gồm các thành phần đồng thời và luồng dữ liệu rõ ràng, nhưng không thứ gì trong code thể hiện nó.

Lấy cảm hứng từ autopilot drone PX4, tác giả viết thư viện backplane. Mỗi module là một hàm Go thường func(ctx, deps...) error, trong đó tham số chan<- T nghĩa là publish topic kiểu T, <-chan T là subscribe, *backplane.Latest[T] là theo dõi giá trị mới nhất. Topic định danh bằng kiểu Go, không dùng chuỗi. New kiểm tra wiring trước khi chạy, Run giám sát các module theo kiểu errgroup. Delivery diễn ra trong process, có backpressure, không durable. Service được dựng lại thành sáu module, với quy tắc then chốt commit-then-notify: scheduler ghi nhận job vào SQLite trước khi publish, để message chỉ đánh thức module chứ không phải nguồn sự thật. Sơ đồ Mermaid được sinh từ chính các khai báo này. Bài học rút ra là tách stream sự kiện khỏi lời gọi request/response, cẩn thận deadlock khi đồ thị có chu trình, và thư viện như vậy chỉ đáng dùng khi cùng một cơ chế lặp lại khắp ứng dụng.

Generic Methods in Go 1.27

Khi Go 1.18 ra mắt generics năm 2022, type parameter chỉ áp dụng cho function và struct, còn method thì không. Go 1.27 gỡ bỏ giới hạn này: method giờ có thể khai báo type parameter của riêng nó mà không cần thêm vào struct nhận. Bài viết minh họa bằng một node của đồ thị chứa giá trị generic Node[T]. Muốn thêm method Map biến node kiểu T thành node kiểu U, trước đây phải nhét U vào chính struct thành Node[T, U]. Đây là thiết kế tệ, vì U chỉ liên quan tới Map, vậy mà mọi method khác vẫn phải mang nó trong khai báo receiver. Cách né duy nhất là viết Map thành function cấp package, khá rườm rà. Từ Go 1.27, có thể viết func (n *Node[T]) Map[U any]() Node[U], để U chỉ thuộc về Map.

Lý do tính năng này mất nhiều năm nằm ở cách Go hiện thực generics. Compiler chủ yếu dùng monomorphization, tức tạo một bản sao của struct hay function generic cho mỗi kiểu cụ thể được dùng. Trong khi đó, hệ thống interface của Go hoạt động ở runtime qua dynamic dispatch. Hai mô hình này xung đột: nếu interface Mapper khai báo Map[U any]() Node[U], compiler phải xác định được một kiểu có implement interface hay không, nhưng với mỗi T có thể có vô số cách khởi tạo U. Reflection còn có thể gọi method ở runtime mà compiler không nhìn thấy khi quyết định cần sinh những bản khởi tạo nào. Cuối cùng, Go team chọn không cho phép generic method trong interface: kiểu cụ thể có thể có generic method, interface thì không, và generic method cũng không thỏa mãn một method interface tương ứng.

Your executable is a SQLite database

Farid Zakaria, tác giả sqlelf, đi xa hơn một bước: thay hẳn ELF bằng SQLite làm định dạng file thực thi. Prototype tên SELF (Structured Executable & Linkable Format) là một file SQLite thật sự, có thể chmod +x rồi chạy. Lập luận cốt lõi là ELF vốn đã là một database “không chịu thừa nhận”: string table, hash section, section header, symbol versioning đều tự hiện thực lại string interning, index, foreign key và record. Schema của SELF gồm bảng self_meta chứa ELF header, bảng segments lưu mỗi program header một dòng với dữ liệu dạng BLOB, và bảng symbols có index B-tree thay cho .dynstr, .gnu.hash. Một đăng ký binfmt_misc giúp kernel chuyển file cho self-exec, một trình nạp C nhỏ map segment, relocate rồi nhảy tới entry point.

Dynamic linking có hai cách: giữ ld.so của glibc và dùng rtld-audit để một câu SQL quyết định thư viện nào được nạp, hoặc dùng self-ld, linker thử nghiệm làm mọi việc qua SQL. Lệnh self closure đóng gói binary cùng toàn bộ dependency vào một database, khiến ldd chỉ còn là một phép JOIN. Áp dụng cho 723 chương trình trên một máy cho ra một database 611,9 MiB, nhỏ hơn 644,4 MiB của ELF nhờ khử trùng lặp thư viện và symbol, dù riêng từng file SELF lớn hơn 2,2 tới 3,6 lần. Lợi ích gồm query binary bằng SQL, strip hay patch như một transaction, và LD_PRELOAD nguyên tử trên toàn hệ thống. Hạn chế là segment phải copy ra thay vì mmap nên các process không chia sẻ trang text, khởi động chậm hơn với chương trình có nhiều object, và chưa có compiler hay linker sinh SELF trực tiếp.

What happens when a GPU reads memory

Fergus Finn, founder của Doubleword, lần theo một lệnh load toàn cục duy nhất (LDG.E) xuyên qua phần cứng RTX 4090. Vì NVIDIA công bố rất ít về con đường này, phần lớn chi tiết đến từ thí nghiệm đo thời gian và hardware counter. Bộ coalescer gộp 32 request bốn byte của một warp thành bốn sector 32 byte, đúng một cache line 128 byte. Request trượt L1, rồi qua TLB 16 entry mỗi SM để dịch địa chỉ trên trang 2 MiB, vì L2 được index theo địa chỉ vật lý. Crossbar đưa request tới một trong 36 slice L2, được chọn bằng một hàm phức tạp mà tác giả phải dò ra. Tiếp đó là 12 memory controller, mỗi cái điều khiển một chip GDDR6X: controller mở một row 1 KiB bằng lệnh activate tốn kém, rồi đọc bốn sector với chi phí rẻ.

Các con số đáng chú ý: L1 hit khoảng 15,4 ns, L2 hit khoảng 127 ns, còn một lần trượt mọi tầng xuống DRAM mất khoảng 255 ns, tương đương 660 chu kỳ mà warp phải đứng chờ. Activate một row tốn gấp khoảng 15 lần một lần đọc trong row đang mở. Load dồn vào một slice L2 chỉ đạt 1.957 triệu load/s, còn trải đều 36 slice đạt khoảng 68 nghìn triệu, gấp 34,8 lần. GPU che giấu độ trễ bằng song song khổng lồ: trong khi một warp chờ, phần còn lại của chip vẫn tiếp tục phát lệnh load. Vì thế hiệu năng phụ thuộc vào mẫu truy cập, cần coalesced và trải đều địa chỉ qua slice và row. Tác giả lưu ý các hàm ánh xạ L1, L2 tìm được chỉ là mô hình hợp lý, chưa phải đặc tả chính thức.

A faster way to calculate the day-of-the-week

Ben Joffe giải bài toán nghe có vẻ tầm thường: đổi số ngày tính từ Unix epoch (một số nguyên 32-bit có dấu, 1970-01-01 là thứ Năm) thành thứ trong tuần, sao cho vừa nhanh vừa đúng trên toàn bộ miền giá trị. Thuật toán của Neri (2024) được chọn làm mốc so sánh, nhưng cần thêm bước hiệu chỉnh vì 7 là ước số “khó chịu”. Ý tưởng chính của tác giả là tận dụng việc 7 = 2³ − 1, một số Mersenne, nên N mod 7 bằng floor(N·8/7) mod 8. Phép nhân 8/7 được xấp xỉ bằng một phép nhân với hằng số magic rồi dịch phải, còn mod 8 có sẵn nhờ chỉ giữ ba bit cao. Phiên bản giới hạn chỉ cần (u32(rd) * M + Z) >> 29, đúng trong khoảng ±242 nghìn năm, giúp thư viện Rust jiff nhanh hơn khoảng 40% ở một số hàm.

Để phủ toàn bộ miền 32-bit, tác giả đưa ra nhiều biến thể: nhân 64-bit (được WebKit dùng), thêm số hạng hiệu chỉnh bằng phép dịch có thể tính song song với phép nhân, dùng hai phép nhân để tăng throughput, hoặc chỉ ba lệnh x86 nhờ LEA. Định dạng ISO chỉ cần đổi hằng số. Kỹ thuật còn tổng quát hóa cho các ước số dạng 2^N − 2^K, như x % 24 hay x % 60 khi tính giờ, phút. Benchmark trên Apple M4 Pro cho thấy các biến thể mới chỉ tốn khoảng 0,17 tới 0,39 lần thời gian của Neri, trên Ryzen 9 9950X3D là 0,27 tới 0,59 lần. Kỹ thuật đã có mặt trong WebKit, Elixir, Jiff và thư viện Zig Zeit.

Dark mode toggles: two states are enough

Lea Verou lập luận rằng nút chuyển dark mode trên header website chỉ nên có hai trạng thái hiển thị, dù mô hình dữ liệu bên dưới có ba: System, Light và Dark. Theo bà, trạng thái thứ ba giải quyết một mục tiêu “tưởng tượng”. Người dùng tìm tới nút chuyển theme khi trang khó đọc, chứ không phải để ghim trước một theme vốn đã ổn. Đây là UI thiết kế theo data model thay vì mục tiêu người dùng. Toggle ba trạng thái rất phổ biến, từ Tailwind tới Docusaurus, nhưng chúng thêm rối mắt, thêm thao tác và tăng tải nhận thức. Ngược lại, một toggle hai trạng thái làm kém còn tệ hơn, vì có thể khóa người dùng vào lựa chọn ghi đè mà không có đường quay về System. Tác giả cũng thừa nhận chỉ dùng system preference mà không có toggle là lựa chọn hoàn toàn hợp lệ.

Thiết kế được đề xuất là một toggle duy nhất nhưng biểu diễn đủ ba trạng thái. Ở chế độ mặc định, nút hiển thị theme đang áp dụng và không lưu gì. Lần bấm đầu chuyển sang theme ngược lại và lưu giá trị đó vào localStorage. Lần bấm thứ hai quay về System và xóa giá trị đã lưu, tránh biến thay đổi tạm thời thành ghim vĩnh viễn. Override chỉ được xét lại khi người dùng tương tác, nên người dùng có OS tự đổi theme theo giờ vẫn ghim được theme mong muốn. Control ba trạng thái vẫn hợp lý trong trang settings hoặc với site có bảng màu khác nhau tùy theme OS. Bài học chung vượt ra ngoài dark mode: không phải trạng thái nào của state machine cũng cần UI hiển thị.