Máy chủ Minecraft được tạo từ đầu bằng Bash (2022)

 (sdomi.pl)
4 điểm bởi GN⁺ 2024-03-04 | 1 bình luận | Chia sẻ qua WhatsApp
  • Witchcraft là một dự án thử nghiệm triển khai máy chủ Minecraft từ đầu chỉ bằng Bash; dự án xử lý cả giao thức nhị phân, Join Game và truyền chunk, với mục tiêu cho phép client thật kết nối
  • Hạn chế Bash không thể giữ byte null trong chuỗi được né tránh bằng cách không đưa nhị phân vào biến, mà xử lý trong pipeline dd và xxd
  • Các khó khăn triển khai tập trung vào những kiểu dữ liệu riêng của Minecraft như VarInt/VarLong, số thực dấu phẩy động IEEE 754, Position, NBT; đặc biệt việc chuyển đổi Double chậm do chi phí gọi lệnh bên ngoài
  • Máy chủ được mở rộng theo thứ tự các gói Server List Ping, handshake, Join Game, Chunk Data And Update Light; Dimension codec dùng blob nhị phân NBT lấy từ máy chủ vanilla
  • Plugin dựa trên hook có thể thay đổi việc sinh world và hiệu ứng, nhưng vẫn còn các hạn chế như multiplayer chưa hoàn thiện, giao tiếp thread dựa trên /dev/shm/witchcraft, trao đổi dữ liệu chậm và phụ thuộc vào BusyBox 1.35.0

Xử lý giao thức Minecraft nhị phân trong Bash

  • Nỗ lực ban đầu nhắm đến Classic protocol năm 2009, nhưng giới hạn khó phân tích dữ liệu nhị phân đúng cách bằng Bash đã lộ ra trước tiên
  • Chuỗi Bash bỏ qua byte null (0x00) và cũng không có cách phát hiện byte null có xuất hiện hay không, nên dữ liệu có thể bị hỏng trong các giao thức nhị phân nghiêm ngặt
  • Cách né tránh là không đưa dữ liệu nhị phân vào biến Bash hay command substitution, mà giữ nó trong pipeline
    • Dùng dd count=$len bs=1 status=none | xxd -p để đọc số byte cần thiết và chuyển thành chuỗi hex
    • Thực hiện khớp mẫu, thay thế và trích xuất dữ liệu trên chuỗi hex
    • Khi gửi phản hồi, dùng tùy chọn reverse của xxd để đổi lại thành nhị phân
  • Để nhận kết nối trên cổng TCP mặc định của Minecraft, dự án dùng ncat; khi có kết nối, script shell chính mc.sh được chạy

