달력

112017  이전 다음

  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  •  
  •  

'개발하면서/코드읽기'에 해당되는 글 26건

  1. 2015.02.04 QuickList
  2. 2013.02.12 Key notification
  3. 2012.10.04 Slowlog
  4. 2012.10.04 Bit operation
  5. 2012.09.21 Auth
  6. 2012.09.13 Pub / Sub
  7. 2012.09.08 transactions
  8. 2012.09.03 persistence RDB
  9. 2012.08.21 Expires
  10. 2012.06.17 Sorted Set
  11. 2012.06.17 persistence AOF
  12. 2012.06.17 Set
  13. 2012.06.17 Maxmemory policy (3)
  14. 2012.03.13 Redis 팀내 공유자료 (2)
  15. 2011.12.18 Dict
  16. 2011.12.11 Redis 소스를 분석해보자.
  17. 2011.12.10 String
  18. 2011.11.17 List
  19. 2011.11.15 Object
  20. 2011.11.13 Hashes

2015년 1월 초에 unstable에 merge된 QuickList에 알아본다.

https://matt.sh/redis-quicklist 에서 나온 얘기를 조금 하고 코드를 보자


Redis에 List 자료구조는 일반적인 Linked list와 메모리를 절약을 위한 Ziplist두개가 있다.

포인터를 이용하여 리스트 구현한것과 배열을 이용하여 리스트를 구현한것이라고 생각하면 쉽다.

list-max-ziplist-entries 512
list-max-ziplist-value 64

(노드 갯수가 512개 이상 || 저장하려는 값의 길이가 64 byte 초과)면 Linked list로 저장이 되고

(노드 갯수가 512개 미만 && 저장하려는 값의 길이가 64 byte 이하)면 ziplist로 저장이 된다.

재미진건 ziplist -> Linked list변환은 되는데 Linked list -> ziplist 변환은 안된다.
(하긴 511개 노드였을때 넣다뺐다 하면 변환하다가 끝나겠네...그리고 추가전에만 타입 변환 검사 한다.삭제할때는
검사 안함)


http://dol9.tistory.com/187


Linked list의 장점은 추가/삭제가 쉽다는 점이고, 단점으로는 작은 값(예:4 byte)을 추가하는데 실제 값보다
더 많은 메타데이타?(예: prev, next 포인터, 8 byte)를 사용한다.

Ziplist의 장점은 내부적으로 포인터를 안써서 메모리 절약이 된다는 점이고, 단점으로는 리스트 중간에 노드를
추가/삭제를 하게되면 메모리 재할당, 복사/이동이 일어난다.



2014년 2월 3일에 봤을때 Redis에 리스트 자료구조는 QuickList만 사용한다.

https://github.com/antirez/redis/pull/2143 QuickList에 대해 정말 활발한 리뷰 오고가는걸 볼 수있다.
(재밌겠다~~~~~!!!!)


각 노드를 ziplist로 구성하고 적정 크기로 유지하면서 각각의 노드는 포인터로 연결하는 자료구조 그게 QuickList이다.

[ziplist 0] <-> [ziplist 1] <-> ... <-> [ziplist N]

데이타를 ziplist에 추가하다 조건이 충족되면 노드를 하나 더 생성해서 새로운 노드에 데이타를 저장하거나 노드를
split한후 데이타를 저장하고 Merge하는 작업
을 한다.

재미진건 ziplist에서 더 아끼기위해 압축을 한다.


QuickList에 대해 대략 알아봤으니 궁금한 부분을 나열하고 그에 대해 알아보자


. 데이타 traverse

. 데이타 추가할때 동작

Compression의 동작과 발생 조건

Decompression의 동작과 발생 조건

. 노드 Merge 동작과 발생 조건

. 노드 Split 동작과 발생 조건

로 나눠서 하면 좀 간단하지 않을까 했지만 결국엔 주저리 떠드는걸로 됐음



. 데이타 traverse

pop이나 push명령이 아닌 중간에 있는 노드에 작업을 해야할때가 있다.

기존 ziplist, Linked list는 하나하나씩 노드 곱씹어가며 index 도달할때까지 이동하는데

QuickList는 quicklistNode->count에 ziplist의 데이타 갯수가 저장되있어서 마치 skiplist처럼 탐색을 한다.


. 데이타 추가할때 동작을 보기전에 관련 설정값을 알아보도록 하자

list-max-ziplist-size는 한 노드의 ziplist 최대 크기또는 최대 갯수를 정한다. -5~-1은 최대 크기(byte),
양수는 최대 갯수를 
의미한다. 1로 해놓으면 성능 더 안 좋은 Linked list라고 보면 된다.

list-compress-depth는 head, tail부터 안쪽으로 이동하면서 압축 하지 않을 노드의 깊이를 정한것이다. 
compress에서 다시 보자.

# For a fixed maximum size, use -5 through -1, meaning:

# -5: max size: 64 Kb  <-- not recommended for normal workloads

# -4: max size: 32 Kb  <-- not recommended

# -3: max size: 16 Kb  <-- probably not recommended

# -2: max size: 8 Kb   <-- good

# -1: max size: 4 Kb   <-- good

list-max-ziplist-size -2


# Lists may also be compressed.

# Compress depth is the number of quicklist ziplist nodes from *each* side of

# the list to *exclude* from compression.  The head and tail of the list

# are always uncompressed for fast push/pop operations.  Settings are:

# 0: disable all list compression

# 1: depth 1 means "don't start compressing until after 1 node into the list,

#    going from either the head or tail"

#    So: [head]->node->node->...->node->[tail]

#    [head], [tail] will always be uncompressed; inner nodes will compress.

# 2: [head]->[next]->node->node->...->node->[prev]->[tail]

#    2 here means: don't compress head or head->next or tail->prev or tail,

#    but compress all nodes between them.

# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]

# etc.

list-compress-depth 0



데이타 추가전에, _quicklistNodeAllowInsert 함수로 해당 노드가 가득찬 상태인지 아닌지 판단한다. 

그리고 추가되는 위치가 ziplist의 처음이면서 정방향인지, ziplist의 마지막이면서 역방향인지도 판단한다. 

총 6개로 구분해서 추가 로직을 구현했는데 간단하게 알아보자


대부분의 분기문에서 해당 노드를 decompress하고 데이타 추가 작업후 compress를 한다. 

얼마나 안타까운 현실인가 LINSERT 명령어는 자제 해야겠다.
비즈니스상 꼭 필요한 거라면 list-compress-depth를 0으로 사용해서 압축을 안하던가...




. 노드 Merge 동작과 발생 조건

. 노드 Split 동작과 발생 조건

발생조건은 데이타 추가에서 알아본 6개의 분기문중 마지막 분기문에서 split과 Merge가 발생한다.



노드 Merge할지 말지 결정할때 사이즈를 구하는데 11을 빼는이유는 ziplist Header사이즈 제거
(두 노드중 한 노드는 header 필요없음)




[A]<->[B]<->[C]<->[D]<->[E]

Merge 는 기준이 되는 노드를 인자로 받아 A/B Merge , D/E Merge , B/C Merge , C/D Merge 가 발생한다.(쉽게 설명한 감이 있음, 사실 앞에서 Merge 가 발생되면 달라짐)


Split 은 동작이 단순 무식하다. split할 노드와 동일한 노드를 새로 만들어서, 

한 노드는 (offset+1)~끝까지 지우고 다른 하나는 0~offset까지 지운다.



. Compression의 동작과 발생 조건

ㄴ 노드 생성하고 기존 노드에 포인터 연결후 기존 노드 compress

ㄴ LSET 명령으로 값 수정 후 해당 노드 compress

ㄴ 노드 merge 할때 count가 큰 노드 compress (ziplist 합치는 작업시 작은 ziplist가 큰 ziplist에 merge된다.)

ㄴ iter 사용후 release할때 iter에서 가리키고 있는 노드 compress

ㄴ A <-> B 노드가 있고 iter가 A의 ziplist 마지막으로 가리키고 있을때 Next 실행 시 A 노드 compress
(iter가 B의 ziplist 처음을 가리키고 있고 Prev 실행시 B 노드 compress)


compress는 두가지 방법으로 한다. 하나는 인자로 들어온 노드만 compress하는 방법이 있고,

다른 하나는 list-compress-depth 변수를 이용하는 방법이 있는데 다음과 같다.


list-compress-depth=2, 인자로 들어온 노드=[E] 

[A]<->[B]<->[C]<->[D]<->[E]<->[F]<->[G]

바깥쪽에서 안쪽으로 list-compress-depth만큼은 compress 안하겠다는 말인데,[A], [B], [F], [G] 노드를 decompress하고 [E]를 compress한다
아...이건 설명하기 참 거시기 하다. compress 방식을 두개로 나눈 이유는 decompress 에서 알아본다.


. decompress의 동작과 발생 조건

