시스템 설계쪽 면접 문제입니다. 다양한 답변,토론을 희망합니다.

Sailor_moon의 이미지

안녕하세요 . 정말 정신이 하나도 없네요 .
상당히 어려운 면접 문제를 제시받아 , 그냥 제대로 풀어보지도 못하고 왔습니다. (챙피하다 싶을정도입니다 .. )
뭐 알고리즘 문제나, 간단한 수학 문제 해결이 아니라 이건 완전 경험에서 우러나와야 하는거같은데 ....

여러 분들의 의견을 구해본다면 혹 추후 스터디에라도 도움이 되지 않을까 하여 , 적어봅니다. 최대한 기억과 당시 면접보며 캡춰했던 구글doc에 의존하여 다시 적은 것이라, 확실치 않은 부분이 있을수도 있습니다만 , 정말 이렇게 정신없이 털린 경우도 처음이네요. 워낙에 시스템쪽은 약하기도 했지만, 회사들 어플라이를 잘못했다는 느낌입니다. 스카이프 끊으면서 울먹거리지 않을려고 애쓰느라 혼났네요 ...
자괴감도 지금 엄청납니다.총 두문제 입니다.

* 이제 막 당국의 구제금융을 통해 회생한 은행의 데이타 스토리지 및 복구 시스템을 구축하려 한다고 가정합니다.
많은 수학자들이 과거의 주식시장 실적을 보고, 앞으로의 일을 예측할 수 있는 통계적 툴을 개발하여 이 시스템에 도입했구요. (우리는 더이상 구제금융신청과 같은 불운한 사태를 원하지 않습니다). 가장 신뢰도 높은 데이터는 각각 2500 개의 다른 매일 거래가 10만 거래가 넘는 주식시장에서 수집됩니다. 각 주식시장별 데이터 히스토리 는 최대 10년 까지는 보관이 되어야 합니다. 또한 , 수백개의 trace, 혹은 월별 , 연도별 현황을 시뮬레이션 할 수 있어야 합니다. 우리 회사는 위와 같은 시스템을 설계하고 가동시키려 하는데 천만달러,즉 약 100억원 정도의 예산이 있습니다. 대역폭(bandwidth) 는 어느정도로 설계해야 겠습니까 ? (거래 단위별 기록은 약 100 바이트 정도라고 가정합시다 껄껄껄 ... 이라고하시더군요)

* 우리는 최근에 새로 시작한 핵 물리학 시뮬레이션 연구를 위한 새로운 컴퓨터 시스템을 구축하려합니다. 이 시뮬레이터는 우주(universe)를 모델화한 상호작용하는 입자(파티클)시뮬레이션을 할 예정입니다.(아마도 각 행성과 항성을 파티클로 두고 계산하려는 듯 합니다.) 이런 파티클들은 각각 시간(t)별로 물리학 공식을 따라 독립적으로 움직이게 됩니다. 각 시뮬레이션들은 초당 수백만번으로 분할되어 작동될것입니다.모든 파티클들이 독립적으로 움직이는 계산을 하는거기 때문에 어떤 입자가 어디서 끝날지는 아무도 모릅니다. 자 이런 우리의 새 시뮬레이터를 위한 시스템을 도입하려하는데, 시뮬레이션 되는 파티클들이 메모리에서 차지하는 공간이 800 기가바이트는
넘지 않았으면 합니다. 자, 매 월별로 최대한 많은 실험을 하려면 당신같으면 어떤 시스템을 구상하시겠습니까 ?

dymaxion의 이미지

제가 그쪽 분야랑 별 상관이 없어서 도움되지는 못하지만
면접에서 저런 흥미로운 문제를 받았던 게 재미있는 경험이셨을 듯 하네요.
추측컨데 외국계 업체 같기도 하구...

