2 luồng chậm hơn 1 luồng 11 lần: lock convoy, và vì sao cái đắt không phải khóa

Hình dung một cuộc chạy tiếp sức, nhưng mỗi vận động viên chỉ cầm gậy chạy đúng hai mét rồi trao cho người sau. Nghe thì nhanh — nhiều người cùng chạy mà. Nhưng có một trục trặc: mỗi lần trao gậy, người nhận đang lơ đãng đứng chờ, phải mất mấy giây mới bừng tỉnh chộp lấy gậy và chạy. Hai mét chạy tốn một phần nghìn giây; cú trao gậy tốn mấy giây. Tốc độ cả đội giờ không do ai chạy nhanh quyết định, mà do các cú trao gậy — và càng thêm người vào đội, càng thêm cú trao, càng chậm. Đó chính xác là lock convoy ("đoàn tàu khóa"): cái đắt không phải việc trong khóa, mà là bàn giao khóa.

Ta đã đo nhiều mặt của khóa: chi phí mutex, spinlock so mutex, tranh chấp làm scale âm. Giờ đến một hiện tượng có tên riêng và một hình ảnh rất đắt: lock convoy. Nó xảy ra khi nhiều luồng tranh một khóa cho một vùng tới hạn ngắn, và kết quả là chương trình song song của bạn không chỉ chậm hơn kỳ vọng, mà chậm hơn cả bản một luồng. Tôi đo, và con số phơi bày một sự thật phản trực giác: với vùng tới hạn tí xíu, thêm luồng làm tệ đi, và cái đắt không phải việc trong khóa — mà là bàn giao khóa.

Đoàn tàu hình thành thế nào

Hình dung nhiều luồng cùng cần một mutex, mỗi lần chỉ để làm một việc rất ngắn trong đó (tăng một biến đếm, đẩy một phần tử). Luồng A giữ khóa, làm việc tí xíu, nhả khóa. Ngay lúc nhả, nó đánh thức một luồng B đang ngủ chờ khóa. Nhưng đánh thức không tức thì — B phải được hệ điều hành lập lịch lại, một chuyển ngữ cảnh ~8,5 µs như ta đã đo (đúng người nhận gậy phải bừng tỉnh). Trong suốt 8,5 µs đó, khóa nằm trống — không ai làm gì cả. Rồi B thức dậy, làm việc tí xíu của nó (vài ns), nhả khóa, đánh thức C... và cứ thế.

Kết quả là một "đoàn tàu": các luồng nối đuôi nhau qua khóa, nhưng tốc độ của cả đoàn bị quyết định bởi chi phí đánh thức giữa mỗi toa, không phải bởi việc tí xíu trong khóa. Vùng tới hạn chỉ tốn vài ns, nhưng mỗi lần bàn giao khóa từ luồng này sang luồng khác tốn hàng µs. Cái đắt gấp cả nghìn lần cái rẻ. Tôi đo trong container gcc:13 (10 lõi), một mutex bảo vệ một phép cộng duy nhất — vùng tới hạn ngắn nhất có thể.

Đo (a): nhiều luồng chậm hơn một luồng

Cho NT luồng, mỗi luồng lặp: khóa, shared++, mở khóa. Đo throughput (triệu phép cộng/giây), kiểm tổng khớp (shared == NT × số vòng):

NT | throughput | so với 1 luồng
 1 | 236 M/s    | 1,00×
 2 |  22 M/s    | 0,09×   (!!)
 4 |  64 M/s    | 0,27×
 8 |  47 M/s    | 0,20×

Một luồng đạt 236 triệu/giây — khóa không tranh chấp rất rẻ (chỉ khóa-mở trong cache của chính nó). Nhưng thêm luồng thứ hai, throughput sụp xuống 22 triệu — chậm hơn một luồng 11 lần! Không phải chậm hơn kỳ vọng, mà chậm hơn bản tuần tự. Với 4 và 8 luồng, throughput hồi lên chút (0,27× và 0,20×) nhưng vẫn thảm — nhiều luồng luôn tệ hơn một luồng 4 tới 11 lần. (Trường hợp 2 luồng tệ nhất vì đó là ping-pong thuần: hai luồng đổi tay nhau liên tục, mỗi lần một lần đánh thức đầy đủ — hai người trao qua trao lại mãi.)

