Background Image
조회 수 34291 추천 수 0 댓글 5
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

-- 큐브리드 면접용 기술문제를 회고하며 --

오래전에 큐브리드에서 개발자를 뽑을때, 그 당시의 면접문제가 여러 사이트에 퍼지면서
한 동안 IT 계를 뜨겁게 달구었던(?) 적이 있읍니다. 여러 문제 중에서 특히 아래 문제가
아주 높은 관심을 이끌어 냈습니다.

-- (개발팀)
--
-- 2. 전체 개수를 미리 알 수 없는 number stream에서 무작위로 1000개를 추출하려고 합니다.
--    추출된 것이 stream의 특정 지역에 집중되면 안될 것이고,
--    전체 개수를 미리 알 수 없으니, 전체를 디스크에 저장할 수도 없을 것입니다.

처음에 저거를 어떻게 처리할까 고민하면서 flow 를 대충 떠올려보니

-- 처음 1000 개는 무조건 버퍼에 들어갈 테고, 그 다음 데이타를 이 버퍼에 넣기 전에,
-- 분포가 균일해야 하니까, 음, 그럼 분포를 알려주는 수학함수에는 뭐가 있더라?

라는 생각을 하면서, 나름대로 피와 살을 붙이던 중, 문제를 출제하신 분께서,
이 문제가 발생한 배경을 설명한 글을 올려 주신 적이 있읍니다.

-- int GetNextNumber(Stream *p)라는 함수가 있는데,
-- 한번 호출할 때마다 음수가 아닌 하나의 숫자를 리턴한다.
-- 그러다가, 끝이 되면 음수를 리턴한다. 마치, fgetc(fp)와 유사하다.
-- 그런데, 문제는 이 함수가 몇 개를 리턴한 후 음수를 리턴할 지 끝까지 가 봐야 안다는 것이다.
-- 내가 원하는 것은 이 함수가 리턴하는 숫자들 중에 무작위로 1000개를 고르고자 하는 것이다.
-- 만약, 이 함수가 1000개를 리턴하고 음수를 리턴한다면,
-- 1000개 그대로가 원하는 데이터이겠지만, 만약, 이 함수가 1억개를 리턴한다면
-- 1억개 중 1000개를 랜덤(무작위)하게 뽑아야한다.
-- 그런데, 문제는 1억개를 저장할 공간이 없다는 것이다.
-- 따라서, 1억개를 모두 받아놓은 후 1000개를 추출할 수 없고,
-- 하나씩 보면서 결국 끝을 보았을 때,
-- 1000개가 1억개의 임의추출 결과가 만들어지는 방법이 필요하다.
-- 이 문제는 내가 MS-SQL 데이터마이닝팀에 있을 때,
-- 방대한 데이타의 샘플분석을 위해 해결해야 했던 문제이고,
-- 실제로 그 결과가 SQL 2005 DM의 데이터탐험 기능에 탑재되어 있다.
-- 수학적으로 맞는지를 증명하는 것은 좀 어려울지 몰라도,
-- 방법을 찾는 것은 그리 어렵지 않을 것이다.

이 설명을 듣는 순간 처음에 생각하듯이 '단순하게 접근해서는 안되는구나' 하는
생각을 했읍니다. "방대한 데이타의 샘플분석" 이라면 필요에 따라 분산처리를
하게 되는 경우도 발생하지 않을까 합니다. 꼭 분산처리가 아니라 할지라도
정교한 멀티쓰레드 설계가 필요하겠구나 싶었읍니다.

위 문제에 대해 의견을 적은 글 중에

-- http://www.okjsp.pe.kr/seq/95256 (김창준님)
--
-- parallel 구현을 할 수 있냐 없냐는 큰 문제가 아닐 것 같은데
-- (예컨대 N개의 worker thread가 숫자들의 chunk들을 처리하도록 하고
-- 그 결과를 애그리게이터에게 async 메시지 패싱하고 결과를 join해서 다시 worker를 돌리고),
-- optimal한 parallel 구현을 하는 것은 간단한 문제가 아닐 것 같습니다