두번째 문제의 경우엔 '핵물리학'이라는 분야와 '우주', 그리고 '파티클'이라는 키워드로 봐서는
현재의 우주라기 보다는 빅뱅 직후의 초기 우주 시뮬레이션을 염두에 둔 문제 같다는 생각이 드네요.
즉 '파티클'은 항성,행성이 아니고 글자 그대로 소립자들을 말하는 것 처럼 들리고요.
초당 수백만번 분할해서 자세히 분석하겠다는 것도 그런 초기 우주니깐 필요하지 않나 싶어요.

각각의 입자를 기술하는 구조체를 정의하고, 각각의 입자들 간의 상호작용을 일일이 계산해야 할테니
정말 대규모 시스템인 것 같은데
아주 아주 단순하게 비전문가인 저의 생각으로는 그냥 딱 떠오르는게

"슈퍼 컴퓨터를 산다" 라고 답안을 낼 듯...

(-_-); 후다닥 (도망)

======================================
Mechanical Engineer
DymaxionKim.github.io
======================================

Sailor_moon의 이미지

정말 이렇게 챙피한적도 처음이었네요....아 그리고 그럴수도 있겠네요.
아마도 초창기 시뮬레이션을 하는 것일수도 . 여하튼 파티클을 단순하게 컴퓨터 그래픽스에서 쓰는 것 처럼
뿌려버리는게 아니라 입자 하나하나 계산하려면 진짜 어마어마한 시스템이 필요할거같다 .... 라고 하기엔
너무 주어진 게 자세하더군요 ... 에휴

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

익명 사용자의 이미지

저정도 문제를 내는 회사가 어디인가요??

Sailor_moon의 이미지

미 동부의 금융권 회사들이예요 ;;;

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

onion의 이미지

차근차근 생각해볼만한 문제인거같네요.
대역폭의 설계야 다다익선이니깐 인피니밴드등을 사용하면 될거고...(돈만 많으면)
제가봤을때 면접에서 묻고싶은건 정확한 수치가 아니라 어떤식으로 system을 설계할 것인가에 대한 방향성을 얘기하는게 아니었을꺼 합니다.

1번문제에서 저라면....
1. 보관되는 스토리지가 있어야 할거구요
2. 100000 * 2500 * 100byte = 25000000000 > 하루에 23G정도 되는 log데이터가 쌓인다는거네요
3. 이 경우에는 1시간정도 단위로 데이터를 splite해서 디렉토리에 나누어 넣으면 될듯합니다.
4. 데이터를 process하는 서버가 여러대라면 storage서버의 대역폭이 중요하다는건데 1시간에 1G정도 쌓이는거니깐 각 서버별로 SAN을 나눈다고해도 일반적인 SAN storage면 되겠네요.(3G정도의 san switch대역이면 충분할듯염)
5. 백업이라는건 중요하니 백업서버는 따로 두면 되겠습니다. 베리타스를 쓰던 뭘 쓰던.... 그건 os마음
6. 결과적으로 몇개의 point에서 data를 받아내느냐가 관건인데 data의 input의 개수만큼 서버만 있으면 그 다음은 SAN으로 할것인가 NFS스타일로 할것인가가 문제..... 그건 윗선의 판단에 맡겨야겠죠. 저라면 NFS스타일.(어차피 data가 중복으로 오는건 아닐거니 쌓기만 하는거라면요)
7. 서버와 NFS단으로 간다면 switch를 분리해서 대역폭을 최대로 이끌어내는게 관건이겠네요.

2번문제에서 저라면
1. 클러스터링처리
2. 해당 알고리즘을 전담으로 프로그래밍하는 팀
3. 하드는 별로없는 cpu만 빵빵하신 1u머신 수백대
4. 데이터를 저장할 NFS타입의 스토리지
5. NFS단과 서버단을 분리할 별도의 스위치(인피니밴드면 좋고.. 아니어도 10G면 충분하죠)

이정도의 답을 했을거같네요.

이걸로 떨어지면 저도 자격미달! ㅋㄷㅋㄷ

-----새벽녘의 흡혈양파-----

snowall의 이미지

2번문제에서 아마 10G스위치로는 부족할수도 있어요 ㅎㅎ 다 합쳐서 800G정도의 데이터가 네트워크 메모리 안에서 돌아다닐테니까요.

