[Twg] T10 End-to-End Data Integrity HLD

Tue Apr 17 07:06:18 UTC 2012

On 2012-04-13, at 4:26 PM, Nathan Rutman wrote:
> On Apr 11, 2012, at 11:42 PM, Andreas Dilger wrote:
>> I think it should be possible to come to a common solution between the T10 design you presented, and the Merkle tree design that was done for HPCS a few years ago.  
> 
> I view this as different solutions to the problem, but I see no reason why they can't coexist.

The difficulty with having two independent, but closely related features that solve the same general problem is that this introduces additional code that needs to be maintained indefinitely for the future.  I think that having separate checksum algorithms is fine, and possibly different transports for the checksums (if that is really needed, more below), but there should definitely only be a single framework for the checksum calculation and in-core storage that varies only by the selection of the algorithm.

>> The only potential area of difficulty would be around the APP tags (if those are being used by the client/application at all) since they cannot be regenerated at the server.
> 
> There is little consensus on what/who gets to use the APP tag; we were going to use it for our own purposes at the MDRAID layer.

That definitely simplifies things, since it means that the APP tags do not need to be sent from the client at all, since they would just be discarded by the server and replaced by the MDRAID layer.

>> One of the attractive features of the Merkle tree design is that it doesn't impose any extra overhead on the bulk RPC transmission, since the checksum sent with the RPC is distilled down to a single number, regardless of whether it is a single checksum on the data as is done today, or a hash of individual sector/page/chunk checksums as is proposed in both of our designs.  Similarly, this avoids the need to store long lists of GRD+REF+APP tags on large pages (which is really the smallest unit of coherency on the client), as would be needed with the straight T10-DIX implementation (128 * 8 bytes for a 64kB PAGE_SIZE with 512-byte sectors).
> 
> From a technical point of view, the tradeoff here is between transmitting a small amount of data (4k per 1MB) and recalculating that data on the servers.  Depending on where/how often we re-verify the checksums, we could remove the recalculation from the server entirely.

That is potentially true, but if the checksums are not verified until you get down to the disk, if there ever is a real checksum error you won't have any idea where the error is being introduced.

I thought the same thing as John - that the appeal of standardized T10 DIF is that it can be verified all along the IO path to isolate the failing components.

> From a philosophical point of view, it's between trusting the software to do the right thing in all cases, versus "my own checksums verified by disk hardware" (and trusting only the disk).  I think the appeal of T10 to many people is exactly that - no matter what happens in the intervening layers, in the end I know my checksums have made it to disk.

I don't see this argument.  Having the OST verify the checksum from the network does not invalidate the additional checking down at the controller and/or disk layer (if there actually are disks that validate DIF, I'm not sure).  If the OST is regenerating the individual DIF sector checksums for verification by the hardware based on a per-RPC checksum (which has itself been verified to match the RPC checksum), then there is still end-to-end checksum coverage.

It would be a strange software bug that generated new DIF checksums that were accepted by the hardware (for possibly corrupt data?) but also generated a valid hashed checksum to match the RPC.  Since the RPC hash is a direct hash of the DIF checksums, the only way I can see this happening (for any reasonable RPC hash function, with a 32-bit or 256-bit RPC hash) is if the 16-bit DIF hash on the corrupt data matched the original value, in which case DIF would have missed the corruption as well...

I can buy the argument that doing the DIF data checksum on the OST consumes CPU cycles, but I had always imagined that it would do this anyway for data/checksum verification as soon as possible instead of waiting until the IO makes it to the controller.  That would ensure that the data the RPC put into the OST cache is valid.

Waiting for the controller to be the first to do the verification precludes ever having writeback caching on the OST.  A writeback cached RPC would be completed before the data was verified by the controller, and it is not possible (today, at least) for the OST to force the client to resend just that RPC/data for replay.  Any checksum error caused by network errors would require the OST to reset and start recovery for all RPCs in order to get the client to resend the failed RPC.

