요약

  • Tridgell과 Mackerras의 원래 기술 보고서에서 받는 쪽은 가지고 있는 파일을 블록으로 나누고 블록마다 두 검사값을 보낸다. 보내는 쪽은 새 파일의 모든 위치에서 그 블록을 찾아, 재사용할 블록 번호와 맞지 않는 부분의 실제 바이트를 전송한다.
  • rsync 프로젝트의 구현 설명은 회선이 아낀 몫의 가격도 적었다. 블록 검색에는 보내는 쪽 CPU가, 옛 파일을 다시 엮는 데에는 받는 쪽 디스크가 쓰이고, 마지막에는 완성 파일 전체의 검사값을 확인한다.

먼저 도착한 것은 파일이 아니라 재고표였다

큰 파일의 비슷한 두 판이 느린 선로 양쪽에 있다고 하자. 새 판의 앞부분에 문단 하나가 들어갔고 나머지는 대체로 같다. 전체를 복사하면 받는 쪽이 이미 가진 내용을 다시 나른다. 같은 위치의 블록끼리만 비교해도 실패한다. 삽입된 문단이 뒤의 내용을 모두 다른 위치로 밀었기 때문이다. 초기 rsync 보고서는 바로 이 상황, 곧 대역폭이 좁고 왕복 지연이 큰 연결을 문제로 삼았다. 각 컴퓨터는 자기 파일 전체를 볼 수 있지만, 두 파일을 한곳에 모아 보통의 차이 계산을 하려면 피하려던 전송부터 해야 한다.

따라서 첫 쓸모 있는 메시지는 목적지에서 나온다. 목적지는 자기 옛 파일을 겹치지 않는 블록으로 자르고, 각 블록에 빠르게 갱신할 수 있는 검사값과 더 강한 검사값을 붙여 보내 준다. 당시 알고리즘의 기록은 약한 값으로 32비트, 강한 값으로 MD4를 썼다. 이는 역사적 설계의 수치이며 오늘날 모든 버전의 설정을 뜻하지 않는다. 핵심은 원본을 가진 컴퓨터가 옛 파일 전체를 받지 않고도 상대가 가진 조각의 지도를 얻는 데 있다.

보내는 쪽은 자신이 가진 새 파일을 훑는다. 상대에게 이미 있는 블록을 찾으면 그 번호를 보낸다. 맞는 블록이 없는 구간에는 실제 새 바이트를 보낸다. 받는 쪽은 옛 파일에서 지정된 블록을 꺼내고 새 데이터를 끼워 넣어 목표 파일을 만든다. 검사값과 블록 번호도 회선을 지나므로 문자 그대로 ‘차이만’ 건너는 것은 아니다. 다만 비슷한 파일과 느린 회선이라는 원래 조건에서는 그 부가 정보가 파일 전체를 다시 보내는 비용보다 훨씬 작을 수 있다.

한 바이트씩 미끄러져야 같은 조각이 보였다

옛 파일의 블록 경계에서만 새 파일을 보면, 앞의 삽입 때문에 뒤의 공통 내용을 모두 놓친다. 보내는 쪽은 새 파일의 모든 바이트 위치에서 옛 블록을 찾아야 한다. 매번 블록 전체의 검사값을 처음부터 계산한다면 CPU 비용이 크게 늘어난다.

보고서의 이동식 검사값 설명은 창을 한 바이트 밀 때 직전 결과를 활용한다. 빠져나간 바이트를 빼고 새로 들어온 바이트를 더하면 다음 후보의 약한 검사값을 얻는다. 값이 맞는 후보에만 더 강한 검사를 한다. 검색 절차는 그 앞에 해시 표까지 둬 후보를 좁혔다. 덕분에 위치가 바뀐 내용도 찾을 수 있다. 컴퓨터가 계산에 땀을 흘리니 가는 선로는 같은 책을 다시 들지 않아도 된다.

보고서는 계산과 통신을 겹치는 방법도 적었다. 일치하는 블록을 찾을 때마다 보내는 쪽은 그 전까지 모인 새 데이터와 블록 번호를 보내고 계속 검색할 수 있다. 초기 방식의 교환에는 한 번의 왕복이면 된다. 지연이 큰 선로에서는 대화 한 차례를 덜 기다리는 것 역시 이득이다.

줄어든 바이트가 다른 작업으로 청구됐다

프로젝트의 실제 동작 설명은 작업을 생성기, 보내는 프로세스, 받는 프로세스로 나눈다. 목적지 쪽 생성기는 갱신할 파일을 고르고 기존 기준 파일의 검사값을 보낸다. 보내는 쪽은 일치 항목을 검색하느라 CPU를 많이 쓴다. 받는 쪽은 옛 파일의 떨어진 위치를 읽고 새 임시 파일을 쓰느라 디스크를 많이 쓴다. 파일이 완성되면 전체 검사값을 비교하고, 맞지 않으면 잘못 만든 임시 파일을 버린다.

회선에 맞춘 간결한 통신 방식도 유지 보수 비용을 낳았다. 프로젝트 설명은 바이트가 끊임없이 이어지는 흐름에서 각 부분의 의미가 문맥과 프로토콜 버전에 크게 달린다고 지적한다. 메시지 경계를 분명히 적는 방식보다 전송량은 적지만 설명, 디버깅, 확장이 어렵다. 좁은 회선을 아낀 만큼 프로그램과 유지 관리자가 더 까다로운 규칙을 다뤄야 했다.

목적지에 비슷한 옛 파일이 없다면 재사용할 블록이 거의 없다. 연결은 빠른데 디스크가 느리다면 추가 계산과 읽기가 직접 복사보다 비쌀 수 있다. 원 보고서가 좋은 조건으로 든 것은 비슷한 파일을 느린 선로로 맞추는 작업이었다. 모든 복사에 붙일 만능 가속 스티커는 아니었다.

발언 순서를 바꾼 것이 발명이었다

원본 쪽은 완성할 파일을 알고, 목적지는 손에 있는 옛 조각을 안다. rsync는 목적지에 그 조각을 먼저 설명하게 하고 원본 쪽이 번호로 가리킬 것과 실제로 보낼 것을 고르게 했다. 두 파일 전체를 한 컴퓨터로 모으지 않아도 쓸 만한 차이를 찾을 수 있다. 돌아오는 것은 조립 안내서와 비슷하다. 이 블록을 쓰고, 다음 블록을 쓰고, 이 부분에 새 바이트를 넣어라.

목적지는 여전히 조립과 최종 확인을 해야 한다. rsync의 역사적 성과는 비용 없는 ‘차이만 보내기’ 주문이 아니었다. 계산, 디스크 접근, 까다로운 통신 규칙을 써서 귀한 네트워크 용량을 되찾은 거래였다. 운송차는 도서관 전체를 또 싣지 않았지만, 양쪽 창고는 서가를 더 꼼꼼히 정리해야 했다.