ㄴ 노드 compress 작업할때 decompress

ㄴ 두 노드 Merge 할때 두 노드 decompress

ㄹ 데이타 삽입시 노드 decompress

ㄹ 데이타 삭제시 노드 decompress


ㄹ로 되어있는 발생조건이 ㄴ과 다른건 recompress값을 1로 대입하는것 말고는 없다.
차이는 해당 노드만 compress할것이냐, 아니면 compress 두번째 설명한 방식대로 할것이냐 차이다.
ㄹ조건을 보면 데이타 추가/수정/삭제인 경우이다. matt의 섬세함이 느껴졌다.
한번 decompress/compress 한 노드이니까 굳이 할 필요가 없는거지...



따라가기도 버거운걸 코드로 표현한 matt...참 대단하다 난 QuickList 자료구조만 알아본건데
aof, rdb등 전체적인 구조 다 수정 했을텐데...무서운사람....덜덜

antirez가 활발하게 커뮤니케이션 하는거 처음봤다. 부러움이 넘쳤다, 재밌겠다 ㅜ,ㅜ.
영어로 내 의견 쓸 정도는 되야하는데...

기승전 자기반성 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

이 기능은 2013년 1월달에 unstable로 merge되었습니다.

https://github.com/antirez/redis/commit/4cdbce341ebff64d392a42011f4a9258f8aa834f#src


처음 시작할때는 2.6으로 했는데 하;;; 시간을 너무 끌었네요. 뭐든지 한번할때 왕창해야겠어요.

간단하게 말하면, 이 기능의 요지는 key가 추가/수정/삭제가 되었을때 이벤트를 잡아서

client한테 알려주는것입니다


슬기로운 antirez는 redis에 있는 기능을 이용해서  간단하게 구현을 했습니다.

이 글을 보시기전에 Pub/Sub을 보시고 오시면 더 좋겠습니다.


key에 대해 이벤트(추가/수정/삭제)가 발생하면, 어떤키인지, 그리고 어떤 이벤트인지 두가지로 나뉩니다.
체널명을

__keyspace@[dbid]__:[key name] [event name], __keyevent@[dbid]__:[event name] [key name] 로 생성합니다.


또 재미있는건 모든 자료구조(+ expire, evicted, generic)마다 flag를 두었다는 점입니다.
redis.conf를 보면 아래 flag가 있습니다

#  K     Keyspace events, published with __keyspace@<db>__ prefix.
#  E     Keyevent events, published with __keyevent@<db>__ prefix.
#  g     Generic commands (non-type specific) like DEL, EXPIRE, RENAME, ...
#  $     String commands
#  l     List commands
#  s     Set commands
#  h     Hash commands
#  z     Sorted set commands
#  x     Expired events (events generated every time a key expires)
#  e     Evicted events (events generated when a key is evicted for maxmemory)
#  A     Alias for g$lshzxe, so that the "AKE" string means all the events.


redis.h

/* Keyspace changes notification classes. Every class is associated with a
 * character for configuration purposes. */
#define REDIS_NOTIFY_KEYSPACE (1<<0)    /* K */
#define REDIS_NOTIFY_KEYEVENT (1<<1)    /* E */
#define REDIS_NOTIFY_GENERIC (1<<2)     /* g */
#define REDIS_NOTIFY_STRING (1<<3)      /* $ */
#define REDIS_NOTIFY_LIST (1<<4)        /* l */
#define REDIS_NOTIFY_SET (1<<5)         /* s */
#define REDIS_NOTIFY_HASH (1<<6)        /* h */
#define REDIS_NOTIFY_ZSET (1<<7)        /* z */
#define REDIS_NOTIFY_EXPIRED (1<<8)     /* x */
#define REDIS_NOTIFY_EVICTED (1<<9)     /* e */
#define REDIS_NOTIFY_ALL (REDIS_NOTIFY_GENERIC | REDIS_NOTIFY_STRING | REDIS_NOTIFY_LIST |

REDIS_NOTIFY_SET | REDIS_NOTIFY_HASH | REDIS_NOTIFY_ZSET |

REDIS_NOTIFY_EXPIRED | REDIS_NOTIFY_EVICTED)      /* A */


K, E는 위에서 말한 두가지이고, 'g$lshzxeA' 문자열을 가지고 골라먹는 재미가있습니다.

[K | E | KE][g, $, L, s, h, z, x, e | A]


하나 의문점이 드는게 있습니다. g의 expire와 x의 expire는 왜 두개나 있지? hdel을 하면 g에 걸리는거여,
h에 걸리는거여?  등 중복될것같은 생각이 들었습니다.


코드를 보면, expire명령어를 실행하면 g, expire가 되서 key가 지워지면 x,

hash에 item이 지워지면 h, db의 key자체가 지워지면 g입니다.

그리고 redis.io에서 얘기한게, 있지도 않은 키에대한 수정/삭제는 이벤트가 발생하지 않습니다.


key가 추가/수정/삭제시 위의 flag랑 이벤트명, key명을 가지고 호출하는 함수는 notifyKeyspaceEvent 입니다.



자 이젠 이 알람을 subscribe하면 됩니다
redis.io 문서에서는 아래와 같이 하라고 합니다.

$ redis-cli config set notify-keyspace-events KEA
$ redis-cli --csv psubscribe '__key*__:*'
Reading messages... (press Ctrl-C to quit)
"psubscribe","__key*__:*",1


성능은.....아무래도 느려지긴 할것 같습니다. 특히 __key*__:* 가......덜덜

저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

Slowlog는 지정한 시간이 넘어서는 command를 기록해서 나중에 관리차원에서 볼수있게 해줍니다.


설정으로 slowlog-log-slower-than, slowlog-max-len을 설정합니다.

slowlog-log-slower-than는 microseconds단위로써,
지정한 시간보다 느린 command를 기록합니다. threshold같은거죠.음수로 지정하면 slowlog를 사용하지 않고,
0으로 하면 모든 command를 기록합니다.

slowlog는 list 자료구조에 저장하는데, 이 List의 최대 크기를 지정하는 설정이 slowlog-max-len 입니다.
(검색하면서 알았는데, MySQL Slow Query log 란게 있었네요.

이젠 소스 분석하는만큼 직접 만들어보는것도 시간을 쏟아야겠어요 /엉엉/)



slowlog.c는 slowlogEntry를 만드는 slowlogCreateEntry, 해제하는 slowlogFreeentry,

server start할때 server.slowlog 초기화해주는 slowlogInit,

그리고 실제 slowlog-log-slower-than 이상 걸리는 명령어에 대해 로그를 저장하는 slowlogPushEntryIfNeeded

"slowlog reset" 를 담당하는 slowlogReset, 마지막으로 저장되어있는 slowlog의 정보를 볼수 있는

slowlogCommand 함수가 있습니다.


알아볼건, slowlogPushEntryIfNeeded입니다. 그리고 마지막으로 실제 해보고 slowlog를 마치겠스니다.

slowlogCommand도 후보였는데, 'slowlogEntry, length를 보고, slowlog를 reset하는 기능이다' 이게 끝이라;;;


slowlogPushIfNeeded 함수는 먼저 server.slowlog_log_slower_than이 음수면 return입니다.

그리고 command의 duration이 설정한 값보다 크면 그때 slowlogEntry를 만들어서

server.slowlog에 add해줍니다. 

argc, argv가 있는데 어간 redisClient 명령어 argument입니다. 또 인자의 갯수가 너무 많을수도 있는걸

고려해서 최대 32개의 인자만 저장하도록 되어있습니다.


마지막으로 server.slowlog-max-len이 server.slowlog의 max_length먄큼의 크기를 유지하는 작업을 합니다.



각 명령어마다 총 4개의 설명이 나옵니다.

1)은 server.slowlog_entry_id로서 slowlog_entry별 고유값입니다.

2)는 명령어가 실행한 unix timestamp

3)은 명령어가 실행하는데 걸린 시간, 단위는 microseconds입니다.

4)는 실제 명령어가 저장됩니다.



http://garantiadata.com/blog/enhancing-redis-slow-log#.URRHvdFx50w

그리고 오른쪽 "Don't let Redis scalability limitations turn into business limitations." 

동영상이 있는데 참 재미있게 만들었습니다.

물론 속도가 빠르고, 다양한 기능이 있는것도 중요하지만, 관리하는것도 그만큼 중요하다는 것을 다시한번 느낍니다.

저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

Redis 2.6부터 Bit operation이 지원되었습니다.


BITOP [NOT | AND | OR | XOR ], BITCOUNT, SETBIT, GETBIT  입니다.


Bit operation에 쓰이는 자료형은 String입니다.  String이 512MB가 제한입니다.

그래서 bit offset 의 최대 길이는 0 ~ (512*1024*1024*8 -1 )입니다.


SETBIT, GETBIT, BITCOUNT, BITOP 순으로 진행하겠습니다.