인피니밴드 쓰는게 좋을듯...

그리고 코어당 램을 8G이상 16G는 물려야 할거예요

피할 수 있을때 즐겨라! http://melotopia.net/b

onion의 이미지

한번에 메모리로 로딩되는 데이터를 생각한다면 메모리야 다다익선이죠 :D

하지만 작은단위를 빠르게 연산하는거라면 상관없다고 생각합니다. (그렇다고 적어도 문제)

pattern matching을 하는거라면 메모리가 많아야 좋겠지만
수치연산이라면 굳이 많을 필요는 없다....
이정도의 차이가 있지 않을까.........생각해봤네요..^.^;
(생각의 방향등이 틀렸다면 지적 부탁드립니다)

-----새벽녘의 흡혈양파-----

snowall의 이미지

수치해석에서도 격자가 촘촘해지면 메모리가 많아져야하는 상황이 벌어지죠.

입자 시뮬레이션이면, 입자 수에 따라 계산량도 많아지고 메모리도 많아져야하고요...

피할 수 있을때 즐겨라! http://melotopia.net/b

Sailor_moon의 이미지

아마도 정확한 값보다는 시스템 설계를 어느 방향으로 잡아가나를 보려고 한것 같은데 ,
막상 그 당시엔 수치에만 집착하다보니 .... 큰 숲을 못본듯 합니다.

2번 문제에서의 클러스터링 처리는 무엇을 의미하는 것인가요 ? 그냥 패러랠 컴퓨팅을 의미하시는 것인지 ?
혹시 설명좀 해주실 수 있나요 ?

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

onion의 이미지

제가 적은건 연산이라는 측면에서 MPI 또는 PVM을 의미한거였습니다.
혼돈이 있으셨다면 죄송합니다..(꾸벅)

-----새벽녘의 흡혈양파-----

익명 사용자의 이미지

PVM... 요즘은 안쓰죠. 이건 15년전에 끝난 거.
차라리 CUDA를 ㅎㅎㅎ

Sailor_moon의 이미지

하드는 별로 없는 CPU 만 빵빵한 1u 머신에 대해 궁금한 점이 있습니다. 구지 CPU 에만 치중하는 이유는
파티클의 연산이 위주이기 때문에 별로 저장해둘 데이터는 크지 않아서 인가요 ? 혹은 저렇게 구성하는 시스템이 갖는 장점이 있는건지요 ?

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

Sailor_moon의 이미지

코어당 16 기가 이상씩 물려야 하는 이유가 있을까요 ?

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

shint의 이미지

개인PC를 사용한 분산처리를 하겠습니다.

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

익명 사용자의 이미지

그러니깐 어떻게요?

shint의 이미지

ㅇ_ㅇ;;; 제가 그냥 짜서...

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

익명 사용자의 이미지

800G의 메모리를 동시에 사용하는 구조를 가져가게 되면 메모리 대역폭에 대해서 고민을 해야 합니다.
실제로 ddr3의 듀얼채널을 사용하더라도 대역폭이 25g 이내 이거든요.

메모리 사용에 대한 최소화 최적화를 통해 위에서 말씀 하신 것처럼 클러스터링처리를 해주어야 하겠죠..

태훈의 이미지

딱 봐도 맵리듀스/분산파일시스템 필요한 분야네요. 저라면 Hadoop을 쓰겠습니다.

하둡/Hadoop

Just do it!

Sailor_moon의 이미지

안녕하세요 ! 리플 여기에도 ..감사합니다 . Hadoop 은 들어본적 있는데 , 맵 리듀스라는건
대략 무엇이죠 ? 왜 이런 분야에 좋을까요 ?

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

태훈의 이미지

- 확장성
- 대용량 처리
- 분산 처리

이러한 요구사항이 필요한 분야에 hadoop과 같은 분산 시스템이 적합합니다. 문제에서 요구하는 시스템에서 필요한 특징을 뽑아보면 저런 것들이 있네요.