Đây là bản chất convoy: bạn thêm sức tính (nhiều luồng) nhưng chúng không thể chạy song song — chúng bị tuần tự hóa qua khóa, và tệ hơn, mỗi lần chuyển tay trả một chi phí đánh thức. Số lõi không giúp gì; cái nút cổ chai là bàn giao khóa.

Đo (b): gom lô, hồi phục 118 lần

Vậy thuốc là gì? Không phải thêm luồng (đã thấy phản tác dụng), không phải đổi loại khóa (spinlock chỉ đổi cách chờ, không giảm số lần bàn giao). Thuốc là giảm số lần bàn giao khóa — và cách trực tiếp nhất là gom lô: thay vì khóa cho mỗi phép cộng, khóa một lần cho một lô phép cộng (mỗi vận động viên cầm gậy chạy xa hơn). Đo ở 8 luồng, thay đổi kích thước lô:

batch =   1 :   47 triệu/giây   (convoy)
batch =  10 :  471 triệu/giây   -> hồi phục 10×
batch = 100 : 5491 triệu/giây   -> hồi phục 118×

Gom 100 phép cộng dưới một lần khóa đưa throughput từ 47 lên 5491 triệu/giây — hồi phục 118 lần, và vượt xa cả bản một luồng (236). Vì sao? Vì số lần bàn giao khóa giảm 100 lần: thay vì một triệu lần khóa-mở-đánh thức mỗi luồng, chỉ còn mười nghìn. Cái đắt (bàn giao) được chia cho cả lô. Đây đúng là bài học batching ở producer-consumer: giảm số lần đồng bộ gần như luôn thắng giảm chi phí mỗi lần. Đoàn tàu tan rã khi mỗi toa chở nhiều việc hơn.

(Môi trường đo: container gcc:13 trên host ARM AArch64, 10 lõi, một mutex bảo vệ một phép cộng, số lấy sau warmup. Con số tuyệt đối đổi theo máy; điều bền vững là hình dạng: vùng tới hạn ngắn + nhiều luồng cho throughput dưới cả một luồng, và gom lô hồi phục nhiều lần.)

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với hai niềm tin. Thứ nhất, ngây thơ: "thêm luồng thì xong nhanh hơn". Đo lật tan: với vùng tới hạn ngắn, thêm luồng làm chậm hơn cả một luồng (0,09–0,27×). Thứ hai, tinh vi hơn và là đo hớ thật của tôi: "khóa chỉ tốn đúng thời gian giữ khóa" — tức tôi nghĩ chi phí khóa nằm ở việc bên trong vùng tới hạn. Sai. Vùng tới hạn ở đây là một phép cộng (vài ns), nhưng throughput sụp về ~5 triệu/giây, tức ~200 ns mỗi thao tác — gấp hàng chục lần việc thật. Chi phí không nằm trong khóa; nó nằm ở bàn giao khóa giữa các luồng: mỗi lần chuyển tay là một lần đánh thức (~8,5 µs chia đều ra), và khóa nằm trống trong lúc chờ.

Hai niềm tin gặp nhau ở một bài học: trong một convoy, thứ chặn throughput không phải việc bạn làm trong khóa, mà số lần khóa được bàn giao giữa các luồng — và mỗi bàn giao tốn một lần đánh thức, không phải thời gian giữ khóa. Điều này đổi hẳn cách sửa. Nếu tin "cái đắt là giữ khóa", tôi sẽ tối ưu việc bên trong vùng tới hạn (vốn đã tí xíu, không giúp gì). Sự thật là phải giảm số lần bàn giao: gom lô, làm việc ngoài khóa rồi chỉ khóa để cập nhật kết quả cuối, chia khóa thành nhiều khóa nhỏ (mỗi luồng một mảnh), hay bỏ khóa dùng thao tác nguyên tử. Đúng tinh thần đo lường: chỉ đo mới cho biết nút thắt là tần suất bàn giao, không phải nội dung vùng tới hạn.

