2014년 12월 21일

Redis partitioning (레디스 파티셔닝)

본 문서는 http://redis.io/topics/partitioning의 번역입니다.





http://redis.io/topics/partitioning


Partitioning: how to split data among multiple Redis instances.

Partitioning is the process of splitting your data into multiple Redis instances, so that every instance will only contain a subset of your keys. The first part of this document will introduce you to the concept of partitioning, the second part will show you the alternatives for Redis partitioning.

Why partitioning is useful

Partitioning in Redis serves two main goals:
  • It allows for much larger databases, using the sum of the memory of many computers. Without partitioning you are limited to the amount of memory a single computer can support.
  • It allows scaling the computational power to multiple cores and multiple computers, and the network bandwidth to multiple computers and network adapters.

파티셔닝: 데이터를 여러 Redis 서버로 분리하는 방법

파티셔닝은 사용자 데이터를 여러 개의 Redis 인스턴스로 분리하는 과정입니다. 그래서 각 인스턴스는 전체 키(keys)의 일부(subset)만을 포함합니다. 이 문서의 첫번째 부분에서는 파티셔닝의 개념에 대해서 소개합니다. 두번째 부분에서는 Redis 파티셔닝을 위한 대체수단을 알려드릴 것입니다.

왜 파티셔닝은 유용한가.

파티셔닝은 두 개의 주요 목적이 있습니다:
  • 파티셔닝은 더 큰 데이터베이스를 가능하게 해줍니다. 즉, 여러 서버들의 메모리들의 모두 합쳐서 사용할 수 있습니다. 서버 한대가 지원하는 메모리에는 한계가 있기때문에 파티셔닝이 없다면 이 한계를 넘지 못할 것입니다.
  • 파티셔닝은 멀티 코어와 여러 서버를 이용하여 컴퓨팅 파워를 증가시켜 줍니다. 그리고, 각 서버가 가진 네트워크 대역폭을 합쳐서 사용할 수 있게 해 줍니다.

Partitioning basics

There are different partitioning criteria. Imagine we have four Redis instances R0R1R2R3, and many keys representing users like user:1user:2, ... and so forth, we can find different ways to select in which instance we store a given key. In other words there are different systems to map a given key to a given Redis server.
One of the simplest ways to perform partitioning is with range partitioning, and is accomplished by mapping ranges of objects into specific Redis instances. For example, I could say users from ID 0 to ID 10000 will go into instance R0, while users form ID 10001 to ID 20000 will go into instance R1 and so forth.
This system works and is actually used in practice, however, it has the disadvantage of requiring a table that maps ranges to instances. This table needs to be managed and a table is needed for every kind of object, so therefore range partitioning in Redis is often undesirable because it is much more inefficient than other alternative partitioning approaches.
An alternative to range partitioning is hash partitioning. This scheme works with any key, without requiring a key in the form object_name:, and is as simple as:
  • Take the key name and use a hash function (e.g., the crc32 hash function) to turn it into a number. For example, if the key is foobarcrc32(foobar) will output something like 93024922.
  • Use a modulo operation with this number in order to turn it into a number between 0 and 3, so that this number can be mapped to one of my four Redis instances. 93024922 modulo 4 equals 2, so I know my key foobar should be stored into the R2 instance. Note: the modulo operation returns the remainder from a division operation, and is implemented with the % operator in many programming languages.
