예전에 구글에서 일하시는 한분이 본인은 시스템 디자인 인터뷰가 가장 어렵다고 이야기한적 있다. 코딩인터뷰의 경우 문제 set이 존재하기때문에 문제를 많이 풀어보면 되지만, 시스템 디자인은 질문을 예측하는것도 어렵고 정답이란것도 존재하지 않기때문이다. 구글에서 시스템 디자인 문제를 검색해봐도 결과에 정답은 나오지 않는다. 시스템 디자인은 대부분 스케일 문제를 다룬다. “수억명의 사람들이 너의 서비스를 사용한다면 너는 어떻게 이 문제를 해결할래?” 이런 질문에 경험에서 우러나오는 사골같은 답을 할수 있다면 얼마나 좋을까마는 사실 그런 시스템을 다 만들어본 엔지니어는 극히 소수일 것이다. 나 역시 시스템 분야로 PhD도 했고 수년간 같은 분야에서 다양한걸 만들었지만 여전히 이 질문은 어렵다. 그러나 디자인 인터뷰 역시 살아남는 방법은 있다. 그 방법이란 좀 싱겁지만…,

“공부를 많이하면 된다.”

우선 내가 그동안 받았던 디자인 질문들을 나열해보면 이렇다.

• Queue 시스템을 디자인해라
• Twitter를 디자인해봐라
• TinyURL 디자인해봐라
• Yahoo의 Stock Quote 시스템을 디자인해라
• Elevator 시스템을 구현해봐라
• Hadoop의 namenode를 새로 디자인해봐라
• (AI 관련팀) 우리 시스템을 네가 디자인해봐라

4-5명과의 인터뷰중 시스템 디자인은 최소 한차례, 많게는 두세번 질문을 받게된다. 시스템 디자인에서 인터뷰어가 파악하고자 하는것은 크게 세가지로 볼수 있다:

1. 커뮤니케이션을 잘 하는가?
2. 문제를 정확히 알고있는가?
3. 괜찮은 디자인을 할수있는가?

디자인 질문은 의도적으로 모호하게 주어진다. 예를들어 Queue 시스템을 디자인하라는 질문은 사실 밑도끝도 없다. <어떤 Application이 Queue를 사용하는가?>, <Queue에는 무엇이 들어가는가?>, <Producer/Consumer의 숫자는 몇개인가?> 등 디자인에 꼭 필요한 디테일이 빠져있다. 그래서 디자인 질문을 받았을때 처음 해야하는것은 <질문>이다. 여러번 충분한 질문을 통해서 인터뷰어가 생각하는 진짜 문제를 파악해내고 여기에서 Requirement를 알아내는것이 첫 단계에서 반드시 해야할 일이다. 이 과정에서 인터뷰어는 지원자의 커뮤니케이션 능력을 평가한다. 혹시 예전에 비슷한 시스템을 구현해본적이 있다고 질문을 생략한다면 이는 인터뷰가 망하는 길로 가는 지름길이다.

내가 받았던 디자인 질문중 특히 좋았던 것 한가지는 엘리베이터 시스템을 디자인하라는 것이었다. 무한하게 많은 수의 엘리베이터가 늘어서있다고 가정하고 사용자가 각 층에서 누르는 Up/Down 버튼에 맞추어 어떻게하면 최적의 서비스를 제공할수 있을까라는 질문이었다. 이 질문이 좋았던 이유는 엘리베이터라는 잘 알려진 문제가 그동안 생각하지 못했던 수많은 분산시스템의 컨셉을 드러내기 때문이다. 예를들어서,

• Controller가 중앙에 한개 놓여있고 모든 엘리베이터가 통제에 따른다고 가정해보자. 그럼 Controller가 죽어버리면 엘리베이터의 Availability는 어떻게 될것인가?
• 그럼 엘리베이터를 분산시스템으로 구현해보자. 엘리베이터 사이의 커뮤니케이션이 불안정할때 스케줄이 항상 정확할수 있을까? (CAPS theorem)
• 엘리베이터는 사용자가 버튼을 누른 시간순으로 서비스를 제공한다. 그럼 엘리베이터의 시간은 모두에게 동일하게 흘러가는가? (Vector clock의 개념)