우선 SETBIT는 "SETBIT key offset bitvalue(0 | 1)" 입니다.

offset이 위에서 말한 bit 범위인지, bitvalue는 맞게 들어왔는지 검사합니다.


그 후에 해당 key가 기존 DB 존재 여부를 판단하고, 없으면 String형을 생성하고

있으면 value의  Type 검사와 참조 하는 데가 있는 지를 판단해서 처리를 해줍니다.


(offset >> 3) + 1 만큼 메모리  공간을 확보한 다음에 offset >> 3에 해당하는 데이타를 가져온 후

해당 offset에 bitvalue를 set 해줍니다.


======================= Example ===========================

key user1에는 00000000 01000000 00000000이 저장되어있고
setbit user1 20 1 실행한다고 하면

(10 >> 3) + 1  크기의 메모리를 할당한후, (키가 존재하고, 이미 더 큰 메모리가 할당 되있으면 이 부분은 패스~!!)

bit = 7 - (bitoffset & 0x7); 의 동작을 하는 이유는 한 byte는 0~7의 오프셋이 있고,

사람이 이해하기 편하게 하려고 한것같습니다.(제 추측....;;)


( (uint8_t*)user1에 해당하는 value->ptr)[(10 >> 3)] 을 가져오고 또한 offset의 값을 가져옵니다. 

offset의 값을 가져오는 이유는 client에게 원래 있던 값을 리턴하기위함입니다.
그리고 가져온 바이트는 3번째 byte 00000000 을 가져오겠네요.


이젠 ( (uint8_t*)user1에 해당하는 value->ptr)[(10 >> 3)] 값에 원하는 값을 세팅할 차례입니다.

byteval &= ~(1 << bit)
offset의 비트는 0으로 나머지 비트는 그대로 둡니다.. ( offset의 값만 set해주기위해)

byteval |= ((on&0x1) << bit);
그 다음 3번째 바이트와 ((on & 0x1) << bit); 결과와 OR연산을 합니다.

( (uint8_t*)o->ptr)[byte] = byteval;  로 set을 마칩니다.

======================= Example ===========================



Bit Operation에 대해 알아보겠습니다. 단순합니다. XOR, AND, OR, NOT bit 연산을 하는데,
그 방식이 4~xx 번째 인자의 value들을 bit 연산한 결과를 3번째 인자에 저장을합니다.


4~xx 의 인자들의 value를 가리킬 포인터와(unsigned char **src),
각 value의 길이(long *len)를 저장할 변수에 값을 대입합니다.   대입하면서 maxlen과 minlen을 찾습니다.


4~xx의 인자의 갯수가 16개 이하면, 이중포문으로 각 인자들의 value들을 minlen만큼 bit 연산을 합니다.

왜 16개인지는 모르겠네요;;   이중포문이 끝나면, minlen~maxlen에 대해서 bit 연산을 합니다.

4~xx의 인자의 갯수가 16초과면 바로 아래 포문을 탑니다. 

위의 이중포문에서는 unsigned long * 4 씩 뭉탱이로하고, bit연산자별로 나뉜다음에 포문이 있는데,

아래는 포문안에 switch가있고, byte로 연산을 합니다.


위 for문에서 연산한 결과를 3번째 인자에 저장합니다. 이미 해당 key가 있다면 지우고 다시 저장합니다.



마지막으로 bitcount가 있습니다. start와 end차이(byte단위)를 구해서 해당하는 byte의 bit가 1인걸 count합니다.

이 부분에 재밌는 두가지 있습니다. (나만 그럴라나......ㅋㅋㅋ)

첫번째는 16byte씩 뭉탱뭉탱 count하는것...  CountBitsSetParallel  에 있는걸 사용했습니다.

그냥보면 그저 멍합니다. 실행해보는게 답이죠 ㅋㅋ


결과 (보기편하려고 띄어쓰기는 제가.....;; 머리가 나쁘니 ㅋㅋㅋ)
0000 1100 1100 1101 0101 1011 1010 0100
0000 1000 1000 1001 0101 0110 0101 0100
0000 0010 0010 0011 0010 0011 0010 0001
0000 0000 0000 0000 0000 0000 0000 1111
Bit Num : 15
계속하려면 아무 키나 누르십시오 . . .
와우~!! 계산기랑 수작업으로 했는데 맞게 나오네요. 당연한걸.....ㅋㅋㅋ
대충은 알겠는데 마지막은 왜 저런지;;;; 알려주세요.

두번째는 위에서 뭉탱뭉탱하고 나머지 byte들은 1byte씩 count를 하는데,
이걸 또 그냥하지 않고 256배열에 해당 index의 1의 갯수를 미리 입력해 놓았습니다.
static const unsigned char bitsinbyte[256] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,
2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,
3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,
4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 아 센스쟁이....ㅋㅋㅋ


bit 연산할때 minlen, maxlen을 잘 따져서 그래도 좀 빠르게 할수도 있지않을까 생각해봅니다....


저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

Redis의 보안관련해서 소개하겠습니다.

http://redis.io/topics/security


위의 문서중에서 rename-command, masterauth/require가 어떻게 동작하는지 알아보겠습니다.


첫째로, rename-command에 대해 알아보겠습니다.

우선 어떤 기능이냐면, 일반적인 client가 특정 명령어를 못하도록 막는 기능을 합니다.

SORT나 FLUSHALL, CONFIG같은 명령어는 일반 client가 실행하게 하면 안되겠죠.


사용법은 간단합니다. redis.conf에   rename-command [org command] [new command]

ex ) rename-command FLUSHALL kakaka

아래는 실행 화면입니다.



populateCommandTable 함수로 redisCommandTable 에 명령어를 dict에 저장합니다.

그 다음에 loadServerConfig 함수가 호출됩니다.

redis.conf에 있는 설정들을 읽는 부분입니다. 수많은 if-else문이 있지요...ㅋㅋ

rename-command을 보면 아래와 같이 소스가 구성되어 있습니다.


populateCommandTable 에서 server.commands에 load한 command의 정보중 key값을 교체합니다.

sort, randomxxx, flush, config같은 명령어 들은 서버 관리자만 실행 할 수 있도록 바꿔놓으면 좋을것 같네요 ; )



두번째로 masterauth/requirepass에 대해 알아보겠습니다.

두 설정 모두 암호를 걸어 인증을 요구하도록 합니다. 차이점이라면 masterauth는 replication

          (master, slave관계에 있을때 사용)    requirepass는 client에 접속에 이용됩니다.

masterauth는 인증하는게 흠....replication 학습할때 알아보고 requirepass는 어떻게 인증하는지 알아보겠습니다.


서버가 기동될때 redis.conf에 설정한 requirepass는 server.requirepass에 저장이 됩니다.

그리고 client에서 auth 명령어로 입력한 암호와 server에 설정되어 있는 암호와 비교를 하는데, time_independent_strcmp로 합니다.

strncmp로 하면 되지 왜 굳이 모든 char를 비교하는지 모르겠네요;; 혹시 아시는 분있으면 알려주세요.: )

저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

Pub/Sub는 분산시스템에서 거의 뭐 필수적으로 사용되는 모델입니다.  간단히 말하면 그룹채팅같은거죠...


Redis에서는 이 모델을 어떻게 구현했는지 알아보겠습니다.



우선 channel에 참여하는 명령어 SUBSCRIBE는 (pubsub.c:pubsubSubscribeChannel) 를 호출합니다.

엇~?? 이거 어디서 많이 봤습니다.


redisClient->pubsub_channels(dict) 에 key : channel, value : NULL을 저장합니다.

그리고 watch와 마찬가지로 해당 server.pubsub_channels에 key와 client를 저장합니다.

WATCH와 다른점은 client에서 ilst가 아니라 dict로 정보를 저장하고 있다는점입니다.




서버에는 channel에 접속한 client 정보가(server.pubsub_channels),
클라이언트에는 subscribe한 channel명이 저장되어있습니다.(client.pubsub_channels)


특이한점은 channel을 패턴을 활용해서 여러체널을 한번에 참여할 수 있습니다.

패턴은 List자료구조 pubsub_patterns에 저장합니다.  psubscribe foo*는 pubsub_chennels에 저장되는게 아니라,

pubsub_patterns에 저장되게 됩니다.


dict가 아니라 list이기 때문에 search할때 O(n){n은 pubsub_patterns의 길이} 만큼 발생되게 됩니다.

아래에서도 보겠지만 publish를 하면  pubsub_channels에서 해당 channel에 저장되어있는 client에게 메세지 보내고,

pubsub_patterns에 저장되어있는 client에 메세지를 보냅니다. 그런데 패턴의 경우 stringmatchlen함수를 호출하는데

이놈이 List 길이만큼 탐색을 합니다.


말하고 싶은게 뭐냐면....'앵간하면 psubscribe보다는 subscribe를 쓰자' 입니다 ㅎㅎ