Map과 Reduce 연산을 통칭해서 MapReduce라고 부릅니다.

Map 연산은 각 데이타 셋에 동일한 연산을 적용합니다. 분산 컴퓨팅에서 대용량 데이터를 쪼개서 병렬 처리하는 과정에서 사용합니다. 파이썬의 map() 함수를 생각하시면 될 듯하네요.
Reduce 연산은 쪼개진 데이타를 합칠때 사용합니다. 관련된 데이터끼리 묶어서 처리해야 하는 작업에 사용합니다.

자세한 내용은 MapReduce 논문[1]과 하둡 가이드 문서[2]로 대신 하겠습니다.

[1] MapReduce: Simplified Data Processing on Large Clusters, http://usenix.org/events/osdi04/tech/full_papers/dean/dean.pdf
[2] Hadoop Guide(한글), http://pds21.egloos.com/pds/201101/18/63/Hadoop_Guide_ext.pdf

Just do it!

태훈의 이미지

구글, 페이스북, 트위터등에서 사용하고 있습니다.

Just do it!

익명 사용자의 이미지

2번의 시스템에 하둡 이런걸로 구축하는 것은 "이상"이고요 현실은
scalable NAS를 만들면 됩니다. 하둡은 이론만 거창하지 현실적으로 직접 쓸 수 있는 시스템은 아직은 아닙니다. Scalable NAS를 구축하기 위해서 사용할 Clustering File System으로 어떤것을 도입할 것이냐를 고민해야하는데, SNFS, Luster 등도 역시 하둡못지 않게 이론적일 뿐 현실에서의 안정성은 문제가 됩니다.

네트워크 설계는 n-body problem의 경우 각 개별 입자간의 해석에 통신량이 많아서 infiniband를 사용해서 구성해야하며, 스토리지 네트워크는 별도로 사이징을 해야합니다만... 의외로 N-body problem의 경우 write는 딱 한줄로 끝나므로 스토리지보다는 주로
메모리 및 CPU 사이징이 중요합니다.

각 입자별로 x,y,z 좌표 값, u, v, w 같은 속도 벡터 값과 각 값의 미분치를 기록할 변수가 파티클 한개당 잡혀야하고 8바이트(더블)로 잡았을 때 메모리 총량이 나옵니다만, 통상적으로 static으로 잡을 공산이 크므로 메모리를 충분히 잡아둬야지요.

그와 함께 충분한 실험을 하기 위해서는 prarametric study가 필요하므로 좋은 job scheduler를 넣어야 합니다.

증권사 시스템은 최근에 나오듯이 big data 처리 시스템인데 이건 주로 read가 많으므로 역시 scalable NAS가 가장 좋은 구조입니다만, IO의 속도도 중요하므로 각 scalable NAS에서의 개별 I/O 시스템 및 HDD를 뭘로 하느냐도 중요하지요.

증권사 시스템의 경우 스토리지시스템으로 가는 총 네트워크 양이 각 서버의 하드웨어 네트워크 양의 합을 바쳐주도록 사이징을 해야하므로, 대략 서버가 기가비트라면 스토리지는 10G를 고려하면 좋겠지요.

Sailor_moon의 이미지

감사합니다 ..ㅠㅠ ...현업종사자신가요 ? 책이나 공부할 수 있는 곳좀 추천해주세요 ....

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

익명 사용자의 이미지

책이요? 제가 안쓰면 아직 없습니다. 게을러서 못쓰고 있습니다. 저한테 고객이 연락하면 제안서는 보냅니다. 물건 살거면~

익명 사용자의 이미지

그리고 미동부의 금융권 회사라면, 구글에서 "HPC in Wall Street"로 검색하면 비슷한 내용 및 비슷한 거 판 사례 등등 나옵니다.

익명 사용자의 이미지

근데 100억 예산이면 뭐 설계할것도 없이 딱 나오는데요???

