Project

General

Profile

Actions

Feature #13916

open

ZAP should support shrinking

Added by Alexander Stetsenko 3 months ago. Updated 3 months ago.

Status:
In Progress
Priority:
Normal
Category:
filesystems (not ZFS)
Start date:
Due date:
% Done:

90%

Estimated time:
Difficulty:
Medium
Tags:
zfs, zap, shrink
Gerrit CR:

Description

ZFS ZAP can expand, but cannot shrink. This change makes ZAP capable to shrink.

Algorithm is kinda opposite to that how ZAP is expanding. While expanding, a leaf is split on two (siblings).
While shrinking, if we got an empty leaf and it has a sibling and the sibling leaf is empty as well, we remove one of them. The remaining leaf is empty and might have a sibling again. So, we repeat the procedure until there is no sibling or the sibling is not empty.

To clarify: the sibling leaves are those ones, which have same prefix_len and their prefix differs only by least significant bit (sibling bit).

Actions #1

Updated by Alexander Stetsenko 3 months ago

  • Description updated (diff)

Alexander Stetsenko wrote:

ZFS ZAP can expand, but cannot shrink. This change makes ZAP capable to shrink.

Algorithm is kinda opposite to that how ZAP is expanding. While expanding, a leaf is split on two (siblings).
While shrinking, if we got an empty leaf and it has a sibling and the sibling leaf is empty as well, we remove one of them. The remaining leaf is empty and might have a sibling again. So, we repeat the procedure until there is no sibling or the sibling is not empty.

Actions #2

Updated by Electric Monk 3 months ago

  • Gerrit CR set to 1580
Actions #3

Updated by Alexander Stetsenko 3 months ago

  • % Done changed from 0 to 90
Actions

Also available in: Atom PDF