Cache 파헤치기

What is cache?

캐시는 속도 차이로 인한 퍼포먼스 저해를 막기 위한 것이라고 생각해도 과언이 아니다.

단 한 대의 서버 내부에서도 여러 이유로 캐시를 사용할 수 있으며,

여러 서버 간의 통신에서도 캐시를 사용할 수 있다.

어느 하나가 상대적으로 너무 느리기 때문에 생기는 문제를 계층적 구조를 통해 해결하고자 한 방법이 캐시라고 할 수 있다.

“Caching”은 이제 특정 레벨에서 뿐 아니라 OS level, Architecture level, Programming level 등 다양하게 쓰인다.

 

Why we need cache (in OS Level)?

이용 가능한 가장 빠른 메모리의 속도에 근접한 메모리를 제공하는 동시에, 비용이 저렴한 대용량의 메모리를 제공하기 위해서.

CPU와 주기억장치 속도 간의 차이로 실제 퍼포먼스 저해가 일어나게 되었다.

그렇다고 빠른 주기억장치를 쓰자니 돈이 많이 들게 되었고, 따라서 Cache가 필요하게 되었다.

캐시는 주기억장치 일부의 복사본을 포함하고 있다.

따라서 캐시를 이용하는 과정은 다음과 같다.

CPU가 메모리에서 한 워드를 읽으려고 할 때, 그 워드가 캐시 내에 있는지 여부를 먼저 점검하게 된다.

1) 만약 그렇다면, 그 워드는 CPU로 바로 전달

2) 그렇지 않다면, 고정된 개수의 워드로 구성된 주기억장치 블록이 캐시로 읽혀진 뒤, 해당 워드가 전달

참조 지역성(Locality of Reference) 때문에 어떤 메모리의 참조를 위해 하나의 데이터 블록을 캐시로 가져오게 되면, 그 이후의 참조는 그 블록 내에 있는 한 워드가 될 가능성이 높다.

 

Criteria for creating a cache

“캐시를 어떻게 설계하는가?”는 중요하지 않은 질문 같다.

“내가 캐시를 만들 것도 아닌데...”라고 생각할 수 있지만, 캐시를 더 잘 쓰기 위해서 어떤 점들을 고려하고 캐시가 설계되었는지 알아야 한다.

나중에 운영을 할 때에도 해당 정책들을 설정해야 할 필요가 있다면 알아둬야만 한다.

(참고로 뒤에도 관련 내용이 나온다.)

대략적으로 다섯 범주로 나눌 수 있다.

 

캐시 크기

우리가 왜 캐시를 쓰고자 했는가?

캐시는 빠르다. 그리고 빠르면서 큰 메모리는 비싸다.

 

블록 크기

블록 크기가 클수록 더 많은 데이터가 캐시로 이동되고 참조 지역성이 많이 요구되는 상황이라면 이득이 된다.

하지만 어느 순간 기존 블록에서 읽는거보다 새 데이터를 가져오는 경우가 더 늘어나는 상황이 일어난다면 **적중률(Hit rate)**이 낮아질 수 있다.

 

Mapping function

불러온 블록이 캐시의 어느 위치에 저장될지를 결정하는 함수이다.

해당 함수가 유연할수록, 즉 광범위 영역을 커버할 수록 블록 교체 확률이 작지만,

필요한 데이터 블록이 캐시 내에 있는지 판단하기 위한 탐색 과정이 복잡해진다.

 

Replacement Algorithmn

캐시 메모리가 가득찼을 때 어떤 데이터를 **퇴출(eviction)**할 것인가?

아래의 기재된 알고리즘들을 사용한다.

FIFO, LRU(least-recently-used), LFU 등등

(LRU와 LFU는 간략히 아래에서 설명한다)

 

Write policy

캐시 내 블록의 데이터가 변경되었다면 이걸 언제 주기억장치에 쓸지.

 

Profits when you use cache

 

https://aws.amazon.com/ko/caching/

캐싱이란 무엇이고 어떻게 작동합니까 | AWS

 

 

(웹 개발자인) 내가 궁금했던 Cache

웹 개발을 하다보면, 외부 캐시로 Redis와 Memcahced를 사용한다.