요약하면 parallel 구현을 위해 쓰레드 여러 개 돌리는 것은 큰 문제가 아닌데
각 작업쓰레드에 분배해서 그 결과를 수집하는 정교한 처리가 어렵다는 것입니다.

여기에 찬성합니다. 작업쓰레드를 정교하게 설계하자면,
기본적으로 제일 먼저 쓰레드 풀링을 구현해야 하는데,
이게 은근히 그리고 상당히 까다롭습니다.
쓰레드가 아닌 일반 데이타의 풀링이라면 동기화영역에서 데이타를 넣고 뺏다가,
데이타 풀에 데이타가 없다면, 풀에서 데이타를 가져오려는 쓰레드는
세마포어나 조건변수에서 대기하면 그만입니다.
그런데 쓰레드 풀링은 데이타와 쓰레드 모두 풀링의 대상이 된다는 점에서
일반 데이타의 풀링과는 차별화된 복잡성을 내포하고 있읍니다.
상당한 경력의 소유자분들도 쓰레드 풀링을 다른 라이브러리의 도움없이
밑바닥부터 구현해야 하는 경우라면 다소 당황할지도 모르겠읍니다.

게다가 분산처리까지 해야 하는 상황이라면 문제가 더 복잡한데,
각각의 작업을 N 개의 노드(원격지 컴퓨터) 에게 분배해서 그 결과를 수집해야 할 뿐만 아니라.
노드와 통신할 때, 반드시 고속의 네트워킹 처리를 해주어야 합니다.
윈도우라면 IOCP 를 써야 할 것이고, Linux 라면 EPOLL 을 써야 하겠죠.
(물론 다른 OS 에서는 KQueue 나 dev/poll 같은게 있겠죠)
그런데 EPOLL 이라는게 사용의 편리성에 있어서 IOCP 에 상당히 못미칩니다.
원래 IOCP 와 EPOLL 은 컨셉 자체가 틀리기 때문에 어떤게 좋다 나쁘다 비교한다는게
적절하지는 않습니다. 그래도 윈도우의 IOCP 가 작업쓰레드까지 손쇱게 설계할 수 있는데 반해
EPOLL 은 쓰레드풀링을 비릇한 작업쓰레드 설계를
프로그래머가 처음부터 끝까지 알아서 해야 한다는 점에서
사람을 아주 피곤하게 만듭니다. 프로그램의 편리성 면에서는
IOCP 에 높은 점수를 주어도 될 것 같습니다.

이런 분산처리용으로 사용할 수 있는 것 중에 자바기반의 유명한 hadoop 이 있고,
그리고 C++ 기반의 naver 의 오픈소스 coord 가 있읍니다.
hadoop 은 NIO 를 사용하고 있으니 충분히 고성능 처리가 되어 있다고 볼 수 있지만,
coord 는 C++ 기반이면서도 시대에 뒤떨어진(?) select 를 사용하고 있읍니다.
coord 관련 세미나에서 개발자분에게 '작업' 을 전달받는 서버노드 측에서
네트워트 응답 처리가 고속이어야 할 텐데 어떤 방식으로 응답하느냐고 질문했더니
select 를 사용한다고 대답하시면서 멋쩍게 웃으시더라구요.(ㅎㅎ)
이것 자체는 별 문제는 안됩니다.
이 부분 라이브러리가 존재 하니까 나중에 리펙토링하면 됩니다.

실제 문제는 "설계, 특히 작업 쓰레드 모델을 어떻게 정교하게 설계할 것이냐" 입니다.
분산처리를 하는 경우에도 각 노드 컴퓨터마다 역시 적절한 쓰레드 모델이 필요합니다.