There are many other ways to perform partitioning, but with these two examples you should get the idea. One advanced form of hash partitioning is called consistent hashing and is implemented by a few Redis clients and proxies.
파티셔닝의 기초.
조금씩 다른 파티셔닝 기준이 있습니다. 먼저, 4개의 Redis 인스턴가 있다고 가정합니다. R0, R1, R2, R3 입니다. 그리고, 여기에 사용되는 많은 키(keys)들이 user:1, user:2와 같은 형식으로 사용자를 표현하고 하고 있습니다. 우리는 이러한 키들이 어느 인스턴스에 속해있는지 알기 위한 여러 방법이 가능하다는 것을 알 수 있습니다. 다시 말하면, 특정 키가 특정 Redis 서버에 맵핑되는 방식입니다.
파티셔닝을 수행하는 가장 간단한 방법 중에 하나는 이러한 range partitioning 입니다. 이 방식은 특정 구간의 오브젝트들을 특정 Redis 서버에 맵핑 시키는 것입니다. 예를 들어, 사용자들의 아이디 ID 0에서 ID 10000까지는 R0 인스턴스에 할당하고, ID 10001에서 20000까지는 R1 인스턴스에 할당하는 방식입니다.
이러한 시스템은 잘 동작하고, 실제로 사용되기도 합니다. 그러나, 이 방식의 단점은 특정 구간이 특정 인스턴스에 맵핑 되어있다는 정보를 가진 맵핑 테이블이 필요하다는 것입니다. 이 테이블은 지속적으로 관리되어야 하고, 모든 오브젝트가 이 테이블을 필요로 합니다. 그래서, range partitioning은 매력적이지 않습니다. 다른 효과적인 파티셔닝 방법이 있습니다.
Range partitioning의 대체수단으로 hash partitioning이 있습니다. 이 방식은 어떤 키에 대해서도 동작에 문제가 없고, 키의 형태가 object_name: 같은 모습이 가지도록 할 필요도 없습니다. 이 방식 또한 매우 간단합니다:
  • 키 이름 가지고 이를 숫자로 만들기 위해 해쉬 함수를 이용합니다(예를 들면, crc32 해쉬함수). 예를 들어, 키 이름이 foobar이고 이를 해쉬함수에 넣으면(crc32(foobar)) 93024922 같은 출력을 얻게 됩니다.
  • 이 숫자를 0에서 3사이에 숫자로 변환하기 위해서 이 숫자에 모듈로(modulo)를 수행합니다. 그러면 이 숫자는 Redis 인스턴스 4개 중에 하나로 맵핑됩니다. 93024922를 4로 모듈로를 수행하면 2가 됩니다. 따라서, foobar라는 키는 R2 인스턴스에 저장됩니다. Note: 모듈로는 나누기를 수행한 후에 나머지를 구하는 계산입니다. 일반적으로, 여러 언어가 ‘%’  기호를 통해서 구현해 놓았습니다.

파티셔닝을 수행하는 다른 방법도 많습니다만, 이 두 가지 예를 통해서 기본 아이디를 이해할 수 있습니다.
hash partitioning의 진보된 형태로 consistent hashing이라고 불리는 방식이 있습니다. 이 방식은 일부 Redis 클라이언트와 프락시에 구현되어 있는 상태입니다.

Different implementations of partitioning

Partitioning can be the responsibility of different parts of a software stack.
  • Client side partitioning means that the clients directly select the right node where to write or read a given key. Many Redis clients implement client side partitioning.
  • Proxy assisted partitioning means that our clients send requests to a proxy that is able to speak the Redis protocol, instead of sending requests directly to the right Redis instance. The proxy will make sure to forward our request to the right Redis instance accordingly to the configured partitioning schema, and will send the replies back to the client. The Redis and Memcached proxy Twemproxy implements proxy assisted partitioning.
  • Query routing means that you can send your query to a random instance, and the instance will make sure to forward your query to the right node. Redis Cluster implements an hybrid form of query routing, with the help of the client (the request is not directly forwarded from a Redis instance to another, but the client gets redirectedto the right node).

파티셔닝의 다른 구현 방식들