마지막으로 publish에 알아보겠습니다.

pubsubPublishMessage 함수로 channel명과 메세지가 인자로 넘어오면

pubsub_channels에서 channel을 검색하고, 있다면 연결되어있는 client로 메세지를 보냅니다. 

그리고 pubsub_patterns에서 channel을 stringmatchlen을 이용해서 검색하고, 

있다면 연결 되어있는 client로 메세지를 보냅니다.

저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

Redis에는 transaction기능도 있습니다. :) 

MULTI, EXEC, DISCARD, WATCH, UNWATCH 명령어가 있는데, 

transaction이 redisClient별 이루어 지는 관계로 우선 redisClient에 대해 먼저 알아보겠습니다.

redisClient 구조체는 아래와 같이 생겼습니다. transaction 설명하는데 필요한 변수만 적었습니다.



우선 MULTI, EXEC명령어에 대한 source를 보겠습니다.

redisClient 에는 flag라는 변수가 있는데, OR연산을 통해 아래와 같은 정보를 표시합니다.


MULTI라는 명령어를 실행하면 별거 없습니다. 해당 client의 flag에 REDIS_MULTI를 표시합니다. (multi.c:multiCommand)

MULTI이후에 명령어들은 EXEC가 실행되기 전까지 수행되지 않습니다.

어떻게 그렇게 되는지 보게되면 (redis.c :processCommand)


if문 안에 있는 문장들 반갑지 않나요? ㅎㅎㅎ REDIS_MULTI이고 그외 명령어들이 나오기 전까지는 queueMultiCommand를 실행합니다.


queueMultiCommand의 기능도 간단합니다. 입력된 명령어들을 실행하라고 서버로 보내지않고,
zrealloc하면서 명령어(c->cmd), 명령어의 인자값(c->argv)들을 c->mstate에 저장합니다.

MULTI를 실행하고 명령어 1000개 2000개 입력하면 그만큼 메모리를 할당하게 됩니다. 서버에 데이타가 

하나도 없어도 max_memory효과를 볼수 있겠네요?   ; ) ㅎㅎㅎ;;   


명령어를 다 입력했으면 이젠 실행 시켜야겠죠??  EXEC를 실행합니다.  (multi.c : execCommand)

딱~ 보이는게 REDIS_MULTI냐 아니냐를 판단하고,   c->flags & REDIS_DIRTY_CAS인지 아닌 지를 봅니다.

CAS에 대해서는 WATCH 명령어에 대해 알아볼때 자세히 하도록 하겠습니다. 

지금은 그냥 REDIS_DIRTY_CAS인 경우 mstate에 있는 명령어들이 실행이 안되는구나....라는 정도만 이해해도 좋을 것 같습니다.


정상적이라면 아래 처럼 그동안 모아두었던 명령어들을 수행합니다.


마지막으로 server.dirty++를 하게 되는데 replication, AOF할 건덕지를 남겨주는거라고 합니다. dirty = 0인게 좋은거죠.ㅋㅋㅋ


WATCH명령어에 대해 알아보겠습니다.

http://redis.io/topics/transactions 에 보면 Redis는 Optimistic Lock을 사용한다고 합니다.

제가 영어가 짧아 소스로 배웠습니다.  

optimistic concurrency control Wiki에 보면 아래와 같이 설명했습니다.

  • Begin : transaction을 시작한다고 timestamp를 기록 (Redis에서는 WATCH명령어)
  • Modify : 값을가져오고 가공을한다   (Redis에서는 MULTI명령어 이후 일반 명령어까지~)
  • Validate : 가공된 값을 저장하려고 할때 이값이 유효한(valid)지 검사
               (Redis에서는 EXEC명령어를 수행하면 REDIS_DIRTY_CAS를 검사)
  • Commit/ Rollback : 아무런 문제가 없으면 Commit, 문제가 있다면 지금까지 입력했던 명령어들 무효


watched_keys가 그 역할을 해줍니다.

흐름이 어떻게 되는지 알아보겠습니다.

우선 서버가 가동되면 redisDB를 생성합니다(redis.c:initServer)



빨강색 안쪽이 생성되는거죠.



서버가 가동됐습니다. 
다음엔 client가 생성될 때 (network.c:createClient) c->watched_keys = listCreate();를 수행합니다.



client에서 WATCH 명령어를 날릴때는 아래와 같은 동작을 합니다.





동일한 redisDb에서 동일한 key를 다른 client가 수정을 하게되면 다음과 같은 연산을 합니다.(multi.c:touchWatchedKey)

EXEC 명령어를 실행하면 validate를 검사합니다. 상상가시죠? 

해당 client의 flag가 REDIS_DIRTY_CAS인지 검사하는것입니다.

check결과에 따라 commit을 할건지, rollback을 할건지 정합니다.


저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

Redis는 두 종류의 persistence기능을 가지고 있습니다. RDB와 AOF가 있습니다.


RDB에 대해 알아보겠습니다.  snapshot입니다.


끝....은 페인팅이고...


RDB는 해당 시점에 저장되어있는 데이타를 모두 iterator로 돌면서 key, value, expire정보들을 파일에 기록합니다.


파일에 기록할때는 rio라는 interface를 사용합니다.                단순합니다.   

read, write, tell(현재 file pointer의 위치를 리턴), checksum 함수 포인터가 있고, 
union으로 메모리에 쓸때 사용하는 구조체, 파일에 쓸때 사용하는 구조체가 있습니다.


memory인지, 파일인지에 따라서 사용하기 전에 초기화를 해줍니다.

재미진건 rdb에서 crc64를 이용해서 checksum을 만듭니다.

파일에 쓸때마다 checksum을 계산합니다. 그리고 모든 db의 내용을 다쓰고 마지막에 checksum을 기록합니다.

나중에 파일 손상이나 악의적인 수정을 방지하려는 장치가 있네요 : )
(학교공부 하다가 알았는데, md5sum 동작을 구현했네요.)

http://stackoverflow.com/questions/3395690/md5sum-of-file-in-linux-c


RDB를 load할때 read에 대해 checksum을 하고, 최종 결과와, file에 있는 checksum과 비교를 해서 같아야 정상,
아니면 redis종료를 하게 됩니다.  파일에 대한 변조 검사보다 좀 더 빠르게 하는게 좋다고 생각하신다면
redis.conf:  rdbchecksum no로 설정하시면 되겠습니다.




config에 save옵션이 있습니다. 몇건 이상 변경우, 몇초 이상의 조건을 만족할때 save를 하는 옵션입니다.

설정된 값을 체크해야하니까 serverCron에서 check를 하겠죠?

서버 init시 config.c:appendServerSaveparams에서 save관련 구조체에 값을 세팅합니다.

아하~!!!! dirty의 용도가 저거 였군요~!!!!



데이타를 기록할때 Redis만의 encoding방식이 있다. 조사하다가 정리가 잘된 블로그를 발견했습니다. : 0 
어떤식으로 RDB를 기록하는지 보다 자세히 알고싶으면 참고하세요~~ : ) http://invents.sinaapp.com/lab/?p=432 

Redis 소스를 보면서, 처음봤을때는 참~~ 쉬워보였는데, 보면 볼수록 절묘하게 이어지게 짠 소스들에 감탄을하고, 
아직 모르는게 태반이라는걸 깨닫네요. 그리고 질좋은 중국어 자료들이 많아지고 있는걸 느낍니다. 


결론은........분발해야겠어요. 그저그런 개발자로 살고싶지 않다면.........엉엉 ㅠ,.ㅠ



저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

http://redis.io/commands/expire

위 링크와 소스를 보고 이해했습니다.


expireGenericCommand 함수에서 설정을합니다.

expire는 마스터에서만 직접 이뤄집니다.

그리고 (설정시간이 현재보다 이전시간이고, AOF를 로딩하지않고, 마스터일때의 동작)과 (그렇지 않을때의 동작,) 
두가지 branch가 나옵니다.


첫번째의 경우는,  이미 시간이 지나간 것이니 삭제를 수행합니다. (networking.c rewriteClientCommandVector 따로 포스팅 해야겠다...)   

두번째의 경우는 redisDb의 expires dict에 key를 저장하고 signalModifiedKey를 수행합니다.

Redis에서는 Optimistic Lock을 사용합니다. get / set 연산에 대해서 lock이 필요하겠죠~

1. val = [get kang]

2. val += 10

3. [set kang val]

2번일때 kang 에 대해서 다른 명령어가 온다던가, 다른 클라이언트에서 kang 에 대해 다른 연산을 할 경우

원치 않는 결과가 나옵니다. sequence를 보장하고 싶다면 watch~!를 이용합니다.

Redis의 transaction 은 다른 transaction과 마찬가지로 '모 아니면 도' 로 실행합니다.

즉~!! signalModifiedKey 함수는 해당 키에 대해 '수정했음' 표시라고 생각하시면 됩니다.

             (다른 클라이언트에 대해서는 무효임ㅎㅎ)