물론 내장 캐시를 사용하는 경우도 많지만 대규모 처리에서는 따로 캐시를 두기 때문에

Redis와 Memcached에 관한 내용을 다뤄보았다.

 

Redis vs Memcached

소개하기에 앞서 이하 내용은 Redis에 관한 내용을 위주로 다뤘다.

Redis는 Memcached에 저장소 개념이 생긴 캐시라고 이해하면 편하다.

종류	Redis	Memcached
속도	초당 100,000 QPS +	초당 100,000 QPS +
자료구조	Key-value, List, Hash, Set, Sorted Set (Redis의 큰 장점이다. Full-persistent redis를 DB로 쓰려는 움직임이 발생하고 있는 이유 중에 하나기도 하다.)	Key-value만 지원
안정성	특성을 잘못 이해할 경우, 프로세스 장애 발생 (라고 하지만.. 이건 모든 인프라가 그렇다)	장애 거의 없음 (하지만 거의 없는 그 장애가 정말정말 크리티컬하다 이하의 내용을 읽어보자)
응답속도의 균일성	Memcached에 비해 떨어짐(이라고 하지만 사실 최근 레퍼런스들을 보면 전혀 그렇지 않다. 예전 Redis 기준인듯)	전체적으로 균일

위를 표를 보다보면 궁금증이 2개 정도 생긴다.

 

특성을 잘못 이해할 경우가 무슨 뜻이지?

Redis는 싱글 스레드라는 특성과 지속적인 저장이 가능하다는 (persistent) 특성이 있다.

두 특성 모두, Redis 사용자가 장애를 겪게 하는 큰 원인이 된다.

여기서 중요한 점은, "장애"를 발생하는 게 꼭 큰 문제가 되지는 않는다는 점이다.

오히려 장애보다도, Cache에서도 Data loss가 가장 크리티컬하다. 생각해보자.

Memcached를 쓰다가 모든 데이터가 날아갔다고 한다면, Cache miss가 굉장히 많이 일어날 것이다.

그렇다면 트래픽은 어디에 쏠리는가? 답은 Database이다. 최악의 경우 Database도 같이 뻗어버릴 수 있다.

 

따라서 Persistent 때문에 Data loss가 일부 있을 수는 있어도, Data loss가 100%인 거보다는 훨씬 좋다.

 

참고

Memcahced는 멀티 스레드를 지원하며 따라서 여러 코어를 사용하는 것도 큰 문제가 없다고 한다.

Memcached는 서버가 장애를 일으켜 문제가 발생하면 모든 데이터가 사라지지만

Redis는 Persistent 기능(RDB, AOF)을 이용하면 저장된 데이터를 통해 복구 가능하다.

 

근데, Single Thread인 Redis가 시장의 대부분을 점유하고 있을까?

 

Single Thread

싱글 스레드이기 때문에 시간이 오래 걸리는 Redis 명령을 호출하면,

명령을 처리하는 동안에는 Redis가 다른 클라이언트의 요청을 처리할 수 없다.

장애의 꽤 많은 부분이 이 이슈로 발생한다.

(실제로, redis 공식 문서에는 실행 시간이 긴 keys나 flushdb 같은 명령어를 위와 같은 이유로 권장하지 않는다고 적혀있다.)

 

하지만 실제로 Redis는 굉장히 빠르다. 뭔가 이상하지 않은가?

싱글 스레드인데 I/O가 자주 일어나는 Cache 트래픽 패턴을 생각해보면.. 어라? 이거 node.js의 기본 개념과 비슷하네?

Redis 6+부터는 I/O도 multiplexing을 하기 시작했다.

지연 시간을 가장 많이 발생 시키는 I/O 쪽에서 지연 시간이 줄어들었다는 이야기다. 성능이 좋아졌다.

즉, Single Thread로 인한 penalty가 거의 없는 수준까지 왔다고 생각해도 된다는 이야기다.

 

Persistent

 

RDB (RDBMS와 전혀 상관없다.)

Redis에서 현재 메모리에 대한 덤프 생성하는 기능이다.

