[Ceph Storage] CRUSH 알고리즘과 CRUSH Map
![[Ceph Storage] CRUSH 알고리즘과 CRUSH Map](https://blog.kakaocdn.net/dn/uqd2G/btr1Y9ae9y2/I6HIm0KdESYTh9PlP70Yw1/img.jpg)
Ceph는 오픈소스 분산 스토리지 시스템으로, 객체, 블록, 파일 시스템 등 다양한 형태의 데이터를 저장하고 관리할 수 있습니다. Ceph의 중요한 구성 요소 중 하나는 CRUSH 알고리즘과 CRUSH Map입니다. 이번에는 Ceph의 CRUSH Map에 대해 자세히 살펴보겠습니다.
CRUSH 알고리즘
CRUSH 알고리즘은 Ceph에서 사용하는 분산 데이터 복제 및 위치 결정 알고리즘입니다. CRUSH 알고리즘은 데이터를 저장하는 OSD (Object Storage Device)의 위치를 결정하는 데 사용됩니다. 이를 통해 데이터를 안정적으로 분산 저장하고, 데이터의 안전성 및 가용성을 보장합니다. CRUSH 알고리즘은 단순한 해시 알고리즘보다 효율적이며, 데이터 복제 및 복구에 있어서도 우수한 성능을 보입니다.
CRUSH 알고리즘은 데이터를 저장할 수 있는 OSD의 위치를 결정하기 위해, 일련의 규칙과 매핑을 사용합니다. 이러한 규칙과 매핑은 CRUSH Map을 통해 정의됩니다.
CRUSH Map
CRUSH Map은 Ceph 클러스터의 물리적인 노드 및 OSD의 계층 구조와 관련된 정보를 담고 있는 데이터 구조입니다. CRUSH Map은 OSD의 위치 결정 및 데이터 복제, 데이터 이동 등에 사용됩니다. CRUSH Map은 JSON 형식으로 정의되며, 일반적으로는 "ceph osd crush dump" 명령어를 사용하여 확인할 수 있습니다.
CRUSH Map은 다음과 같은 구성 요소로 이루어져 있습니다.
Bucket
Bucket은 OSD 그룹화를 위한 가상 노드입니다. Bucket은 다른 Bucket 또는 OSD를 자식으로 가질 수 있습니다. Bucket은 다양한 형태로 정의될 수 있으며, 다음과 같은 유형이 있습니다.
- Root Bucket: 전체 클러스터를 대표하는 가상 노드입니다.
- Failure Domain Bucket: 장애 도메인을 정의하는 가상 노드입니다. 예를 들어, 랙, 샤드 등의 물리적인 장애 도메인을 나타낼 수 있습니다.
- Device Class Bucket: 장치 유형을 정의하는 가상 노드입니다. 예를 들어, SSD, HDD 등의 장치 유형을 나타낼 수 있습니다.
Bucket은 다음과 같이 JSON 형식으로 정의됩니다.
{
"id": <bucket id>,
"type": <bucket type>,
"name": <bucket name>,
"weight": <bucket weight>,
"alg": <bucket 알고리즘>,
"hash": <bucket 해시 알고리즘>,
"items": [
<child bucket or OSD>,
...
]
}- id: Bucket의 고유 식별자입니다. 모든 Bucket과 OSD는 고유한 ID를 가집니다.
- type: Bucket의 종류를 나타냅니다. 예를 들어, root, host, rack 등이 있습니다.
- name: Bucket의 이름입니다.
- weight: Bucket의 가중치입니다. Bucket의 크기에 비례합니다.
- alg: Bucket 내의 OSD 배치 알고리즘입니다. 예를 들어, straw2, uniform 등이 있습니다.
- hash: Bucket 내의 OSD 선택을 위한 해시 알고리즘입니다. 예를 들어, rjenkins1, sha1 등이 있습니다.
- items: Bucket이 가지고 있는 자식 Bucket 또는 OSD의 목록입니다.
OSD
OSD는 Object Storage Device의 약자로, 데이터를 저장하고 관리하는 단위입니다. OSD는 다음과 같이 JSON 형식으로 정의됩니다.
{
"id": <OSD id>,
"weight": <OSD weight>,
"crush_location": {
"<bucket type>": "<location>",
...
}
}- id: OSD의 고유 식별자입니다. 모든 OSD는 고유한 ID를 가집니다.
- weight: OSD의 가중치입니다. OSD의 크기에 비례합니다.
- crush_location: OSD가 속한 Bucket의 위치 정보입니다. Bucket type과 위치를 쌍으로 저장합니다.
Rule
Rule은 데이터의 복제 규칙을 정의하는 구성 요소입니다. Rule은 다음과 같이 JSON 형식으로 정의됩니다.
{
"rule_id": <rule id>,
"rule_name": "<rule name>",
"ruleset": <ruleset id>,
"type": <replication type>,
"min_size": <minimum number of replicas>,
"max_size": <maximum number of replicas>,
"steps": [
...
]
}- rule_id: Rule의 고유 식별자입니다.
- rule_name: Rule의 이름입니다.
- ruleset: Rule이 적용되는 ruleset의 ID입니다.
- type: 데이터의 복제 방식을 나타냅니다. 예를 들어, replicated, erasure coded 등이 있습니다.
- min_size: 최소 복제 수입니다.
- max_size: 최대 복제 수입니다.
- steps: 데이터의 위치 결정을 위한 매핑 단계입니다. 각 매핑 단계는 Bucket ID, Bucket type, Bucket 내 OSD 배치 알고리즘 등의 정보를 포함합니다.
예시
다음은 Ceph의 CRUSH Map 예시입니다.
{
"nodes": [
{
"id": -1,
"name": "default",
"type": "root",
"children": [
{
"id": -2,
"name": "zone1",
"type": "zone",
"children": [
{
"id": -3,
"name": "host1",
"type": "host",
"children": [
{
"id": 0,
"name": "osd.0",
"weight": 1.0
},
{
"id": 1,
"name": "osd.1",
"weight": 1.0
}
]
},
{
"id": -4,
"name": "host2",
"type": "host",
"children": [
{
"id": 2,
"name": "osd.2",
"weight": 1.0
},
{
"id": 3,
"name": "osd.3",
"weight": 1.0
}
]
}
]
},
{
"id": -5,
"name": "zone2",
"type": "zone",
"children": [
{
"id": -6,
"name": "host3",
"type": "host",
"children": [
{
"id": 4,
"name": "osd.4",
"weight": 1.0
},
{
"id": 5,
"name": "osd.5",
"weight": 1.0
}
]
},
{
"id": -7,
"name": "host4",
"type": "host",
"children": [
{
"id": 6,
"name": "osd.6",
"weight": 1.0
},
{
"id": 7,
"name": "osd.7",
"weight": 1.0
}
]
}
]
}
]
}
],
"straw_calc_version": 1
}위의 예시에서는 root Bucket이 하나 있으며, 그 하위에 두 개의 zone Bucket이 있습니다. 각 zone Bucket은 다시 두 개의 host Bucket을 가지고 있으며, 각 host Bucket은 두 개의 OSD를 가지고 있습니다.
이 CRUSH Map에서는 straw2 알고리즘을 사용하여 OSD를 배치합니다. 이 알고리즘은 OSD의 가중치와 Bucket의 가중치를 고려하여 OSD를 선택합니다. 각 OSD는 여러 Bucket에 속할 수 있으며, 이를 통해 데이터를 분산하여 저장할 수 있습니다.
또한, 위의 예시에서는 Rule도 정의되어 있습니다. 다음은 예시의 Rule입니다.
{
"rules": [{
"rule_id": 0,
"rule_name": "replicated_rule",
"ruleset": 0,
"type": "replicated",
"min_size": 1,
"max_size": 10,
"steps": [{
"op": "take",
"item": -1,
"item_name": "root",
"type": "osd",
"chooseleaf_type": "rack",
"chooseleaf_hash": "rjenkins1",
"required_features": [
"rack",
"host"
]
},
{
"op": "emit"
},
{
"op": "chooseleaf_firstn",
"num": 2,
"type": "osd",
"chooseleaf_type": "indep",
"chooseleaf_hash": "rjenkins1"
},
{
"op": "emit"
}
]
}],
"types": [{
"type_id": 0,
"name": "osd"
}],
"buckets": [{
"id": -1,
"name": "root",
"type_id": 0,
"type_name": "osd",
"children": [{
"id": -2,
"name": "zone1",
"type_id": 0,
"type_name": "osd",
"children": [{
"id": -3,
"name": "host1",
"type_id": 0,
"type_name": "osd",
"children": [{
"id": 0,
"name": "osd.0",
"type_id": 0,
"type_name": "osd",
"weight": 1
},
{
"id": 1,
"name": "osd.1",
"type_id": 0,
"type_name": "osd",
"weight": 1
}
]
},
{
"id": -4,
"name": "host2",
"type_id": 0,
"type_name": "osd",
"children": [{
"id": 2,
"name": "osd.2",
"type_id": 0,
"type_name": "osd",
"weight": 1
},
{
"id": 3,
"name": "osd.3",
"type_id": 0,
"type_name": "osd",
"weight": 1
}
]
}
]
},
{
"id": -5,
"name": "zone2",
"type_id": 0,
"type_name": "osd",
"children": [{
"id": -6,
"name": "host3",
"type_id": 0,
"type_name": "osd",
"children": [{
"id": 4,
"name": "osd.4",
"type_id": 0,
"type_name": "osd",
"weight": 1
},
{
"id": 5,
"name": "osd.5",
"type_id": 0,
"type_name": "osd",
"weight": 1
}
]
},
{
"id": -7,
"name": "host4",
"type_id": 0,
"type_name": "osd",
"children": [{
"id": 6,
"name": "osd.6",
"type_id": 0,
"type_name": "osd",
"weight": 1
},
{
"id": 7,
"name": "osd.7",
"type_id": 0,
"type_name": "osd",
"weight": 1
}
]
}
]
}
]
}]
}위의 Rule은 "replicated" 타입으로 정의되어 있으며, 2개의 OSD에 데이터를 복제하는 규칙입니다. 이 규칙은 ruleset 0에서 사용되며, 이 ruleset은 CRUSH Map에서 정의된 Bucket 계층 구조에서 데이터를 배치하는 데 사용됩니다. 따라서 이 Rule은 위에서 정의한 CRUSH Map의 Bucket 계층 구조와 관련이 있습니다.
Rule은 다음과 같은 세 가지 단계로 구성됩니다.
- take 단계: 데이터를 배치할 OSD를 선택합니다. 이 단계에서는 root Bucket에서 시작하여 각 Bucket의 하위 Bucket 중에서 데이터를 저장할 OSD를 선택합니다. 위 예시에서는 zone1, zone2, host1, host2, host3, host4 중에서 OSD를 선택할 수 있습니다.
- emit 단계: 데이터를 저장할 OSD를 선택한 후, 해당 OSD의 위치를 결정합니다. 이 단계에서는 선택된 OSD가 속한 Bucket 계층 구조에서 OSD의 위치를 결정합니다. 위 예시에서는 zone1, zone2, host1, host2, host3, host4 Bucket 중에서 선택된 OSD가 속한 Bucket을 결정합니다.
- chooseleaf 단계: 데이터를 저장할 OSD의 위치가 결정되면, 데이터를 저장할 OSD를 선택합니다. 이 단계에서는 선택된 OSD 중에서 가장 적합한 OSD를 선택합니다. 위 예시에서는 straw2 알고리즘을 사용하여 가장 적합한 OSD를 선택합니다.
위의 예시에서는 Rule이 하나 있지만, Ceph에서는 여러 Rule을 정의할 수 있습니다. 예를 들어, replication factor이 3인 Rule을 정의하여 3개의 OSD에 데이터를 복제할 수도 있습니다.
CRUSH Map은 Ceph에서 데이터를 분산하여 저장하는 데 필수적인 요소입니다. 이를 통해 Ceph는 데이터를 안정적으로 보관하면서도 데이터 복제 및 데이터 복구를 쉽게 수행할 수 있습니다. 또한 CRUSH Map을 조정하여 클러스터의 확장성을 개선할 수 있습니다. 따라서 Ceph를 사용하는 데 있어서 CRUSH Map을 이해하고 활용하는 것은 매우 중요합니다.