<commit_before>---
authors: <NAME> <<EMAIL>>, with input from <NAME>, <NAME>
state: predraft
---

<!--
    This Source Code Form is subject to the terms of the Mozilla Public
    License, v. 2.0. If a copy of the MPL was not distributed with this
    file, You can obtain one at http://mozilla.org/MPL/2.0/.
-->

<!--
    Copyright (c) 2018, Joyent, Inc.
-->

# RFD 143 Manta Scalable Garbage Collection Plan

## Introduction

This RFD describes a set of projects that can be delivered in a phased approach
to address several goals:

- Significantly reduce the work required for garbage collection in the most
  common case of objects having no snaplinks.
- Enable the optimized path to be used in existing deployments without modifying
  data in cases where operators can manually confirm the absence of snaplinks.
- Enable garbage collection in Manta deployments where full-shard backups cannot
  be completed on a regular basis.  The basis for this is described in [RFD
  123](../0123/README.md).

This document does not obviate [RFD 123 ("Online Manta Garbage
Collection")](../0123/README.md).  The project described in RFD 123 is part of
the plan described in this RFD.


## Background

**Manta garbage collection and snaplinks**  In Manta, garbage collection ("GC")
refers to the process of cleaning up data associated with objects that have been
removed from Manta.  Because of Manta's support for snaplinks, when the system
processes an API request to delete an object, it is not possible for the system
to know whether the last reference to the object is being removed.  In the case
that a user has created a snaplink `B` from an object `A`, then the object
itself cannot be deleted until both `A` and `B` have been removed.  When only
`A` or `B` is removed, the GC process sees the removal but takes no action,
seeing another reference to the underlying object.  When the other link has been
removed, then GC needs to clean up the associated object.  This needs to work
no matter the order and timing that `A` and `B` are removed.

To address this, the system records the delete request into a delete log.  A
separate process later scans these logs, determines which objects' data can be
cleaned up (because they're not referenced elsewhere), and then executes the
cleanup.  This process is referred to as garbage collection.

**Garbage collection today.**  Today, the GC process requires periodic backups
of metadata databases.  These backups include the delete log itself (which is
stored in the database), plus the set of all objects referenced in the database.
With this information, the system runs a job to find any references to deleted
objects, filter out such objects, and schedule the rest of the objects for
cleanup.  This process is fairly straightforward, but somewhat expensive to run.
Since the process needs to look for references to each object across all
database dumps, the time required increases with the number of objects stored in
Manta.

## Proposed improvements

### Online garbage collection

RFD 123 proposes a process for _online garbage collection_, which refers to
executing this process continuously using the live databases rather than
periodically using batch jobs on database backups.  The primary advantage is
that this would not require the system to create full backups on a regular
basis, nor scan the whole database every day.  It could take advantage of
indexes already provided in the database for the fields it needs to query on.

However, online garbage collection still requires a number of database
operations _on each shard for each object deleted_.  There are likely ways to
mitigate the impact, and definitely ways to control it, but this is still a lot
of extra work to do, and that work competes for resources with the Manta data
path.

### Accelerated GC for objects with only one link

The above approaches to GC are expensive and complex because of the need to
determine for each deleted link whether the underlying object has other links
referencing it.  But while snaplinks are very useful for many use-cases, the
vast majority of objects in most Manta deployments are never snaplinked.  We
propose modifying the data path so that Manta can tell when an object is being
removed that has never had a snaplink created from it.  In that case, instead of
recording the delete to the delete log, it would be recorded to a new table
that's used for accelerated deletion.  A new component would periodically read
entries from this table and immediately queue objects for deletion, rather than
going through the expensive part of the GC process.

The essence of the mechanism is as follows:

- When new objects are created, they are created with a new top-level metadata
  field called `singlePath` with boolean value `true`.
- Whenever a snaplink `B` is created from an object at path `A`, before the new
  metadata entry is created for `B`, the metadata for `A` is modified to remove
  the `singlePath` property (or set it to `false`).
- Whenever any object is removed, if its metadata has `singlePath == true`, then
  for each copy of the object, a row is created in the accelerated delete table.
  There is no row created in the existing delete log table.
- A new component periodically scans entries in the accelerated delete table and
  generates instructions for both storage zones and Moray shards that are
  identical to those generated by the existing GC mechanism.

Note that instead of a new component generating instructions similar to the
existing GC pipeline, we could consider a component that runs _inside_ each
storage zone and processes these deletes.  This is simpler in a sense, but means
that the number of Moray connections and database requests would scale up more
aggressively with the number of storage zones.  It would also make it more
difficult to control the amount of load applied to the databases from this
process, since the configuration of hundreds or thousands of components would
need to be updated.

This scheme was initially proposed under
[MANTA-3347](https://smartos.org/bugview/MANTA-3347).  However, it's largely
orthogonal to online GC.  In particular, this mechanism can be implemented
before or after online GC, and it would likely handle the vast majority of
cases, whether or not the online GC project had already been integrated.

### Accelerated GC for existing objects

The scheme proposed above for accelerated deletion requires that a new bit of
information be stored with new objects.  Existing objects won't have this bit,
and the system will have to assume for safety that these objects may have other
references in other shards.  This means that even after the above has been
implemented and deployed, all existing objects would have to be cleaned up via
the traditional GC mechanism.

There are existing Manta deployments with large amounts of data for which we
would like to take advantage of the accelerated delete mechanism.  In these
cases, it is believed that snaplinks have not been used at all within the
accounts that want to take advantage of the accelerated GC mechanism.  This
suggests another way to trigger accelerated GC:

- Add support for an operator-controlled per-account flag to disable snaplinks
  for the account.
- Add support for an operator-controlled per-account flag to indicate that the
  account's metadata has been checked and verified to contain no snaplinks.
- Modify Manta so that when an object is removed in an account with both of
  these flags set, cleanup runs through the accelerated delete flag described
  above.

This approach enables the accelerated GC option to be used for an account that
already has a lot of object data that the user wants to delete, provided that an
operator can verify that there are no snaplinks in the account.  This puts a
significant burden on the operator, since incorrectly setting this flag could
result in data loss, where an object was removed when it was still referenced.
Real business situations exist where we believe this can be verified reliably
and it would be worthwhile to do so.

## A concrete plan
<commit_msg>RFD 143 initial description of fast delete bucket schema<commit_after>---
authors: <NAME> <<EMAIL>>, with input from <NAME>, <NAME>
state: predraft
---

<!--
    This Source Code Form is subject to the terms of the Mozilla Public
    License, v. 2.0. If a copy of the MPL was not distributed with this
    file, You can obtain one at http://mozilla.org/MPL/2.0/.
-->

<!--
    Copyright (c) 2018, Joyent, Inc.
-->

# RFD 143 Manta Scalable Garbage Collection Plan

## Introduction

This RFD describes a set of projects that can be delivered in a phased approach
to address several goals:

- Significantly reduce the work required for garbage collection in the most
  common case of objects having no snaplinks.
- Enable the optimized path to be used in existing deployments without modifying
  data in cases where operators can manually confirm the absence of snaplinks.
- Enable garbage collection in Manta deployments where full-shard backups cannot
  be completed on a regular basis.  The basis for this is described in [RFD
  123](../0123/README.md).

This document does not obviate [RFD 123 ("Online Manta Garbage
Collection")](../0123/README.md).  The project described in RFD 123 is part of
the plan described in this RFD.


## Background

**Manta garbage collection and snaplinks**  In Manta, garbage collection ("GC")
refers to the process of cleaning up data associated with objects that have been
removed from Manta.  Because of Manta's support for snaplinks, when the system
processes an API request to delete an object, it is not possible for the system
to know whether the last reference to the object is being removed.  In the case
that a user has created a snaplink `B` from an object `A`, then the object
itself cannot be deleted until both `A` and `B` have been removed.  When only
`A` or `B` is removed, the GC process sees the removal but takes no action,
seeing another reference to the underlying object.  When the other link has been
removed, then GC needs to clean up the associated object.  This needs to work
no matter the order and timing that `A` and `B` are removed.

To address this, the system records the delete request into a delete log.  A
separate process later scans these logs, determines which objects' data can be
cleaned up (because they're not referenced elsewhere), and then executes the
cleanup.  This process is referred to as garbage collection.

**Garbage collection today.**  Today, the GC process requires periodic backups
of metadata databases.  These backups include the delete log itself (which is
stored in the database), plus the set of all objects referenced in the database.
With this information, the system runs a job to find any references to deleted
objects, filter out such objects, and schedule the rest of the objects for
cleanup.  This process is fairly straightforward, but somewhat expensive to run.
Since the process needs to look for references to each object across all
database dumps, the time required increases with the number of objects stored in
Manta.

## Proposed improvements

### Online garbage collection

RFD 123 proposes a process for _online garbage collection_, which refers to
executing this process continuously using the live databases rather than
periodically using batch jobs on database backups.  The primary advantage is
that this would not require the system to create full backups on a regular
basis, nor scan the whole database every day.  It could take advantage of
indexes already provided in the database for the fields it needs to query on.

However, online garbage collection still requires a number of database
operations _on each shard for each object deleted_.  There are likely ways to
mitigate the impact, and definitely ways to control it, but this is still a lot
of extra work to do, and that work competes for resources with the Manta data
path.

### Accelerated GC for objects with only one link

The above approaches to GC are expensive and complex because of the need to
determine for each deleted link whether the underlying object has other links
referencing it.  But while snaplinks are very useful for many use-cases, the
vast majority of objects in most Manta deployments are never snaplinked.  We
propose modifying the data path so that Manta can tell when an object is being
removed that has never had a snaplink created from it.  In that case, instead of
recording the delete to the delete log, it would be recorded to a new table
that's used for accelerated deletion (see 'Accelerated Delete Table').  A new
component would periodically read entries from this table and immediately queue
objects for deletion, rather than going through the expensive part of the GC
process.

The essence of the mechanism is as follows:

- When new objects are created, they are created with a new top-level metadata
  field called `singlePath` with boolean value `true`.
- Whenever a snaplink `B` is created from an object at path `A`, before the new
  metadata entry is created for `B`, the metadata for `A` is modified to remove
  the `singlePath` property (or set it to `false`).
- Whenever any object is removed, if its metadata has `singlePath == true`, then
  for each copy of the object, a row is created in the accelerated delete table.
  There is no row created in the existing delete log table.
- A new component periodically scans entries in the accelerated delete table and
  generates instructions for both storage zones and Moray shards that are
  identical to those generated by the existing GC mechanism.

Note that instead of a new component generating instructions similar to the
existing GC pipeline, we could consider a component that runs _inside_ each
storage zone and processes these deletes.  This is simpler in a sense, but means
that the number of Moray connections and database requests would scale up more
aggressively with the number of storage zones.  It would also make it more
difficult to control the amount of load applied to the databases from this
process, since the configuration of hundreds or thousands of components would
need to be updated.

This scheme was initially proposed under
[MANTA-3347](https://smartos.org/bugview/MANTA-3347).  However, it's largely
orthogonal to online GC.  In particular, this mechanism can be implemented
before or after online GC, and it would likely handle the vast majority of
cases, whether or not the online GC project had already been integrated.

### Accelerated GC for existing objects

The scheme proposed above for accelerated deletion requires that a new bit of
information be stored with new objects.  Existing objects won't have this bit,
and the system will have to assume for safety that these objects may have other
references in other shards.  This means that even after the above has been
implemented and deployed, all existing objects would have to be cleaned up via
the traditional GC mechanism.

There are existing Manta deployments with large amounts of data for which we
would like to take advantage of the accelerated delete mechanism.  In these
cases, it is believed that snaplinks have not been used at all within the
accounts that want to take advantage of the accelerated GC mechanism.  This
suggests another way to trigger accelerated GC:

- Add support for an operator-controlled per-account flag to disable snaplinks
  for the account.
- Add support for an operator-controlled per-account flag to indicate that the
  account's metadata has been checked and verified to contain no snaplinks.
- Modify Manta so that when an object is removed in an account with both of
  these flags set, cleanup runs through the accelerated delete flag described
  above.

This approach enables the accelerated GC option to be used for an account that
already has a lot of object data that the user wants to delete, provided that an
operator can verify that there are no snaplinks in the account.  This puts a
significant burden on the operator, since incorrectly setting this flag could
result in data loss, where an object was removed when it was still referenced.
Real business situations exist where we believe this can be verified reliably
and it would be worthwhile to do so.

## Accelerated Delete Table

As described in the previous sections, the accelerated delete mechanism will
keep track of objects deleted in a new table called `manta_fastdelete_queue`.
We propose the following Postgres schema for this new table:

```
                                      Table "public.manta_fastdelete_queue"
  Column   |     Type     |                                   Modifiers
-----------+--------------+--------------------------------------------------------------------------------
 _id       | integer      | default nextval('manta_fastdelete_queue_serial'::regclass)
 _txn_snap | integer      |
 _key      | text         | not null
 _value    | text         | not null
 _etag     | character(8) | not null
 _mtime    | bigint       | default ((date_part('epoch'::text, now()) * (1000)::double precision))::bigint
 _vnode    | bigint       |
Indexes:
    "manta_fastdelete_queue_pkey" PRIMARY KEY, btree (_key)
    "manta_fastdelete_queue__etag_idx" btree (_etag) WHERE _etag IS NOT NULL
    "manta_fastdelete_queue__id_idx" btree (_id) WHERE _id IS NOT NULL
    "manta_fastdelete_queue__mtime_idx" btree (_mtime) WHERE _mtime IS NOT NULL
    "manta_fastdelete_queue__vnode_idx" btree (_vnode) WHERE _vnode IS NOT NULL
```

This schema differs from the `manta_delete_log` in that we omit the `objectId`
column (and its corresponding index). We opt to store the object id of the
deleted object in the `_key` column of the table instead. This is safe to do
because:

1. Object ids are unique
2. Any rows inserted into `manta_fastdelete_queue` must have had no snaplinks
when they were removed from the `manta` table

(2) implies both that a row in `manta_fastdelete_queue` can be neither a delete
record for a snaplink nor a delete record for an object that could at some point
be snaplinked to a different path (that object id will never be in the manta
bucket again). It follows from (1) that all insertions into
`manta_fastdelete_queue` will have unique values under the proposed accelerated
delete mechanism.

The `_value` column of the table will store the same contents as the
identically named column in `manta_delete_log` does. Crucially, these contents
include

1. The `manta_storage_id`s of the sharks on which the object is located
2. The the uuid of the account that created object

These two pieces of information are needed to identify the backing file for
the object on a Mako. For context, the backing file is stored at the following
path on some subset of the Makos:

```
/manta/<creator-uuid>/<object-id>
```

We choose to keep the remaining contents of `_value` because they may be useful
in the future. Further, `manta_fastdelete_queue` is unlikely to ever grow that
much since it is processed continuously by a new component described in the
previous sections. The suggests that any space gains that might come from paring
away at the contents `_value` column would likely be minimal.

## A concrete plan

{'fraction_non_alphanumeric': 0.043586809528763135, 'fraction_numerical': 0.004785186726308124, 'mean_word_length': 4.066403162055336, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 19, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6843005', 'n_tokens_mistral': 4714, 'n_tokens_neox': 4598, 'n_words': 2986}