버킷

버킷은 데이터를 정해진 기준으로 나눠 담는 통입니다. 어디에 담을지도, 찾을 때 어디를 열지도 그 기준이 정합니다. 해시테이블에서는 키를 나눠 담는 칸 하나가 버킷입니다. 오브젝트 스토리지에서는 파일을 담는 가장 바깥 통이 버킷입니다.

쉽고 빠른 이해

무슨 일을 하는 물건인가 — 여럿을 나눠 담는 통 하나입니다. 키로 값을 찾는 표는 칸을 여러 개 늘어놓고 키마다 갈 칸을 정해 둡니다. 그 칸 하나가 버킷입니다. 파일을 맡아 두는 저장 서비스에서 파일을 담는 가장 바깥 통도 버킷이라고 부릅니다.

왜 이렇게 하나 — 통이 하나뿐이면 찾을 때마다 안에 든 것을 처음부터 끝까지 봐야 합니다. 통을 여럿으로 나누고 어디에 담을지 정하는 규칙을 두면, 찾을 때 그 규칙으로 통 하나만 골라 그 안만 보면 됩니다.

어떻게 도나

1. 담을 것마다 규칙을 따져 갈 통을 고릅니다
2. 그 통 안에 담습니다
3. 찾을 때 같은 규칙을 따져 같은 통을 열고 그 안만 봅니다

대가 — 규칙이 한쪽으로 쏠리면 한 통에 다 몰려서 나눈 값이 사라집니다. 통 수를 바꾸면 규칙이 내는 답도 달라져, 담긴 것을 다시 나눠 담아야 합니다.

상세

빨래를 갤 때 흰옷 바구니와 색옷 바구니를 따로 둡니다. 옷을 집으면 색을 보고 어느 바구니에 넣을지 바로 정해집니다. 나중에 흰 셔츠를 찾을 때는 흰옷 바구니만 뒤집니다.

이 비유는 한 군데서 어긋납니다. 빨래 바구니는 색이라는 눈에 보이는 기준으로 갈립니다. 버킷은 사람이 붙인 이름으로 갈리기도 합니다. 오브젝트 스토리지의 버킷이 그쪽입니다.

버킷을 이루는 것 셋

버킷이라고 부르려면 셋이 있어야 합니다. 담을 것이 여럿이어야 하고 담을 통도 여럿이어야 합니다. 그리고 어느 통에 담을지 정하는 기준이 있어야 합니다. 셋 가운데 기준이 빠지면 그냥 통 여러 개입니다.

통을 하나만 두면 찾을 때마다 안에 든 것을 처음부터 끝까지 봐야 합니다. 통을 여럿으로 나누고 기준을 두면 그 기준이 열어 볼 통 하나를 찍어 줍니다. 훑는 양이 통 하나 안으로 줄어드는 것이 버킷을 두는 까닭입니다.

기준이 하는 일은 하나입니다. 담을 것 하나를 받아 통 하나를 가리키는 것입니다. 같은 것을 두 번 넣어도 늘 같은 통을 가리켜야 합니다. 그래야 넣을 때 고른 통과 찾을 때 고른 통이 같습니다.

기준은 두 갈래로 갈립니다. 하나는 담을 것에서 계산해 뽑는 기준입니다. 다른 하나는 사람이 통에 이름을 붙이고 무엇을 어디에 넣을지 직접 정하는 기준입니다. 계산해 뽑는 기준은 해시테이블이 쓰고, 이름을 붙이는 기준은 오브젝트 스토리지가 씁니다.

해시테이블의 버킷

해시테이블은 키로 값을 찾는 자료구조입니다. 안에 칸을 늘어놓은 배열을 하나 둡니다. 키마다 갈 칸을 미리 정해 둡니다. 그 칸 하나가 버킷입니다.

키를 받아 숫자 하나로 바꾸는 함수가 해시 함수입니다. 그 함수가 낸 숫자가 해시값입니다. 같은 키를 넣으면 언제나 같은 해시값이 나옵니다. 이것이 계산해 뽑는 기준입니다.

