툼스톤

데이터를 지울 때 그 자리의 값을 없애는 대신 남기는 삭제 표시입니다. 지웠다는 사실 자체를 하나의 기록으로 새로 써 넣는 것입니다. 조회는 이 표시보다 오래된 값을 없는 것으로 봅니다. 표시 자체는 정해진 기간이 지난 뒤에 따로 걷어냅니다.

상세

명부에서 한 사람을 뺄 때 이름을 지우개로 지우는 대신 그 위에 줄을 하나 긋습니다. 글자는 그 자리에 그대로 남아 있어도 읽는 사람은 그 이름을 빠진 것으로 넘깁니다. 이름과 줄이 함께 없어지는 것은 명부를 새 종이에 옮겨 적을 때입니다.

툼스톤은 삭제를 값의 제거가 아니라 기록의 추가로 처리할 때 남는 그 기록입니다. 지우라는 요청이 들어오면 저장소는 그 자리의 값을 건드리지 않고 "이 대상은 이 시각에 지워졌다" 는 표시를 새로 씁니다. 표시에는 언제 지워졌는지가 시각으로 박혀 있고, 언제 만료되는지도 함께 붙습니다.

이 표시는 일반 쓰기와 같은 경로를 탑니다. 그래서 삭제도 쓰기와 똑같이 복제되고, 똑같이 저장 파일에 실립니다. 삭제가 별도의 특별한 연산이 아니라 그냥 또 하나의 쓰기가 되는 셈입니다.

조회는 이 표시에 찍힌 시각보다 앞선 값을 전부 무시합니다. 값이 디스크에 그대로 남아 있어도 읽는 쪽에서는 없는 것으로 보입니다. 값과 표시가 함께 없어지는 것은 나중입니다. 만료 기간이 끝나고, 저장 파일을 다시 정리하는 컴팩션이 그 둘을 함께 떨어뜨릴 때입니다.

수명을 미리 붙여 두는 길도 있습니다. 값에 TTL(Time To Live, 생존 시간)을 걸면 그 시간이 지난 뒤 저장소가 그 대상에 툼스톤을 붙입니다. 그때부터는 손으로 지운 것과 똑같이 다뤄집니다.

배경

복제본이 여럿인 저장소에서는 값을 진짜로 지우는 것이 위험합니다. 노드 셋이 값 [A] 를 한 벌씩 들고 있다고 해봅시다. 삭제가 값을 없애기만 하는 연산이면, 노드 하나가 죽어 있는 사이에 삭제가 돌면 상태가 [], [], [A] 가 됩니다. 그 뒤 복제본을 맞추는 수리가 돌면 수리는 빠진 쪽을 채워 넣는 일을 합니다. 결과는 [A], [A], [A] 입니다. 지운 값이 되살아났습니다. 이렇게 지워졌는데 살아 돌아온 데이터를 좀비라고 부릅니다.

없음과 아직 못 받았음을 구별할 수 없다는 것이 뿌리입니다. 값이 사라진 자리와 애초에 값이 온 적 없는 자리가 똑같이 생겼으면, 수리하는 쪽은 둘을 가릴 방법이 없습니다. 그래서 삭제도 하나의 사실로 남아야 합니다. 삭제를 표시의 추가로 바꾸면 상태는 [A, 삭제 표시], [A, 삭제 표시], [A] 가 되고, 수리는 값이 아니라 표시를 퍼뜨립니다. 늦게 돌아온 노드도 삭제를 받게 됩니다.

이 표시를 툼스톤, 곧 묘비라고 부릅니다. 로그 구조 저장 엔진에서 흔히 쓰지만 그 동네에서 시작한 말은 아닙니다. 디렉터리를 여러 서버가 복제하는 자리에서 같은 이름이 더 이르게 문서화돼 있습니다. Microsoft 는 Active Directory 스키마의 tombstoneLifetime 속성을 Windows 2000 Server 부터 구현 목록에 올려 두었습니다. 지워진 개체를 디렉터리에서 실제로 치우기까지 며칠을 둘지 정하는 값이고, 공식 문서는 그 목적이 복제된 서버에서 개체를 없애는 것과 복원이 지워진 개체를 다시 들여오는 것을 막는 데 도움이 되는 것이라고 적습니다. 값을 안 넣으면 60일입니다. 누가 이 이름을 처음 붙였는지는 확인되지 않았습니다.

동작

삭제 요청이 곧바로 자리를 비우지 않으므로, "언제 실제로 사라지나" 가 따로 있습니다. 그 답이 유예 기간과 컴팩션입니다.

flowchart TD
    A["삭제 요청"] --> B["툼스톤을 쓰기 경로로 기록"]
    B --> C["복제본으로 전파"]
    C --> D{"유예 기간이 지났나"}
    D -->|아니다| E["컴팩션이 지나가도 툼스톤은 남긴다"]
    E --> D
    D -->|지났다| F["컴팩션이 값과 툼스톤을 함께 버린다"]