이러한 질문의 의도는 지원자가 시스템에서 발생하는 <문제> 혹은 <컨셉>을 다양하게 알고있는가를 파악하기 위한것이다. 가상의 문제에 대해 대화하면서 분산시스템의 클래식한 문제들 — vector clock, CAPS theorem, distributed consensus, quorum vote, data hashing등 — 을 연상해낼수 있는지를 보는것이다. 뛰어난 인터뷰어일수록 이런 질문을 던진다. 이런 문제에 답하기 위한 쉬운 방법은 없다. 아래에 달린 긴 리스트에서 보듯, 그저 다양하게 많이 아는 수밖에…

마지막으로 디자인 질문에서 파악하고자 하는것은 <괜찮은 디자인을 할수 있는가?> 여부이다. 복잡한 시스템에는 정답이 없다. 다만 괜찮은 답이 있을뿐이다. 여기에서 괜찮은 답이란 디자인의 각 단계에서 어떠한 선택을 해야할때 각 선택의 Trade-off 를 알고 있고, 자신의 선택을 논리적으로 방어할 수 있는 디자인이다. 즉 취할것은 취하고 버릴것은 버리되, 왜 그러한 선택을 하는지는 설명을 할 수 있어야 한다는 뜻이다. 예를들어 트위터를 디자인한다면,

• Relational DB를 Shard해서 사용할것인가 아니면 Cassandra, Dynamo와 같은 분산 key-value DB를 사용할 것인가?
• In-memory cache로 Redis 혹은 Memcached 를 사용할까?
• Push model (모든 follower에게 tweet을 저장) 혹은 pull model (모든 following에게서 tweet을 읽음)을 사용할까?
• Tweet의 아이디는 DB의 Sequential ID를 사용할까 아니면 snowflake와 같은 분산시스템을 따로 만들까?

코딩 질문이 한가지 질문에 optimal 알고리즘을 구현하기위한 것이라면 시스템 디자인은 시스템의 각 파트를 해결하기위해 제각각 여러개의 알고리즘을 끌어와서 큰 스케일에서 동작하는 그림을 보여주는 것이다. 그러므로 좋은 답을하기 위한 핵심은 얼마나 많이 그러한 알고리즘을 알고 있는가의 여부이다. 예를들어,

• 어떻게 분산된 컴퓨터에 데이터를 나눌 것인가 —> Consistent hashing
• 분산 컴퓨터들은 어떻게 자신이 담당할 문제의 영역을 선택할까? —> Paxos algorithm or zookeeper
• 데이터가 복제되어있을때 어떻게 consistency를 보장할까? —> Quorum vote
• 분산 컴퓨터가 어떻게 ID를 고유하게 만들까? —> Twitter’s snowflake
• 데이터 통신의 보안은? —> PKI encyprtion

아래는 내가 그동안 공부했던것들중 인터뷰에서 가장 유용했던 자료들이다. 꼭 인터뷰가 아니더라도 최신의 시스템을 이해하는데 좋은 자료들이라고 생각해 여기에 공유한다. 가장 중요한 자료에는 별점 5개를 붙여놓았다.

[Designing Data-Intensive Applications]
시스템 디자인 준비하기에 가장 좋은 책. 아래의 레퍼런스 대부분 내용을 책 한권에 다 요약해 놨다. https://www.amazon.com/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321

[Distributed Systems]

