배시(Bash)를 이용해 처음부터 만든 마인크래프트 서버 (2022)

 (sdomi.pl)
4P by GN⁺ | ★ favorite | 댓글 1개
  • Witchcraft는 Bash만으로 Minecraft 서버를 처음부터 구현한 실험 프로젝트로, 바이너리 프로토콜과 Join Game, 청크 전송까지 다뤄 실제 클라이언트 접속을 목표로 함
  • Bash가 널 바이트를 문자열에 보존하지 못하는 한계는 바이너리를 변수에 담지 않고 dd와 xxd 파이프 안에서 처리하는 방식으로 우회함
  • 구현 난점은 VarInt/VarLong, IEEE 754 부동소수점, Position, NBT 같은 Minecraft 고유 데이터 형식에 집중됐고, 특히 Double 변환은 외부 명령 호출 비용 때문에 느렸음
  • 서버는 Server List Ping, handshake, Join Game, Chunk Data And Update Light 패킷 순으로 확장됐으며, Dimension codec은 vanilla 서버에서 가져온 NBT 바이너리 blob을 사용함
  • 훅 기반 플러그인으로 월드 생성과 효과를 바꿀 수 있지만, 멀티플레이 미완성, /dev/shm/witchcraft 기반 스레드 통신, 느린 데이터 교환, BusyBox 1.35.0 의존성이 남아 있음

Bash에서 바이너리 Minecraft 프로토콜 다루기

  • 초기 시도는 2009년 Classic protocol을 대상으로 했지만, Bash로 바이너리 데이터를 제대로 파싱하기 어렵다는 한계가 먼저 드러남
  • Bash 문자열은 널 바이트(0x00) 를 무시하고, 널 바이트 발생 여부를 감지할 방법도 없어 엄격한 바이너리 프로토콜에서는 데이터가 손상될 수 있음
  • 우회 방식은 바이너리 데이터를 Bash 변수나 명령 치환에 넣지 않고 파이프 안에 유지하는 것임
    • dd count=$len bs=1 status=none | xxd -p로 필요한 바이트 수를 읽고 hex 문자열로 변환함
    • hex 문자열 위에서 패턴 매칭, 치환, 데이터 추출을 수행함
    • 응답 전송은 xxd의 reverse 옵션으로 다시 바이너리로 바꿈
  • Minecraft 기본 TCP 포트에서 연결을 받기 위해 ncat 을 사용하고, 연결이 들어오면 메인 셸 스크립트 mc.sh를 실행함