더 간략히 말하면, 스냅샷을 뜨는 기능인데 **“아까 싱글스레드라며! 어떻게 해?!”**라고 할 수 있다.

Redis는 fork를 통해 자식 프로세스를 생성하여 스냅샷을 만든다.

COW(Copy On Write)이라는 메모리에서 실제로 변경이 발생한 부분만 복사하는 방식도 사용한다.

그러나 COW를 이용함에도 불구하고,

Write가 많기 때문에 자식 프로세스, 부모 프로세스 각각 하나씩 해서

메모리를 두 배로 사용하는 경우가 쉽게 생긴다.

메모리 할당량을 정해야 하는 예시를 생각해보자.

 

예시

Core 4개를 가지고 있고 메모리가 32GB인 장비를 사용한다고 하자.

4개의 Redis를 하나의 서버에 띄우고, RDB 저장을 한다고 치자.

프로세스 4개 + RDB 저장 프로세스를 합쳐 5개의 프로세스가 생성된다.

즉, 프로세스 별로 6GB를 할당한다고 생각하면 30GB만 사용하기 때문에 2GB 정도의 여유가 생긴다.

(참고 : Redis는 싱글스레드이기 때문에 하나의 Redis를 하나의 장비에서 띄우기보다 멀티코어를 활용하기 위해 여러개의 Redis 서버를 한 서버에 띄우는 것이 성능상 유리하다고 한다.)

 

AOF(Append Only File)

AOF는 RDBMS의 WAL(Write Ahead Log)이랑 비슷하다.

1. 클라이언트가 업데이트 관련 요청
2. Redis는 해당 명령을 AOF에 저장
3. 쓰기 완료시 실제 명령을 실행해서 메모리 변경

 

HA(High Availability) at Redis

고가용성(HA)은 클라우드 환경의 어느 인프라에서든 필수이다.

Redis 서버를 한 대만 구동하던 중 죽어버리면 퍼포먼스에 큰 영향을 줄 수 있다.

만약 Redis 한 대가 여러 WAS나 DB의 성능을 유지해주고 있던 거라면,

트래픽 과부하로 인해 시스템 전체가 다운될 가능성도 배제할 수 없다.

Redis에서의 HA는 Master - Slave 관계의 Replication을 유지하고 있다가,

“master가 정상이 아니다.”라고 판단되면 Slave를 새로운 master로 올리게 된다.

 

그 과정에서 Sentinel이라는 데몬을 이용하여

1) 마스터의 장애 판별

2) 슬레이브를 마스터로 승격

3) 해당 내용을 클라이언트에 통지

참고로 서버 장애를 감지하기 위해서 Quorum(정족수) 과반을 따진다.

5버전+부터는 Redis자체에 센티넬 포함되었다고 한다.

 

Cache Replacement algorithm at Redis

솔직히 이거 좀 궁금했는데, 생각보다 별거 없었다.

Redis의 경우, 제공하는 정책이 꽤 있고 그냥 내가 원하는 거 쓰면 된다.

 

Aprroximage LRU

흥미로운 점은 LRU 알고리즘을 샘플링을 통한 근사로 구현하고 있었다는 점이다.

좀 더 설명하자면, 소수의 키를 샘플링하고 샘플링 키 중 가장 적합한(접근된지 가장 오래된) 키를 제거하는 방식이다.

(참고로 샘플 수는 조정 가능하며, 샘플 수 증가시 이론적인 LRU 성능에 가까워진다.)

(놀랍게도 Redis 글을 읽어보니 샘플 수가 10만 되더라도 성능이 꽤 나온다고 한다.)

(물론 전체 키의 수에 따라 영향이 갈 것 같다. - 필자 뇌피셜)

3.0 이후부터는 키 방출(eviction)을 위한 좋은 후보자 풀을 가져오는 방법도 사용한다고 한다.

 

왜 이렇게 근사로 구현하는가?

진짜 LRU구현하면 메모리 비용이 더 많이 든다고 한다.

 

왜 비용이 많이 들까?

LRU 알고리즘에서는 참조된 시간을 알 수 있는 부분을 저장해야 한다.

 

LFU

Redis 4.0부터는 LFU도 있다.