• https://en.wikipedia.org/wiki/CAP_theorem
• CAP Theorem: https://www.youtube.com/watch?v=hUd_9FENShA (*****)
• http://www.allthingsdistributed.com/2008/12/eventually_consistent.html
• http://michaelnielsen.org/blog/consistent-hashing/ (*****)
• https://lethain.com/introduction-to-architecting-systems-for-scale/
• http://www.aosabook.org/en/distsys.html
• https://www.cl.cam.ac.uk/teaching/0910/ConcDistS/11a-cons-tx.pdf
• http://basho.com/posts/technical/why-vector-clocks-are-easy/

[Distributed Key-Value Database]

• Dynamo: Amazon’s Highly Available Key-value Store (*****)
• Cassandra – A Decentralized Structured Storage System
• Bigtable: A Distributed Storage System for Structured Data
• https://www.slideshare.net/guestdfd1ec/design-patterns-for-distributed-nonrelational-databases
• http://horicky.blogspot.com/2009/11/nosql-patterns.html

[Sharding]

• https://medium.com/@Pinterest_Engineering/sharding-pinterest-how-we-scaled-our-mysql-fleet-3f341e96ca6f (*****)
• http://highscalability.com/blog/2013/4/15/scaling-pinterest-from-0-to-10s-of-billions-of-page-views-a.html

[Caching]

• http://highscalability.com/blog/2013/7/8/the-architecture-twitter-uses-to-deal-with-150m-active-users.html (*****)
• https://content.pivotal.io/blog/using-redis-at-pinterest-for-billions-of-relationships
• https://medium.com/@Pinterest_Engineering/building-a-follower-model-from-scratch-b51a08c5b54e
• http://highscalability.com/blog/2013/4/15/scaling-pinterest-from-0-to-10s-of-billions-of-page-views-a.html
• https://www.slideshare.net/oemebamo/introduction-to-memcached

[Search]

• https://www.elastic.co/blog/found-elasticsearch-from-the-bottom-up#sthash.wlshw2Cj.dpbs
• https://www.elastic.co/blog/found-elasticsearch-top-down#sthash.gZwYNymj.dpbs
• https://blogs.dropbox.com/tech/2015/03/firefly-instant-full-text-search-engine/

[Distributed Consensus]

• Paxos Made Simple (*****)
• Paxos Made Live – An Engineering Perspective (*****)
• The Chubby Lock Service for Loosely-Coupled Distributed Systems
• ZooKeeper: Wait-free coordiination for Internet-scale systems (*****)
• https://www.youtube.com/watch?v=WX4gjowx45E
• https://www.quora.com/Distributed-Systems-What-is-a-simple-explanation-of-the-Paxos-algorithm

[Concurrency]

• https://caffinc.github.io/2016/03/simple-threadpool/
• http://javarevisited.blogspot.com/2012/02/producer-consumer-design-pattern-with.html
• http://javarevisited.blogspot.com/2015/07/how-to-use-wait-notify-and-notifyall-in.html
• http://www.thinkingparallel.com/2007/07/31/10-ways-to-reduce-lock-contention-in-threaded-programs/
• http://www.sosp.org/2001/papers/welsh.pdf (*****): 대형 웹 서비스를 구축할때 thread model 이 어떻게 고려되야 하는지에 대한 클래식 논문.

[Distributed Queue]

• https://kafka.apache.org/documentation/#quickstart_download (*****): 놀랍게 많은 수의 디자인 인터뷰가 Queue에 관한 것이다. Kafka의 디자인을 살펴보는것이 도움이 많이 된다.
• http://docs.aws.amazon.com/AWSSimpleQueueService/latest/SQSDeveloperGuide/sqs-visibility-timeout.html

[그외]

• https://www.slideshare.net/davegardnerisme/unique-id-generation-in-distributed-systems (*****)
• https://neil.fraser.name/writing/sync/
• http://highscalability.com/all-time-favorites/
• http://work.tinou.com/2012/09/write-ahead-log.html
• https://www.slideshare.net/AmazonWebServices/spot302-under-the-covers-of-aws-core-distributed-systems-primitives-that-power-our-platform-aws-reinvent-2014
• https://github.com/checkcheckzz/system-design-interview