흔히 코딩하기전에 설계를 먼저 해야 한다고 알고 있읍니다.
그런데 이게 실제적으로는 잘 지키기 어려운게 손가락으로 코딩을 하면서
어떤 설계에 대한 밑그림을 그리게 되는 경우가 많아 보입니다.
저야 초보라서 그렇다지만 다른 분들도 많이 이렇게 하는 것 같습니다.
그리고 이렇게 설계부터 하지 않고 코딩해 가면서 중간중간 설계를 하는 것이
(결과가 안나온다면 문제겠지만) 그렇게 나빠 보이지도 않습니다.

그런데 멀티쓰레드, 병렬 프로그래밍이라면 얘기가 좀 달라질 듯 합니다.
각 쓰레드가 독립적으로 작업한다면야 문제가 아니지만 서로 통신을 해야 하는 경우라면
그 복잡도가 폭증하게 되는데, 잘못된 메모리 참조로 프로그램이 중간에 뻗을 수도 있구요,
특정 쓰레드가 Dead Lock 에 빠질 수도 있읍니다. 더 웃긴 것은, 같은 작업을 하는
N 개의 작업쓰레드에서 그 중 하나나 두 개가 슬며시 Dead Lock 에 빠지면
나머지 작업쓰레드가 분명히 돌고 있기 때문에, 여전히 어떤 작업을 할 것이고,
따라서 사용자는 Dead Lock 에 빠졌는지 조차 모르게 된다는 것입니다.
그래서 로그를 남겨보니, 로그에는 이상이 없어서, 로그 출력을 지웠더니 다시 재발하고...
이런 얘기는 개발자들이 이미 다 알고 있는, 별로 새로울 것도 없는, 멀티쓰레드 프로그래밍에서
가장 흔히 발생하는 사례들입니다. 이런 것들을 막을 수 있는 근원적인 방법은 없을 것 같구요,
그나마 약간의 접근법이라도 찾는다면 초기 설계에 상당히 공을 들여서
Dead Lock 상황이나 잘못된 메모리를 참조할 수 있는 경우를 미리 예측하고 방비하는게
할 수 있는 최선 같습니다.

그렇다면 멀티쓰레드 프로그래밍에 있어서 설계란 무엇일까요.
이 질문에 대한 대답도 쉽지 않은데, 저라면(물론 얕은 경험으로)
1) "쓰레드 아키텍쳐"와,
2) "동기화영역에서 수행되어야 하는 작업(코드)의 기획" 그리고
3) "단위 테스트에 관한 전략" 등이 설계에 중요한 부분을 이룬다고 말하고 싶습니다.

"쓰레드 아키텍쳐" 를 그린 다음에, "동기화영역에서 수행되어야 하는 작업"을 확정한 후,
"단위 테스트 사양서" 까지 나와준다면 좋을 것 같구요, 그 중에 1) 2) 는
초기에 나와줘야 하고 3) 은 코딩하면서 천천히 생각해도 될 듯 합니다.
1) 과 2) 를 완성한 다음에는 또 그것을 제 3 자에게 보여주고
다시 한 번 검증을 하는 것도 중요할 것 같습니다.
사람인 이상 실수할 수 있기 때문에 검증을 받지 않은 체로 "쓰레드 아키텍쳐" 나
"동기화영역의 기획" 에서 오류가 있는 지를 모르고 그대로 프로그램을 짜다가,
중간이나, (더 운이 나쁘면) 프로젝트의 막바지에 Dead Lock 같은 무서운 상황이 벌어지면,
그때의 리스크는 태산처럼 부풀어 오를 것 같습니다.

"단위 테스트" 도 일반적인 "단위 테스트" 와는 좀 다르다고 보는데,
일반적으로 단위 테스트를 할 때에는, 일어날 수 있는 여러 상황을 상정하고,
그 상황별로 테스트를 하게 됩니다만, 멀티쓰레드 프로그래밍 시의 단위 테스트라면
여러 상황을 예상하는 거야 어렵지 않지만, 예상되는 그런 상황들을 만드는 것 자체가
(때에 따라 아주) 복잡할 수 있읍니다.
(물론 "여러 상황을 예상하는 것" 조차 어려울 수 있읍니다.)