Về đến code hằng ngày

Điều đầu tiên: một khóa nóng bảo vệ việc tí xíu là dấu hiệu convoy — gom lô hoặc bỏ khóa. Nếu bạn thấy nhiều luồng cùng khóa liên tục cho một cập nhật nhỏ (một biến đếm, một con trỏ), và thêm luồng làm chậm đi, đó là đoàn tàu khóa. Cách chữa không phải thêm luồng hay đổi mutex thành spinlock, mà giảm tần suất khóa: gom nhiều cập nhật dưới một lần khóa, hoặc cho mỗi luồng một bản cục bộ rồi gộp cuối (như reduction).

Điều thứ hai: giữ vùng tới hạn hoặc rất hiếm, hoặc đủ lớn để bù chi phí bàn giao. Convoy tệ nhất khi vùng tới hạn ngắn mà thường xuyên — tỉ lệ chi phí bàn giao trên việc thật cao nhất. Hoặc làm việc thật ngoài khóa (chuẩn bị xong rồi mới khóa để ghi), hoặc gom để mỗi lần khóa làm nhiều.

Chỗ này cái mẫu "bỏ khóa nóng đi, đừng bàn giao mỗi thao tác" là một trong những bài tối ưu kinh điển nhất, và mỗi hệ sinh thái có lời giải đóng gói sẵn. Java gặp lock convoy đủ nhiều để đặt hẳn tên gọi đó, và câu trả lời chuẩn cho một bộ đếm nóng là LongAdder thay AtomicLong: nó chia biến đếm thành nhiều ô (một dạng striping), mỗi luồng cộng vào ô riêng, sum() mới gộp — đúng ý "cho mỗi luồng một bản cục bộ rồi gộp cuối", né sạch bàn giao; ConcurrentHashMap cũng chia khóa theo segment vì lý do y hệt. Ở tầng database, đây là bài toán hot row kinh điển: một dòng đếm mà mọi transaction cùng UPDATE trở thành khóa nóng tuần tự hóa cả hệ — cách chữa là gom cập nhật theo lô, hoặc sharded counter (nhiều dòng cộng lại), hoặc với sinh ID thì dùng sequence cache (Postgres/Oracle cấp một lô id cho mỗi phiên, thay vì khóa sequence mỗi lần chèn — chính là batching). Go thì sync.Mutex dưới tranh chấp cao cũng convoy y vậy; thành ngữ là sharded counter (mảng ô đệm theo dòng cache) hoặc gom qua channel. Mẫu số chung: khi một khóa được bàn giao hàng triệu lần cho việc tí xíu, đừng tối ưu việc — hãy cắt số lần bàn giao bằng gom lô hoặc chia nhỏ trạng thái.

Muốn tự soi thì nhìn một đoạn code đa luồng có khóa và hỏi: khóa này được lấy bao nhiêu lần mỗi giây, và mỗi lần làm gì? Nếu nó được lấy hàng triệu lần để làm một việc tí xíu (tăng đếm, thêm vào list), bạn có nguy cơ convoy — và dấu hiệu chẩn đoán rất rẻ: chạy nó với 1 luồng rồi với 8 luồng và bấm giờ. Nếu 8 luồng chậm hơn 1 luồng, đó chính là đoàn tàu khóa. Rồi thử gom lô: thay vì khóa cho mỗi thao tác, tích lũy cục bộ vài chục thao tác rồi khóa một lần để cập nhật — đo lại. Bạn rất có thể thấy throughput nhảy vọt nhiều lần. Vài phút đó dạy bạn nhận ra một trong những cái bẫy hiệu năng phổ biến nhất của code song song: không phải khóa chậm, mà bàn giao khóa quá thường xuyên — và thuốc luôn là làm cho mỗi lần giữ khóa đáng giá hơn.