Triển khai các kiểu dữ liệu của giao thức

  • Mục tiêu dễ triển khai đầu tiên là gói Server List Ping
    • Đây không phải gói bắt buộc, nên ngay cả khi máy chủ không phản hồi đúng, bản thân việc vào game vẫn có thể thực hiện được
    • Tuy vậy, nó giúp dễ làm quen với các khái niệm giao thức cốt lõi như data types

  • VarInt và VarLong

    • VarInt/VarLong của Minecraft là một biến thể LEB128 có thể quen thuộc với người từng dùng MQTT
    • LEB128 là cách nén lưu độ dài số nguyên bằng cách chia byte thành 1 bit tín hiệu và 7 bit dữ liệu
    • Nếu bit đầu là 0 thì byte đó là byte cuối, nếu là 1 thì còn byte tiếp theo
    • Vì khó chuyển nguyên reference implementation sang Bash, tác giả viết encoder riêng dùng modulo và phép chia
    • Decoder được triển khai tương tự cách reference bằng phép AND và phép nhân
    • Điều phiền phức hơn bản thân LEB128 là nó xuất hiện khắp giao thức, xen lẫn với int, long và signed short thông thường

  • Số thực dấu phẩy động IEEE 754

    • Chuyển đổi IEEE 754 Double là một trong những phần khó chịu nhất khi triển khai
    • Cách triển khai cơ bản cần vòng lặp áp dụng lũy thừa âm, nhưng Bash không hỗ trợ sẵn lũy thừa âm
    • Perl bị tránh dùng, còn bc dường như không hỗ trợ lũy thừa trong môi trường sử dụng hoặc phiên bản BusyBox
    • awk có thể xử lý lũy thừa âm như 2**-1, nên được dùng để triển khai chuyển đổi
    • Triển khai ban đầu chậm đến mức mất vài phút để xử lý khoảng 50~100 gói mà client gửi trong gói Player Move, cùng 3 giá trị Double X·Y·Z của mỗi gói
    • Cấu trúc gọi awk lặp đi lặp lại trong vòng lặp for của Bash được chuyển thành vòng lặp bên trong awk, giảm số lần gọi lệnh bên ngoài
    • Sau đó, thời gian chuyển đổi giảm xuống khoảng 10ms trên Xeon E5-2680v2
    • Con số khoảng 350ms của phiên bản trước không phải là số đo chắc chắn

  • Kiểu dữ liệu Position

    • Position là kiểu dữ liệu dựa trên Long 64-bit do Mojang tạo ra
    • X được lưu ở 26 bit cao, Z ở 26 bit giữa, Y ở 12 bit thấp
    • Bash có toán tử bitshift cần thiết nên triển khai khá dễ
    • Tuy nhiên kiểu này không được dùng nhiều; nhiều gói lưu tọa độ X·Y·Z thành các giá trị Double riêng biệt
    • Kết quả là dữ liệu vị trí tăng từ 64 bit lên 192 bit mỗi gói
    • Nếu giả định chỉ cần các số đến world border mặc định là 30.000.000, ta có độ chính xác số thực 9 chữ số
    • Giao tiếp máy chủ thông thường dùng zlib, và thực tế vị trí bên trong block được cho là không cần quá 2~3 chữ số thập phân

  • NBT

    • NBT là định dạng nội bộ của Mojang, tương tự JSON cho dữ liệu nhị phân
    • Giống JSON, nó cũng được dùng để lưu dữ liệu tùy ý ngoài đặc tả
    • Ví dụ Mojang lưu bitstream độ dài biến thiên dưới dạng mảng Long
    • Nếu mảng không căn theo Long hoặc byte, Long cuối sẽ được padding bằng 0
    • Từng có lúc parser NBT gần như hoàn tất, nhưng tác giả cho rằng không đáng hoàn thiện đến cùng
    • Phần mã đó bị mất do hệ thống crash trong lúc dùng nhiều tmpfs làm thư mục dự án

Tạo một máy chủ có thể kết nối

  • Bước sau Server Ping là xử lý handshake và các gói bổ sung cần thiết để kết nối vào game thật
  • Để client vào được máy chủ, nó phải hoàn tất handshake và nhận các gói liên quan đến chunk, player position, inventory, join game
  • Trở ngại lớn nhất là gói Join Game và cấu trúc dữ liệu bên trong gói Chunk

  • Join Game

    • Gói Join Game truyền metadata ban đầu
    • Nội dung gồm player entity ID, gamemode, thông tin liên quan đến world, và Dimension codec được thêm vào từ khoảng trước/sau Minecraft 1.16
    • Dimension codec là NBT Compound nên gánh nặng triển khai lớn
    • Witchcraft lấy trường NBT này từ máy chủ vanilla để sử dụng
    • Đây là blob nhị phân duy nhất trong quá trình triển khai; có thể tái triển khai, nhưng được cho là không cần tùy chỉnh

  • Chunk Data And Update Light

    • Gói Chunk Data And Update Light ban đầu trông lớn và phức tạp, nhưng sẽ đơn giản hơn nếu đặt nhiều trường BitSet là 0x00 và không gửi trường Block Entity
    • Các trường còn lại là X, Y, heightmaps và Data
    • heightmaps là dạng mã hóa phức tạp hơn của chuỗi lặp b000000010, và tác giả cho rằng thực tế gần như giá trị nào cũng có thể dùng được