드물게 사용하는 항목은 제거되고 자주 사용하는 건 메모리에 남기는 방식이며

즉, 참조 횟수가 가장 작은 페이지 교체한다는 것이다.

그러나 가장 최근에 불러온 페이지가 교체될 수 있다는 단점이 있다.

구현 방식은 확률 알고리즘(모리스 알고리즘)을 통해 데이터들의 접근 빈도와 빈도 관련 기간을 결합하여 처리한다.

모리스 알고리즘(Morris Algorithm)?

많은 이벤트 수를 작은 메모리로 처리하기 위해 개발된 알고리즘이라고 한다.

확률적 계산을 이용해 정확히 세는 것이 아닌 근사값으로 처리하는 방식으로

8 비트 레지스터에서 256까지 셀 수 있던걸 약 512까지 셀 수 있게 하는 알고리즘이라고 한다.

 

What happend when we have a lot of cache?

Facebook에서 무려 2013년에 쓴 아주 올드하지만, 그래도 읽어볼만한 논문은 꽤 괜찮은 인사이트를 제시한다.

 

https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf

 

캐시를 유지하는 것은 어렵다.

• 캐시를 데이터베이스와 어떻게 동기화 상태로 유지할 것인가?
• 캐시 누락이 데이터베이스 서버에 과부하를 주지 않도록 어떻게 설계할 것인가?

이걸 위해서 Facebook에서 캐시를 어떻게 사용했고 문제를 어떻게 해결했는지 한 번 살펴 보자.

 

At Facebook

페이스북에서는 읽기 로드를 줄이기 위한 look-aside cache로 memcached를 사용한다.

Read

• 먼저 캐시에서 데이터 가져오려고 시도
• 없으면 DB에서 데이터 가져온 다음, 캐시에 데이터 세팅

Write

• 웹 서버에서 키에 대한 새로운 값을 데이터베이스로 전송
• 요청을 캐시에 보내 해당 키 삭제

논문에 나와 있는 그림 1

 

Full Architecture

이건 솔직히 엄청 크긴 한데, 굳이 알 필요가 있나 싶긴하다.

실제로 Facebook에서 제시하는 전체 아키텍쳐는 그림과 흡사한데 다음과 같다.

(참고로 Region은 데이터센터를 의미한다.)

여러 프론트엔드 클러스터를 구성하고, 이들을 묶어 데이터 센터를 구성한다

 

논문에 나와 있는 그림 2

 

내가 궁금한 내용

 

1. 캐시의 응답 대기 시간 단축

Memcache 클라이언트 병렬 및 Batch Request

웹서버들은 Page(웹사이트 페이지를 의미)에 필요한 모든 데이터 의존성에 대해 DAG(Directed Acyclic Graph)를 구성한다. 그 다음, memcache 클라이언트는 DAG를 이용해서 memcache 서버에서 필요한 키를 배치요청을 통해 가져온다. → 네트워크 왕복이 줄어든다.

 

 

읽기에 UDP를, 쓰기에 TCP를

Memcache 클라이언트에서 데이터 읽는 요청에 UDP를 사용하고, 서버에 대한 쓰기 요청은 TCP를 쓴다. UDP 구현은 패킷이 드랍됐거나 전송 순서가 이상할 때 cache miss로 client에 결과를 반환한다. 이 경우 기존처럼 DB로부터 데이터를 가져오되, cache에 데이터를 채우려고 하지는 않는다. → 채우려고 하지 않는 이유 : 네트워크나 서버에 추가 부하가 가는 것을 방지. UDP를 쓰는 이점을 최대한 누리려는 것.

개인적으로는 이 점이 굉장히 인상깊었는데, Google에서 이미 쓰고 있는 QUIC(Quick UDP Internet Connections) 프로토콜은 HTTP/3에도 들어갈 정도로 논의되고 있기 때문. 근데 TCP에 비해 UDP는 신뢰성이 낮지 않나? 라고 할 수 있지만, packet loss detection, congestion control 방법을 어떻게 하는지에 따라서 비슷한 수준의 신뢰성 + 높은 성능을 가져갈 수 있다고 한다. 궁금한 점은 QUIC 관련 논문이나 문헌 참고.

 

