샤딩은 어떻게 동작하는가 (How Sharding Works 번역)

원문: (https://medium.com/@jeeyoungk/how-sharding-works-b4dec46b3f6#.234lgjddv)

How Sharding Works 

서비스가 갑자기 인기가 많아져서 트래픽과 데이터가 증가하기 시작하고, 데이터베이스에는 과부하가 걸릴 것이다. 이때 샤딩을 할 필요가 있다.

What is sharding?

샤딩이란 단일의 논리적 데이터셋을 다수의 데이터베이스에 쪼개고 나누는 방법. 이렇게 쪼갬으로써 데이터베이스 시스템의 클러스터에서 큰 데이터셋을 저장하고 추가적인 요청을 처리할 수 있다. 샤딩이란 데이터셋이 단일 데이터베이스에서 저장하기에 너무 클때 필수적이다. 게다가, 많은 샤딩 전략들이 추가적인 머신들이 붙을 수 있도록 만든다. 샤딩은 데이터베이스 클러스터가 디비의 데이터와 트래픽 증가와 함께 스케일을 확장할 수 있게 한다.

(클러스터라는 개념을 어떻게 봐야할까? 단순 node 개념?)

Vertical Partitioning

• 도메인에 특화되있음(도메인이란 필드에 들어갈 수 있는 밸류들을 의미?)
• 애플리케이션의 데이터를 로지컬하게 스플릿하고 다른 데이터베이스에 저장
• 애플리케이션 레벨에서  항상 구현됨 - 명시된 디비에 read/write를 라우팅하는 코드가 구현되야함

Sharding

• 같은 타입의 데이터를 다수의 데이터베이스에 쪼개서 저장하는 것
• 샤딩의 알고리즘이 매우 쉽게 일반화가 가능하기에 샤딩은 애플리케이션 레벨이나 데이터베이스 레벨에서 구현이 가능함
• 많은 데이터베이스에서 샤딩은 가장 좋은 개념
• 데이터베이스는 어떻게 클러스터에 데이터를 저장하고 검색하는 법을 알고 있음.
• 거의 모든 모던 데이터베이스는 자연스럽게 샤딩되어있음
• Cassandra, Hbase, HDFS, 그리고 MongoDB와 같은 분산 디비들
• 주목할만한 Non-sharded 모던 데이터베이스는 sqlite, Redis(spec in progress), Memcached, 그리고 Zookeeper  

(배경지식)

여기서 간단하게 보면 database는 server 한대, cluster는 그 server들의 묶음 으로 보면 됨. sharding할 때 data를 several servers로 나누는데 그 server들의 묶음이 cluster가 되는 것임.

데이터를 다수의 데이터베이스로 분산하는 수많은 전략들이 있음.

각각의 전략은 그들이 만드는 다양한 전제에 따라 찬반이 나뉨.

이러한 전제와 제한에 대해 이해하는 것은 매우 중요함

operation은 요청된 데이터를 찾기 위해 많은 데이터베이스를 검색할 필요가 있는데, 이것을 cross-partition operation이라고 부르고 이는 비효율적인 경향이 있음.

Hotspots은 또다른 문제인데, 이는 데이터와 operation의 분균등한 분산을 가지는 것임.

hotspot은 샤딩의 이점에 매우 크게 대응한다.

Before you start: you may not need to shard!

샤딩은 애플리케이션에 추가적인 프로그래밍적, 운영적인 복잡도를 더함. 이로 인해 아마 단일 위치에서의 데이터에 접근하는 편안함을 잃을 것임. 다수의 서버는 운영의 도전을 더하는데, 샤딩을 시작하기전에 샤딩을 피하거나 지연시킬 수 있을지 확인해보자.

• 좀 더 비싼 머신을 도입
• 저장소 수용량이 무어의 법칙의 속도에 따라 성장하고 있다.
• 애플리케이션이 read 퍼포먼스가 많다면 캐시나 데이터베이스 레플리케이션을 적용시킬 수 있다. 이들은 힘들게 애플리케이션의 수정하는 것없이도 추가적인 read 커패시티를 제공한다.
• 기능에 따라 vertically partition
• Binary blob은 거대한 공간을 차지하는 경향이 있고 애플리케이션에 고립된다. S3에 파일을 저장하는 것은 스토리지 부담을 줄여줄 수 있다.
• full text search나 tagging이나 분석과 같은 기능들도 분리된 데이터베이스로 하기에 최고의 기능들이다.

모든 것이 샤딩될 필요는 없다. 흔히, 오직 몇개의 테이블이 디스크 공간의 다수를 차지한다. 수백개의 로우를 가지는 작은 테이블을 샤딩함으로서 얻을 수 있는 것은 거의 없다. 거대한 테이블에 집중을 해야한다.

Driving Principle

각각의 샤딩 전략의 찬반에 대해 비교를 하면, 몇가지 룰을 따를 수 있다.

1. 데이터가 읽어들여지는 방법: 데이터베이스는 데이터를 저장하고 검색하기 위해 사용되어지는데, (만약 데이터를 전혀 읽을 필요가없다면 단순히 데이터를 /dev/null에 저장하면 된다. 만약 우리가 오직 잠시동안만 데이터를 batch형태로 처리해야한다면 우리는 하나의 파일을 추가하고 이를 통해 주기적으로 읽으면 된다.) 데이터 검색의 필요성은 샤딩 전략에 엄청난 영향을 미칠 것이다.
2. 데이터가 분산되는 방법: 일단 같이 묶여서 행동하는 머신들의 cluster를 가지고 난 후, 데이터와 작업이 동등하게 분산되도록 하는 것이 중요해진다. 불균등한 부하는 스토리지와 성능의 hotspot을 야기한다. 몇몇 데이터베이스는 다른 데이터베이스들이 클라이언트가 동등하게 분산되고 데이터에 접근하는 동안 데이터를 동적으로 재분산한다.

일단 샤딩이 채택된 후에는, 데이터의 재분산이 중요한 문제가 된다. 일단 서비스의 데이터베이스가 샤딩된 후에는 데이터가 급속도로 늘어나는 것 같다. 추가로 노드를 더하는 것은 일반적인 루틴이 된다. 설정에는 변화가 필요할 것이며 노드사이의 방대한 데이터의 움직임이 필요하다. 샤딩은 또 성능과 운영의 부담을 더한다.

Common Definitions

많은 데이터베이스가 자신들의 터미날러지를 가진다. 아래의 터미날러지는 다른 알고리즘을 설명하는 내내 사용된다.

Shard 혹은 Partition Key는 프라이머리 키의 부분인데 이는 어떻게 데이터가 분산되어야하는지를 결정한다. Partition key는 우리가 데이터를 효율적으로 검색하고 수정하는 것을 허락하는데, 이는 operation을 올바른 데이터베이스에 라우팅함으로써 가능하다. 같은 partition key의 entry들은 같은 노드에 저장된다. Logical shard는 같은 partition key를 공유하는 데이터의 콜렉션이다. 이따금씩, 데이터베이스 노드는 physical shard로 언급되기도 하는데 이는 다수의 logical shard를 포함한다.

Case 1-Algorithmic Sharding

샤딩을 분류하는 하나의 방법은 algorithmic vs. dynamic이다. Algorithmic sharding에서는, 클라이언트가 어떠한 도움없이 주어진 파티션의 데이터베이스를 결정한다. Dynamic sharding에서는 separate locator service가 노드들 사이에서 파티션을 추적한다.

알고리즘적으로 샤딩된 데이터베이스는 샤딩 펑션을 사용하는데, 이는 데이터를 저장하기 위하여 partition key를 database_id로 바꾼다. 간단한 샤딩 펑션은 "hash(key) % NUM_DB"일 것이다.

Partition key가 주어지는 한 read는 단일 데이터베이스에서 수행될 것이다. Partition key가 없는 쿼리는 아마 모든 데이터베이스 노드를 조사할 필요가 있다. partition되지않은 쿼리는 cluster의 크기의 측면과 함께 확장되면 안된다. 그러므로 이들은 수행되어서는 안된다.

Algorithmic sharding은 오직 샤딩 펑션을 통해서만 데이터를 분산한다. 이는 전혀 payload(가 뭐지?)나 공간 활용을 고려하지 않는다. 균등하게 데이터를 분산하기 위해서 각각의 partition은 유사하게 크기가 잡힐 필요가 있다. 잘 나뉘어진 파티션들은 hotspot을 제거하는데 - 단일 데이터베이스는 많은 파티션을 포함할 것이며, 데이터베이스간의 데이터의 총합은 통계적으로 거의 유사할 것이다. 이러한 이유로, algorithmic sharding은 같은 값을 가지는 key-value 데이터베이스에 적합하다.

데이터를 resharding하는 것은 매우 도전적일 수 있는데,, 이는 샤딩 펑션을 수정하고 cluster의 데이터를 옮길 필요가 있다. consistency와 availability를 유지하면서 동시에 데이터를 옮기는 것은 힘들다. 샤딩 펑션의 클레버한 선택은 전송되는 데이터의 양을 줄일 수 있다.Consistent Hashing이 바로 그 알고리즘이다. (consistent hasing link: http://www.paperplanes.de/2011/12/9/the-magic-of-consistent-hashing.html)

Case 2 - Dynamic Sharding

(locator의 의미 및 역할에 대해서 감을 잡을 필요가 있음)

Dynamic Sharding에서, external locator service(아까부터 계속 locator라는 말이 뭘까?)가 entry(entry란 뭘까, 찾아보자)의 위치를 결정한다. 이는 다양한 방법으로 구현될 수 있다. 만약 partition keys의  cardinality(튜플의 수.; count of rows?)가 상대적으로 낮다면, locator는 개인 키별로 할당될 수 있다. 그렇지 않다면, 단일 locator는 다수의 partition key를 나타낼 수 있다. 

데이터를 read/write하기 위해서, 클라이언트는 locator service에게 먼저 물어볼 필요가 있다. Primary key에 의한 operation은 꽤 사소하게 될 수 있다. locator의 구조에 따라 다른 쿼리들또한 효율적일 수 있다. Range기반의 partition key의 예의 경우, range 쿼리는효율적인데, 그 이유는 locator service가 데이터베이스 후보군의 수를 줄여주기 때문이다. Partition key가 없는 쿼리의 경우 모든 데이터베이스를 검색해야만 할 것이다.

(partition key라 함은 GUID와 같은 것으로 생각을 해도 될지.? GUID또한 그 키의 구성에 따라 데이터 센터나 워커 아이디를 구분할 수 있으니.)

Dynamic Sharding은 더 데이터의 불균등 분산에 레질리언트하다. locators는 만들어질 수 있고 분리될 수도 있고 재분산된 데이터에 대해 재정의 될 수 있다. 그러나 데이터의 relocation과 locator의 수정이 동시에 될 필요가 있다. 이 프로세스는 수많은 흥미로운 이론적인, 운영적인, 그리고 구현적인 도전과 함께 많은 corner cases(예외 상황이라고 봐야할까?)를 가진다.

[locator를 음 range에 대한 인덱스라고 보면 될지?]

Locator service는 SPOC(Single Point Of Contention)와 SPOF가 된다. 모든 데이터베이스 operation은 이를 접근할 필요가 있고, 따라서 performance와 availability가 가장 중요하다. 그러나, locators는 단순히 캐싱되거나 레플리케이션될 수 없다. 만기된 locator는 아마 부정확한 데이터베이스로 operation을 라우트할 것이다.

[이때까지 나온 operation의 의미는 클라이언트의 DB로의 요청 및 그 응답을 위한 작업이라고 해석을 해도될까]

미스라우팅된 write는 특히 좋지 않은데, - 이는 라우팅 이슈가 해결된 이후에는 찾을 수 없게 된다.

미스라우팅된 트래픽의 효과가 매우 치명적이기 때문에, 많은 시스템은 high consistency solution을 선택한다. Consensus(all agree) algorithms과 sync replication은 이 데이터를 저장하기 위해 사용되어진다. 운이 좋게도, locator data는 작은 경향이 있기때문에, heavyweight solution과 같은 것과 함께 computational비용이 낮은 경향이 있다.

이런 강력함때문에 dynamic sharding은 많은 인기있는 데이터베이스에서 사용된다. HDFS는  Name Node를 filesystem의 metadata를 저장하기 위해 사용한다. 불행하게도, name node는 HDFS의 SPOF이다. Apache HBase는 row key를 range로 분리한다. 그 range 서버가 다수의 region?을 저장할 책임이 있다. Region 정보는 Zookeeper에 저장되는데, 이는 consistency와 redundancy를 위함이다. MongoDB에서는 configServer가 sharding 정보를 저장하며 mogos는 쿼리 라우팅을 수행한다. ConfigServer는 sync replication을  사용하여 consistency를 보장한다. Config server가 redundancy를 잃을때, 이는 안전성을 위해서 readonly 모드로 전환한다. 일반 database operation은 영향을 받지 않지만, shard는 생성되거나 변동될 수 없다.

Case 3 - Entity Groups

이전의 예들은 key-value operation에 대해 적합한 형태이다. 그러나, 많은 데이터베이스들은 더 expressive한 쿼리와 manipulation capability를 가진다. 고전적인 RDBMS의 기능들(join, index, transaction과 같은)은 애플리케이션의 복잡도를 줄인다.

Entity groups의 개념은 매우 간단하다. 같은 partition에 관련있는 entity를 저장하는 것인데 이는 단일 partition에서 부가적인 capability를 제공하기 위함이다. 더 상세하게는

1. single physical shard내에서의 쿼리가 효율적이다.
2. 하나의 샤드에서 더 강력한 consistency가 이뤄질 수 있다.

이는 RDB를 sharding하는 인기있는 어프로치이다. 전형적인 웹 애플리케이션에서, 데이터는 자연스럽게 사용자별로 고립된다. 사용자에 따라 partitioning하는 것은 대부분의 그것의 플렉서빌리티를 유지하는 동안 샤딩의 확장성을 준다.(?) 이는 일반적으로 단순한 company-specific solution으로써 시작하는데, 이 solution은 resharding operation이 개발자에 의해 수동적으로 되는 솔루션이다. Youtube의 Vitness나 Tumblr의 Jetpants와 같은 성숙한 솔루션은 대부분의 operational task를 자동화할 수 있다.

다수의 partition으로 확장되는 쿼리는 전형적으로 single partition 쿼리보다 consistency의 보장을 더 잃는다. 그들은 또한 비효율적인 경향이 있는데, 그래서 이런 쿼리들을 조금씩 수행됭어야 한다.

하지만, 특정의 cross-partition 쿼리는 아마 자주, 효율적이게 필요할 것이다. 이런 상황에선, 데이터는 효율적인 read를 지원하기 위해서 다수의 partition에 저장될 필요가 있다. 예를 들면, 두 사용자간의 채팅 메시지는 아마 두번 저장 될 것인데 - 보내는 사람과 받는사람에 의해 partitoned되었기에. 사용자들에 의해 보내지거나 받아진 모든 메시지는 단일 파티션에 저장된다. 일반적으로, 파티션간의 다대다 관계는 복사될 필요가 있다.

Entity groups는 algorithmically 혹은 dynamically 구현될 수 있다. 그들은 보통 dynamic하게 구현이 되는데, 그룹당 전체 크기가 매우 다양하게 변하기 때문이다. locator를 수정하거나 데이터를 이동하거나에 대한 같은 경고가 여기도 똑같이 적용된다. 개별의 테이블 대신에 전체적인 그룹이 함꼐 이동될 필요가 있다.

다른 샤딩된 RDBMS 솔루션보다, Google Megastore은 이와 같은 시스템의 예이다. Megastone은 공식적으로 Google App Engine의 Datasotre API로 노출되어 있다.

Case 4 - Hierarchical keys & Column-Oriented Databases

[계층키&칼럼지향적 데이터베이스?.??]

Column-oriented 데이터베이스는 key-value 저장소의 연장선이다. 그들은 hierarchical primary key와 함께 entity groups의 expressiveness를 더했다. Primary key는 row key와 column key로 된 pair를 구성한다. 같은 partition key의 Entry들은 함께 저장된다. Single partition으로 제한된 칼럼에 대한 range 쿼리는 효율적이다. 이것이 바로 column key가 DynamoDB에서 range key로 불리는지에 대한 이유이다.

이 모델은 2000년대 중반부터 인기가 있었다. Hierarchical key에 의한 제한은 데이터베이스가 data-agnostic?(데이터 상관없이?)적인 샤딩 메카니즘과 효율적인 저장 엔진을 구현하도록 돕는다. 한편, hierarchical key는 우아한 관계를 표현하기에 충분히 expressive하다.column-oriented 데이터베이스는 효율적으로 time series(뭐지?)와 같은 문제를 모델링할 수 있다.

Column-oriented 데이터베이스는algorithmically 혹은 dynamically 샤딩될 수 있다. 작고 수많은 작은 partition과 함께, 이들은 key-value 저장소와 유사한 constraint를 가진다. 그렇지 않으면, dynamic sharding이 더 적합하다.

Column database라는 용어는 인기를 잃고 있다. HBase와 Cassandra는 스스로를 column database라고 칭하며 마켓에 올라섰었는데, 지금은 아니다. 만약 이런 오늘날에 이런 시스템을 분류할 필요가 있다면 이들을  hierarchical key-value 저장소라고 부를 것인데, 이것은 가장 그들의 구분하기 쉬운 특징이기 때문이다.

2005년에 처음으로 나온 Google BigTable은 대중들사이에서 column-oriented 데이터베이스로 인기를 얻었다. Apache HBase는 하둡 에코시스템 상에서 구현된 BigTable과 같은 데이터베이스이다. Apache Cassandra는 이전에는 column 데이터베이스로 스스로를 설명했는데, - entries가 row,column key와 함께 column family에 저장되었다(???) 

Cassandra를 위한 최근의 API인 CQL3는 flatten하게 된 데이터 모델(partition key, column key)를 표현하는데, 이 CQL3는 간단하게 primary key를 구성할 수 있다. 아마존의 Dynamo는 매우 available 한 데이터베이스로 인기를 얻었다. 아마존의 DynamoDB는 Dynamo가 제공하는 PaaS이다. DynamoDB는 (hash key, range key)를 primary key로써 사용한다.

[Hierarchical keys & Column-Oriented Database에 대해서는 전혀 감이안온다..  공부를 더 할 필요가 있는 것 같다.]

Understanding the pitfalls(pitfall: 처음에는 두드러지지 않지만 숨겨진 위험이나 어려움)

위에서 많은 경고들이 논의되었다. 하지만, 많은 전략들과 함께 주의해야할 다른 공통적인 이슈들이 있다.

Logical shard(같은 partition key를 공유하는 데이터)는 반드시 single node안에 있어야 한다. 이것이 가장 중요한 전제이며 미래에 가장 바꾸기 어려운 것이다. logical shard는 저장소의 원자적인 단위이고, 다수의 노드로 확장할 수 없다. 이런 상황에서, database cluster는 결과적으로 공간이 모자라게 된다. 그러나, partitions이 이런 문제를 좀더 완화시키면서, 이는 데이터베이스와 애플리케이션에 복잡도를 더했다. Cluster는 추가적인 파티션들을 관리할 필요가 있고 애플리케이션은 추가적인 corss-partition operartion을 할 필요가 있을 것이다.

[파티셔닝이 어떻게 이런 로지컬 샤드의 근본적인한계를 완화시켰는가.? 음..]

많은 웹 애플리케이션이 사용자에 따라 데이터를 샤딩한다. 이것은 시간이 흐르면서 문제를 일으킬 수 있는데,  애플리케이션은 방대한 양의 데이터와 함께 power user를 축적하기 때문이다. 예를 들어, email 서비스는 테라바이츠의 email과 함께 사용자들을 가진다. 이를 수용하기 위해서, 개별 유저의 데이터는 partition으로 스플릿되어진다. 이런 migration은 보통 매우 도전적인데, 그 이유는 이것이 근본적인 데이터 모델상에서의 많은 핵심적인 전제를 무효화시키기 때문이다.

비록 dynamic sharding이 불균형 데이터에 더 레질리언트할지라도, 예기치 못한 작업량이 그것의 효과성을 줄일 수 있다. Range-partioned sharding scheme에서, partition key 순서에 따라 데이터를 삽입하는 것은 hotspot을 만든다. 오직 마지막 range만 삽입을 받을 것이다. 하지만, range를 쪼개면면서, 오직 마지막 range만 추가적인 write를 받을 것이다. cluster의 write 스루풋은 결과적으로 단일 노드로 줄어들게 된다. MongoDB, HBase, 그리고 Google Datastore가 이것을 막는다.

Dynamic sharding의 경우, 많은 수의 locator를 가지는 것은 좋지 않다. locator가 자주 접근되면서, 그들은 RAM으로부터 직접적으로 서빙된다. HDFS의 name node는 적어도 그것의 metadata를 위해 파일 당 150바이트의 메모리가 필요하다. 따라서 많은 수의 파일을 저장하는 것은 금지하는 편이다. 많은 데이터베이스는 partition range별로 정해진 리소스의 양를 할당한다. HBase는 서버별로 약 20~200 region을 추천한다.

Concluding Remarks

여기에 다뤄지지 않은 샤딩과 밀접하게 관련된 많은 주제들이 남아있다. Replication은 분산 데이터베이스에서 durability와 availability(가용성: 서비스가 얼마나 죽지않고 잘 운영되어지는가)를 보장하기 위해 중요한 개념이다. Replication은 샤딩에서 아무렇게나 수행되어 질 수 있거나 밀접하게 샤딩의 전략과 연결될 수 있다.(?)

데이터의 재분산에 관련한 세부사항은 중요하다. 이전에 언급한 것과 같이, 데이터가 이동되는 동안 데이터와 locator 둘다 sync를 맞추는 것을 보장하는 것은 매우 힘든 문제이다. 많은 기술들이 consistency, availability, performance사이에서 tradeoff이다. 예를 들어., HBase의 region 분산은 복잡한 다단계의 프로세스이다.  이것을 약화시키기 위해선 region을 분산하는 동안 downtime이 필요하다.

이들중 아무것도 마법인 것은 없다. 일단 데이터가 어떻게 저장되고 검색될지에 대해 고려한다면, 모든 것은 논리적으로 따라온다. Cross-partition query(?)는 비효율적이며 많은 샤딩 스킴이 cross-partition operation의 수를 최소화하려고 시도한다. 반면에, partition은 노드들 사이에서 부하를 적절히 분산하기에 충분히 상세한 거 같다. 알맞은 균형을 찾는 것은 까다로울 수 있다. 물론, 소프트웨어 엔지니어링에서 최고의 해결책은 완전히 문제를 피하는 것이다. 전에 설명한 것처럼, 샤딩 없이 운영하는 성공적인 웹사이트들이 많다. 만약 완전히 문제를 피하거나 연기시킬 수 있다면 그렇게 하는게 좋다.!