프로토콜 데이터 타입 구현

  • 가장 먼저 구현하기 좋은 대상은 Server List Ping 패킷임
    • 필수 패킷은 아니어서 서버가 제대로 응답하지 않아도 게임 접속 자체는 가능함
    • 다만 data types 같은 핵심 프로토콜 개념을 익히기 쉬움

  • VarInt와 VarLong

    • Minecraft의 VarInt/VarLong은 MQTT 경험자에게 익숙할 수 있는 LEB128 변형임
    • LEB128은 바이트를 1개의 신호 비트와 7개의 데이터 비트로 나눠 정수 길이를 저장하는 압축 방식임
    • 첫 비트가 0이면 해당 바이트가 마지막이고, 1이면 다음 바이트가 이어짐
    • Bash로 reference implementation을 그대로 옮기기 어려워 modulo와 division을 이용한 자체 인코더를 작성함
    • 디코더는 AND 연산과 곱셈을 이용해 reference 방식과 비슷하게 구현함
    • LEB128 자체보다 일반 int, long, signed short와 섞여 프로토콜 곳곳에 등장하는 점이 더 번거로웠음

  • IEEE 754 부동소수점

    • IEEE 754 Double 변환은 구현에서 가장 성가신 부분 중 하나였음
    • 기본 구현에는 음수 거듭제곱을 적용하는 루프가 필요하지만, Bash는 음수 거듭제곱을 기본 지원하지 않음
    • Perl은 피했고, bc는 사용 환경이나 BusyBox 버전에서 거듭제곱을 지원하지 않는 것으로 보였음
    • awk는 2**-1 같은 음수 거듭제곱을 처리할 수 있어 변환 구현에 사용됨
    • 초기 구현은 Player Move 패킷에서 클라이언트가 보내는 약 50~100개 패킷과 각 패킷의 X·Y·Z Double 3개를 처리하는 데 여러 분이 걸릴 정도로 느렸음
    • Bash for 루프 안에서 반복적으로 awk를 호출하던 구조를 awk 내부 루프로 옮겨 외부 명령 호출 수를 줄임
    • 이후 변환은 Xeon E5-2680v2에서 약 10ms 수준까지 줄어듦
    • 이전 버전의 약 350ms 수치는 확실한 측정값은 아님

  • Position 데이터 타입

    • Position은 Mojang이 만든 64-bit Long 기반 데이터 타입임
    • X는 상위 26비트, Z는 중간 26비트, Y는 하위 12비트에 저장됨
    • Bash에는 필요한 bitshift 연산자가 있어 구현은 쉬웠음
    • 다만 이 타입은 많이 쓰이지 않으며, 많은 패킷은 X·Y·Z 좌표를 별도 Double 값으로 저장함
    • 그 결과 위치 데이터가 패킷당 64비트에서 192비트로 커짐
    • 기본 world border인 30,000,000까지의 숫자만 필요하다고 가정하면 9자리 부동소수점 정확도를 얻게 됨
    • 일반 서버 통신은 zlib을 사용하고, 블록 안 위치 표현에는 현실적으로 소수점 2~3자리 이상이 필요하지 않다고 봄

  • NBT

    • NBT는 Mojang 내부 형식이며, 바이너리 데이터를 위한 JSON과 비슷한 형식임
    • JSON처럼 명세 밖의 임의 데이터 저장에도 사용됨
    • Mojang은 예를 들어 가변 길이 bitstream을 Long 배열로 저장함
    • 배열이 Long 또는 byte 정렬이 아니면 마지막 Long은 0으로 padding됨
    • NBT 파서는 거의 완성한 적이 있었지만, 끝까지 마무리할 가치가 없다고 판단함
    • 해당 코드는 프로젝트 디렉터리로 tmpfs를 많이 사용하던 중 시스템 crash로 유실됨

접속 가능한 서버 만들기

  • Server Ping 다음 단계는 실제 게임 접속에 필요한 handshake와 추가 패킷 처리였음
  • 클라이언트가 서버에 들어오려면 handshake를 마치고 chunk, player position, inventory, join game 관련 패킷을 받아야 함
  • 가장 큰 장애물은 Join Game 패킷과 Chunk 패킷 내부 데이터 구조였음

  • Join Game

    • Join Game 패킷은 초기 메타데이터를 전송함
    • 포함 항목은 플레이어 entity ID, gamemode, 월드 관련 정보, Minecraft 1.16 전후부터 들어간 Dimension codec임
    • Dimension codec은 NBT Compound라 구현 부담이 컸음
    • Witchcraft는 이 NBT 필드를 vanilla 서버에서 가져와 사용함
    • 이 부분은 구현에서 유일한 바이너리 blob이며, 재구현은 가능하지만 커스터마이즈할 필요가 없다고 판단함

  • Chunk Data And Update Light

    • Chunk Data And Update Light 패킷은 처음에는 크고 복잡해 보이지만, 여러 BitSet 필드를 0x00으로 두고 Block Entity 필드를 보내지 않으면 단순해짐
    • 남는 필드는 X, Y, heightmaps, Data 필드임
    • heightmaps는 b000000010 반복을 더 복잡하게 인코딩한 형태이며, 사실상 어떤 값이어도 될 수 있다고 봄

