Igor, Javier, both of you are right. Here is what I came up with after some more thinking. We can avoid the races in 2. and 3. with the following two invariants: I1: If we have a GC line with seq_id X, only garbage collect from lines older than X (this addresses 2.) I2: Guarantee that the open GC line always has a smaller seq_id than all open user lines (this addresses 3) We can enforce I2 by adding a minor seq_id. The major sequence id is only incremented when allocating a user line. Whenever a GC line is allocated we read the current major seq_id (open user line) and increment the minor seq_id. This allows us to order all GC lines before the open user line during recovery. Problem with this approach: Consider the following example: There exist user lines U0, U1, U2 (where 0,1,2 are seq_ids) and a non-empty GC5 line (with seq_id 5). If we now do only sequential writes all user lines will be overwritten without GC being required. As a result, data will now reside on U6, U7, U8. If we now need to GC we cannot because of I1. Solution: We cannot fast-forward the GC line's seq_id because it contains old data, so pad the GC line with zeros, close it and open a new GC9 line. Generality: This approach extends to schemes that use e.g. hot, warm, cold open lines (adding a minor_minor_seq_id) Heiner On Thu, May 2, 2019 at 2:08 AM Igor Konopko <igor.j.konopko@xxxxxxxxx> wrote: > > > > On 01.05.2019 22:20, Heiner Litz wrote: > > Javier, Igor, > > you are correct. The problem exists if we have a power loss and we > > have an open gc and an open user line and both contain the same LBA. > > In that case, I think we need to care about the 4 scenarios: > > > > 1. user_seq_id > gc_seq_id and user_write after gc_write: No issue > > 2. user_seq_id > gc_seq_id and gc_write > user_write: Cannot happen, > > open user lines are not gc'ed > > Maybe it would be just a theoretical scenario, but I'm not seeing any > reason why this cannot happen in pblk implementation: > Let assume that user line X+1 is opened when GC line X is already open > and the user line is closed when GC line X is still in use. Then GC > quickly choose user line X+1 as a GC victim and we are hitting 2nd case. > > > 3. gc_seq_id > user_seq_id and user_write after gc_write: RACE > > 4. gc_seq_id > user_seq_id and gc_write after user_write: No issue > > > > To address 3.) we can do the following: > > Whenever a gc line is opened, determine all open user lines and store > > them in a field of pblk_line. When choosing a victim for GC, ignore > > those lines. > > Your solution sounds right, but I would extend this based on my previous > comment to 2nd case by sth like: during opening new user data also add > this line ID to this "blacklist" for the GC selection. > > Igor > > > > > Let me know if that sounds good and I will send a v2 > > Heiner > > > > On Tue, Apr 30, 2019 at 11:19 PM Javier González <javier@xxxxxxxxxxx> wrote: > >> > >>> On 26 Apr 2019, at 18.23, Heiner Litz <hlitz@xxxxxxxx> wrote: > >>> > >>> Nice catch Igor, I hadn't thought of that. > >>> > >>> Nevertheless, here is what I think: In the absence of a flush we don't > >>> need to enforce ordering so we don't care about recovering the older > >>> gc'ed write. If we completed a flush after the user write, we should > >>> have already invalidated the gc mapping and hence will not recover it. > >>> Let me know if I am missing something. > >> > >> I think that this problem is orthogonal to a flush on the user path. For example > >> > >> - Write to LBA0 + completion to host > >> - […] > >> - GC LBA0 > >> - Write to LBA0 + completion to host > >> - fsync() + completion > >> - Power Failure > >> > >> When we power up and do recovery in the current implementation, you > >> might get the old LBA0 mapped correctly in the L2P table. > >> > >> If we enforce ID ordering for GC lines this problem goes away as we can > >> continue ordering lines based on ID and then recovering sequentially. > >> > >> Thoughts? > >> > >> Thanks, > >> Javier > >> > >>> > >>> On Fri, Apr 26, 2019 at 6:46 AM Igor Konopko <igor.j.konopko@xxxxxxxxx> wrote: > >>>> On 26.04.2019 12:04, Javier González wrote: > >>>>>> On 26 Apr 2019, at 11.11, Igor Konopko <igor.j.konopko@xxxxxxxxx> wrote: > >>>>>> > >>>>>> On 25.04.2019 07:21, Heiner Litz wrote: > >>>>>>> Introduce the capability to manage multiple open lines. Maintain one line > >>>>>>> for user writes (hot) and a second line for gc writes (cold). As user and > >>>>>>> gc writes still utilize a shared ring buffer, in rare cases a multi-sector > >>>>>>> write will contain both gc and user data. This is acceptable, as on a > >>>>>>> tested SSD with minimum write size of 64KB, less than 1% of all writes > >>>>>>> contain both hot and cold sectors. > >>>>>> > >>>>>> Hi Heiner > >>>>>> > >>>>>> Generally I really like this changes, I was thinking about sth similar since a while, so it is very good to see that patch. > >>>>>> > >>>>>> I have a one question related to this patch, since it is not very clear for me - how you ensure the data integrity in following scenarios: > >>>>>> -we have open line X for user data and line Y for GC > >>>>>> -GC writes LBA=N to line Y > >>>>>> -user writes LBA=N to line X > >>>>>> -we have power failure when both line X and Y were not written completely > >>>>>> -during pblk creation we are executing OOB metadata recovery > >>>>>> And here is the question, how we distinguish whether LBA=N from line Y or LBA=N from line X is the valid one? > >>>>>> Line X and Y might have seq_id either descending or ascending - this would create two possible scenarios too. > >>>>>> > >>>>>> Thanks > >>>>>> Igor > >>>>> > >>>>> You are right, I think this is possible in the current implementation. > >>>>> > >>>>> We need an extra constrain so that we only GC lines above the GC line > >>>>> ID. This way, when we order lines on recovery, we can guarantee > >>>>> consistency. This means potentially that we would need several open > >>>>> lines for GC to avoid padding in case this constrain forces to choose a > >>>>> line with an ID higher than the GC line ID. > >>>>> > >>>>> What do you think? > >>>> > >>>> I'm not sure yet about your approach, I need to think and analyze this a > >>>> little more. > >>>> > >>>> I also believe that probably we need to ensure that current user data > >>>> line seq_id is always above the current GC line seq_id or sth like that. > >>>> We cannot also then GC any data from the lines which are still open, but > >>>> I believe that this is a case even right now. > >>>> > >>>>> Thanks, > >>>>> Javier