> Mainly for that latter reason we choose to send the CRCs instead of a function of them.  But as I said, our goal is to introduce enough flexibility that multiple data integrity schemes can be used.
> 
>> There is enough flexibility in the current Lustre RPC checksum wire format that both the T10 GRD+REF and the ZFS Fletcher4 checksum could be chosen as leaf checksums, and a tree hash can be used for both to get a single RPC hash, giving 2 or 3 new Lustre wire checksum formats.  Since the server side needs to recompute the checksums anyway, it can regenerated GRD tag from the data, get the REF (offset) values from the RPC niobufs, and then rehash it to compare to the RPC checksum.
>> 
>> Using a Merkle tree for the RPC checksum also avoids the potential problems as described in section 8.5, since the rather large amount of GRD+REF+APP tags do not actually need to be sent with the RPC, only the hash of them (currently a 32-bit value, but it could be expanded to be a 256-bit value if needed/desired).
>> 
>> The Merkle tree also has the added benefit that the client does not need to know the sector sizes of the OSTs and handle them separately.  Otherwise, there is either a restriction that the OSTs all have to have drives with the same sector sizes (to avoid the need for the client to compute GRD tags differently for each page in a striped file), or the llite layer will need to poke into the OSC for every page to figure out the sector size.
> 
> This is a good point; I think a reasonable solution would require a common sector size within an OST.

I hope that it would always to be the case that the disks in a single OST have the same sector size, but my concern was more about different sector sizes between OSTs.  In that case, because the data checksum would be dependent on the sector size on each OST, the client per-page checksums would need to be computed based on the OST on which each page was to be written, which adds complexity into the IO path.

In some sense this is no worse than having different checksum algorithms on different OSTs, but that would largely be an administrator choice that would otherwise default to using the same checksum algorithm for all OSTs.  In contrast, different sector sizes on different OSTs is nearly inevitable over the next several years if new storage is added to an existing system, as 4kB sector drives arrive on the market and users may have little choice but to buy them.

In summary, I'm not wholly against the idea of shipping the extra T10 GEN+REF data with the RPCs as you propose, so long as there is a single framework for rest of the checksum code for both the pages and the RPC is shared with existing checksum algorithms.

Cheers, Andreas

>> Since the client would always resend the whole RPC on checksum failure anyway, having a single checksum that is validated at both ends is enough for the Lustre part of the transfer.  If it compares correctly, then the GRD+REF tags must match the originals, and can be used to submit to the underlying DIF hardware (if available) and/or recomputed to match the actual sector size if it is different between OSTs.
>> 
>> The one issue is the APP tags.  They are arbitrary 16-bit values, but it seems for the purpose of this design that the client and MDRAID layer will be generating the APP tags internally (versions), so there is currently no need (or ability) to store userspace APP tags all the way to disk?  That would also avoid the need to pass them over the wire, since there is no chance of a torn/lost write for the RPC part of the data path.
>> 
>> Some other comments on the design:
>> 6.3: the mmap issue was fixed for Lustre 2.2 by Jinshan using the
>>   PG_writeback/page_mkwrite() support in newer kernels.  It should
>>   no longer be possible for pages to change after calculating the
>>   checksum but before the RPC is sent.  See LU-884 for details.
> Excellent!
> 
>> 8.5.2: why not compute the CRC in the correct endianness in the first
>>   place?  The kernel already has e.g. crc32_le() and crc32_be()
>>   routines, so it may also have the needed routines for T10-CRC.
>>   It also isn't clear whether CRC-then-swab is the same as doing
>>   the CRC in the other endianness in the first place?  Typically,
>>   RPCs are in "receiver makes right" format, which reduces overhead
>>   in the common case that both ends are the same.  However, if
>>   the underlying DIF API requires the CRC to always be big endian,
>>   it makes sense to swab it on the client already.
> Our conclusion as well - big endian everywhere.
> 
>> 
>> Cheers, Andreas
>> --
>> Andreas Dilger                       Whamcloud, Inc.
>> Principal Lustre Engineer            http://www.whamcloud.com/
>> 
>> 
>> 
>> 

Cheers, Andreas
--
Andreas Dilger                       Whamcloud, Inc.
Principal Lustre Engineer            http://www.whamcloud.com/