파티셔닝은 소프트웨어 스택에서 다른 부분이라고 할 수 있습니다.

  • Client side partitioning : 주어진 키에 따라 읽기, 쓰기를 수행할 노드를 클라이언트가 직접 선택하는 방식입니다. 많은 Redis 클라이언트가 이 방식을 구현하고 있습니다.
  • Proxy assisted partitioning : 클라이언트가 직접 맞는 Redis 인스턴스에 요청을 보내는 대신에, 요청을 프락시 서버로 보냅니다. 이때의 프락시 서버는 Redis 프로토콜을 처리할 수 있는 서버입니다.  프락시는 그 요청을 파티셔닝의 스킴에 따라 맞는 Redis 인스턴스에 전달하고 그 응답을 클라이언트에 전달합니다. Redis와 Memcached 프락시 역할을 구현한 Twemproxy가 파티셔닝을 지원하고 있습니다.
  • Query routing : 클라이언트는 요청을 임의의 인스턴스에 보냅니다. 그러면, 그 인스턴스는 그 요청을 맞는 인스턴스로 전달합니다. Redis 클러스터는 query routing 방식을 클라이언트를 도와주는, 하이브리드 형식으로 구현하고 있습니다(그 요청이 Redis 인스턴스에서 다른 인스턴스로 직접 전달되지 않고, 클라이언트가 맞는 노드로 재전달하도록 합니다)(역자주: 클라이언트는 임의의 인스턴스에 요청을 보내는 그 노드 서버는 맞는 노드를 응답하고, 다시 클라이언트가 그 노드에 다시 요청을 보내는 방식인 것으로 보입니다). 

Disadvantages of partitioning

Some features of Redis don't play very well with partitioning:
  • Operations involving multiple keys are usually not supported. For instance you can't perform the intersection between two sets if they are stored in keys that are mapped to different Redis instances (actually there are ways to do this, but not directly).
  • Redis transactions involving multiple keys can not be used.
  • The partitioning granuliary is the key, so it is not possible to shard a dataset with a single huge key like a very big sorted set.
  • When partitioning is used, data handling is more complex, for instance you have to handle multiple RDB / AOF files, and to make a backup of your data you need to aggregate the persistence files from multiple instances and hosts.
  • Adding and removing capacity can be complex. For instance Redis Cluster supports mostly transparent rebalancing of data with the ability to add and remove nodes at runtime, but other systems like client side partitioning and proxies don't support this feature. However a technique called Presharding helps in this regard.

파티셔닝의 단점

Redis의 일부 기능은 파티셔닝에서는 동작하지 않습니다.
  • 파티셔닝 환경에서는 일반적으로, 멀티 키와 관련 있는 동작들이 지원되지 않습니다. 예를 들어, 서로 다른 Redis 인스턴스에 맵핑 되어 있는 두 개의 SET 사이의 상호처리를 수행하는 것은 불가능합니다(실제로는 이 기능을 가능하게 하는 방법이 있지만, 직접적으로 가능한 방법은 아닙니다.)
  • 멀티 키와 관련되어 있는 트랙젝션은 사용될 수 없습니다.
  • 파티셔닝이 사용될 때에는 데이터 핸들링이 더 복잡합니다. 예를 들면, 여러 개의 RDF/AOF 파일들을 다루어야 하고 여러 인스턴스와 호스트로부터 영속성 유지에 필요한 파일들을 모으고 이를 백업해야합니다.
  • 용량을 더하거나 빼는 것이 복잡해질 수 있습니다. 예를 들어, Redis 클러스터는 런타임 중에도 노드를 추가하거나 제거할 수 있는데, 이때의 데이터들은 투명하게 밸런싱이 재조정됩니다. 그러나, Client side 파티셔닝과 프락시 같은 시스템에서는 이 기능을 지원하지 않습니다. 하지만, Presharding 이라고 불리는 기술을 이용하면 이러한 고려 상황에 도움이 될 수 있습니다.


Data store or cache?

