Lines Matching refs:in
7 requested by a user to the compressed blocks on SSD. The scheme described in this document
9 framework. This algorithm will be implemented in a library called "libreduce". Higher-level
10 software modules can built on top of this library to create and present block devices in a
19 (Note that in some cases, blocks of storage may not be compressible, or cannot be compressed enough
25 compression for reasons described later in this document. This algorithm has no direct knowledge
34 in place, some additional backing storage is required to temporarily store data for writes in
37 Storage from the backing storage device will be allocated, read, and written to in 4KB units for
42 A compressed block device compresses and decompresses data in units of chunks, where a chunk is a
45 consumes a number of 4KB backing IO units between 1 and the number of 4KB units in the chunk. For
47 much the chunk was able to be compressed. The blocks on disk associated with a chunk are stored in…
48 "chunk map" in persistent memory. Each chunk map consists of N 64-bit values, where N is the maxim…
49 number of backing IO units in the chunk. Each 64-bit value corresponds to a backing IO unit index.…
53 writes and will be explained later in this document. At start, all of the chunk maps represent the
58 chunk map. Each entry in the logical map is a 64-bit value, denoting the associated chunk map.
61 array index into the array of chunk map entries. At start, all entries in the logical map have no
62 associated chunk map. Note that while access to the backing storage device is in 4KB units, the
76 the 20 4KB IO units in the backing storage.
77 * A "chunk map" will be 32 bytes in size. This corresponds to 4 backing IO units per chunk
79 * 5 chunk maps will be allocated in 160B of persistent memory. This corresponds to 4 chunk maps
80 for the 4 chunks in the compressed block device (64KB / 16KB), plus an extra chunk map for use
84 * The "logical map" will be allocated in 32B of persistent memory. This corresponds to
85 4 entries for the 4 chunks in the compressed block device and 8B (64b) per entry.
113 * Entry 2 in the logical map is "X". This means no part of this 16KB has been written to yet.
114 * Allocate a 16KB buffer in memory
118 entries in the free backing IO unit list - this ensures that unnecessary backing storage
119 is not allocated in the thin-provisioned logical volume holding the backing storage.
124 * Write the chunk map index to entry 2 in the logical map.
147 * Entry 0 in the logical map is "X". This means no part of this 16KB has been written to yet.
158 * Write the chunk map index to entry 0 in the logical map.
180 * Offset 16KB maps to index 1 in the logical map.
181 * Entry 1 in the logical map is "X". This means no part of this 16KB has been written to yet.
186 * Offset 4KB maps to index 0 in the logical map.
187 * Entry 0 in the logical map is "1". Since we are not overwriting the entire chunk, we must
204 * Write chunk map 2 to entry 0 in the logical map.
234 chunk 0 in the logical map) and a 8KB write at offset 16KB (affecting only chunk 1 in the
255 operation covers an entire chunk, we can remove the chunk's entry in the logical map
269 This ensures that if a system crashes in the middle of a write operation - i.e. during or
271 related to that in-progress write will be ignored after the compressed volume is restarted.
276 operation 1 writes some data to chunk A, and while this is in progress, operation 2 also writes