서버 약 600대 (12 core x 600 = 6000~7000 core) 하면 대략 800만원씩 잡아서 서버 비용 50억.
스토리지는 저정도 규모면 적어도 1차, 2차 잡아야하고, Scalable NAS 솔루션으로 H사의 Ibrix를 쓰던지, EMC의 isilon을 사용하던지 Dell의 Compellent를 묶어서 쓰던지 한 20억, 네트워크(10G 등등)해서 내부 네트워크로 약 5억, 인피니밴드 10억, 기타 구축비, OS 및 Job Scheduler (LSF 로 한 2~3억) 해서 100억이면 끝이죠.

사이징 하나마나 누가 해도 그냥 저정도면 되요... 이건 제안서를 써도 일주일이면 되는 표준 사양인데, 고객이 면접을 본 이유는 업체가 이렇게 제안을 하면 왜 그렇게 제안을 했는지를 볼 수준의 직원이 필요한거고, RFP를 낼려고 해도 알아야 내니까 물어보는거군요.

골드만삭스에 대략 12000대 짜리 파생상품 시스템 있을거고요, 보험사에는 Risk Management 시스템으로 갖고 있을거여요.

그리고 금융권에서 N body problem을 물어보는 이유는 결국 이게 방정식만 다르지 금융사의 리스크 메니지먼트 시스템의 문제가 핵물리학의 n body problem과 동일한 구조로 시스템 설계 및 알고리즘을 갖고 있기 때문이지요.

그래서 Qunta라고 부르는 금융공학출신들의 백그라운드가 대부분 물리학인거지요.

날 뽑지...

Sailor_moon의 이미지

저 같은 갓 학부 출신은 택도 없는 대답이었습니다.... 익명 사용자님이
뽑히셔야 했을듯 합니다.

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

익명 사용자의 이미지

그런데 이런 일은 흔히 말하는 개발자가 할 일은 아니고, SE가 하거나 Presales라고 부르는 조직에서 해야할 일인데, 이런 시스템을 설계(결국 납품이지요)해볼려면 현업에서 해도 좋겠지만, HP나 IBM같은데서 Presales일을 하면 금새 배웁니다.

문제는 학부졸업한 신입이 하기에는 좀 힘든 일이라서 오히려 Global IT 회사(그래봐야 HP, IBM 정도?)의 파트너사에서 일을 배워서 나중에 옮기는게 더 좋을 수도 있지요.

해볼 생각 있으세요? 선수가 필요한데...
물론 저는 지극히 작은 갑을병정무기에서 "기"정도 되는 중소기업에서 저런일을 합니다만...

Sailor_moon의 이미지

사실 이런 시스템 설계쪽은 아예 모르고 있다가 오히려 요 며칠새 , kldp 에 토론 올라오는거 보고 관심이 확 생겼습니다 ...

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

number3의 이미지

Twitter’s Plan to Analyze 100 Billion Tweets
http://highscalability.com/blog/2010/2/19/twitters-plan-to-analyze-100-billion-tweets.html

DataSift Architecture: Realtime Datamining At 120,000
http://highscalability.com/blog/2011/11/29/datasift-architecture-realtime-datamining-at-120000-tweets-p.html

Facebook's New Realtime Analytics System: HBase To Process 20 Billion Events Per Day
http://highscalability.com/blog/2011/3/22/facebooks-new-realtime-analytics-system-hbase-to-process-20.html

http://highscalability.com/blog/category/facebook (필요한 내용을 찾아보시면..)
<-- 이게 도움이 될 듯 하네요.

검색 플랫폼의 변화: 구글에서 Hadoop까지 -한재선
http://www.slideshare.net/Channy/hadoop-432075

Dremel: Interactive Analysis of Web-Scale Datasets
https://profiles.google.com/goog.research.buzz/buzz/WsARqxc7d7R
@xguru: 구글의 분산 다단계 컬럼 데이터베이스 "Dremel" 에 대한 논문 http://j.mp/ijqhG6 1조개 이상의 레코드에 대해서도 순식간에 쿼리가능. 맵리듀스의 보완재. 구글의 여러 서비스에 이미 사용중