Although partitioning in Redis is conceptually the same whether using Redis as a data store or as a cache, there is a significant limitation when using it as a data store. When Redis is used as a data store, a given key must always map to the same Redis instance. When Redis is used as a cache, if a given node is unavailable it is not a big problem if a different node is used, altering the key-instance map as we wish to improve the availability of the system (that is, the ability of the system to reply to our queries).
Consistent hashing implementations are often able to switch to other nodes if the preferred node for a given key is not available. Similarly if you add a new node, part of the new keys will start to be stored on the new node.
The main concept here is the following:
  • If Redis is used as a cache scaling up and down using consistent hashing is easy.
  • If Redis is used as a store, a fixed keys-to-nodes map is used, so the number of nodes must be fixed and cannot vary. Otherwise, a system is needed that is able to rebalance keys between nodes when nodes are added or removed, and currently only Redis Cluster is able to do this, but Redis Cluster is currently in beta, and not yet considered production-ready.

데이터 저장 또는 캐쉬?

Redis를 데이터 저장용이든 캐쉬용이든 이를 사용할 때, Redis 파티셔닝은 개념적으로 동일합니다. 그러나, 데이터 저장용도일 때 중요한 한계점이 있습니다. Redis를 저장용으로 사용하게 되면, 특정 키는 항상 같은 Redis 인스턴스에 맵핑되어야 합니다. Redis가 캐쉬로 사용된다면, 특정 노드가 이용될 수 없는 상태이더라도 큰 문제가 되진 않습니다. 왜냐하면, 보통은 다른 노드가 사용가능하기 때문입니다. 시스템의 사용성이라는 측면(즉, 요청에 대한 시스템이 응답할 수 있는 능력)에서 이를 개선하기 위해서 키-인스턴스 맵핑을 변경하고자 하는 바램이 있습니다.

consistent 해싱의 구현은 특정 키에 대해서 그 노드가 응답할 수 없을 때, 다른 노드로 변경할 수 있도록 해줍니다. 유사하게, 새로운 노드를 추가하기를 원한다면 새로운 키들이 새로운 노드에 저장되도록 해야할 것입니다.

다음은 이러한 기능을 위한 주요 개념을 설명합니다.:
  • Redis를 캐쉬 기능으로 사용하고 있다면, consistent 해싱을 이용하여 그 확장성을 높이고 줄이는 것(Scaling up and down)이 쉽습니다.
  • Redis를 저장용도로 사용하고 있다면, 고정된 키-노드 맵핑이 필요하게 됩니다. 그래서, 노드의 수가 고정되어야만 하고, 변경될 수 없습니다. 또 다른 상황으로, 노드가 추가 또는 제거되어 노드 사이에 키들의 밸런싱을 다시 조정해야하는 시스템이 필요할 수 있습니다. 현재는 Redis 클러스터만이 이 문제를 해결할 수 있는 유일한 방법입니다. 그러나, Redis 클러스터는 현재 베타이고, 아직 실제 서비스(production-ready)에 사용하도록 고려되어 있지 않은 상태입니다.

Presharding

We learned that a problem with partitioning is that, unless we are using Redis as a cache, to add and remove nodes can be tricky, and it is much simpler to use a fixed keys-instances map.
However the data storage needs may vary over the time. Today I can live with 10 Redis nodes (instances), but tomorrow I may need 50 nodes.
Since Redis is extremely small footprint and lightweight (a spare instance uses 1 MB of memory), a simple approach to this problem is to start with a lot of instances since the start. Even if you start with just one server, you can decide to live in a distributed world since your first day, and run multiple Redis instances in your single server, using partitioning.
And you can select this number of instances to be quite big since the start. For example, 32 or 64 instances could do the trick for most users, and will provide enough room for growth.
In this way as your data storage needs increase and you need more Redis servers, what to do is to simply move instances from one server to another. Once you add the first additional server, you will need to move half of the Redis instances from the first server to the second, and so forth.
Using Redis replication you will likely be able to do the move with minimal or no downtime for your users:
  • Start empty instances in your new server.
  • Move data configuring these new instances as slaves for your source instances.
  • Stop your clients.
  • Update the configuration of the moved instances with the new server IP address.
  • Send the SLAVEOF NO ONE command to the slaves in the new server.
  • Restart your clients with the new updated configuration.
  • Finally shut down the no longer used instances in the old server.