Chunk Section과 palette 처리

  • Data 필드는 Chunk Section 배열임
  • Chunk Section은 16×16×16 블록이며, 여러 section을 쌓아 하나의 Chunk를 만들 수 있음
  • 구현 단순화를 위해 이 배열은 단일 요소만 사용함
  • Chunk Section은 block count, block states container, biome container로 구성됨
  • block states와 biome container는 palette 구조를 사용함
    • 실제 블록 데이터 앞에서 서버가 local block ID와 global block ID의 매핑을 정의해야 함
    • 가능한 한 많은 데이터를 작은 공간에 넣기 위한 구조임
    • 블록 정의는 최소 4비트까지 작아질 수 있음
  • Witchcraft는 관리 편의상 최소 4비트 대신 8 bits per block을 사용함
    • 사용 가능한 palette entry가 256개가 됨
    • 실제 chunk 데이터는 palette entry를 가리키는 hex 숫자를 보내면 됨
    • 4비트 palette도 hex 문자열에서 한 바이트가 두 블록을 표현할 수 있어 다루기 쉽지만, chunk당 16개 블록으로 제한됨
  • 표준은 4 bits per block부터 9 bits per block까지 허용하고, 그 외에는 15 bits per block direct palette mapping으로 간주함
  • biome palette는 별도 방식으로 처리됨
    • 빈 palette를 보내고 biome ID 0x01, 즉 minecraft:plains를 chunk 안 모든 region에 직접 매핑함
    • vanilla 동작을 역공학한 결과에 기반함
    • 해당 패킷 부분의 기존 문서가 부정확할 수 있다고 의심함

훅 기반 플러그인 구조와 데모

  • 기본 구현만으로는 평범한 chunk만 표시되기 때문에, 서버가 chunk 표시 이상의 동작을 할 수 있음을 보여줄 데모가 필요했음
  • 데모마다 별도 소스 트리를 만들지 않기 위해 override 가능한 함수들을 hooks라고 부르고, 서버가 사용자 코드를 로드할 수 있게 함
  • 이 구조로 월드 모양 변경부터 pkt_effect를 연결해 마우스를 움직일 때 플레이어가 ticking noise를 내게 하는 동작까지 구현할 수 있음
  • 예시 플러그인은 기본 palette에서 무작위 블록을 골라 chunk를 생성함
    • hook_chunks()에서 chunk_header를 호출함
    • 4096개 블록에 대해 RANDOM%30 값을 hex로 추가함
    • 생성한 chunk를 $TEMP/world/0000000000000000에 저장함
    • 주변 좌표에 pkt_chunk를 여러 번 호출해 chunk를 전송함
  • 또 다른 데모인 digmeout은 점수 기반 간단한 게임임
    • 플레이어를 무작위로 배치된 돌과 광물이 있는 chunk에 던짐
    • 제한 시간이 끝날 때까지 가장 가치 있는 광물을 캐는 방식임

Witchcraft의 제약

  • Bash는 십진 소수 처리에 매우 약함
    • Integer는 어느 정도 처리할 수 있음
    • 십진 소수는 입력에서 곱하고 출력에서 적절한 위치에 점을 넣는 방식으로 다뤄야 함
    • 이 때문에 Witchcraft가 처리하는 대부분 또는 모든 숫자는 int임
  • 멀티플레이는 제대로 작동하지 않음
    • 어느 정도 동작은 하지만, 완성하거나 다듬는 데 시간을 들이지 않았음
  • Witchcraft는 기술적으로 multi-threaded server임
    • 그 결과 스레드 간 통신을 위해 좋지 않은 hack이 필요함
    • 대부분의 global data는 /dev/shm/witchcraft 아래 저장되며, 내부적으로 $TEMP로 참조됨
  • 성능은 큰 제약으로 남아 있음
    • 특히 여러 thread 사이의 데이터 교환이 느림
    • 많은 양의 데이터를 보내기는 어렵고, solid chunk 16개를 생성해 보내는 데 최대 1초가 걸릴 수 있음
  • 현재는 최신 BusyBox 1.35.0이 설치된 경우에만 실행됨
    • GNU coreutils로는 테스트하지 않았고, 작동하지 않을 것으로 예상함

