사실 어제 알고리즘을 작성하다가 두 값을 넣어서 첫번째 값이 두번째 값보다 우선할때 true를 리턴하는 함수를 작성했다.
그리고 그걸 이용해서 데이터를 소팅을 했는데 처음 몇백건에 대해서는 아무런 문제 없이 되다가 실제 수백만건으로 작업을 하다가 메모리가 풀나버렸다. (당연하겠지만…)
일단 이전과 같이 하던 작업 스타일인 우열을 가늠할 수 있는 필드를 레코드 마지막에 넣어서 나중에 sort 명령으로 소팅해 버리면 가장 좋을텐데 내가 작성한 함수는 두 값을 넣어서 첫번째 값이 클때 true를 리턴하게끔 만들었다.
누구든지 이렇게 말할수 있겠다.
“두 값을 비교할수 있는데 왜 각 값의 절대치는 나오지 않는거냐” 하고 반문할 수 있지만 그게 전체 알고리즘상 그렇게 될수 밖에 없다.
이게 수학적인 알고리즘에서 나오는거라서 상대적인 크기를 가늠할 수 있는 어떤 값이 있다면 그 값을 도출하는건 아마도 수학적으로나 가능할거다. 그래서 이 문제를 수학적인 방법을 사용해서 풀어보는게 최종 목표이다. 오늘 선형대수학 책을 집에서 가져온 이유도 바로 그때문이다.
그리고 다른 방법은 Disk에 저장해서 sorting하는 방법인데 솔직히 이건 최후의 수단으로나 쓸까 지금 바로 쓸 생각은 없다. 별로 재미도 없고…
마지막 방법은 가장 재미있는 방법이겠는데, 수개의 노드로 데이터를 분산시켜 분산소팅하는 방법이다. 아마도 분산소팅 방법은 메모리와 디스크가 하나의 노드에 데이터를 올리기 힘들다는 가정이라면 최적의 방법일 것이다. 게다가 이런 메모리 문제가 날걸 대비해서 알고리즘을 Erlang으로 만들어 두어 쉽게 분산소팅이 가능할듯 하다. 이건 첫번째 방법으로 해결이 된다고 하더라도 한번정도 해볼만 할거라 생각한다.
대용량을 가보니 실제 이런 문제가 비일비재하게 나온다. 몇년전 구글 입사 문제에서나 나오던 것들이 실제 업무에 나오니 재미있기도 하구.
아무튼 이건 반드시 풀어야 한다. 입사문제가 아니라 현실문제라서…
하드훕에 대한 플래폼데이 발표를 잘들었습니다.
대용량으로 가면 이젠 소트까지도 이렇게 생각해보아야 하는군요.
항상 좋은 자료 좋은글 감사드리며… 주말 즐겁게 보내시길…
궁금한 게, 제가 MPI로 과제하면서 초기 데이터를 루트 프로세스가 가지고 있다가 그걸 뿌리고 각각이 처리를 하고 다시 합치면 그 ‘뿌리고 합치는’ 과정 자체가 엄청난 부하를 유발하더군요.
실제 활용에서는 어떻게 하는지 궁금합니다. 예를 들면 근본적으로 뿌리거나 합치지 않고 각각에서 데이터를 얻고 결과를 활용하는 방식으로 하나요?
어떤 작업인지 좀 자세한 설명이 있었으면 좋았을텐데요…
물론 말씀하신 부분이 분산처리의 가장 큰 병목입니다.
일단 데이터가 크다면 그 데이터를 뿌리는 작업 자체가 굉장한 부하겠죠. 그래서 분산처리에서 가장 선호하는 작업이 입력되는 데이터가 적지만 그 computation 연산이 많은 작업들이 선호됩니다. 예를들어 N번째 피보나치 수열의 값을 구하는 연산같은것이 좋은 예가 되겠죠.숫자만 전달하면 되니까요.
물론 이 부분은 나중에 합칠때도 문제가 되죠.
hadoop의 Job의 상황을 볼수 있는 페이지가 있는데 그 페이지에 보면 sorting 작업이 많은지 데이터 복사 작업이 많은지 각 작업에 할당된 리소스를 그래프로 볼수 있습니다. 그런 그래프를 활용해서 노드의 갯수를 조절하거나 job의 갯수, 그리고 알고리즘을 수정하는 작업을 하죠.