Old design notes (from the README of scubed3) These notes describe the scheduling of an earlier design (blocks with roles DATA and FILLER, scheduled in advance by sequence number); scubed3 does not work like this anymore, see "Write order" in the README. Random block selection ~~~~~~~~~~~~~~~~~~~~~~ How to randomly select blocks and assign roles to them? In this example, we use 6 macroblocks, each write a group of 3 blocks needs to be preserved. Suppose we have the random numbers 20312015.. The algorithm works as follows: - assume the current list of random numbers is valid - add a number * check for problems caused by this number, stop if no problems * mark problem causing number as unused, check for problems caused by this shift, of so continue here step | disk | rng output | commentary | 012345 | 20312015.. | --------------------------------------------------------------------- 0 | 0 | 2 | check none, use empty #2 as DATA0 1 | 1 0 | 20 | check [0..0], use empty #0 as DATA1 2 | 1 02 | 203 | check [0..1], use empty #3 as DATA2 3 | 1302 | 2031 | check [0..2], use empty #1 as DATA3 4 | 1342 | 20312 | check [1..3], overwrite DATA0 at #2 with DATA4 5 | 5342 | 203120 | check [2..4], overwrite DATA1 at #0 with DATA5 6 | 5642 | 203_201 | check [3..5], conflict at #1 with DATA3, mark as unused 6.5 | 5642 | 2_3_201 | check [1..5], conflict at #0 with DATA1, mark as unused 6.4 | 5642 | __3_201 | check [0..4], conflict at #2 with DATA0, mark as unused 7 | 5642 7 | __3_2015 | check [], conflict at #2 with DATA0, mark as unused So, how to know when a block designation as datablock is definitive (i.e.: will not be changed to _)? Let's take for example (NO_BLOCKS=6, SIMULTANEOUS_BLOCKS=3) 012345012345 This looks pretty safe. Lets try to add numbers to break it 012345012345 ++ 145 0123450231451 012345023451 251 01234503425 012345012345 ++ 1 -> 0123450123451 0123450123451 ++ 4 -> 0123450123514 0123450123514 ++ 5 -> 012345023145 012345023145 ++ 1 -> 012345023451 012345012345 ++ 1451 -> 012345023451 012345023451 ++ 2512 -> 012345034512 012345034512 ++ 3123 -> 0123045123 0123045123 012345012345 SIMULTANEOUS_BLOCKS=0 -> all blocks are immediately safe SIMULTANEOUS_BLOCKS=1 -> a block is safe if it is followed by another block SIMULTANEOUS_BLOCKS=2 -> ? due to cascade effect, you are never safe ? for example: NO_BLOCKS=4, SIMULTANEOUS_BLOCKS=2 01230123 21 0123012321 2 0123012312 13 01230123213 1 01230123231 32 012301232132 3 01230123123 ----------------------------- NONSENSE, to delete: In this example, we use 6 macroblocks, each write a group of 3 blocks needs to be preserved (as can be seen in testing/, this is not possible (if you try it, every block will be marked as filler)), but it leads to a nice example that illustrates the recursive workings of the algorithm. Randomly select blocks to write is easy; just use an RNG. But how to select roles? We must do it in such a way, that after every write the group of 2 blocks (that contain the state of the scubed3 device) are preserved. Suppose we have the random numbers 20312015.. The algorithm works as follows. The the first random number, mark the block as used on de disk as a DATA block. Take the next random number: - if we overwrite an old data block, a filler block or an empty block, just continue - if we overwrite a data block that is not old enough, backtrack to that block, mark it as filler and then revisit all blocks between the old block and the current block (revisiting: because we lost a data block, we have to check that new data blocks do not overwrite data blocks that are too young, if we overwrite a block that is too young, backtrack and mark that block as filler etc....) step | disk | rng output | commentary | 012345 | 20312015.. | --------------------------------------------------------------------- 0 | 0 | 0 | use empty #2 as DATA0 1 | 1 0 | 01 | use empty #0 as DATA1 2 | 1 02 | 012 | use empty #3 as DATA2 3 | 1302 | 0123 | use empty #1 as DATA3 4 | 1342 | 01234 | overwrite DATA0 at #2 with DATA4 5 | 5342 | 012345 | overwrite DATA1 at #0 with DATA5 6 | 5*42 | 012345* | conflict at #1 with DATA3, rewind to 3 6.3 | 1-02 | 012- | mark #1 as FILLER 6.4 | 1-*2 | 012-* | conflict at #2 with DATA0, rewind to 0 6.4.0 | - | - | mark #1 as FILLER 6.4.1 | 0 - | -0 | use empty #0 as DATA0 6.4.2 | 0 -1 | -01 | use empty #3 as DATA1 6.4.3 | 0--1 | -01- | block #1 already marked as FILLER 6.4.4 | 0-21 | -01-2 | overwrite FILLER at #2 with DATA2 6.5 | *-21 | -01-2* | conflict at #0 with DATA0, rewind to 1 6.5.1 | - - | -- | mark #0 as FILLER 6.5.2 | - -0 | --0 | use empty #3 as DATA0 6.5.3 | ---0 | --0- | block #1 already marked as FILLER 6.5.4 | --10 | --0-1 | overwrite FILLER at #2 with DATA1 6.5.5 | 2-10 | --0-12 | overwrite FILLER at #0 with DATA2 6.6 | 2310 | --0-123 | overwrite FILLER at #1 with DATA3 7 | 2310 4 | --0-1234 | use empty #5 as DATA4 ETC | ETC | ETC | ETC step | disk | rng output | | 0123 | 0123012301231 | ------------------------------------------------ 0 | 0 | 0 | use empty #0 as DATA0 1 | 01 | 01 | use empty #1 as DATA1 2 | 012 | 012 | use empty #2 as DATA2 3 | 0123 | 0123 | use empty #3 as DATA3 4 | 4123 | 01234 | overwrite DATA0 at #0 with DATA4 5 | 4523 | 012345 | overwrite DATA1 at #1 with DATA5 6 | 4563 | 0123456 | overwrite DATA2 at #2 with DATA6 7 | 4567 | 01234567 | overwrite DATA3 at #3 with DATA7 8 | 8567 | 012345678 | overwrite DATA4 at #0 with DATA8 9 | 8967 | 0123456789 | overwrite DATA5 at #1 with DATA9 a | 89a7 | 0123456789a | overwrite DATA6 at #2 with DATAa b | 89ab | 0123456789ab | overwrite DATA7 at #3 with DATAb c | 8*ab | 0123456789ab* | conflict at #1 with DATA9, rewind to 9 c.9 | 8-67 | 012345678- | mark #1 as FILLER c.a | 8-* | 012345678-* | conflict at #2 with DATA6, rewind to 6 c.a.6 | 45-3 | 012345- | mark #2 as FILLER c.a.7 | 45-* | 012345-* | conflict at #3 with DATA3, rewind to 3 c.a.7.3 | 012- | 012- | mark #3 as FILLER c.a.7.4 | *12- | 012-* | conflict at #0 with DATA4, rewind to 0 c.a.7.4.0 | - | - | mark #0 as FILLER c.a.7.4.1 | -0 | -0 | use empty #1 as DATA0 c.a.7.4.2 | -01 | -01 | use empty #2 as DATA1 c.a.7.4.3 | -01- | -01- | block #3 already marked as FILLER c.a.7.4.4 | 201- | -01-2 | overwrite FILLER at #0 with DATA2 c.a.7.5 | 2*1- | -01-2* | conflict at #1 with DATA0, rewind to 1 c.a.7.5.1 | -- | -- | mark #1 as FILLER How can we be sure that te numbering of a data block is definitive? Well, just look at maximum backtrack the algorithm produces, if we are far away from the maximum backtrack, we assume everyhting is ok. If we would continue with the above example, all blocks will eventually be labeled as FILLER. [TODO: find criterium for definitive numbering] Suppose we have 4 macro blocks with the following roles: D1 D0 D2 D3 D1 D0 0 1 2 3 4 5 D1 D0 D2 D1 D0 D3 0 1 2 3 4 5 D1 -2 -3 -0 -3 -2 -3 -3 D2 -3 -1 -3 -1 D0 D3 D1 0 1 2 3 4 D1 -2 -3 -0 -3 -2 -3 -3 D2 -3 -1 -3 -1 -0 D3 D1 D0 0 1 2 3 4 -1 -2 -3 -0 -3 -2 -3 -3 D2 -3 -1 -3 -1 -0 -3 D1 D0 D3 0 1 2 3 -1 -2 -3 -0 -3 -2 -3 -3 D2 -3 -1 -3 -1 -0 -3 D1 D0 D3 D2 0 1 2 3 4 -1 -2 -3 -0 -3 -2 -3 -3 D2 -3 -1 -3 -1 -0 -3 D1 -0 D3 D2 D0 0 1 2 3 4 -1 -2 -3 -0 -3 -2 -3 -3 -2 -3 -1 -3 -1 -0 -3 D1 -0 -3 D2 D0 D3 0 1 2 3 NO_BLOCKS=5, SIMULTANEOUS_BLOCKS=2 D4 D3 D0 D2 D1 D3 D0 D4 D2 D0 D1 D3 D2 D1 D0 D2 D4 D1 D3 D0 D2 D4 D3 D0 D2 D1 D3 D0 D4 D2 D0 D1 D3 D2 D1 D0 D2 D4 D1 D3 D0 D2 D1 D4 D3 D0 D2 D1 D3 D0 D4 D2 D0 D1 D3 D2 D1 D0 D2 D4 D1 D3 D2 D1 D0 D4 D3 D0 D2 D1 D3 D0 D4 D2 D0 D1 D3 D2 D1 D0 D2 D4 D3 D1 D0 D2 D4 D3 D0 D2 D1 D3 D0 D4 D2 D0 D1 D3 D2 D1 D0 D2 D4 D3 D0 D2 D1 D4 D3 D0 D2 D1 D3 D0 D4 D2 D0 D1 D3 D2 D1 D0 D2 D4 D3 D0 D2 D1 D2 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2 1 1 2 3 4 5 1 2 3 - 5 2 4 1 2 3 4 5 1 3 2 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2 1 2 3 4 5 1 2 3 - 5 2 4 1 2 3 4 5 1 - 3 - 4 5 2 3 1 2 3 4 5 1 - 3 - 4 - 2 3 5 1 2 3 4 5 1 3 4 5 2 3 1 2 3 4 5 1 3 4 5 2 1 2 3 4 5 1 3 4 5 2 3 1 2 3 4 5 1 3 4 5 2 1 2 3 4 5 1 3 4 5 2 1 1 2 3 4 5 1 2 5 3 4 1234512345 1234512354 12345125432 12345125423 123415234 y 512345 ++ 43234 -1---5--234 15234 ++ 134 152--134 NO_BLOCKS=3 SIMULTANEOUS_BLOCKS=2 012012012 ++ 1 0-2-1-0-21 32103213201 321032132012 32103213021 Maximum backtrack (in situations where not all blocks will be marked as FILLER eventually) is about equal to two times NO_BLOCKS for a run of 300000 blocks. So we wait 5 times NO_BLOCKS to be sure. How to restart the RNG after close/open or resize? Generate a random sequence, and assign roles according to the algorithm. Then permute the numbers so that the new sequence is consistent with the state of the disk. An example: Suppose the disk is at sequence 39: (the numbers here are sequence numbers, every block has a sequence number, in step n of the writing process, the block with sequence number n is written) 39: 0/35~ 1/39- 2/34~ 3/38- 4/37D 5/29~ 6/32~ 7/36D This means that: block 0 OLD data block established at seqno 35 block 1 FILLER block established at seqno 39 block 2 OLD data block established at seqno 34 block 3 FILLER block established at seqno 38 block 4 CURRENT data block established at seqno 37 block 5 OLD data block established at seqno 29 block 6 OLD data block established at seqno 32 block 7 CURRENT data block established at seqno 36 Now we want to sync the RNG to this harddisk state. Assume the RNG generated 464047060734627375331140... our algorithm gives -D-DDD-DDDDDDD-DDD-D-DDD... Interpret RNG output as symbols using this translation 01234567 stuvwxyz Note that this translation does not affect the roles assigned to the blocks by the algorithm. We get: wywswzsyszvwyuzvzxvvttws... This is the reconstructed timeline based on the pattern on disk and our new data. data block and prospective datablock turned to FILLER blocks ages, age is 0, 1 or '~' (meaning OLD), '.' overwritten or ' ' empty 3333333344444444 2345678901234567 ~.~~DD!!-D-DDD-D 6?207431wywswzsy --old--><--new-- 0 ...01~~~ 1 .......0 2 ..01~~~~ 3 ......01 4 .....000 5 ~~~~~~~~ 6 ~~~~~~~~ 7 ....0111 ' ' is an empty block on disk (MAY overwrite) (not shown in the example) '~' is an old data block on disk (MAY overwrite) '.' is a block that is not on disk anymore (ignore) 'D' is a current data block (MUST NOT overwrite until it's obsolete) '!' is an old FILLER block (MUST overwrite Now we must choose the values of stuvwxyz based on the constraints. Since each data block encodes the disk block that obsoletes it, we already know the value of y and s. Furthermore: - w or y must be equal to 3 to obsolete disk block 3 in time - w, y or s must be equal to 1 to obsolete disk block 1 in time