Thursday, 14 October 2010

Tác động lớn của một byte

~~ Vừa có mạng, vừa có Automata :)) hay ít nhát là máy Turing. Đọc đê~~~
TCP là một trong những giao thức phổ dụng nhất của mạng máy tính. Mỗi lần ta click vào một trang web mới là có (ít nhất) một kết nối TCP được thiết lập từ trình duyệt đến máy chủ. Vì thế, hiệu suất hoạt động của TCP ảnh hưởng trực tiếp đến toàn bộ mấy tỉ người dùng Internet. Thiết kế một giao thức phổ dụng như TCP quả thật rất khó, vì thế Cerf và Kahn được giải thưởng Turing rất xứng đáng.
Dù có viễn kiến vĩ đại, Cerf và Kahn hiển nhiên không phải là những người duy nhất đóng góp vào TCP. Họ chỉ đặt một cái nền. Còn trong vòng 40 năm nay có biết bao nhiêu người đã đóng góp vào cải thiện nhiều mặt của TCP. Thật ra chỉ cần đến khoảng cuối những năm 80 là “diện mạo” của TCP đã rất khác so với hồi Cerf và Kahn thiết kết nó.
Xem qua quá trình tiến hóa của TCP, một điều hiển hiện là việc giữ cho một giao thức hoạt động đúng như ý mình muốn thật là nan giải. Có hai lý do chính, đều liên quan đến sự đa dạng. Thứ nhất là sự đa dạng của các loại mục tiêu khác nhau mà ta muốn giao thức đạt được: hiệu suất cao, tính bảo mật tốt, dùng ít tài nguyên mạng và tài nguyên tính toán, xử lý cực nhanh với tốc độ ánh sáng, giữ cho phiên bản mới của giao thức tương hợp với phiên bản cũ, vân vân. Thứ hai là sự đa dạng (và đa nguyên) của những nhóm nghiên cứu và các công ty đóng góp vào cải tiến về lý thuyết và lập trình giao thức trên thực tế. Làm thế nào để đảm bảo rằng TCP do Microsoft lập trình chạy tốt với TCP của Linux, của BSD, của SunOS, MacOSX, cùng với cơ man nào là các phiên bản khác nhau của chúng. Khó nữa là chúng ta không có một bộ khung lý thuyết nào khả thi để có thể xác minh xem một thiết kế giao thức cho trước là thiết kế “tốt”: các bộ phận hoạt động đồng bộ với nhau, các phiên bản hoạt động không ngáng giò nhau, vân vân.
Khó thế đấy. Vậy mà, khi ta click vào http://www.procul.org/blog ta thấy ngay cái blog này. Bất kể ta chạy máy gì, hệ điều hành gì. Nó cho thấy sự tráng kiện (robustness) của giao thức TCP và của các giao thức mạng nói chung.
Thế nhưng, có khi các bộ phận của TCP thật sự không hoạt động đồng bộ với nhau, thậm chí chỉ vì một byte dữ liệu. Khi điều này xảy ra, nếu không hiểu rõ TCP và các ngóc ngách của nó thì không thể hiểu tại sao lại có những hiện tượng “ma quái” như vậy. Câu chuyện sau đây chỉ là một vị dụ.