Xử lý Chunk Section và palette

  • Trường Data là mảng Chunk Section
  • Chunk Section là khối 16×16×16 block; có thể xếp nhiều section để tạo thành một Chunk
  • Để đơn giản hóa triển khai, mảng này chỉ dùng một phần tử
  • Chunk Section gồm block count, block states container và biome container
  • block states và biome container dùng cấu trúc palette
    • Trước dữ liệu block thật, máy chủ phải định nghĩa ánh xạ giữa local block ID và global block ID
    • Đây là cấu trúc nhằm nhồi nhiều dữ liệu nhất có thể vào không gian nhỏ
    • Định nghĩa block có thể nhỏ đến tối thiểu 4 bit
  • Để dễ quản lý, Witchcraft dùng 8 bits per block thay vì tối thiểu 4 bit
    • Số palette entry có thể dùng là 256
    • Dữ liệu chunk thực tế chỉ cần gửi các số hex trỏ đến palette entry
    • Palette 4 bit cũng dễ xử lý vì trong chuỗi hex, một byte có thể biểu diễn hai block, nhưng bị giới hạn ở 16 block mỗi chunk
  • Chuẩn cho phép từ 4 bits per block đến 9 bits per block; ngoài phạm vi đó thì được xem là ánh xạ direct palette 15 bits per block
  • biome palette được xử lý theo cách riêng
    • Gửi palette rỗng và ánh xạ trực tiếp biome ID 0x01, tức minecraft:plains, vào mọi region trong chunk
    • Dựa trên kết quả reverse engineering hành vi vanilla
    • Tác giả nghi ngờ tài liệu hiện có cho phần gói này có thể không chính xác

Cấu trúc plugin dựa trên hook và demo

  • Chỉ với triển khai cơ bản, máy chủ chỉ hiển thị chunk bình thường, nên cần demo cho thấy máy chủ có thể làm nhiều hơn việc hiển thị chunk
  • Để không phải tạo cây mã nguồn riêng cho từng demo, các hàm có thể override được gọi là hooks, cho phép máy chủ nạp mã người dùng
  • Với cấu trúc này, có thể triển khai từ thay đổi hình dạng world đến nối pkt_effect để khiến người chơi phát ra tiếng ticking noise khi di chuyển chuột
  • Plugin ví dụ tạo chunk bằng cách chọn ngẫu nhiên block từ palette mặc định
    • Gọi chunk_header trong hook_chunks()
    • Thêm giá trị RANDOM%30 ở dạng hex cho 4096 block
    • Lưu chunk đã tạo vào $TEMP/world/0000000000000000
    • Gọi pkt_chunk nhiều lần ở các tọa độ xung quanh để gửi chunk
  • Một demo khác là digmeout, một game đơn giản dựa trên điểm số
    • Thả người chơi vào chunk có đá và quặng được đặt ngẫu nhiên
    • Cách chơi là đào loại quặng có giá trị nhất cho đến khi hết thời gian

Hạn chế của Witchcraft

  • Bash xử lý số thập phân rất kém
    • Integer thì có thể xử lý ở mức nhất định
    • Số thập phân phải được xử lý bằng cách nhân ở đầu vào và chèn dấu chấm vào vị trí thích hợp ở đầu ra
    • Vì vậy hầu hết hoặc toàn bộ số mà Witchcraft xử lý là int
  • Multiplayer không hoạt động đúng
    • Nó có hoạt động ở mức nào đó, nhưng tác giả không dành thời gian để hoàn thiện hay trau chuốt
  • Về mặt kỹ thuật, Witchcraft là multi-threaded server
    • Do đó cần một hack không tốt để giao tiếp giữa các thread
    • Phần lớn global data được lưu dưới /dev/shm/witchcraft, và bên trong được tham chiếu là $TEMP
  • Hiệu năng vẫn là hạn chế lớn
    • Đặc biệt, việc trao đổi dữ liệu giữa nhiều thread chậm
    • Khó gửi lượng dữ liệu lớn, và việc tạo rồi gửi 16 solid chunk có thể mất tới 1 giây
  • Hiện tại chỉ chạy khi đã cài BusyBox 1.35.0 mới nhất
    • Chưa được kiểm thử với GNU coreutils và dự kiến sẽ không hoạt động