해시값은 버킷 수보다 클 수 있습니다. 그래서 해시값을 버킷 수로 나눈 나머지를 버킷 번호로 씁니다. 나머지는 0부터 버킷 수보다 하나 작은 수 사이에 들어오므로, 어떤 키든 번호 하나를 받습니다.

버킷이 8개인 표라면 번호는 0부터 7까지입니다. 어떤 키의 해시값이 3105 면 8로 나눈 나머지는 1 입니다. 그 키는 1번 버킷에 담깁니다.

찾을 때도 같은 계산을 해서 1번 버킷만 엽니다. 배열을 처음부터 훑지 않으니 담긴 수가 늘어도 여는 통은 하나입니다.

flowchart TD
    K1["키 사과"] --> H["해시값을 버킷 수로 나눈 나머지"]
    K2["키 포도"] --> H
    K3["키 배"] --> H
    H --> B0["0번 버킷 · 사과 · 배"]
    H --> B1["1번 버킷 · 포도"]
    BX["2~6번 버킷 · 생략"]
    B7["7번 버킷 · 비어 있다"]

키 셋을 버킷 8개짜리 표에 담은 그림입니다. 8개 가운데 셋만 그렸습니다. 사과와 배는 나머지가 같아 0번 버킷에 함께 들어갔고, 포도는 혼자 1번 버킷에 있습니다. 7번 버킷에는 아무것도 오지 않아 들어가는 화살표가 없습니다.

서로 다른 두 키가 같은 번호를 받는 일을 해시 충돌이라고 부릅니다. 키로 올 수 있는 값은 끝없이 많습니다. 버킷 수는 정해져 있으니 충돌은 피할 수 없습니다. 그래서 버킷은 하나만 담는 통이 아니라, 여럿이 들어올 수 있는 통으로 다룹니다.

들어온 것이 여럿일 때 뒤를 받는 방법이 둘 있습니다. 분리 연쇄법은 버킷마다 목록을 하나 둡니다. 같은 버킷으로 온 것을 그 목록에 이어 붙입니다.

개방 주소법은 버킷 하나에 하나만 담습니다. 가려던 버킷이 차 있으면 정해진 규칙으로 다른 버킷을 차례로 들여다봅니다.

flowchart TD
    subgraph SC["분리 연쇄법 · 버킷에 목록을 매단다"]
        C0["0번 버킷"] --> C0A["사과"]
        C0A --> C0B["배"]
        C1["1번 버킷 · 포도"]
        C2["2번 버킷 · 비어 있다"]
    end
    subgraph OA["개방 주소법 · 다음 버킷으로 밀려난다"]
        O0["0번 버킷 · 사과"] -->|"차 있어 다음을 본다"| O1["1번 버킷 · 포도"]
        O1 -->|"여기도 차 있다"| O2["2번 버킷 · 배"]
    end

0번 버킷에 사과가 이미 있는데 배가 같은 번호를 받았을 때의 모양입니다. 분리 연쇄법은 0번 버킷에 매달린 목록에서 사과 뒤에 배를 잇습니다. 개방 주소법은 배를 다음 버킷으로 보내는 쪽이고, 1번은 포도가 차지하고 있어 배는 2번에 담깁니다. 화살표는 배가 옮겨 간 길입니다.

담긴 수를 버킷 수로 나눈 값을 적재율이라고 합니다. 적재율이 오르면 한 버킷에 여럿이 들어올 확률도 올라 조회가 길어집니다.

그래서 어느 선을 넘으면 버킷 수를 늘리고 담긴 것을 전부 다시 나눠 담습니다. 이 다시 담기를 리해싱이라고 부릅니다.

오브젝트 스토리지의 버킷

파일 하나를 통째로 맡기고 통째로 꺼내는 저장 방식을 오브젝트 스토리지라고 합니다. 맡긴 파일 하나를 오브젝트라고 부릅니다. 폴더를 겹겹이 두는 대신 통 하나와 이름표로 정리합니다.