참고 자료

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Java와 Bedrock용 스크립트 가능한 Minecraft 서버 작업을 많이 해본 입장에서, 이건 꽤 인상적임
    문장 안에 “duckduckgoing”을 쓴 것도 가산점 줌

  • 당시 토론: https://news.ycombinator.com/item?id=30347501 — 댓글 92개

  • 음수 지수는 2^(-n) = 1/(2^n)일 뿐임
    글쓴이가 본인 예시로 2^-1 = 0.5까지 들고도 이걸 떠올리지 못하고 결국 awk에 넘긴 게 의외였음

    • Bash는 어차피 부동소수점 숫자를 지원하지 않는데, 그게 글쓴이에게 어떻게 도움이 되는지 모르겠음

  • 내 바보 같은(?) 라이브러리 ctypes.sh를 썼어야 했음: https://github.com/taviso/ctypes.sh
    그러면 Bash에서 libm, poll(), select() 같은 것도 접근 가능함 :)

    • 굳이 그렇게까지 했어야 했는지는 모르겠지만, 그 무모함만으로도 인상적임
      Frankenstein을 되살리는 느낌임
    • 멋지긴 한데, 기술적으로 Bash일 필요가 전혀 없는 걸 Bash로 작성한다는 본질에서는 좀 벗어남
      Bash에 별도 설치한 컴파일된 C 코드까지 필요하다면, 그냥 C나 Python 같은 걸 요구해도 되는 거라 “Bash로 작성”했다고 부를 이유가 약해짐. 물론 존중을 담아 하는 말이고, 이런 “쓸데없는” 프로젝트 자체는 좋아함
      다만 이 Minecraft 프로젝트도 xxd 같은 외부 도구에 의존하고 있어서, 이 경우엔 ctypes.sh를 써도 더 나쁠 건 없고 오히려 맞는 말임
      참고로 dd나 xxd 없이도 순수 Bash로 바이너리를 읽고, 저장하고, 조작하고, 계산하고, 출력할 수 있음. 문제가 되는 바이트는 널뿐인데, 직접 저장은 못 해도 읽었다는 사실을 감지해 기록하고 나중에 출력 시 복원하거나 숫자값으로 배열 인덱스·바이트 오프셋 등에 사용할 수 있음
      바이너리 파일을 복사하는 최소 예시는 while LANG=C IFS= read -d '' -r -n 1 x ;do printf '%c' "$x" ;done bin2임. 다만 이건 cat 없이 cat을 하는 수준이라 유용성이 잘 드러나진 않음
      좀 더 일반적이고 유용한 예시는 https://gist.github.com/bkw777/c1413d0e3de6c54524ddae890fe8d705에 있음
      LANG=C, IFS=, -d''를 조합하면 0x00을 제외한 모든 바이트에 접근 가능하고, read()의 반환값으로 “0x00을 읽었는지”, “아무것도 못 읽었는지”, “입력이 끝났는지”를 구분할 수 있음
      전체 while() 명령에 <와 >를 쓸 필요도 없음. exec 3<>file_or_fifo_or_tty로 열고 루프 안에서 read -u3, printf >&3 등을 쓰면 됨
      시리얼 포트에서 읽는 예시는 https://gist.github.com/bkw777/ddde771cc85fdd888c7ec74953193d66에 있고, 실제로 쓴 코드는 https://github.com/bkw777/pdd.sh에 있음. tpdd_read, tpdd_write, file_to_fhex, str_to_shex를 보면 시리얼 포트와 로컬 파일을 읽고 쓰면서 데이터를 여러 방식으로 처리함
      이 루프들은 외부 프로세스는커녕 서브셸도 아님. 루프 안에서 변수를 조작해도 원래 컨텍스트 그대로임. 자식이 없으니 부모 셸이라고도 하기 애매함
      예시들은 read -n 1로 한 바이트씩 읽지만 반드시 그래야 하는 건 아님. -n1 없이 읽으면 루프 한 번마다 널 사이의 가능한 많은 데이터를 모으므로 메모리와 반복 횟수를 덜 쓸 수 있음
      내가 쓰는 용도는 숫자 오프셋 기준으로 개별 바이트와 바이트 범위를 자르고 조작해야 하고, 데이터도 요즘 기준으론 작아서 16진수 쌍 배열이 너무 편함. a[n] == byte n이 되고, 출력 가능 문자·비출력 문자·널을 모두 동일하게 다룰 수 있으며, printf로 저장·재생성하는 것뿐 아니라 0x$n이나 0x${a[n]}처럼 숫자값으로도 바로 쓸 수 있음
      예를 들어 h[]의 두 번째 바이트를 뒤따르는 페이로드 길이로 읽고, ${h[@]:2:0x${h[1]}}로 그 페이로드를 잘라낼 수 있음
    • 와, 방금 뭘 읽은 거지? 대단함. 바로 설치함. 나도 문제의 일부가 되고 싶음
    • 오 멋지다 :) 그리고 안녕 tavis
    • 이런 방식으로 poll()과 select() 가 어떻게 동작하는지 보고 싶음

  • 이래야 진짜 해커 사이트지. 훌륭함

  • Bash 프로그래밍을 잘하진 않지만, 실제로는 생각보다 강력하고 덜 끔찍하다는 점이 놀라움

  • Bash는 vim, Lua만큼 좋아하는 도구 중 하나임
    2MB도 안 되는 단일 바이너리이고, 어디에나 있으며, 많은 사람이 생각하는 것보다 훨씬 더 할 수 있는 일이 많음
    shellcheck와 좋은 습관을 쓰면 Bash도 읽기 쉽고 안전해질 수 있음
    더 필요한 게 있으면 복잡한 FFI 없이 C/C++로 유틸리티를 붙이면 되고, pip/npm 같은 걸로 정체 모를 의존성을 잔뜩 끌어올 필요도 없음

    • shellcheck로 제일 좋아하는 일은 CI에 넣는 것임. 개발자들이 싫어하는 그 한 수!
      CI와 Dockerfile 안에 인라인 Bash 스크립트가 들어가는 경우가 많은데, 그걸 전부 별도 스크립트 파일로 옮기는 것도 좋아함. 이제 CI에 shellcheck가 있으니 그 코드들도 검사됨
      개발자들은 “가독성이 떨어진다”고 싫어하는데, 가독성이 떨어지기는커녕 훨씬 더 안전함
      다음 문제는 같은 Bash 스크립트가 여러 저장소의 같은 파일에 복제된다는 것임. 분산 빌드 구조인데, 개선 아이디어가 있으면 열려 있음
    • Bash를 잘 못해서 싫어함. 별로긴 한데도 여전히 가능한 최선의 해법일 때가 많음
      학생 때 더 시간을 투자하지 않은 게 후회됨. 내 커리어 내내 따라온 드문 도구 중 하나였기 때문임

  • 상용 게임용 커스텀 서버를 만드는 일이 아직도 있나 궁금함

    • Minecraft에서는 아주 활발함
      특히 Java 버전은 비교적 특이한 위치에 있는데, 큰 무료 콘텐츠 업데이트를 계속 받으면서도 모든 과거 버전 실행을 공식 지원하고, 모딩 커뮤니티도 엄청 활발함
      Minecraft(Java)는 게임인 동시에 다른 사람들이 그 위에 쌓아 올리는 게임 엔진에 가까움
    • 서버뿐 아니라 어떤 게임은 클라이언트도 있음: https://runelite.net/
    • 게임을 하면서 기술을 만져보는 걸 좋아하는 사람들에겐 늘 있을 일이라고 봄
      버그를 고치거나, 언어를 배우거나, 내부가 어떻게 돌아가는지 보고 싶어서 하게 됨
    • 아는 한 리버스 엔지니어링 쪽은 아직 활발함

  • Minecraft는 Quake 이후 나온 최고의 게임 중 하나임

  • 이런 일이 실제로 벌어졌다니, 세상에
    구현 방식에 대한 글을 많이 읽어봤지만 이건 압도적임. 지금까지 읽은 괴상한 프로젝트 글 중 단연 최고 수준이고, 정말 훌륭한 글임

답변달기