유예 기간은 테이블 속성 gc_grace_seconds 로 정합니다. Apache Cassandra 의 기본값은 864000초, 곧 10일입니다. 테이블마다 다른 값을 줄 수 있습니다. DataStax 문서는 복제본이 없는 단일 노드 클러스터라면 이 값을 0으로 두어도 안전하다고 적습니다. 유예 기간의 목적은 응답 없던 노드가 회복해 툼스톤을 정상으로 처리할 시간을 주는 것입니다.

유예 기간 안에는 세 가지가 다르게 처리됩니다. 그 사이 클라이언트가 같은 대상에 새 갱신을 쓰면 툼스톤은 그 갱신으로 덮입니다. 그 사이 읽기가 들어오면 저장소는 툼스톤을 무시하고 가능하면 다른 복제본에서 값을 가져옵니다. 그리고 죽었던 노드가 살아나면 힌티드 핸드오프가 그동안 놓친 변경을 재생하지만, 유예 기간 중인 툼스톤 대상의 변경은 재생하지 않습니다. 다만 노드가 유예 기간이 끝난 뒤에야 회복하면 삭제를 놓칠 수 있습니다.

유예 기간이 끝나면 그 다음 컴팩션에서 툼스톤이 떨어집니다. 조건이 하나 붙습니다. 그 툼스톤이 다른 저장 파일에 있는 삭제 대상 데이터를 아직 가리고 있으면 안 됩니다. 한 저장 파일이 툼스톤만 담고 있고 다른 파일의 데이터를 가리지 않는 것이 보장되면, 컴팩션은 그 파일을 통째로 버릴 수 있습니다. 툼스톤만 든 파일이 안 없어진다면 다른 파일에 더 오래된 데이터가 남아 있을 가능성이 큽니다. Apache Cassandra 는 어느 파일이 버릴 수 있는 상태이고 무엇이 그것을 막고 있는지 보여주는 sstableexpiredblockers 도구를 함께 답니다.

기다리지 않고 앞당기는 절차도 문서로 나와 있습니다. ScyllaDB 는 이것을 다섯 단계로 적습니다. 먼저 nodetool repair 로 노드 사이 데이터를 맞춥니다. 다음으로 gc_grace_seconds 를 마지막 수리를 시작한 시점만큼으로 낮춥니다. 그 상태에서 nodetool flush 와 nodetool compact 를 돌립니다. 끝으로 유예 기간을 원래 값으로 되돌립니다. 데이터가 되살아나는 것을 막으려면 유예 기간에 닿기 전에 수리를 마쳐 두어야 한다는 조건이 붙습니다.

대가

데이터를 안 지우기로 한 값을 치릅니다. 툼스톤은 계속 쌓이고, 컴팩션에서 떨어지기 전까지 디스크 공간을 영구히 차지합니다. 툼스톤을 영원히 들고 있지 않으려고 테이블마다 유예 기간을 거는 것이 바로 이 때문입니다.

읽기도 값을 치릅니다. 조회는 흩어져 있는 삭제 표시를 함께 훑어야 어떤 값이 아직 살아 있는지 가릴 수 있습니다. 그래서 훑은 툼스톤 수 자체가 운영 지표가 됩니다. Cassandra 는 tombstone_warn_threshold 를 두어 한 질의가 이 수보다 많은 툼스톤을 훑으면 경고를 냅니다. 기본값은 1000 입니다. tombstone_failure_threshold 를 넘으면 질의를 아예 중단합니다. 기본값은 100000 입니다. 지워둔 것이 많아지면 읽는 쪽이 먼저 막히는 구조입니다.

의도하지 않은 자리에서도 늘어납니다. DataStax 문서는 삭제가 DELETE 명령으로만 생기지 않는다고 적습니다. TTL 로 만료된 데이터, 구체화 뷰 같은 내부 연산, null 값을 넣는 삽입과 갱신, 컬렉션 컬럼에 대한 갱신이 전부 툼스톤을 만듭니다. 지울 대상이 아예 없어도 마찬가지입니다. 존재하지 않는 레코드를 지우면 표시할 실제 레코드가 없는데도 툼스톤은 그대로 써집니다.

유예 기간은 양쪽으로 값을 치릅니다. 길게 잡으면 디스크 부담과 읽기 훑기가 그만큼 오래 갑니다. 짧게 잡으면 응답 없던 노드가 돌아오기 전에 툼스톤이 사라져 삭제를 놓칠 수 있습니다.

예시

지우는 범위에 따라 남는 표시가 다릅니다. DataStax 문서는 파티션, 로우, 레인지, 복합 컬럼, 셀, TTL 여섯 가지로 나눕니다. 아래는 그중 셋을 sstabledump 로 실제 저장 파일을 열어 본 것입니다.