Presharding

우리는 파티셔닝이 가지는 문제점에 대해서 배웠습니다. Redis를 캐쉬 용도로 사용하고 있지 않다면, 노드를 추가하고 제거하는 것이 매우 까다로울 수 있습니다. 정해진 키-인스턴스 형태의 맵핑 정보를 사용하는 것이 더 간단합니다.

그러나, 데이터 스토리지는 시간에 지남에 따라 변경의 여지가 큽니다. 오늘 내가 10개의 Redis 노드를 운영하다가 내일은 50개의 노드가 필요하게 될 수도 있습니다.

Redis는 매우 작은 메모리 공간(footprint)를 차지하고 매우 가볍습니다(인스턴스 약 1MB 메모리 사용). 이 문제를 해결하기 위한 간단한 해결방법으로 처음부터 많은 인스턴스를 가지고 시작하는 것입니다. 그냥 한대의 서버만 있다고 할지라도 처음부터 온세상에 배포한다는 결정을 하는 것이지요. 파티셔닝을 이용하고, 한대의 서버에 여러 개의 Redis 인스턴스를 실행합니다.

처음부터 매우 큰 수가 될거 같은 인스턴스의 수를 결정할 수 있는데요. 예를 들면, 모든 사용자들에게 32 또는 64개의 인스턴스가 있다고 속이는 것입니다. 그리고, 나중에 커질 것에 대비한 충분한 공간을 공급할 것입니다.

당신의 데이터가 점점 증가하면 더 많은 Redis 서버들이 필요하게 됩니다. 이 경우에 해야할 일은 간단하게 인스턴스를 이 서버에서 다른 서버로 옮기는 것입니다. 첫번째 서버를 추가한 후에 Redis 인스턴스의 반정도를 첫번째 서버에서 두번째 서버로 옮깁니다.

Redis 복제를 이용하면 최소시간 또는 다운시간 없이 이 작업을 수행할 수 있을 것입니다.
  • 새로운 서버에 비어 있는 인스턴스로 서버를 시작합니다.
  • 원본 인스턴스를 위해서 새로운 인스턴스들을 슬레이브로 만들어서 데이터를 옮깁니다.
  • 요청을 받지 않기 위해서 클라이언트들을 중지합니다.
  • 새로운 서버에서 옮겨진 인스턴스들의 설정을 갱신합니다.
  • 새로운 서버에 있는 슬레이브들에게 SLAVEOF NO ONE 커맨드를 전송합니다.
  • 새롭게 갱신된 설정을 가지고 클라이언트를 재시작합니다.
  • 마지막으로, 예전 서버에 더 이상 사용하지 않는 인스턴스들을 종료합니다.

Implementations of Redis partitioning

So far we covered Redis partitioning in theory, but what about practice? What system should you use?
Redis 파티셔닝의 구현

우리는 지금까지 Redis 파티셔닝에 대해서 이론적으로 알아보았습니다. 그러나, 실제는 어떠합니까? 어떤 시스템을 사용해야할까요?

Redis Cluster

Redis Cluster is the preferred way to get automatic sharding and high availability. It is currently not production ready, but finally entered beta stage, so we recommend you to start experimenting with it. You can get more information about Redis Cluster in the Cluster tutorial.
Once Redis Cluster will be available, and if a Redis Cluster complaint client is available for your language, Redis Cluster will be the de facto standard for Redis partitioning.
Redis Cluster is a mix between query routing and client side partitioning.

Redis 클러스터