Chuyện như sau. Một nhóm kỹ sư muốn thử nghiệm hiệu suất hoạt động của một hệ thống Wifi. Họ viết một chương trình nhỏ để gửi dữ liệu giữa hai máy dùng hệ thống Wifi nọ. Chương trình thiết lập một kết nối TCP giữa hai máy, xong rồi bên gửi gửi đi 100KB, bên nhận gửi lại một gói ký nhận nhỏ, rồi bên gửi lại gửi đi 100KB kế tiếp, vân vân. Mục tiêu là thực hiện gửi nhận như vậy liên tục một thời gian xem tốc độ truyền là bào nhiêu.
Kết quả: hệ thống Wifi này trên Windows XP đạt được tốc độ 3.5Mbps, còn trên MacOSX chỉ đạt được 2.7Mbps. Trong ngữ cảnh của họ thì 3.5Mbps là tốt. 2.7Mbps không tốt.
Vậy Windows XP có bộ TCP tốt hơn MacOSX? (Giả sử thẻ mạng và các thứ khác tương tự nhau.)
Không. Sau vài lần nghịch với các tham số. Họ giảm 100KB xuống còn 99,912 bytes (để gửi một đợt trước khi nhận gói xác minh). Về nguyên tắc, thay vì 100KB một vòng, ta thử 99KB một vòng thì tốc độ không nên có thay đổi gì dáng kể. Thế mà tốc độ của MacOSX tự nhiên tăng lên đến 5.2Mbps: hơn Windows và gần gấp đôi tốt độ cũ. Thú vị hơn nữa, nếu thay 99,912 bytes bằng 99,913 bytes một đợt thì tốc độ của MacOSX lại giảm xuống 2.7Mbps như xưa.
1 byte mà có thể tăng tốc TCP của Mac gấp đôi? Chuyện gì xảy ra?
Số là, trong mấy trăm cái mẹo cải thiện hiệu suất được đưa vào TCP trong 40 năm qua, có 4 cái mẹo tương tác với nhau rất độc đáo tạo ra hiện tượng trên.
Để mô tả 4 cái mẹo này, trước hết chúng ta lược qua xem TCP làm việc thế nào. Đại khái, TCP là một giao thức cung cấp dịnh vụ tin cậy cho “khách hàng” là các ứng dụng (như web browser, server, Media player, và rất nhiều các ứng dụng mạng khác). Để tạo ra dịch vụ tin cậy, TCP gửi dữ liệu giữa hai đầu gửi-nhận và bắt bên nhận gửi lại các mẩu xác minh là đã nhận (acknowledgements, viết tắt là ACK). Các mẩu dữ liệu của TCP tiếng Anh gọi là segments. Các mẩu dữ liệu được nhét vào các “gói dữ liệu”, như là các phong bì mà bên trong chứa dữ liệu còn bên ngoài chứa thông tin điều khiển và địa chỉ gửi nhận. Bao bì tốn khoảng 20 bytes, cộng thêm 20 bytes bao bì của mạng nữa là khoảng 40 bytes cho mỗi gói dữ liệu.
Mẹo 1: kích thước từng mẩu dữ liệu. Một phong bì do TCP gửi không thể chứa nhiều dữ liệu quá. Tại vì các gói dữ liệu đi qua nhiều loại mạng khác nhau. Mỗi loại mạng có kích thước gói tối đa khác nhau. Ví dụ mang Ethernet có kích thước tối đa là 1500 bytes, mạng X25 có kích thước gói tối đa là 576 bytes, vân vân. Một trong các lý do mà các mạng giới hạn kích thước gói dữ liệu là vì nếu kích thước gói lớn quá thì mỗi lần đường truyền bị lỗi gì ta phải gửi lại toàn bộ gói. Gói càng lớn thì xác suất nó bị lỗi càng cao, mà gửi lại gói to thì tốn tài nguyên hơn gửi lại gói nhỏ. Thế cho nên, nếu TCP gửi một cái phong bì khổng lồ thì đến mạng có giới hạn kích thước phong bì nó sẽ bị băm nhỏ ra thành nhiều gói nhỏ. Mỗi gói nhỏ tốn một phong bì riêng. Và như thế thì rất tốn. Túm lại, TCP có một biến số gọi là MSS để lưu trữ kích thước mẩu lớn nhất (của một kết nối). Có các thuật toán để xác định MSS nên là bao nhiêu cho mỗi kết nối. Nếu không chạy thuật toán thì trị mặc định là 576 – 40 = 536, trong đó 576 là do X25, còn 40 là kích thước bao bì của TCP/IP như đã nói ở trên. Nếu chỉ truyền trên Ethernet thì MSS nên là 1500-40 = 1460.
Mẹo 2: thuật toán Nagle. Thử tưởng tượng một khách hàng của TCP cứ thích đưa mỗi lần vài bytes cho TCP để gửi qua bên nhận. Các ứng dụng như telnet, ssh, rlogin lấy inputs từ chúng ta. Chúng ta gõ bàn phím rất chậm (tính theo tốc độ máy). Người gõ nhanh nhất thế giới cũng chỉ gõ được khoảng 150 từ một phút, vị chi là khoảng vài chục đến vài trăm mili-giây một ký tự. Do đó, hoàn toàn có khả năng là ứng dụng sẽ “đưa cho” TCP từng ký tự một, cứ khoảng 100-mili giây một ký tự. Mỗi lần tải một mẩu dữ liệu 1 ký tự, TCP phải tốn ít nhất 40 bytes bao bì cho nội dung thư. Tỉ lệ phí hoài là 40/41, gần bằng tỉ lệ phí hoàn cho Vinashin. Rất tốn băng thông! Do đó, hồi 1984 John Nagle đề nghị là TCP nên tích lũy một ít “hàng họ” (nghĩa là, ký tự) trước khi gửi. Ít nhất, nếu có một phong bì gửi trước đó mà chưa có hồi âm thì khoan hẵng gửi phong bì ít hàng hiện tại. Chờ hồi âm của phong bì trước, xong rồi hẵng gửi phong bì mới. Lý do là, trong thời gian chờ hồi âm, nhỡ đâu chú khách hàng lại tuồn thêm cho vài ký tự để đóng chung vào một gói thì đỡ tốn phí vận chuyển. Còn trong trường hợp phong bì đã đầy (MSS) thì gửi luôn không cần chờ.
(Mấy bác chuyên môn đánh áo phông bàn chải bên Đông Âu hồi xưa chắc chắn đã hiểu rõ bài toán đóng hàng này.)
Mẹo 3: hồi âm muộn (Delayed ACK). Ở phía bên nhận, để tiết kiệm phí vận chuyển thì TCP thường cố gắng đóng gói cả hồi âm lẫn dữ liệu chiều ngược (gọi là piggy-backing) gửi chung vào một gói. Ví dụ như sau khi nhận một thư từ browser, web-server đọc lên một file nào đó (index.html chẳng hạn) và gửi lại cho browser. Nếu TCP đừng hồi âm ngay, chờ một xíu cho chú server đọc đĩa, thì có luôn cả index.html mang cùng với hồi âm về. Do đó, chuẩn TCP có cái mẹo hồi âm muộn, bắt bên nhận chờ khoảng 200ms đến 500ms trước khi hồi âm một mẩu dữ liệu từ bên kia. Nhưng nếu trong thời gian chờ mà nhận thêm được một thư nữa thì hồi âm cả hai ngay. (Nếu không, bên kia tưởng thư mất gửi lại mất công lắm.) Đây là luật hồi âm kép.
Mẹo 4: nhãn thời gian (timestamp option). Để đảm bảo độ tin cậy, TCP cần biết xem thư gửi đi đã nhận được chưa. Nếu thư bị mất, hoặc hồi âm bị mất thì không nhận được hồi âm. Do đó, TCP cần có một cái đồng hồ báo mất. Khi đồng hồ reng leng keng thì gửi thư lại. Nếu thời khoảng gửi lại quá bé thì không tốt: tại vì có thể hồi âm đang trên đường về, chưa chi đã gửi lại. Nếu thời khoảng gửi lại quá dài thì cũng không tốt: thư đã mất mà không gửi lại luôn còn chờ gì nữa? Do đó, TCP cần một cơ chế để ước lượng thời gian khứ hồi là bao nhiêu, xong rồi đặt thời khoảng cho đồng hồ gửi lại cỡ chừng thời gian khứ hồi cộng với một khoảng đệm cho chắc. (Thuận toán ước lượng thời khoảng khứ hồi phức tạp hơn một chút, nhưng đại khái là thế.) Làm thế nào để đo thời gian khứ hồi? Cách thứ nhất là gửi thư, rồi khi nhận được hồi âm thì đó là thời gian khứ hồi. Nhưng mà nếu thư bị mất, phải gửi lại, rồi nhận được hồi âm, thì mình không biết là hồi âm cho thư cũ hay thư mới. Ngoài ra, nếu bên nhận lại dùng mẹo hồi âm muộn thì ước lượng thời gian khứ hồi của mình bị sai đi. Còn nữa, TCP thường gửi nhiều thư cùng một lúc, và nếu dùng một đồng hồ cho mỗi thư thì rất phức tạp và tốn tài nguyên. Cách thứ hai là mỗi lần gửi thư đi thì dán tem chứa thời điểm hiện tại vào đó. Bên nhận, trước khi hồi âm, lấy tem của thư bỏ vào hồi âm. Khi nhận được hồi âm thì bên gửi chỉ cần lấy thời điểm hiện tại trừ đi giá trị tem là biết thời khoảng khứ hồi. Cách đo thời khoảng khứ hồi dùng nhãn thời gian này tốt hơn, nhưng như thế thì ta lại tốn thêm 12 bytes để làm nhãn và vì thế trên Ethernet thì MSS chỉ còn tối đa là 1500 – 52 = 1448 bytes thay vì 1460 bytes như trước.
Tương tác giữa 4 cái mẹo. Quay lại với câu chuyện thử hiệu xuất giữa Windows và MacOSX trên Ethernet. Khác biệt thứ nhất là Windows XP không dùng nhãn thời gian, cho nên MSS = 1460, còn MacOSX dùng nhãn thời gian cho nên MSS = 1448 (trong môi trường thử nghiệm). Do đó, 100000 bytes được
  • TCP của Windows XP băm ra thành 68 mẩu, mỗi mẩu 1460 bytes, cộng với một mẩu 720 bytes.
  • TCP của Mac OSX băm ra thành 69 mẩu, mỗi mẩu 1448 bytes, cộng với một mẩu 88 bytes.
