병목은 어디에?

2월 말부터 시작해서, 게임 리소스를 네트워크 너머로 배포하는 유틸리티를 작성하고 있다. C# 공부를 겸해서(…) 틈틈이 짜고 있는데, 요 며칠간은 어떤 골치거리 에 매여있는 터라[1] 주로 성능 평가만 했는데, 병목현상이 생기는 곳이 좀 예상치 못한 곳이더라.

개념적으로 보내는 쪽(이하 S), 받는 쪽(이하 R) 두 개의 entity로 구성되며, 대략 다음과 같이 동작한다

  1. S에서 보낼 디렉터리 전체의 요약 정보 — 이름 크기 md5 hash — 를 담은 Merkle tree를 만든다.
  2. R 쪽에서도 이걸 구하고 이 tree를 비교해서 어떤 파일이 없고, 어떤 파일이 다른지 판단한다.
  3. R에서 없는 파일의 전체, 혹은 다른 파일의 일부를 요구한다.
  4. S에서 이런 파일의 전체/일부를 전송한다
  5. R과 S에서 전체 디렉터리의 Merkle tree를 다시 구한다; 단 이번에는 다른 hash 함수를 쓴다. 그리고 이 root node만 전송한다.
  6. 이걸 비교해서 전체 파일 전송이 성공했는지 판단한다.

처음 짠 코드에서 병목은 3,4 였고, 이 부분을 .net framework의 TPL을 이용해서 복수 request / 복수 sendfile 형식으로 처리하는 식으로 디스크 / 네트워크 사용률을 높여서 해결했다. 근데 오늘 결과를 측정해보니, 예상외의 장소에서 병목이 나오더라.

3.2 GiB / 1700 파일 정도인 모 프로그램의 설치 디스크를 통째로 전송해봤는데, 대략 11분이 걸렸다. S, R에서 각각 Merkle tree를 계산하는 게 약 40초[2] 걸린다. 다음은 전송(3, 4)이 약 5분 걸리더라. 그리고 마지막으로 5단계에서 양쪽에 각각 6분 정도(……….)의 시간이 걸리더라. 16bytes hash를 생성하는 MD5대신에 좀 더 큰 48 bytes (384bits) hash를 생성하는 SHA384를 썼는데 시간이 대략 Orz.

SHA384가 실제로는 SHA 512의 truncated 버전이라, 좀 느릴 거라 생각하긴 했는데, 생각보다 너무 느리다. 거의 똑같이 계산하는데 MD5는 1분도 안 걸리고, SHA384(512?)는 6분이 걸리다니 Orz.

다른 해시를 쓰거나, Merkle tree를 계산할 때 병렬로 – 아마 work-stealing queue를 만들고, I/O 와 CPU 계산에 들어가는걸 고려한 스레드 수를 써서 – 계산해야 하려나?

  1. 이전에 쓴 글을 보면 짐작하리라 []
  2. 물론 이건 양쪽 머신에서 동시에 진행 []

Published by

rein

나는 ...

9 thoughts on “병목은 어디에?”

  1. 1이나 5에서 S는 미리 캐시해둘 수 있을테니 S쪽 부하는 거의 없겠고
    2에서 받은 다음에 사이즈 같은 애들만 md5 돌리는 거임?

    결론 : C#이라니… .Net 깔아야 하는거임?

    1. 1,5에서도 S는 보낼 디렉터리를 모를 수 있다고(…) 가정하고 만든 거라, 그 부하는 (어쩔 수 없이라도) 걸릴 거 같고요; 최종적으로 confirm할 때도 S만 critical path인건 아니라서;;;
      (사실 캐싱해둔다 해도 큰 문제는 없을 것 같지만요)

      생각해보니 사이즈 같을 때만 md5구해도 되네요(전혀 생각 못했네요). 지금은 그냥 다 구해놓고 tree-diff 구하는데요(어이). 근데 뭐 느려터진(…) sata하드에서도 저 정도 속도 나오는 걸로 봐선 신경 안써도 될 것 같은걸요(먼산).
      여튼 문제는 SHA384 같은 애 구할 때의 속도 자체가 너무 느린데 있는 듯하니 일단 그거 해결보려고요. 아예 함수를 바꾸거나, 병렬처리 하거나;

      결론에 대해서는(…), 일단 저거 짜는거 얘기가 나왔을 때 전 그냥 python으로 후딱 짜려고 했지만 (역시 /먼산), 제가 짜고 난 후의 유지 보수 얘기가 나와서, 대중적인 언어로 하자는 결론이 나서 C#으로…
      근데 .net framework이 설치될 서버는 실제 서비스 서버(유저가 실제로 접속하는 서버이거나, 그 서버가 실시간으로 접속하는 서버)는 아니라서 별 문제 없지 않을까요.

      1. sexy.txt.md5 만들어놓고 날짜 비교해서 바뀐것만 돌려도 되겠지만? 서비스 서버가 아니라니 상관없는데… 서버에 .net을 깔다니… 격세지감… python 정도면 충분히 대중적 아닌가.

        1. 네 그런 식으로 하면 (+ 디렉터리만 미리 설정하면) S 쪽 부하는 거의 없겠네요.

          요즘은 게임 서버도 .net으로 만들거나(마x전), Java로 만든다거나(ProjectDarkstar; Heaven and Hearth)하는 걸 봐선 뭐 안될 건 없지요(…이 방향성이 현재 상황이랑 맞는가는 제껴두고)
          나중에 T*에서 가져가려 할지도 모르는데, python으로 짰다가 코드 설명해달라고 하면 좀 귀찮을 거 같은데요(…).
          사람 뽑을 때도 python안다는 사람은 꽤 나오지만, python 잘합니다! 라는 사람은 드물고요. 물론 잘하는 사람도 가끔 나오지만…
          한 2년? 만 있으면 상황이 꽤 바뀔드하지만 그전에는 내부 도구에만 python쓰려고요;;

  2. SHA가 MD5에 비해서는 느리다고 알고 있었는데, 그 정도로 느린 줄은 몰랐네요. 호기심 때문에 여쭤보는데, SHA384 급으로 써야하는 중요한 이유가 있는건가요? 그리고 어떤 것을 선택하실지 궁금~ ㅎㅎ

    1. 일단 md5는 이미 썼으니 안되고(…), 하나만 보내야 하니 임의 데이터끼리 충돌할 확률이 제일 낮아보이는 녀석을 고른건데(덤으로 제가 안짜도 되게 .net framework에 있는걸), 왠지 망한 느낌이네요.
      SHA-1은 그다지 느리단 느낌이 없었는데 — 사실 이 정도로 큰 데이터 셋에 안 넣어본거라 그럴 수도 있지만 — SHA-2, 그것도 워드 사이즈 큰 SHA384는 너무 느리네요(…). 이거 설마 managed language로 짠건가라는 의심을 하는 중입니다(…).

      선택은 주말에 개념 증명 수준으로 병렬화해서 충분히 빠르면 그냥 쓰고(…) 아니면 딴 해시 함수 써봐야겠네요 ㅠㅠ

  3. SHA의 원리는 잘 모르겠지만 동작 속도가 과하게 느리다면 deterministic하게 파일 내부를 샘플링해서 얻은 일부분만 가지고 해쉬값을 구하는 것도 가능하지 않을까요? 어차피 perfect hash가 아닌 이상에야 collision 자체는 피할 수 없는 일이니…

    그런데 생각해보니 이 코드를 짜는데 들어가는 비용도 만만치 않겠군요 (…)

Leave a Reply