Redis 클러스터는 자동 샤딩과 HA(High Availability, 역자주: 고가용성)를 얻기 위해서 선호하는 방식입니다. 이 방식은 마침내 베타 버전이고, 현재는 상용환경에서 사용하기에는 미흡한 상태입니다. 그래도, 베타 버전이므로 우선 적용해서 시험해보시기를 권장합니다. Redis 클러스터에 대한 상세한 정보는 Cluster tutorial 문서를 참고하십시오.
Redis 클러스트가 사용가능한 상태가 되고, 클러스터를 지원하는 클라이언트가 사용가능하게 된다면 Redis 클러스터는 Redis 파티셔닝에서 실질적인 표준이 될 것입니다.
Redis 클러스터는 query routing과 client side partitioning를 혼합해 놓은 형태입니다.

Twemproxy

Twemproxy is a proxy developed at Twitter for the Memcached ASCII and the Redis protocol. It is single threaded, it is written in C, and is extremely fast. It is open source software released under the terms of the Apache 2.0 license.
Twemproxy supports automatic partitioning among multiple Redis instances, with optional node ejection if a node is not available (this will change the keys-instances map, so you should use this feature only if you are using Redis as a cache).
It is not a single point of failure since you can start multiple proxies and instruct your clients to connect to the first that accepts the connection.
Basically Twemproxy is an intermediate layer between clients and Redis instances, that will reliably handle partitioning for us with minimal additional complexities. Currently it is the suggested way to handle partitioning with Redis.
You can read more about Twemproxy in this antirez blog post.

Twemproxy

Twemproxy는 트위터에서 개발된 프락시입니다. 이 프락시는 Memcached 아스키와 Redis 프로토콜을 지원합니다. 이것은 싱글쓰레드로 구현되었고 C 언어로 만들어졌으며 매우 빠릅니다. Apache 2.0 라이센스 기반으로 오픈소스로 릴리즈 되었습니다.
Twemproxy는 여러 Redis 인스턴스 사이에 자동적인 파티셔닝을 지원합니다. 어떤 노드가 사용가능한 상태가 아니라면, 노드 제거도 지원합니다(이 구현은 키-인스턴스 맵 정보를 바꿀 것입니다. 그래서 Redis를 캐쉬 용도로 사용하고 있다면 이 기능을 사용하는 것이 가능합니다).
Twemproxy는 여러 개를 동시에 시작할 수 있고, 클라이언트가 여러 개의 Twemproxy를 순환하면서 연결이 되는 서버를 찾을 수 있기때문에, SPF(single point failure)로 취급되지 않습니다. 
기본적으로, Twemproxy는 클라이언트와 서버 사이에 중간 레이어에 해당합니다. 이것은 우리에게 복잡성이 크지 않으면서도 믿음직스럽게 파티셔닝을 다룰 수 있게 해 줍니다. 현재로써는, 파티셔닝을 다룰 때 가장 괜찮은 방법입니다.
좀 더 자세한 내용은 antirez blog에 있는 글을 참고하십시오.

Clients supporting consistent hashing

An alternative to Twemproxy is to use a client that implements client side partitioning via consistent hashing or other similar algorithms. There are multiple Redis clients with support for consistent hashing, notably Redis-rb andPredis.
Please check the full list of Redis clients to check if there is a mature client with consistent hashing implementation for your language.

클라이언트는 consistent 해상을 지원하고 있습니다.

Twemproxy의 대안으로 가능한 것은, consistent 해싱 또는 다른 유사한 알고리즘을 통해서 client side partitioning 이용하는 것입니다. Consistent 해싱을 지원하는 여러 Redis 클라이언트들이 있습니다. 특히, Redis-rb와 Predis가 있습니다.
redis 웹사이트에서 Redis 클라이언트에 해당하는 전체 리스트를 참고하십시오. 여기에 있는 클라이언트 중에서 오랫 시간 동안 성숙한 클라이언트로의 이름을 유지하면서 consistent 해싱을 지원하는 클라이언트를 확인하실 수 있습니다.





댓글 없음:

댓글 쓰기