여기서 버킷은 오브젝트를 담는 가장 바깥 통입니다. 오브젝트는 반드시 어느 버킷 안에 들어갑니다. 버킷 안에서 오브젝트를 가리키는 이름이 오브젝트 키입니다. 버킷 이름과 오브젝트 키가 있으면 파일 하나가 정해집니다.

갈리는 대목은 통을 고르는 기준입니다. 해시테이블은 계산이 통을 골라 줍니다. 오브젝트 스토리지는 사람이 버킷을 만들고 무엇을 어디에 올릴지 정합니다.

계산이 번호를 내지 않으니 버킷 수를 미리 정할 일이 없습니다. 필요하면 하나 더 만듭니다.

버킷은 설정이 걸리는 단위이기도 합니다. 누가 꺼내 가도 되는지, 오래된 오브젝트를 언제 지울지, 다른 지역에 복사본을 둘지를 버킷에 걸어 둡니다. 그 안에 든 오브젝트는 버킷에 걸린 설정을 따릅니다. 파일마다 따로 걸지 않아도 되는 것이 통으로 묶어 두는 이득입니다.

flowchart TD
    subgraph BK["버킷 · 사진모음"]
        S["버킷에 건 설정 · 누가 꺼내 가도 되나 · 언제 지우나"]
        S --> O1["오브젝트 키 · 봄/꽃.jpg"]
        S --> O2["오브젝트 키 · 봄/나무.jpg"]
        S --> O3["오브젝트 키 · 여름/바다.jpg"]
    end

버킷 하나에 오브젝트 셋이 들어간 모양입니다. 오브젝트는 버킷 밖에 혼자 설 수 없습니다. 설정은 버킷에 겁니다. 화살표를 따라 그 안의 오브젝트 셋이 모두 같은 설정을 따릅니다.

버킷 이름은 오브젝트를 가리키는 주소에 그대로 들어갑니다. 그래서 서비스에 따라 사용자 전체를 통틀어 겹치지 않는 이름을 요구합니다. Amazon S3(Simple Storage Service, 단순 저장 서비스)가 그런 쪽입니다.

두 쓰임이 갈리는 대목

두 쓰임은 「나눠 담는 통」이라는 뼈대를 같이 쓰지만 기준이 다릅니다. 기준이 다르면 통의 개수도, 통이 밖에서 보이는지도 같이 달라집니다.

가장 크게 갈리는 줄은 첫 줄입니다. 통을 계산으로 고르면 버킷 수가 계산에 끼어들어, 수를 바꾸는 순간 담긴 것을 다시 나눠 담게 됩니다. 이름으로 고르면 통 하나하나가 사람이 불러서 쓰는 대상이 되고, 권한이나 보관 규칙을 거는 단위가 됩니다.

허가와 구간을 담는 버킷

담는 것이 데이터가 아닌 버킷도 있습니다. 찾기를 줄이려고 나눈 통이 아니라, 통이라는 뜻만 빌려 쓴 이름입니다. 토큰 버킷 · 히스토그램의 버킷 · 시간 버킷 셋을 짧게 짚습니다.

토큰 버킷은 일을 한 번 할 수 있는 허가를 일정한 속도로 채워 두는 통입니다. 요청이 올 때마다 허가를 하나 꺼내 씁니다. 통이 비면 그 요청은 기다리거나 거절됩니다. 요청을 초당 몇 건까지만 받으려는 처리율 제한에서 씁니다.

값이 어느 구간에 몇 건 들어왔는지를 세어 분포를 보는 것이 히스토그램입니다. 그 구간 하나가 버킷입니다. 응답 시간이라면 0.5초 미만 · 0.5초에서 2초 · 2초 넘음처럼 구간을 그어 둡니다. 그리고 구간마다 몇 건이 들어왔는지 셉니다.