그 한 예를 소개합니다.
윈도우에서 IOCP 객체에 소켓에 대하여 비동기 송/수신을 요청합니다.
요청할 때 소켓은 자신이 속한 소켓 클래스 컨테이너의 노드 포인터도 같이 등록을 해줍니다.
일정 시간 동안 반응이 없자 해당 소켓을 종료하고 해당 소켓 객체를
소켓 클래스 컨테이너에서 삭제합니다. 삭제한 바로 그 순간, 윈도우 커널에서
소켓 종료 전에 비동기 송/수신의 완료가 있었다면, 그 완료정보를 소켓 종료후에도
어플리케이션으로 통보할 수 있읍니다. 이미 소켓은 종료되어 있고,
소켓 관련 정보를 담고 있는 소켓 클래스 또한 메모리에 없는 상태입니다.
이때 이 소켓의 완료통보가 떨어지면서 소켓이 속한 컨테이너의 노드 포인터가 함께 전달될 것이고
이 노드포인터는 이미 유효하지 않기 때문에, 이 노드 포인터로부터
메모리에 없는 소켓 클래스 객체를 참조하면 큰일납니다.
이 상황이 제대로 처리가 되고 있는지 단위 테스트를 할려고 합니다.
어떻게 이 상황을 시물레이션해서 정확한 처리 여부를 테스트할 수 있을까요.
리눅스에서 EPOLL 을 사용하는 경우라면 또 어떻게 시물레이션해야 할까요.

그렇기 때문에 멀티쓰레드 프로그래밍에 있어서,
코딩전 설계는 다른 프로그래밍 보다 중요하다는 생각입니다.
따라서 1000 개의 데이타를 랜덤하게 추출하는 저 기술문제에서도
실제 코드뿐만 아니라 코딩전 설계도를 같이 작성하게끔 하는 것도
프로그램 실력을 평가할 수 있는 방법이 될 것 같구요, 개발자에게
코드뿐 아니라 설계도를 요구하는 것이 좀 가혹할 수 있다면
(따지자면 저는 좀 가혹하다고 생각하는 쪽입니다.^^)
"설계도" 까지 제출하는 경우에는 가산점을 주는 등의 방법을 생각할 수 있읍니다.

이렇게 해서 설계도 및 코드를 동시에 받는다면 해당 코드는
좀 더 완성도 있는 코드일 확률이 높을 것 같구요,
평가항목도 좀 더 다양해 질 것 같습니다.
흔히 객체지향의 정도를 표현하는 말중에 응집성, 커플링, 모듈화 등의 용어를 사용하는데
심사를 할 때, 이렇게 각 부문별로 점수를 매기는 것도 방법일 것 같습니다.
또한 코드작성까지가 부담이라고 느끼는 개발자를 위해서,
자세한 설계도만 제출받는 것도 나쁘지 않을 것 같습니다.
"보기 좋은 떡이 먹기에도 좋다" 라는 속담도 있지 않습니까.

기술문제가 꼭 멀티쓰레드에 관련된 문제가 아니라 할지라도
코딩 전 "설계" 에 대한 고민을 하게 하는 것은 좋은 것 같습니다.

