From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp> Currently, sheepdog doesn't reclaim objects until all the snapshots are deleted. For example: $ collie vdi create image $ collie vdi write image < some_data $ collie vdi snapshot image -s snap1 $ collie vdi write image < some_data $ collie vdi delete image <- this doesn't reclaim the objects of the image $ collie vdi delete image -s snap1 <- this reclaims all the data objects of both image and image:snap1 To resolve this problem, we need to introduce something like reference counting mechanism. However, a naive approach doesn't work well on Sheepdog. It is because, when we create a snapshot or clone vdi, we have to increment all the reference count of its data objects and send many requests to all over the nodes. This series uses generation reference counting [1], which is more appropriate algorithm for distributed system like Sheepdog. With this series, we can reclaim objects just when they are no longer necessary. [1] B. Goldberg, Generation reference counting: A reduced communication distributed storage reclamation scheme, PLDI '89 == Here is a brief explanation of the object reclaim algorithm. If you want to know the details or correctness proof of the generational reference counting, please refer the original paper: Each data object contains the following structure in its inode: struct generation_reference { int32_t generation; int32_t count; } data_ref; The generation field identifies the generation of the reference and the count field records the number of references copied from this particular reference. We also introduce a new type of object, a ledger object. The ledger object exists for each data object and contains an array of int32_t values. The i-th element of the array contains information about the number of outstanding data object references in the i-th generation. Generational reference counting is performed as follows: 1. When a vdi A is created, the initial data object references are initialized as follows: for (i = 0; i < MAX_DATA_OBJS; i++) { A.data_ref[i].generation = 0; A.data_ref[i].count = 0; } and a ledger object for each data object is initialized as follows: ledger_object[0] = 1; for (i = 1; i < MAX_DATA_OBJS; i++) { ledger_object[i] = 0; } In practice, the ledger object is created and initialized when the object is accessed for the first time, so we don't have to create all the ledger objects when the vdi is created. 2. When a VDI B is created as a clone (or snapshot) of A, the new reference B is initialized as follows: for (i = 0; i < MAX_DATA_OBJS; i++) { B.data_ref[i].generation = A.data_ref[i].generation + 1; B.data_ref[i].count = 0; } In addition, A.data_ref.count's are incremented: for (i = 0; i < MAX_DATA_OBJS; i++) { A.data_ref[i].count++; } 3. When a object o is removed, a decrement message is sent to its ledger object containing the values of o.generation and o.count. 4. When a decrement message to o is received, in which the generation field has the value i and the count field has the value c, the following actions are performed: o.ledger[i]--; o.ledger[i + 1] += c; When every element of the ledger becomes zero (for all i >= 0, o.ledger[i] = 0), o can be reclaimed. Note that some elements of the ledger may hold negative values. MORITA Kazutaka (10): sheep: introduce xfallocate and xftruncate helpers use 4KB for trim_zero_sectors instead of 512B sheep: introduce generational reference counting for object reclaim sheep: introduce ledger objects sheep: decrement generational reference count on vdi deletion sheep: decrement generational reference count on copy-on-write sheep: remove max children limit sheep: introduce sparse objects sheep: caluculate actually allocated size tests: update outputs of testcases for reclaim and new vdi size collie/common.c | 12 +-- collie/vdi.c | 27 +++--- include/internal_proto.h | 2 + include/sheepdog_proto.h | 43 ++++++++- include/util.h | 9 +- lib/util.c | 83 +++++++++++++---- sheep/cluster/local.c | 6 +- sheep/gateway.c | 112 +++++++++++++++++++++- sheep/journal.c | 2 +- sheep/md.c | 11 ++- sheep/migrate.c | 2 +- sheep/ops.c | 113 +++++++++++++++++++++-- sheep/plain_store.c | 83 +++++++++++++++-- sheep/sheep_priv.h | 14 +++ sheep/store.c | 26 +++++- sheep/vdi.c | 231 +++------------------------------------------- sheepfs/volume.c | 3 +- tests/016.out | 8 +- tests/042.out | 32 +++---- tests/044.out | 8 +- tests/057.out | 10 +- tests/058.out | 16 ++-- 22 files changed, 528 insertions(+), 325 deletions(-) -- 1.7.9.5 |