해시

캐싱

모든 컴퓨터의 프로그램들은 수많은 명령어로 작동한다.
이때 이 명령어들은 메모리에 들어가있다.
이 메모리에 있는걸 가져오는걸 캐싱이라고 한다.
메모리에 있는 데이터를 캐싱해서 CPU안에 있는 캐시 메모리에 들어가게 된다.

인스타그램에서도 해시 테이블을 사용했다.
인스타그램 같은 경우 수억개의 사진을 사용자 ID로 매핑했었다고 하는데 내부적으로 아래의 요구사항이 만족했어야 했다.

• 키를 빠르게 조회하고 값을 반환
• EC2 고메모리 유형 중 하나에 이상적으로 맞아야 함
• 기존 인프라에 잘 맞아야하고
• 서버가 다운되더라도 다시 채울 필요가 없는 지속성이 있어야 함

인스타그램은 이렇게 캐싱을 할 때 SQL 데이터베이스 대신 Redis를 사용하기로 결정했다.
보통 캐싱을 할 때 가장 많이 사용되는 소프트웨어가 바로 Redis이기에 선택한 듯 하다.

해시 테이블 구조 (출처 : 나무위키)

해시 테이블 등에서 해시 함수로 해시를 구해 그걸 기반으로 데이터를 배치한다.
인스타그램의 경우 미디어 ID를 1000으로 나눠서 버킷 번호를 결정했다고 한다.

해시 함수

해시 함수는 키를 특정한 규칙에 따라 변환하여 배열의 인덱스를 생성하는 함수이다.
해시 함수가 잘 작동하기 위해선 아래의 조건을 만족해야한다.

1. 결과 값이 일정한 범위를 유지해야 함
2. 동일한 입력에 대해 항상 동일한 출력
3. 충돌(Collision)이 적게 발생해야 함

여기서 제일 중요한건 2번이다.
이걸 결정성(Deterministic) 이라고 한다.

충돌(Collision) 처리 기법

1. 체이닝(Chaining)
   링크드 리스트를 활용하여 같은 인덱스에 여러 개의 데이터를 저장하는 방식

2. 개방 주소법(Open Addressing)
   해시 테이블 내에서 충돌이 발생한 데이터를 새로운 위치에 저장하는 방식
   대표적으론 선형 탐사, 이중 해싱이 있다.