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

Wed Apr 18 21:55:27 UTC 2012

On 2012-04-17, at 11:02 AM, Nathan Rutman wrote:
> On Apr 17, 2012, at 12:06 AM, Andreas Dilger wrote:
>> 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.
> 
> As far as Lustre is concerned, I view the T10 method as more of a out-of-band data transfer mechanism.  When you say single framework, you imply that the checksum is performed at the same point in the code path, but I think that is fundamentally different between Merkle tree/ZFS (in core) and T10 (in hardware).

Sure, but the Merkle tree ends up being just a different checksum algorithm supported by the OST, that doesn't need any specific knowledge of the backing filesystem (blocksize, sector size, etc), and it doesn't impose any significant overhead on the protocol.  The only potential change outside of adding the algorithm would be to send a full 256-bit checksum instead of only a 32-bit one today.

Exposing a low-level detail like the disk sector size to the Lustre client (or application, should it get that far) to compute the GRD tag is a terrible layering violation, IMHO.  This flies in the face of code abstraction and proper layering/isolation of different components in the storage stack, and is really contrary to the principles of Lustre that try to isolate the clients from internal details of the storage.  It doesn't make sense that a Lustre client doesn't need to know the block size or even the type of filesystem on the OST, yet it needs to know the sector size of the disks living some layers below each OST?

Perhaps if there was a simple transformation for merging eight 512-byte GRDs into a single 4kB GRD, then at least the Lustre client could always compute and send the GRD tags for the smallest sector size for any OST it is connected to (512 bytes, if there are mixed sector sizes, or 4kB if all OSTs have 4kB AF sector drives), and then the OST could efficiently merge them if it has a larger sector size locally.

My math is too rusty to work this out, and I suspect it would be hard to do for CRC16, but I think it is possible to do with a matrix multiply for the IP16 checksum also used by the Linux DIF/DIX layer?

>>> 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.
> 
> That's a question about debugging really.  Just as today many sites run without checksums at all due to server CPU loading, it makes sense to me to make intermediate verifications optional.

Based on the data in LU-1201, I think with Nehalem CPUs and multi-threaded ptlrpcd the checksum overhead will become a non-issue, and people will happily leave it enabled all the time.  The unfortunate thing is that the CRC16 used by T10-DIF has such poor software performance that I agree there is no option but to leave the verification to the hardware.

See https://ext4.wiki.kernel.org/articles/e/x/t/Ext4_Metadata_Checksums_4d24.html for a useful recent comparison of checksum algorithm performance.  It would be interesting to see if there was some way to improve the kernel crc16-t10 performance through loop unrolling or table lookups, given that significant performance gains were seen for crc32c-kern to the updated crc32c-by8 implementation.

>> 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.
> 
> T10-DIX is not about fault isolation; it's about keeping protection information with the data for as long as possible.
> From the http://snia.org/sites/default/files/Data_Integrity_Architectural_Model_v0.26.pdf Section 5: 
> In the T10 Protection Information model both Data Integrity Metadata and actual data move through any communication path as a single unit. 
> One can consider that two logical paths exist, one for data and the other for Data Integrity Metadata. The data path is called the Data Channel and the Data Integrity Metadata path is called the Protection Information Channel.
> 
> 5.1 Movement of Protection Information
> An important purpose of this specification is to facilitate extending the Protection Envelope from the host-storage interface to the application endpoint. Without extending the protection envelope, the Protection Information Channel terminates at the host storage interface and only the Data Channel continues to the application. Consequently, a key element of this architecture describes how the Protection Information Channel may be extended to the application endpoint.
> 
>> 
>>> 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).
> 
> There are.
> 
>>  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 give you a trivial example: bad code in the Merkle tree implementation always generates a checksum of 0xDEADBEEF.  Client computes it, server computes it, hey they match, and individual sector recomputed CRC's can still be correct, but the data do not match.

Can you give me a non-trivial example? :-)  This same argument (though admittedly a strange bug :-) could be used for the non-Merkle checksums, and we are no further ahead.  Some might also argue that at petascale or exascale data sizes/rates, a 16-bit checksum is going to let so many data corruptions go undetected (1 in 65k random corruptions) that it doesn't really solve the problem either.

To clarify, I'm not dead set on using Merkle tree in place of large RPC requests needed to send the T10 GRD and REF tags for every sector.  I would be OK to land such a capability as long as it would only be a protocol overhead for systems using T10-DIF, and would not exist for anyone using existing simple checksums or a Merkle checksum.  My suggestion was an attempt to potentially avoid adding 4kB or 16kB overhead to every bulk RPC sent to T10-enabled servers, or alternately sending inefficient 1020kB or 1008kB writes to a 1024kB RAID stripe.

I would guess that increasing the RPC request size or sending odd-sized writes has the potential to introduce far more performance overhead than an extra checksum calculation, since it means read-modify-write cycles for the RAID layer, or sending two bulk RPCs for each 1MB of data, but only time will tell.

>> 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.
> 
> I agree - if you're going to store the data in a writeback cache with the assumption that all other buffered copies are unavailable, it becomes a requirement to verify the data integrity when storing it in the cache.  

As an academic question/comment, since I doubt it is possible to change the standards-entrenched DIF checksum algorithm, I don't think that Merkle trees have to be incompatible with T10-DIF.  If there could be a hierarchical checksum algorithm in use for the GRD tag instead of straight CRC16, it would avoid real-world issues that arise from having to compute the CRC differently for 8x 512-byte sectors vs. a single 4kbyte sector.

For example, if the GRD tag for a 4kB sector was the CRC16 of eight 512-byte CRC16s, then it would be trivial to compute and verify the GRD tag at an interface boundary that changed from 4kB/16kB/64kB sector_size or PAGE_SIZE to 512B sectors (or vice versa) without doubling the checksum overhead.

Cheers, Andreas

>>> 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
> 

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