Memcache 클라이언트에서 흐름 제어 구현

해싱을 사용하여 클러스터에 있는 수백 대의 memcache서버에 데이터를 분할하는데, 이건 incast congestion을 초래한다. incast congestion : 고객이 많은 수의 키를 요청할 때, 해당 요청에 대한 응답이 한꺼번에 도착하면 rack, cluster switch 같은 것이 압도될 수 있다. (뻗을 수 있다.)

Memcache클라이언트는 TCP와 유사한 슬라이딩 윈도우를 통해 요청 수를 제한한다고 한다.

 

2. 캐시 누락시 DB 부하 감소

이걸 왜 신경 써야 할까?

cache miss가 어느순간 많아지는 경우가 있을 수 있다.

캐시에서 데이터가 누락된다면 웹 서버는 DB로 이런 요청을 보내야 하기 때문에 부하가 한순간에 쏠릴 수 있다.

근데 읽다보니 사실 부하에 관한 문제보다는 데이터 일관성에 대한 문제 같긴 하다.

특히 주요한 두 문제(stale sets, thundering herds)를 해결하기 위해 lease mechanism(임대)를 사용한다.

• stale sets 웹 서버가 out-dated된 값을 캐시에 설정할 때 발생하는 문제다.

  키 'k'가 캐시 안에 없다.
    C1은 get(k)를 시도하지만, miss가 난다.
    C1 k에 대한 값인 v1을 DB로부터 읽는다.
      C2는 k = v2라고 DB에 쓴다.
      C2는 k를 지운다.  (DB에 쓰는 연산을 하면 캐시의 키를 무효화 해야 함을 기억하자!)
    C1은 set(k, v1)을 한다.
    이미 delete(k)가 일어났기 때문에 캐시는 오래된 데이터를 가지게 된다.
    다음 번 k가 쓰이기 전까지 오래된 데이터가 남아있을 수도 있다.

  lease mechanism을 통해 쉽게 해결할 수 있다.
  • 키에 대한 cache miss 발견 시, memcache서버는 DB에서 데이터를 읽은 후 캐시에 데이터를 설정할 수 있도록 lease를 제공한다.
  • 해당 lease는 key에 바인딩된 64비트 토큰이다.
  • 클라이언트가 캐시에 데이터를 설정하고자 할 때, memcache가 확인할 수 있도록 해당 토큰을 제공해야 한다.
  • 그러나 memcache가 키에 대한 삭제 요청을 받으면 해당 키에 대한 기존 리스 토큰은 무효화된다.
  따라서 위의 시나리오에서는 C1은 리스 토큰을 받지만, memcahce가 C2로부터 키에 대한 삭제 요청을 했기 때문에 해당 키에 대한 리스 토큰은 무효화된다. 해당 키가 누락되기 때문에 다음 reader는 DB로부터 데이터를 읽어온다.
• 간단히 말하면 동시에 수정하려고 할 때 타이밍 이슈로 생기는 문제다. (동시성 제어로 인한 문제라고 할 수 있다.)
• thundering herds
  많은 클라이언트가 무효화된 키에 대해 데이터를 읽으려고 할 때 클라이언트 모두가 DB에 요청을 보내게 될 것이다. 따라서 이 문제를 막기 위해 키당 10초마다 한 번만 임대해준다. lease 발급 후 10초 이내에 또 다른 요청이 들어오면 요청은 기다려야 한다. 리스가 있는 클라이언트가 10초 동안 캐시의 데이터를 성공적으로 설정했다면, 대기중인 클라이언트는 재시도할 때 캐시에서 데이터를 읽게 될 것이다.

좀 옛날 논문임에도 불구하고, 대용량 처리에 대한 고민들이 엿보이는 방법이라 흥미로움.

더 자세한 내용은 아래의 세 번째 레퍼런스 참조.

References

• Operating Systems, Pearson, William Stallings
• Redis운영관리, 한빛미디어, 강대명
• https://timilearning.com/posts/mit-6.824/lecture-16-memcache-at-facebook/
• https://redis.io/topics/lru-cache