100마디 말보다 1장의 스샷 ㅋㅋㅋ

(redis의 transaction에 대해서는 , transactions)





REDIS_HZ(100ms)마다 serverCron을 수행합니다. 어떻게 100ms마다 동작하는지는

http://redis.io/topics/internals-rediseventlib 를 참고하면서 따로 포스팅을 하려고 합니다. : )

일단은 serverCron이 100ms마다 수행이 되는구나.....라고 가정하고 어떻게 expire를 체크하는 지 알아보겠습니다 


실제 expire를 실행하는 함수는 redis.c : activeExpireCycle 에서 수행합니다.

    if (server.masterhost == NULL) activeExpireCycle();     //master인 경우에만 수행

expire하는데 다음과 같은 정책이 있습니다.

 * expire의 dict 의 실제 사용량과(dictht의 used) 할당된 양과(dictht의 size)의 비율이 1%라면  break~!!! 
    (servercron 에서 tryResizeHashTables로 검사)

 * do-while의 loop당 최대 10개의 expire key만 검사합니다. (성능이슈로인해)

 * do-while 16번 수행될때마다 시간검사를 해서 timelimit 이상의 시간이 수행되면 loop종료 (이놈도 성능이슈)
    ( timelimit = 1000000*REDIS_EXPIRELOOKUPS_TIME_PERC/REDIS_HZ/100; 는 왜 하는지 이해가 안되는데...)

 *  do-while loop 한번에 REDIS_EXPIRELOOKUPS_PER_CRON/4 개의 키도 못 지웠다면 loop 종료


위에 정책을 말로 풀어보자면, 

    100ms가 지나서 activeExpireCycle 수행 


start = ustime()

if (used와 size비율을 봐서 1%미만)종료~!!

do {

    { 임의의 key 10개 가져와서, 시간된(?ㅋㅋ) key는 삭제; expired++}

    iteration++

     if (iteration == 16 && 지금시간-start > timelimit) 종료

} while( expired > REDIS_EXPIRELOOKUPS_PER_CRON/4)


삐딱하게보자면,  expire가져올때 임의로 가져오는데 expire가 아닌 한참 남은 키만 계속 가져오면 아웃~!!

2000개정도의 key에 대해 동일한 TTL값을 지정했을때 동시에 지워지지 않는다~!! 뭐 이정도 생각해볼 수 있겠네요.

실제 소스입니다


저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

Sorted Set은 ziplist와 SkipList라는 자료구조를 사용합니다.


SkipList자료구조가 생소해서 소스까지 이해하는데 시간이 좀 걸렸던 기억이 나네요;;

순서대로 읽으시면 이해하시는데 더 편한것같습니다.

가장 강추는 http://www.slideshare.net/jongwookkim/skip-list ~!!

http://www.lsi.upc.edu/~conrado/research/talks/survey-CALIN.pdf search와 insert에 이해가 쉽도록 그려줬음 : )

http://en.wikipedia.org/wiki/Skip_list


수학적인 얘기나오면 무조건 패스~!! 했습니다. 영어가 좀 많다싶어도 패스....(하........멀기만하네요;;)


skiplist에 대한 얘기는 저 3개의 자료로 얼렁뚱땅 마치겠습니다;; 한번 짜면 좋을것같은 자료구조입니다.


t_zset.c은 t_set.c과 비슷한 역할을 합니다. 다른점이라고하면 set에서는 value가 기준이 되어 정렬했다면, zset은
score를 기준으로 정렬이 됩니다.


처음에는 ziplist에 저장을합니다.

뭐 아래와 비슷하게 저장합니다.

위에처럼 저장하다가 entry갯수가 zset_max_ziplist_entries 이상이거나, 

입력된 value가 zset_max_ziplist_value의 길이를 넘는다면 SKIPLIST로 데이타형을 변경합니다.

skiplist는 뭐 알아서 잘 들어가겠죠....;;


저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis
RDB는 snapshot같이 수행한 순간에 데이타를 파일에 기록합니다.
여기서 문제점이 있는데 기록하는 순간에 컴퓨터 파워가 나가거나, 
kill -9 로 강제 종료한다면, 마지막 정상적인 rdb파일 이후에 들어온 데이타는 잃어버리게 됩니다.

그래서 append-only-fie을 사용하게 됩니다.  
 제가 생각한 AOF개념은 데이타를 파일에 쓸때 모든데이타를 한번에 쓰지말고( RDB),  버퍼를 만들어서 
일정크기, 일정시간동안 입력들어온 데이타는 버퍼에 기록하다가 파일에 붙여 넣자입니다.

소스를 보니까 파일에 기록된 것 이후에 들어온 query는 파일에 append도 하지만
fork후 child process가 현재 dict에 저장되어있는 데이타를 파일에 기록하고,
기록 하는 동안에 client의 명령어들을 aof_buf, aof_rewrite_buf_blocks에 저장하는 로직도 있습니다.
redis.io에서 말하기는 파일에 기록된 것 이후에 데이타만 append 하면 
[set kang 1, set kang 2, set kang 3... set kang 1000] 같은 명령어들이 많이 들어오면
AOF 파일 크기가 어마어마하게 커질 수 있는데, 그 이유로 인해 특정 조건이 충족되면 모든 dict의 데이타를
순회하면서 파일에 기록합니다.
여기서 말하는 특정조건은 이전 AOF 파일의 크기가 정해진 비율이상으로 증가 된 경우,
BGREWRITEAOF명령어를 수행한 경우를 말합니다.
  


AOF에 대해 보다 보니 생각나는 사물이 있었습니다. 
바로바로

                                      [출처 :  백전리 물레방아]


물은 데이타, 바닥은 파일, 물레방아에 있는 홉들이 버퍼라고 생각하면 딱이네요. 역시....우리 조상님...

AOF와 관련된 소스는 aof.c, bio.c, redis.c입니다.

Redis에서 파일에 기록하는 데이타는 명령어들로 이루어져있습니다.

그래서 client에서 명령이 들어 올때마다 아래 작업을 진행합니다. 

redis.c:processCommand 에서 call(c, flags)를 호출 합니다.
call 내에서는 command가 dirty를 증가 시키는 거면 aof를 체크하고 propagate를 수행합니다.
propagate 함수는 AOF와 Replication을 수행합니다. 지금은 AOF만 보겠습니다.
(replication 포스트 쓸때는 여기서 부터 진행하면 되겠네요...흐흐)

propagate는 feedAppendOnlyFile를 호출 합니다.
client에서 보낸 데이타를 임시 메모리에 저장하는 함수가 되겠습니다.
두 개의 경우가 있는데 AOF_ON상태이면  server.aof_buf에 저장하고(sds), 현재 child process가 사전을 탐색하면서
파일에 쓰는 작업 중인경우에는 server.aof_rewrite_buf_blocks(list)에 저장합니다.
언뜻 보면 둘중에 하나만 해도될것같은데 if...else, if...if로 한 이유는  child process 작업 중이라
server.aof_rewrite_buf_blocks에만 기록 하고있는데, 서버가 중지되면, 그 사이의 내용은 사라지게 됩니다.
(server.aof_rewrite_buf_blocks은 child process가 종료되어야만 파일에 기록됩니다.)
그래서 aof_buf에도 기록하고, aof_rewrite_buf_blocks에도 기록합니다.

맨 먼저 보이는 게 기존에 사용하는 디비 번호와 다른 디비번호인 경우 select command를 저장해주는 부분이 보입니다.
그리고 다음에는 expire command냐, expire이고 set command이냐, 그리고 나머지냐? 로 나누어 
buf에 명령어를 저장합니다.

client가 명령어를 날리고, 그걸 AOF에 쓸 수 있게 가공해서 임시 buf에 저장까지 했습니다.
이젠 이 임시 buf를  server의 버퍼(server.aof_rewrite_buf_blocks)에 저장하는 
aofRewriteBufferAppend 함수를 호출합니다.



aofRewriteBufferAppend 함수의 기능은 위에서 가공한 buf를  server.aof_rewrite_buf_blocks에 저장 합니다.
aof_rewrite_buf_blocks은 List형으로 되어있고, 한  노드는 aofrwblock 로 이루어졌습니다.
마지막 노드로 이동해서 남은 공간에 buf를 저장하고, 그래도 buf가 남았다면 다시 block을 만들어서 저장합니다.

여기까지가 client가 명령어를 날리고 그 명령어가 server.aof_rewrite_buf_blocks에 저장되는 과정을 알아보았습니다.

 redis.c:serverCron에서 AOF관련 로직에 대해 살펴보기 전에 몇가지 설명하고 진행하겠습니다.
rewriteAppendOnlyFileBackground function은 process를 하나 만들어서 child 가 현재 dict의 데이타를 훑으면서 파일에 기록합니다.   
소스 보시면 아시겠지만 temp-rewriteaof-%d.aof파일에 기록하고 완료되면 temp-rewriteaof-bg-%d.aof로
파일명을 변경합니다.