Khi Windows XP truyền thì:
  • Bên gửi gửi đi 68 mẩu (đầy MSS nên gửi ngay), và giữ lại mẩu cuối (720 bytes) chờ hồi âm của mẩu 68.
  • Bên nhận dùng luật hồi âm kép nên sẽ hồi âm cho các mẩu 2, 4, …, 68 ngay lập tức, và cuối cùng khi bên gửi nhận được hồi âm của mẩu 68 sẽ gửi ngay mẩu lẻ cuối cùng.
Khi Mac OSX truyền thì:
  • Bên gửi gửi đi 69 mẩu (đầy MSS nên gửi ngay), và giữ lại mẩu cuối (88 bytes) chờ hồi âm mẩu 69.
  • Bên nhận theo luật hồi âm kép, nên sẽ hồi âm cho các mẩu 2, 4, …, 68 ngay lập tức, nhưng giữ lại không hồi âm mẩu 69 ngay (trừ phi có thêm hàng họ của khách hàng gửi kèm hồi âm mang về)
  • Nhưng hàng họ chỉ có sau 100KB, mà bây giờ bên nhân mới nhận được 100000-88 bytes thôi nên chưa có hàng.
  • Bên gửi thì dùng thuật toán Nagle, giữ lại 88 bytes chờ khi mẩu 69 có hồi âm.
  • Kết quả là hai bên phải chờ thêm từ 200ms đến 500ms nữa, tùy theo người lập trình TCP chọn giá trị hồi âm muộn là bao nhiêu.
  • Kết quả cuối cùng là cứ 100KB thì MacOSX bị chậm lại 200ms!
200ms là một thời khoảng rất lớn. Trên Gigabit Ethernet, với tốc độ 1Gbps thì trong 200ms ta truyền được 200Mb vị chi là 25MB

 From:
http://www.procul.org/blog/2010/10/13/1-byte/