Tài liệu tham khảo

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-03-04
Ý kiến trên Hacker News

  • Với tư cách là người đã làm khá nhiều việc với các server Minecraft có thể script được cho Java và Bedrock, cái này khá ấn tượng
    Dùng từ “duckduckgoing” trong câu cũng được cộng điểm

  • Thảo luận hồi đó: https://news.ycombinator.com/item?id=30347501 — 92 bình luận

  • Số mũ âm chỉ là 2^(-n) = 1/(2^n) mà thôi
    Thấy tác giả thậm chí còn nêu ví dụ 2^-1 = 0.5 mà vẫn không nghĩ ra điều này, cuối cùng lại đẩy sang awk, khá bất ngờ

    • Dù sao Bash cũng không hỗ trợ số dấu phẩy động, nên không rõ điều đó giúp tác giả thế nào

  • Đáng ra nên dùng thư viện ngớ ngẩn(?) của tôi, ctypes.sh: https://github.com/taviso/ctypes.sh
    Như vậy có thể truy cập cả libm, poll(), select() từ Bash :)

    • Không biết có cần phải làm đến mức đó không, nhưng chỉ riêng sự liều lĩnh ấy đã ấn tượng rồi
      Cảm giác như hồi sinh Frankenstein vậy
    • Ngầu thật, nhưng về bản chất thì hơi lệch khỏi chuyện viết bằng Bash một thứ về mặt kỹ thuật hoàn toàn không cần phải là Bash
      Nếu còn cần cả mã C đã biên dịch cài thêm vào Bash, thì yêu cầu dùng C hay Python luôn cũng được, nên lý do gọi là “viết bằng Bash” yếu đi. Tất nhiên tôi nói với sự tôn trọng, và tôi vẫn thích những dự án “vô dụng” kiểu này
      Tuy vậy dự án Minecraft này cũng phụ thuộc vào công cụ bên ngoài như xxd, nên trong trường hợp này dùng ctypes.sh cũng chẳng tệ hơn, thậm chí còn hợp lý
      Nhân tiện, ngay cả không có dd hay xxd, vẫn có thể đọc, lưu, thao tác, tính toán và xuất nhị phân bằng Bash thuần. Byte gây vấn đề duy nhất là null; dù không thể lưu trực tiếp, ta vẫn có thể phát hiện và ghi nhận việc đã đọc nó, rồi khôi phục khi xuất về sau, hoặc dùng làm giá trị số cho chỉ mục mảng, offset byte, v.v.
      Ví dụ tối thiểu để sao chép file nhị phân là while LANG=C IFS= read -d '' -r -n 1 x ;do printf '%c' "$x" ;done bin2. Tuy nhiên cái này chỉ ở mức làm cat mà không dùng cat, nên chưa thấy rõ tính hữu dụng
      Một ví dụ tổng quát và hữu ích hơn có ở https://gist.github.com/bkw777/c1413d0e3de6c54524ddae890fe8d705
      Kết hợp LANG=C, IFS=, -d'' thì có thể truy cập mọi byte trừ 0x00, và bằng giá trị trả về của read() có thể phân biệt “đã đọc 0x00”, “không đọc được gì” và “đã hết input”
      Cũng không cần dùng < và > cho toàn bộ lệnh while(). Có thể mở bằng exec 3<>file_or_fifo_or_tty, rồi trong vòng lặp dùng read -u3, printf >&3, v.v.
      Ví dụ đọc từ cổng serial có ở https://gist.github.com/bkw777/ddde771cc85fdd888c7ec74953193d66, còn mã thực tế đã dùng nằm ở https://github.com/bkw777/pdd.sh. Xem tpdd_read, tpdd_write, file_to_fhex, str_to_shex sẽ thấy nó đọc/ghi cổng serial và file cục bộ, đồng thời xử lý dữ liệu theo nhiều cách
      Các vòng lặp này thậm chí không phải tiến trình ngoài hay subshell. Thao tác biến trong vòng lặp vẫn ở nguyên context ban đầu. Không có tiến trình con nên gọi là shell cha cũng hơi khó
      Các ví dụ đọc từng byte bằng read -n 1, nhưng không bắt buộc phải thế. Nếu đọc không có -n1, mỗi vòng lặp sẽ gom được càng nhiều dữ liệu càng tốt giữa các byte null, nhờ đó dùng ít bộ nhớ và số lần lặp hơn
      Trường hợp sử dụng của tôi là cần cắt và thao tác từng byte cũng như dải byte theo offset số, dữ liệu cũng nhỏ theo chuẩn ngày nay, nên mảng các cặp hex cực kỳ tiện. a[n] == byte n, có thể xử lý ký tự in được, không in được và null như nhau; ngoài việc lưu/tái tạo bằng printf, còn có thể dùng ngay như giá trị số kiểu 0x$n hoặc 0x${a[n]}
      Ví dụ có thể đọc byte thứ hai của h[] làm độ dài payload theo sau, rồi cắt payload đó bằng ${h[@]:2:0x${h[1]}}
    • Wow, tôi vừa đọc cái gì vậy? Đỉnh thật. Cài ngay. Tôi cũng muốn trở thành một phần của vấn đề
    • Ồ hay đấy :) Và chào tavis
    • Muốn xem poll() và select() hoạt động thế nào theo cách này

  • Thế này mới đúng là trang hacker chứ. Tuyệt vời

  • Tôi không giỏi lập trình Bash, nhưng ngạc nhiên ở chỗ thực ra nó mạnh mẽ và ít kinh khủng hơn mình tưởng

  • Bash là một trong những công cụ tôi thích nhất, ngang với vim và Lua
    Nó là một binary đơn lẻ chưa tới 2MB, có ở khắp nơi, và làm được nhiều thứ hơn rất nhiều so với nhiều người nghĩ
    Dùng shellcheck và các thói quen tốt thì Bash cũng có thể dễ đọc và an toàn
    Nếu cần thêm gì, có thể gắn tiện ích bằng C/C++ mà không cần FFI phức tạp, cũng không cần kéo về cả đống dependency không rõ nguồn gốc bằng pip/npm

    • Việc tôi thích nhất với shellcheck là đưa nó vào CI. Một chiêu mà lập trình viên rất ghét!
      Trong CI và Dockerfile thường có script Bash inline, và tôi cũng thích chuyển toàn bộ chúng thành các file script riêng. Giờ CI đã có shellcheck nên những đoạn mã đó cũng được kiểm tra
      Lập trình viên không thích vì nói “giảm tính dễ đọc”, nhưng chẳng những không kém dễ đọc hơn mà còn an toàn hơn nhiều
      Vấn đề tiếp theo là cùng một script Bash bị nhân bản vào cùng một file ở nhiều repository. Đây là cấu trúc build phân tán, tôi sẵn sàng nghe ý tưởng cải thiện
    • Tôi ghét Bash vì mình không giỏi nó. Dù không hay ho lắm, nó vẫn thường là giải pháp tốt nhất có thể
      Tôi tiếc vì thời sinh viên đã không đầu tư thêm thời gian cho nó. Vì đây là một trong số ít công cụ đã theo tôi suốt sự nghiệp

  • Tôi tự hỏi liệu người ta còn làm server tùy biến cho game thương mại không

    • Với Minecraft thì rất sôi nổi
      Đặc biệt bản Java ở một vị trí khá đặc biệt: vẫn liên tục nhận các bản cập nhật nội dung miễn phí lớn, đồng thời hỗ trợ chính thức chạy mọi phiên bản cũ, và cộng đồng modding cũng cực kỳ sôi động
      Minecraft (Java) vừa là game, vừa gần như là game engine để người khác xây dựng lên trên
    • Không chỉ server, một số game còn có cả client: https://runelite.net/
    • Tôi nghĩ chuyện này sẽ luôn tồn tại với những người thích vừa chơi game vừa vọc kỹ thuật
      Họ làm vì muốn sửa lỗi, học ngôn ngữ, hoặc xem bên trong vận hành thế nào
    • Theo tôi biết thì mảng reverse engineering vẫn còn sôi động

  • Minecraft là một trong những game hay nhất xuất hiện sau Quake

  • Không thể tin chuyện này thật sự xảy ra
    Tôi đã đọc nhiều bài viết về cách triển khai, nhưng cái này áp đảo hẳn. Đây chắc chắn thuộc hàng những bài viết về dự án kỳ quái hay nhất tôi từng đọc, và là một bài viết thật sự xuất sắc