How Google Serves Data from Multiple Datacenters
http://highscalability.com/blog/2009/8/24/how-google-serves-data-from-multiple-datacenters.html

The Three Ages Of Google - Batch, Warehouse, Instant
http://highscalability.com/blog/2011/8/29/the-three-ages-of-google-batch-warehouse-instant.html

The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines
http://research.google.com/pubs/pub35290.html

이 정도면 충분하지 않을까요?

익명 사용자의 이미지

우선 일일 거래량 10만 건의 증권시장에서 2500건의 고신뢰도의 데이터를 추출하는 작업이
먼저 선행되어야 겠네요.

여기서 조건은...

조건 1: 하루 거래량 10만건
조건 2: 2500 개의 고신뢰도 데이터

일단, 증권거래소(NASDAQ으로 가정합니다..) 서버에서 10만건의 데이터를 가져올 때의 대역폭
계산이 먼저 선행되어야 하겠죠.

앞서 문제의 선행조건이 거래 당 100 Bytes라고 하셨으니 100,000 * 100 = 10,000,000 Bytes
이게되죠.. 하지만 여기서 일간 데이터 갱신횟수도 생각해봐야겠죠.. 예를 들어 주가 한 종목의 가격
갱신이 얼마 만에 한 번씩 될까요? 인터넷 검색에서 대략 1초 정도라고 하더라고요..

그렇다면 여기서 나올 수 있는 일일 총 데이터 전송량은 100,000 건 * 100 Bytes * 450 분(NASDAQ 기준) * 60 초
270,000,000,000 Bytes, 약 270 GB 가 되겠죠. (계산의 편의 상 1 GB = 1000 MB)

자 그렇다면, 여기서 하루에 계산할 수 있는 10만 건의 데이터에서 고신뢰도의 데이터를 추출하는데 분산처리가
당연히 적용이 되겠죠.. 2500개의 데이터를 추출한 결과 값을 얻기 전 까지는 분산처리용 서버간 네트워크 대역폭은
외부 네트워크와 동일하거나 더 커야겠죠.

여기까지는 간단히 생각해 볼 수 있는 것인데, 문제는 왜 대역폭이 커야 하나? 입니다..
제가 생각한 답은 향후 10년 동안의 데이터를 모아서 얼마나 빠르게 계산해 낼 수 있느냐는 것입니다.
즉, 기존의 데이터들을 모아서 어떤 식으로 빠르게 검색, 정렬, 추출 할 것인지가 가장 큰 문제지요.
극단적으로, 10년 동안의 2500건 데이터 전부를 처리해 원하는 결과 값으로 추출할 수도 있고요.
그러한 경우의 데이터 량을 계산해보면 (편의 상, 1년은 365일로)

(270 GB / 100,000 건) * 2500 건 = 6.75 GB
6.75 GB * 365 일 * 10 년 = 약 2.46 TB

한 마디로 저 위의 극단적인 계산을 할 경우 2.46 TB의 데이터를 한 번에 분산처리시스템에 뿌려줄 수 있는
네트워크가 필요한 것이죠. 더 큰 문제는 저런 데이터 계산이 필요에 따라 하루에도 몇 번 씩 지속될 수 있다는
점입니다. 따라서 계산된 대역폭에 +20% 혹은 +30% 정도 여유를 더 두어야 할 것 같습니다. 덧붙여 최소한
이중화 설계도 필요하다고 봅니다.

한 가지 더, 분산처리를 할 때 어떤 데이터 형식으로 처리할 지도 중요할 것 같습니다.
일반적인 CSV로 할 지 아니면 MongoDB 같은 NoSQL DB 처럼 JSON으로 처리할 지요.

이상 어설픈 답이었습니다. (틀려도 너무 뭐라고 하지 마세요 ㅜ.ㅜ)

unixcruiser의 이미지

깜빡하고 로그인 안하고 적었습니다..

익명 사용자의 이미지

면접시험 볼려고 미리 자료수집 하는 것처럼 보입니다.