최종적으로 이런 것들이 건전한 소프트웨어 문화에
뭔가 일조(一助)가 되지 않겠나 생각하면서
큐브리드가 DB 분야에서 뿐만 아니라 이런 문화적인 부문에서도
선전하는 기업이기를 바라면서 글을 마칩니다.

  • ?
    정병주 2009.04.23 05:50
    장문의 글 잘 읽었습니다. 전사 공유를 하겠습니다. ^^
  • ?
    초보대왕 2009.04.24 01:20
    제 글을 끌까지 읽어 주시는 분이 있긴 있네요. ~~
  • ?
    정병주 2009.04.25 00:49
    읽는데 힘들었습니다. ^^
  • ?
    초보대왕 2009.04.25 04:55
    아, 쓰는데도 힘들었읍니다.~~ 그러고 보면 "참 쉬운게 없구나"하는 생각이 듭니다.(^^)
  • ?
    빈 터 2009.07.16 20:23
    재밌는 문제네요. 늦었지만 의견 추가.

    number stream. stream 인데 분산처리가 되나요? 분산처리를 언급한 건 잘 납득이 안갑니다.

    완벽한 분포의 균일을 원한다면 좀 복잡하겠지만 대충 해도 되는 정도의 필요라면 이런 방법은 어떨까 싶습니다.

    1000개가 필요하다니 1000짜리 배열을 만듭니다.
    처음 1000개는 나오는대로 배열에 집어 넣습니다.
    1000개를 넘어서서 부터는 하나 건너 하나씩 짝수번 배열에 넣습니다.
    그러면 만약 2000개가 나왔다면 정확히 반은 1000번대 이하, 나머지 반은 1001~2000번대가 되겠죠.
    2000을 넘어서서부터는 3번째로 나오는 수를 3의 배수에 해당하는 배열에 집어넣습니다.
    마찬가지로 3000을 넘어서서부터는 4의 배수에 해당하는 배열에 넣습니다.
    물론 이렇게 했을 경우 그 분포는 완전 균일하지는 않습니다. 
    하지만  대략 필요한 정도의 분산은 되지 않을까요?

List of Articles
번호 제목 글쓴이 날짜 조회 수
103 홈페이지가 새 옷을 입었네요!! 2 진이 2009.07.14 19557
102 CUBRID 프로젝트 6월 소식지~ CUBRID_DEV 2009.06.27 18635
101 3회 CUBRID Inside 생생한 세미나 현장 속으로~ CUBRID_DEV 2009.06.25 33334
100 CUBRID를 어떻게 함께 만든단 말인가?? 2 1 file CUBRID_DEV 2009.06.16 26541
99 큐브리드 매니저 2008 R2 - 맛뵈기 프리뷰 정병주 2009.06.16 49073
98 2009 3rd CUBRID Inside를 다녀와서! 2 시난 2009.05.27 36844
97 오픈소스SW 저작권 인식제고를 위한 공모전 3 정병주 2009.05.22 41692
96 (CUBRID후원) 여성개발자모임터 커뮤니티 세미나 CUBRID_DEV 2009.05.20 20000
95 (CUBRID 후원) 우분투 사용자 커뮤니티 안내 2 file CUBRID_DEV 2009.05.20 23154
94 CUBRID Inside 3회 참가 신청 받습니다. CUBRID_DEV 2009.05.19 18899
93 Java 저장프로시저... 3 초보대왕 2009.05.14 29415
92 헛...;; 2 secret 혜꽁이양 2009.05.13 6
91 큐브리드 다운로드 4만건 돌파 기념 간식 배달 이벤트 - 축하 메시지 남기기 ^^ 291 2 file admin 2009.05.13 219449
90 다운로드 월 3000건 돌파, 축하합니다. 4 flypig 2009.04.30 24405
89 CUBRID 오픈소스 프로젝트 4월 소식지 2 CUBRID_DEV 2009.04.25 23189
» 큐브리드 면접문제를 회고하며... 5 초보대왕 2009.04.22 34291
87 벌써 4월말이 되어 가는데... 1 flypig 2009.04.22 17811
86 오라클이 썬을 인수함 1 flypig 2009.04.21 18083
85 큐브리드양을 소개합니다. 1 정병주 2009.04.07 44543
84 안녕하세요~! 2 루키민규 2009.03.30 18428
Board Pagination Prev 1 ... 3 4 5 6 7 8 9 10 11 12 13 Next
/ 13

Contact Cubrid

Tel. 070-4077-2110 / Email. contact_at_cubrid.com
Contact Sales