파티션을 통째로 지웠을 때

삭제 표시가 파티션 자리에 붙습니다. 파티션 안의 어떤 로우나 셀에도 붙지 않고, rows 는 빈 배열입니다.

JSON

{ "partition" : { "key" : [ "2014", "4th Tour of Beijing" ], "position" :
0, "deletion_info" : { "marked_deleted" : "2018-05-16T19:40:06.454282Z",
"local_delete_time" : "2018-05-16T19:40:06Z" } }, "rows" : [ ] }

marked_deleted 가 지운 시각이고, local_delete_time 이 그 노드에 기록된 시각입니다.

로우 하나를 지웠을 때

파티션 키와 클러스터링 키에 모두 등호 조건을 걸어 로우 하나를 지목합니다.

cql

DELETE FROM cycling.rank_by_year_and_name
WHERE race_year = 2015 AND race_name = '...' AND rank = 2;

race_name 자리에는 실제 경기 이름이 들어갑니다. 아래 저장 파일 덤프의 파티션 키에 그 값이 그대로 보입니다. 이번에는 삭제 표시가 파티션이 아니라 클러스터링 키로 지목된 로우 자리에 붙었습니다. 파티션에도, 로우 안의 셀에도 표시가 없습니다.

JSON

{ "partition" : { "key" : [ "2015", "Giro d'Italia - Stage 11 - Forli >
Imola" ], "position" : 0 }, "rows" : [ { "type" : "row", "position" : 74,
"clustering" : [ 2 ], "deletion_info" : { "marked_deleted" :
"2018-05-18T15:29:06.227148Z", "local_delete_time" :
"2018-05-18T15:29:06Z" }, "cells" : [ ] } ] }

컬렉션 컬럼을 통째로 바꿨을 때

집합 컬럼을 갱신으로 갈아끼우면, 새 원소를 넣기 전에 옛 원소 전체를 덮는 표시가 먼저 붙습니다. 아래 실물에서 teams 라는 이름은 네 번 나옵니다. 첫 줄만 deletion_info 를 답니다. 나머지 셋은 새로 들어간 원소입니다. 지운 적 없다고 생각한 갱신 한 번에 툼스톤이 생기는 자리입니다.

JSON

{ "partition" : { "key" : [ "cb07baad-eac8-4f65-b28a-bddc06a0de23" ],
"position" : 0 }, "rows" : [ { "type" : "row", "position" : 130,
"liveness_info" : { "tstamp" : "2018-05-18T16:26:23.779724Z" }, "cells" :
[ { "name" : "lastname", "value" : "Armitstead" }, { "name" : "teams",
"deletion_info" : { "marked_deleted" : "2018-05-18T16:26:23.779723Z",
"local_delete_time" : "2018-05-18T16:26:23Z" } }, { "name" : "teams",
"path" : [ "AA Drink - Leontien.nl" ], "value" : "" }, { "name" :
"teams", "path" : [ "Boels-Dolmans Cycling Team" ], "value" : "" }, {
"name" : "teams", "path" : [ "Team Garmin - Cervelo" ], "value" : "" } ] }
] }

RocksDB 의 DeleteRange

LSM(Log-Structured Merge, 로그 구조 병합) 트리를 쓰는 다른 저장소에도 같은 것이 있습니다. RocksDB 에서 키 구간을 지우려면 원래는 반복자로 구간을 훑으며 키마다 Delete 를 부르는 방식을 썼습니다. 이 방식은 구간 스캔을 해야 해서 원자적 연산이 못 됩니다. 성능에 민감한 쓰기 경로에 두기에 적절하지 않습니다. 그래서 전용 연산이 따로 있습니다.

C++

Slice start, end; // set start and end
db->DeleteRange(WriteOptions(), start, end);

RocksDB 문서는 이 호출이 내부에서 키·값 한 개로 표현되는 레인지 툼스톤을 만든다고 적습니다. 키마다 삭제를 쓰는 대신 구간 하나를 표시 한 개로 적는 것이라, 쓰기 성능이 크게 나아집니다. 읽기 성능은 훑으며 지우는 방식과 견줄 만한 수준이라고 적습니다.

상세

배경

동작

대가

예시

파티션을 통째로 지웠을 때

로우 하나를 지웠을 때

컬렉션 컬럼을 통째로 바꿨을 때

RocksDB 의 DeleteRange

관련 항목

툼스톤을 실제로 구현·채택한 제품

삭제가 실제로 사라지기까지 거치는 처리 단계

툼스톤과 얽히는 오류·장애

툼스톤의 만료 시점을 정하는 설정값

DELETE 아닌 경로로 툼스톤이 생기는 원인

툼스톤을 점검·정리하는 도구