그리고 bio.c의 기능을 사용하는데 background  I/O의 줄임말로, main thread에서 fsync나 close를 직접 수행하면 block이되기
때문에 bio를 만든것같습니다.   thread 두개를 만들어서 하나는 file descriptor를 close하는 Job을 담당,
다른 하나는 file descriptor 를 fsync 하는 Job을 담당합니다. 각각의 Job들은 Queue형식으로 저장을 합니다.

redis.c:serverCron에서 AOF관련 로직은 다음과 같습니다.    



마지막으로 Redis 는 fsync를 always, everysec, no 설정을 사용자가 수정 가능하도록 만들었습니다.
write(fd, buf, strlen(buf) 한다고 바로 파일에 기록 되는게 아니고, Kernel 내부 버퍼에 기록을 한다고 합니다.
(대충 알고있는건데 자세히 아시는분은 설명 부탁드려요....굽신굽신)
그래서 이 버퍼에 있는걸 실제 파일에 기록하는 명령이 fsync입니다. 이 작업을 파일에 쓸 때마다 할거냐,
아니면 매 초 할거냐(정확히 1초단위는 아니에요.), 아니면 알아서 파일에 저장하도록 냅둘것 이냐를 정합니다.
flushAppendOnlyFile, backgroundRewriteDoneHandler에 로직이 있으니,
성능상 수정 하실 분들은 참고하시면 좋을 것 같습니다.


저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

Set은 intset과 hashtable을 사용합니다.


hashtable은 hashes에서 설명한것처럼 dict을 사용합니다.

intset에 대해 알아보겠습니다.


contents에 value값이 들어가고 encoding에는 현재 어떤 int형인지 (INTSET_ENC_INT16/32/64)

length에는 현재 저장한 value의 갯수가 저장됩니다.


insert할때는 binary search로 해당값이 있는지 확인하고 없으면 min 위치에 값을 저장합니다.


처음에 encoding은 int16_t로 하는데 그 범위에 벗어나는 값이 들어오면 전체 데이타를 다 수정합니다.;;;
intsetUpgradeAndAdd
아~~ 같은값이 있으면 뭐 상관없는데, 아니라면 아래 작업을 수행합니다.
resize후에 memmove로 저장할 위치 비워두는것 (포인터 안쓰면 이방법밖에 없는거겠죠? 덜덜)

t_set.c에서 intset과 hashtable중 어떤걸 쓸지 결정하는데, list나 hashed처럼 entry갯수제한이 있습니다.
(set_max_intset_entries)
또한 입력되는값들이 숫자면 intset, 문자열이 입력되면 그때부터 hashtable을 사용합니다.
직접 실행한 화면입니다.



마지막으로 intset은 object로 관리되지않기 때문에 decrRefCount, hashtable은 incrRefCount 입니다.


set 데이타 명령어중에 Intersect ,union 기능이 있습니다. 그중에 Intersect 부분이 어떻게 작성됐는지 궁금했습니다.
소스보니까;;; 간단하네요. 결론부터 말하자면 intset으로 Intersect 하는게 가장~!! 좋네요; ㅎㅎ

먼저 Intersect 할 데이타들을 qsort로  갯수기준으로 오름차순 정렬합니다.
그럼 가장 첫번째애가 가장 적은 set이겠죠?

그럼 대강 아래와 같은 방식으로 intersect를 수행합니다.

오오 Set은 간단하게 끝~!!

저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

http://antirez.com/post/redis-as-LRU-cache.html


http://eli.thegreenplace.net/2009/10/30/handling-out-of-memory-conditions-in-c/


위 두개의 글을 참고한다음에 소스를 보면 더 이해가 쉽습니다. 

(저는 영어가 짧아 굵은글씨만 읽고 바로 소스로;;; 으헝헝~~)


Redis는 메모리 기반 key-value시스템입니다. 메모리는 한정되어있기때문에 무한정 데이타를 저장할수가 없죠.

그래서 Redis에서 나름대로 몇가지 방법을 만들었습니다.




소스를 보면서 하나씩 알아보도록 해요.

server가 가동되고 client가 접속을 하면 아래와 흐름으로 처리가 됩니다. 


으헉 많이도 거치네요. 자세한건 network(select, kqueue, epoll) 살펴볼때 알아보겠습니다. 여기서는 freeMemoryIfNeeded 함수에 대해 알면 되겠네요~~ : )


사전에 있는 데이타를 정리하기전에, AOF와 slave의 buffer들을 정리해줍니다.(AOF, Network 빨리봐야겠네요...)


while(mem_freed < mem_tofree){ } 에서 어떤일을 하는지 알아보겠습니다.


REDIS_MAXMEMORY_ALLKEYS_LRU, REDIS_MAXMEMORY_ALLKEYS_RANDOM인 경우는 실제 dict를

그 외에는 expires를 선택합니다.


Random Policy는 간단하게 dictGetRandomKey 함수로 key를 고르고,


LRU Policy는 maxmemory_samples 갯수 만큼 random하게 키를 고르고 그 키의 value의 시간을 잽니다.

그래서 가장 오래된 key를 bestkey로 선택합니다.


TTL Policy는 expire에 있는 key중에 maxmemory_samples 갯수만큼 임의로 골라서

그 키의 value(expire한 값)를 비교해서 가장 작은값을 bestkey로 선택합니다.


마지막으로 하는 일은, slave에게 bestkey를 삭제하라는 명령과 aof에 지우라는 기록을 남기게 합니다.

그리고 실제 지워진 메모리를 계산을 합니다.


이 동작을 확보하고자 하는 메모리가 될때까지 반복합니다.

저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis
이번 프로젝트에 Redis를 적용하려고 Redis에 대해 조사한 자료입니다.

Redis를 캐시가 아닌 저장소로 사용하려고했습니다.
조사하고 발표하는중에, Redis가 빠른건 알겠는데, 장애발생시 복구 문제에 대해 이슈가 됐습니다.
(expire, flush도 이슈)
데이타가 들어올때 1초에 1000건 이상이 들어오는데 aof, rdb도 이 부분에 대해서는 조금 아쉬웠습니다.

보시고 내용이 이해 안되거나 틀린부분이 있으면 알려주세요.
(ppt자료 이쁘게 만들려면 어떻게 하는거죠? 후덜덜)
감사합니다~ : )

Redis.pptx



저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis
Dict는 다양한 자료구조를 담는 기본적인 redis의 자료구조입니다.  
key, value형식으로 되어있고 value에 사용자가 입력한 자료구조(?)들이 들어가게 되죠

출처 : http://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_1_LL.svg

사용자가 입력한 John Smith, Lisa Smith같은 key값들이 hash function을 통해서 나름 고유한 숫자로 바뀌고
그 숫자들이 키가되고 키마다 value를 가리키고 있습니다.


주목할건 John Smith, Sandra Dee입니다. hash function을 통해 나온값이 동일한 값이 나오는 경우가 있는데(hash collision) 해결 방법중에 하나가 리스트 형식으로 동일한 hash value에 대해 처리를 해줍니다.

하지만 리스트가 길어지면 성능의 문제가 발생하기 때문에 
결국엔 bucket 크기를 늘려줘야 하는데 Redis 에서는 어떻게 동작하는지 밑에서 알아보도록 하죠 : )



dict의 구조

dictht, dictEntry 에서는 앞서 말한 구조를 구현해 놨고, 

dict 에서는 rehash를 위해서 두개의 dictht 와 hashfuction, key, value 비교/복사/삭제를 위한 dictType을 가지고 있습니다.


 
dictCreate를 하면 dict *d = zmalloc(sizeof(*d)); 를 수행합니다.
자~ 지금부터 재밌습니다. : )


dict에 데이터를 저장하는 순서입니다. (rehash라는 부분이 있는데 이건 뒷부분에 설명하기로 하고, 여기서는 데이타 삽입에 대해서만 알아보겠습니다.)

처음에는 아래의 코드로 인해 4개의 bucket으로 시작합니다.



데이타를 삽입을 계속 진행하다보면, 하나의 bucket에 많은 dictEntry가 이어져서
탐색하는데 상당한 시간이 걸리게 됩니다.
이때 아래와 같은 조건이 될때  Expand를 수행하고 Rehash를 수행합니다.


rehash되는 도중에 데이타 삽입이나, 삭제, 검색이 수행되면 문제 생기는거 아니냐? 라는 생각이 들었지만
소스를 보니 그 걱정은 뚝~!! ht[0]에서 없으면 ht[1]에서 검사합니다.

한번에 ht[0]의 모든 bucket을 Rehash 했으면 좋겠지만, 여기에서는 아래의 경우 하나씩하나씩 Rehash를 수행합니다.(여러개를 할수도 있습니다.)

