Redis를 왜사용했나요? 빨라서요.
Redis가 빨라서 사용했다는건 좋은답변일까? 맞을 수도 있고, 부족한 답변일 수도 있다.
한 면접관이 지원자에게 Redis에 대해서 질문하는 글을 봤다.
면접관: 프로젝트 Y의 시스템 성능을 X% 향상시키기 위해 무엇을 했나요?
지원자: “물론이죠. 우리는 많은 일을 했습니다. 웹 레이어에서 …, 애플리케이션에서 …을 찾았고, 또한 a 및 b 데이터를 캐시에 로드했습니다.”
면접관: “레디스 말씀이신가요? 이전에 다른 캐시 서비스를 살펴보신 적이 있나요? 그리고 결국 Redis를 선택하게 된 이유는 무엇인가요?” 나는 물었다.
지원자: “빠르고 우리 사용 사례에 더 익숙합니다.” 그는 말했다.
면접관: "이렇게 **빠르게 만들 수 있는 핵심 기능이 무엇인지 아시나요?**" 나는 Redis에 대한 그의 이해가 얼마나 깊은지 알아보기 위해 그의 한계를 만져보려고 노력했습니다.
지원자: "내부적으로 LRU에 대한 이중 목록이 있는 스킵 목록을 사용하고 있는데, 이는 속도를 높이는 매우 효율적인 데이터 구조입니다.”
면접관: “아주 좋아, 또 뭐야? 들어오는 **연결을 어떻게 처리합니까**?”.
지원자: "이것은 소켓 기반 서버이며 연결을 수신하고 수락한 다음 스레드를 시작하여 들어오는 데이터를 처리합니다.”
면접관: “그럼 당시 연결 수는 10,000개 정도였나요? Redis는 10,000개의 스레드를 열까요? ".
지원자: "예".
면접관: "좋아요. ...에 대해 이야기합시다.” 나는 여기서 멈춰서 화제를 바꿨다.이 대화를 보고 다시 Redis를 공부해봐야겠다라는 생각이 들었고 그 내용을 정리했다.
빠르게 만들 수 있는 핵심 기능에 대해.
Redis는 들어오는 연결을 어떻게 처리하는지에 대해서 공부해보자.
빠르게 만들 수 있는 핵심 기능 - Redis의 특별한 자료구조 Skip List
“Redis, an ANSI-C open-source persistent key/value store for Posix systems, uses skip lists in its implementation of ordered sets.” -위키백과-
레디스는 String, Lists, Sets, Sorted Sets, Hashes의 자료구조를 사용하는데 그중에 Sorted Set는 Skip List로 구현되어있다.
Skip List는 효율적인 탐색, 삽입, 삭제 작업을 지원하는 확률적 자료구조이다.
기본적으로 여러 레벨의 연결리스트로 구현되며, 각 레벨은 아래 레벨의 일부 노드를 “건너뛰어” 연결한다.
Skip List는 O(log n)의 시간복잡도를 가지며 각각의 상위 레벨은 하위 레벨보다 절반 개수의 원소를 가진다.
Skip List의 탐색 과정
예를 들어, 총 4레벨을 가진 위의 스킵리스트에서 20을 찾는다고 해보자.
1. 헤드에서 레벨 4를 타고 88로 이동한다. 20은 88보다 작으므로, 다시 헤드로 가서 레벨 3을 통해 16으로 이동한다.
2. 레벨 3을 타고 88로 이동한다. 20은 88보다 작으므로 다시 16으로 돌아가 레벨 2를 통해 72로 이동한다.
3. 20은 72보다 작으므로 다시 16으로 돌아가 레벨 2를 통해 20으로 이동한다.이러한 탐색방식은 모든 연산에 대해서 O(log N)의 복잡도가 보장된다.
Redis는 왜 Skip List를 사용할까?
당연 Linked List에 대한 검색시간을 최적화하기 위해서 사용한다.
배열에서 특정 원소를 검색하는 비용은 일반적으로 O(n)이 소요되지만 이진탐색을 이용하면 O(log N)까지 최적화 할 수 있다.
하지만 정렬된 링크드리스트에서 원소를 검색하는 비용은 O(logN)이 절대 될 수 없다.
그 이유는 반드시 포인터를 통해서 다음 노드를 탐색할 수 있기 때문이다.
Skip List에서는 이러한 Linked List의 단점을 여러 level로 나누어서 노드를 Skip 시키는 방법으로 구현되었다.
원리는 간단하다. 각각의 노드는 다수의 이전 또는 다음노드로 가는 포인터들이 존재할 수 있다.
이전 또는 다음노드로 가는 포인터들을 통해 불필요한 탐색을 Skip 할 수 있고 이는 검색에 드는 비용을 O(logN)으로 최적화 시킬 수 있다.
때문에 Redis Sorted Sets은 아래와 같은 이점이 있다.
- Skip List 내에서 검색, 삽입, 삭제 작업을 평균 O(logN)으로 수행할 수 있다.
- Skip List를 통해 자동으로 요소들을 정렬된 상태료 유지하며 특정 범위의 데이터를 빠르게 탐색할 수 있도록 한다.
- Skip List의 구현은 다른 데이터베이스의 이진 탐색 트리나 B Tree에 비해 구현 난이도가 간단하다.
Redis는 어떻게 연결을 관리할까?
Redis는 Socket 기반 서버이다. 그렇기 때문에 TCP 프로토콜을 사용해서 클라이언트와 서버간의 네트워크 통신을 한다.
그렇다면 위 지원자의 답변처럼 정말 Redis는 10000개의 커넥션에 대해서 각각의 스레드를 생성할까?
답은 no이다.
그 이유는, Redis는 싱글 스레드 기반의 서버이며 모든 데이터 처리는 한 개의 메인 스레드 내에서 이루어진다.
Redis 6.0 이후에는 멀티쓰레딩을 도입했지만 이는 네트워크 I/O를 위한 도입이지 여전히 데이터 처리 로직은 싱글스레드이다.
조금 더 알아보자
Redis의 연결 처리 방식
- 비동기 I/O: Redis는 이벤트 루프를 사용하여 네트워크 I/O를 처리한다. 이벤트 루프는 소켓의 상태 변경(예: 새로운 연결, 데이터 도착)을 감지하고, 해당 이벤트에 대한 콜백 함수를 비동기적으로 실행된다..
- 소켓 멀티 플렉싱: Redis는 소켓 멀티 플렉싱을 사용해서 단일 쓰레드에서 여러 소켓을 효율적으로 관리할 수 있다. 이는
select,poll,epoll과 같은 시스템 콜을 사용해서 단일 쓰레드에서 여러 소켓의 상태를 동시에 모니터링 할 수 있도록 도와준다. - 클라이언트 요청 처리: 클라이언트의 요청이 도착하면, Redis는 이를 큐에 넣고 순차적으로 처리한다. 싱글 쓰레드 모델 덕분에, 각 요청은 원자적으로 처리되며 데이터 일관성이 유지된다.
왜 싱글쓰레드로 구현되었을까?
Redis가 싱글 쓰레드 기반으로 설계된 이유는 주로 간소화된 구조, 높은 성능, 그리고 안정성에 중점을 둔 설계 때문이다.
redis가 빠르고 사용하기 편한 이유는 간단한 구조여서 그렇지 않나 생각이든다.
- 간단한 설계: 멀티 쓰레드 프로그래밍에 비해 싱글 쓰레드 프로그래밍이 훨씬 더 간결하고 설계하기 쉽다.
- 성능 최적화: CPU 사용량을 최소화할 수 있고 컨테스트 스위칭이 감소하기 때문에 CPU 오버헤드를 방지할 수 있다.
- 인-메모리 데이터베이스로서, 데이터 접근이 빠르다.