시각을 일정한 길이로 나눠 그 구간에 든 것을 모으는 시간 버킷도 같은 꼴입니다. 한 시간씩 끊어 그 안에 일어난 일을 모아 두는 것이 그런 예입니다.

해시테이블과 오브젝트 스토리지의 버킷과 견주면 담는 것이 다릅니다. 토큰 버킷은 남은 허가를 재는 통입니다. 히스토그램과 시간 버킷은 값이나 시각을 구간으로 묶는 칸입니다. 이 셋은 찾기를 줄이려고 나눈 통이 아니라 「통」이라는 말만 빌린 이름입니다.

나눠도 득이 없는 경우

기준이 담을 것을 고루 나누지 못하면 한 버킷에 다 몰립니다. 그러면 그 버킷 안을 처음부터 훑게 되어 통을 나누기 전과 같아집니다. 해시테이블의 조회가 평균 O(1), 곧 담긴 수와 거의 상관없는 시간이라는 말은 키가 버킷에 고루 나뉜다는 가정 위에 섭니다.

버킷 수를 바꾸는 것도 비용이 큽니다. 나머지를 구하는 계산에 버킷 수가 들어가 있어서, 수가 바뀌면 거의 모든 키의 번호가 바뀝니다. 앞의 키 셋으로 보겠습니다. 사과 · 포도 · 배의 해시값이 각각 24 · 33 · 16 이라고 하겠습니다.

flowchart TD
    subgraph B8["버킷 8개 · 해시값을 8로 나눈 나머지"]
        E0["0번 버킷 · 사과 24 · 배 16"]
        E1["1번 버킷 · 포도 33"]
    end
    subgraph B10["버킷 10개 · 해시값을 10으로 나눈 나머지"]
        F3["3번 버킷 · 포도 33"]
        F4["4번 버킷 · 사과 24"]
        F6["6번 버킷 · 배 16"]
    end
    B8 --> B10

버킷을 8개에서 10개로 늘린 모양입니다. 나누는 수가 바뀌어 세 키의 번호가 모두 달라졌습니다. 사과는 0번에서 4번으로, 배는 0번에서 6번으로, 포도는 1번에서 3번으로 갑니다. 늘리기 전에 어디 있었는지는 도움이 안 되고, 키마다 다시 계산해서 옮겨야 합니다.

서버 여러 대에 데이터를 나눠 담으면 이 비용이 그대로 네트워크 이동이 됩니다. 그래서 수를 바꿔도 옮길 것이 적게 나오도록 만든 일관성 해싱을 씁니다.

담긴 것이 몇 개 안 되면 애초에 나눌 이득이 없습니다. 통을 고르는 계산만 붙고 훑는 양은 비슷합니다. 순서대로 훑거나 범위로 찾아야 하는 데이터도 맞지 않습니다. 버킷은 값의 순서를 지키지 않아서, 범위로 찾으려면 통을 전부 열어 보게 됩니다.

관련 항목

버킷을 칸으로 쓰는 자료구조

해시테이블 · 해시 함수 · 해시값 · 해시 인덱스 · 블룸 필터 · 배열 · 연결 리스트

한 버킷에 여럿이 몰렸을 때 쓰는 방법

해시 충돌 · 충돌 해소 · 분리 연쇄법 · 개방 주소법 · 선형 탐사 · 리해싱 · 적재율 · 균등 분포

버킷을 가장 바깥 통으로 두는 저장 방식

오브젝트 스토리지 · Amazon S3 · 오브젝트 · 오브젝트 키 · 프리픽스 · 버킷 정책 · Google Cloud Storage · MinIO · 수명 주기 규칙

데이터를 버킷 단위로 나누는 분산 기법

샤딩 · 파티셔닝 · 일관성 해싱 · 해시 링 · 가상 노드 · 리밸런싱 · 핫스팟

이름만 같고 담는 것이 다른 버킷

토큰 버킷 · 누출 버킷 · 처리율 제한 · 히스토그램 · 버킷팅 · 시간 버킷