dictAddRaw, dictGenericDelete, dictFind, dictGetRandomKey 함수 호출할때~!!

rehash 중일때는 ht[1]에 데이타 추가합니다.

rehash가 모두 끝나면, 즉 ht[0]에 used가 0이 되면, ht[0]은 ht[1]이 가리키고 있는
 table을 가리키고 ht[1]은 reset됩니다.


 검색의 색인구조에 사용해도 될것 같네요.  : )  key는 키워드, 데이타에는 출현한 문서번호들...
이상 dict 설명을 마치겠습니다. 

다음에는 value에 저장되는 자료구조들에 대해서 알아보겠습니다.(String, Hash, List, Set, SortedSet)

아래는 Redis의 자료구조를 정말 잘 표현한 그림 한장입니다.
예~~전에 좋다고 그냥 다운받아서 출처를 모르겠네요;; 혹시나 구글 이미지검색했는데....ㅋㅋ
문제가 된다면 지우겠습니다.



저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

약 1년전

http://dol9.tistory.com/141

http://dol9.tistory.com/132

사회 경험 2년, 개발에 마음을 정한지 4년이 된 그 시점......
뭔가는 해야겠는데, 주변에 개발하는사람은 없어 물어볼 사람은 없던,
이것저것 다 재미있을것 같은데, 막상 어떤껄 할지 몰라 방황하는 그때,

github를 알게되었고, Redis라는 걸 알게되었다. 처음 그 소스를 처음본 내 느낌은 흥분의 도가니였다.
근데......흥분만 한게 문제......ㅋㅋㅋㅋㅋㅋ 분석을 한다한다 했는데 여지껏 못했다.


1년이 지난 지금 회사에서도 필요하고, 내가 발전하는데도 필요해서 Redis를 
소스를 하나씩하나씩 분석해보려고 합니다. (Redis 2.6)  (시간은 1년 반이 흘러....덜덜)

1년전, 저와 같은 고민을 하시는 분들에게 조금이나마 도움이 되었으면 좋겠습니다.

먼저 경험하신 분들의 글을 보고, 많은것을 배웠는데,
제가 쓴 글들도 누군가에게 그랬으면 좋겠습니다.

더 나아가서는 저랑 비슷한 관심사를 가지신 분과 같이 뭐라도 했으면....하는 마음이 있습니다.

잘못된게 있다면 지적해주시고, 설명이 애매한게 있다면 알려주세요.
환영합니다.

Object

Data Type


Expire

Transaction

Pub / Sub

Persistence





Redis process Flow~ ( server init과 command에 대한 동작), mimul님이 너무나 잘 설명해주신 블로그 링크



언젠가는 볼것....
call function & cronJob  (epoll의 이해 및 실습이 시급합니다 덜덜)
replication                    (epoll의 이해 및 실습이 시급합니다 덜덜)
network                        (epoll의 이해 및 실습이 시급합니다 덜덜)
sentinel                        (epoll의 이해 및 실습이 시급합니다 덜덜)
list명령어중 앞에 'B'들어간 명령어
뭐가 달라졌길대 zrank가 빨라졌는지 https://github.com/antirez/redis/issues/943
Trie 자료구조 우왕 굿~!!          https://github.com/antirez/redis/pull/717
ZRANK ability to return 'unique' rank     https://github.com/antirez/redis/issues/943
zadd - Redis is modifying large "odd number" scores   https://github.com/antirez/redis/issues/1071
TTL keys      https://github.com/antirez/redis/issues/1067
Add Zrank Unique https://github.com/antirez/redis/pull/2011
Make 'lookupKeyRead‘ return NULL if key is expired and current client is not master #1770  https://github.com/antirez/redis/pull/1770 (https://github.com/antirez/redis/issues/1768)
digits10 not applied in networing.c https://github.com/antirez/redis/issues/1994
Lazy free of keys and databases https://github.com/antirez/redis/issues/1748
PFADDEX https://github.com/antirez/redis/issues/1735
BLPOP with LIMIT option https://github.com/antirez/redis/issues/936
LSPLICE https://github.com/antirez/redis/issues/550
zdiffstore https://github.com/antirez/redis/issues/446


https://github.com/antirez/redis/issues/1622
https://github.com/antirez/redis/issues/1748
https://github.com/antirez/redis/commit/0ce352c19f296c37893f5f506af3c4fa7f496d37

루아 쓰는것도....희망사항....지금것도 버벅되고있는데 과연 할까......


대략적인 흐름,
http://pauladamsmith.com/articles/redis-under-the-hood.htm


저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis
sds는 Redis에서 사용하는 문자열 관련 자료구조다


문자열을 붙이고, 메모리가 부족하면 다시 재할당하고.......
비교하고 삭제하고, 이런건 알겠는데
sdshdr의  buf[]의 개념이 뭔지 너무너무 궁금했다


kldp에 질문을 해서 http://kldp.org/node/128629   
flexible array member 키워드를 알게 되었고
검색한 결과 두개의 url을 통해 확실히 알게됐다

아래 두 url을 읽고, 이해하면 String은 끝~~ㅋㅋㅋ 날로먹네!!!

http://minjang.egloos.com/2254472
http://tksssch29.tistory.com/entry/Flexible-array-member

minjang님 blog에서 포인터로도 가능한걸 보여주면서 지역성 문제를 예로 들었다.


그런데 아래와 같이 하면 되지 않을까?   혹시 제가 잘못 생각한거라면 알려주세요~~



result : size : 12 string : kang han goo
          len : 0x0x9281008, size : 0x0x928100c, buf : 0x0x9281010


그리고 sdsnew, sdsnewlen을 할때 struct sdshdr* 을 리턴하는게 아니라 실제 문자열 포인터를 리턴한다.
그럼 len, free 정보를 알고 싶을때는? 

struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));   access횟수를 줄이기위한 좋은 팁을 배웠다. ㅎㅎ :)
구조체 중에서 자주쓰는걸 직접 리턴하고 메타정보들은 포인터 이동으로 접근!!

저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

Redis에서 사용하는 기본 List구조는 우리가 아는 Doubly Linked List입니다. (adlist.c)

그런데 List의 구조체가 아래와 같이 생겨먹었습니다.

value 3을 저장하게되면 기본으로 value의 크기 + sizeof(list) 만큼의 메모리가 사용되게 됩니다.
이를 아깝게 생각한 두 Redis 커미터는 메모리를 아끼는방법이 없을까.....생각합니다.
그게 ziplist와 zipmap입니다. 여기서는 ziplist에 대해서만 알아보겠습니다.
ziplist에 대한 발표자료 4~11 쪽입니다.

ziplist의 구조는 다음과 같습니다.
<zlbytes><zltail><zllen><entry><entry><zlend>

zlbyte는 ziplist의 전체 크기로 byte단위이며, 자료형은 unsigned integer입니다.
zltail은 tail Entry가 시작 offset을 가집니다. 이것도 unsigned integer
zllength는 16 byte이고, ziplist entry의 갯수입니다.  zlend는 1 byte이고, 255인 경우 ziplist의 끝을 뜻합니다.

여기서 모든 숫자는 little-endian order 을 사용합니다.
little-endian의 장점은 낮은주소에 하위 byte를 저장하기 때문에 byte씩 읽어들이면서 필드 구분을 바로 바로 할수있습니다.  (반면에 big-endian은 첫 byte로 음수인지 아닌지 판단이 가능하겠죠.)
<little-endian   and big-endian>   , 바이트 순서



entry에는 실제 데이타와 두개의 header로 구성되어 있습니다.
첫번째 header는 이전 entry의 크기 
두번째 header는 현재 entry의 크기를 나타냅니다.

첫번째 header의 규칙은 다음과 같습니다.
이전 entry의 크기가 (두개의 header 크기 + value의 크기)가 254보다 작으면 1 byte만 사용
254보다 크거나 같으면 1byte에는 254를 기록하고, 뒤에 4 bytes에 이전 entry크기를 저장합니다


두번째 header는 1 byte 읽어서, 

1 byte가 00xxxxxx 이면, value type은 String이고 63보다 같거나 작은 경우
2 bytes가 01xxxxxx xxxxxxxx 이면, value는 String이고 16383보다 같거나 작은 경우

5 bytes가 10______ xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx이면, value는 String이고 16384보다 큰 경우


1 byte가 11000000 이면, value는 int16_t    value 2bytes

1 byte가 11010000 이면, value는 int32_t    value 4bytes

1 byte가 11100000 이면, value는 int64_t    value 8bytes

1 byte가 11110000 이면, value는 int24_t    value 3bytes

1 byte가 11111110 이면, value는 8bit signed integer  value 1 byte


1 byte가 1111xxxx 이면, value는 4bit integer(0000~1111사용가능하지만,    
11110000은 int24_t에서 사용, 11111111은 ziplist end를 나타낼때 사용하므로 0001~1101를 사용가능,

실제 숫자는 0~12를 표현하므로 ziplist에 저장된 value에 -1을 한값이 실제 값이 된다.

1 byte가 11111111  이면 ziplist의 끝



(next도 있는데 그려보니 지저분해서....귀찮아서 화살표 저런거 아니에요 ㅋㅋㅋ)

prev, next pointer를 value의 길이, datatype에 따라 최대한 메모리를 아껴 list와 동일한 기능을 하도록 구현됩니다.
첫번째 header를 통해 이전 entry의 시작점을 알수있고, 두번째 header를 통해 다음 entry의 시작점을 알수있습니다.
물론 pointer는 그냥 쓰면 되지만 위에처럼 하게되면 encoding, decoding하는 과정이 필요합니다.


__ziplistInsert, __ziplistCascadeUpdate 에 대해 설명하려고 합니다. 

먼저 __ziplistInsert에 대해 알아보겠습니다.

===================================================================================================


삽입되는 위치가 tail이 아닌경우의 사진에서 2번을 보면 reqlen + nextdiff만큼 메모리를 재할당 했습니다.
이유는 그 차이만큼의 header 크기가 필요하기때문이다.
1번사진의 두번째 entry의 크기가 nextdiff 만큼 커졌다고 보면 됩니다.


__ziplistCascadeUpdate를 살펴보겠습니다.

tail에 있는 entry를 삭제하거나 추가하면 아무 문제 없지만,
header나 중간위치에 insert/delete 연산이 들어가게되면 위에서 본것처럼 header의 크기가 달라집니다.

header의 크기가 달라지면 결국엔 그 entry의 크기가 달라진것이고,
그렇다는건 결국 다음 entry의 prev header가 변경되어야 한다는 말이 됩니다.
그 작업을 __ziplistCascadeUpdate 수행합니다.
insert/delete된 위치에서부터 entry하나씩 하나씩 살펴보면서 header를 수정합니다.

아래는 언제까지 header update를 수행하는지 주석으로 적어보았습니다.


https://github.com/antirez/redis/issues/627    에서 nextdiff에 대한 issue가 나왔습니다. 

(우왁~!! 나는 백날 봐도 이해하기 바쁜데.....ㅠ,.ㅠ)
first 는 지우려는 entry의 첫 entry, p는 마지막으로 지워지는 entry에 다음 entry
testcase 만드는거 배울만 하네요. ; ), 영어도......;;

마지막으로 두개의 list를 관리해주는게 t_list.c입니다.
이놈이 list관련 명령어가 올때 ziplist로 할지 doubly linked list로 할지 정해줍니다.

그 역할을 하는 함수가 listTypeTryConversion입니다. redis.conf의 두개의 설정값에 따라서 그 이하인 경우엔 ziplist, 아니면 doubly linked list를 사용합니다.
512개 entry, value최대길이 64, 더 크게하지 왜 저렇게 했을까요?
pdf 발표자료에 벤치마크결과가 있는데 간단히 말하면
아까도 언급한것처럼 encoding/decoding과정이 있기때문에 entry가 많아지면 성능이 저하가 나온다고 하네요.
조금씩 늘려봐서 자신의 서비스에 맞게 조정하는것도 좋을것 같습니다.


redis.conf에 입니다.

# Similarly to hashes, small lists are also encoded in a special way in order
# to save a lot of space. The special representation is only used when
# you are under the following limits:
list-max-ziplist-entries 512
list-max-ziplist-value 64

마지막으로 listTypePush 함수를 보면 ziplist의 경우 decrRefCount, linked list의 경우는 incrRefCount 입니다.
이유는 간단합니다. redis의 모든 값들은 object로 다루게되는데,
ziplist의 경우는 object가 아니라, ziplist에 직접 value를 기록하기때문에 decrRefCount가 하게되고,
linked list의 경우는 listNode *node; node->value = value라 object로 관리가 되서, refcount++을 하게 됩니다.

이상 List를 마치고, Set을 알아보아요~


ps. linked list, ziplist 테스트

저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis
redis object에 대해 알아본다
볼 소스는 redis.h와 object.c 두개의 파일.


실제 데이타는 void *ptr에 저장되고,  list,hash,set 등에 대한 자료구조 정보를 type, encoding 에 저장한다.




redis.io 에 object command에 있는걸 캡쳐한 사진이다. 빨간줄은 type, 파랑줄은 encoding 을 뜻한다

(ziplist, hashtable은 두개 type에 걸쳐있네요)



언뜻생각하면, encoding으로만 자료형을 구분해도 될것 같은데 굳이...왜 type이라는 자료형을 두었을까????


나름의 제 생각은 encoding으로 검사하는것보다 비슷한 encoding(자료형)끼리 묶어서 동일한 type으로 놓고,

검사를 하려고 한게 아닐까 생각된다...(그게 아니면 32 bit 맞추려고....쿨럭;;)





refcount의 나타나게된 배경은 다음과 같다.

Redis는 key-value 구조인데, value의 값이 동일한데도 메모리 할당하는게 많이 아깝다고 생각했던 antirez는
(술 -> 돈, 학교 -> 돈, 노트북 -> 돈  의 key-value가 있을때, value의 값은 '돈'으로 동일하지만 각각 메모리 할당하고 있는걸 아깝다고 생각~!!)
자주 쓰는걸 미리 만들어놓자~!! 해서~ 그것들을 모아놨다 : ) 이런 센스쟁이. ㅎㅎ

value가  0~REDIS_SHARED_INTEGERS 에 있으면 sharedObjectsStruct.integers 를 사용.
LONG_MIN보다 크거나 같고, LONG_MAX보다 작거나 같으면, 메모리 할당 없이 void *ptr에 직접 값을 넣는다.


저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis

<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"

위의 모습은 foo : bar,   hello : world 를 입력했을때 zipmap에 저장된 구조입니다.
zmlen은 zipmap 의 실제 크기입니다. 1 byte를 사용하고,
            크기가 254보다 크거나 같으면, 사용하지 않습니다. 
len은 1 byte 또는 5 byte를 사용합니다.    데이타의 길이가 0~252라면 1 byte가 사용되고, 
         253이면 다음 4 byte가 data의 길이가 됩니다. 255는 데이타의 끝을 나타냅니다.
free는 수정후, 사용안한 byte의 크기를 나타냅니다.
          unsigned int형으로 8 bit입니다. 만약 8 bit가 넘는다면 zipmap 을 resize하게 됩니다.


zmlen len key len free value len key len free value len(ZIPMAP_END)   이런구조가 되겠죠?

여기까지가 주석에 나온 부분이고, 소스를 보면서 zipmap에 대해 알아봅시다.

제일 처음 볼 함수는 zipmapSet 입니다.

zipmapRequiredLength 에서 key,value가 필요한 총 byte를 구해줍니다.
(len * 2, free 의 총합, key/value의 len이 254가 넘는다면 4씩 더해줍니다.)

1. key 와 같은 부분을 찾고, 없으면 NULL return   zipmapLookupRaw
2. NULL이면 현재 필요한 길이(len + key + len + free + value)만큼 resize를 해주고,
3. NULL이 아니면  입력할 data의 길이(reqlen)와 현재 set되어있는 길이(freelen)를 구하고,
4. reqlen > freelen 이라면 그 차이만큼 map size를 늘리고,
5. freelen - reqlen >= 4 라면 그 차이만큼 map size를 줄인다.

4, 5에 대한 것을 그림으로 보자면 아래와 같습니다.


 그외 몇가지 함수를 살펴보면 zipmap에서 iterator역할을 해주는 zipmapNext,
입력한 key에 해당 구간을 삭제해주는 zipmapDel
입력한 key의 value를 찾아주는  zipmapGet 가 있습니다.

zipmap 크기 조절 해주는거랑 zipmapLookupRaw  를 이해하니 나머지는 술술 잘 풀렸습니다.
zmlen Size 관련 issue : https://github.com/antirez/redis/issues/188  

hashtable은 dict자료구조를 사용합니다. : )  (좋구먼~~ ㅎㅎ)


 t_hash.c에서 zipmap과 hash 를 쓰지않고, ziplist와 hash를 씁니다.
why? https://github.com/antirez/redis/issues/188 ,  https://github.com/antirez/redis/pull/285

ziplist에 값을 넣을때 key, value로 tail에 두개씩 insert하고, 삭제할때도, key, value삭제를 합니다.
ziplist와 마찬가지로 제한을 두었습니다.

# Hashes are encoded using a memory efficient data structure when they have a
# small number of entries, and the biggest entry does not exceed a given
# threshold. These thresholds can be configured using the following directives.
hash-max-ziplist-entries 512
hash-max-ziplist-value 64

정작 사용하는곳은 rdb.c이네요.

이상 Hash data type을 마치겠습니다.


저작자 표시 비영리
신고
Posted by 오산돌구
TAG redis