> -----Original Message----- > From: Sage Weil [mailto:sage@xxxxxxxxxxxx] > Sent: Thursday, June 16, 2016 9:47 AM > To: Allen Samuels <Allen.Samuels@xxxxxxxxxxx> > Cc: Mark Nelson <mnelson@xxxxxxxxxx>; Evgeniy Firsov > <Evgeniy.Firsov@xxxxxxxxxxx>; Jianjian Huo <jianjian.huo@xxxxxxxxxxx>; > Somnath Roy <Somnath.Roy@xxxxxxxxxxx>; Igor Fedotov > <ifedotov@xxxxxxxxxxxx>; Manavalan Krishnan > <Manavalan.Krishnan@xxxxxxxxxxx>; Varada Kari > <Varada.Kari@xxxxxxxxxxx>; Ramesh Chander > <Ramesh.Chander@xxxxxxxxxxx>; ceph-devel@xxxxxxxxxxxxxxx > Subject: Re: bluestore onode encoding efficiency > > Based on some of Allen's comments I've updated my branch with (so far) > three different encoders: > > 1) varint - general purpose small integers (lops off high and low zero > bits) > > first byte: > low 2 bits = how many low nibbles of zeros > 5 bits = data > 1 high bit = another byte follows > subsequent bytes: > 7 bits = data > 1 high bit = another byte follows > > 2) delta varint > > first byte: > 1 low bit = sign (0 = positive, 1 = negative) > low 2 bits = how many low nibbles of zeros > 4 bits = data > 1 high bit = another byte follows > subsequent bytes: > 7 bits = data > 1 high bit = another byte follows > > 3) raw lba: > > first 3 bytes: > low 2 bits = how many low bits of zeros > 00 = none > 01 = 12 (4k alignment) > 10 = 16 (64k alignment) > 11 = 20 (256k alignment) > 21 bits = data > 1 high bit = another byte follows > subsequent bytes: > 7 bits = data > 1 high bit = another byte follows Let's do some math here :) Let's say I want to optimize for 4, 8, 16 and 32 TB devices going forward. That's 2^42, 43, 44 and 45 respectively. If assume a 4K blocksize/alignment, then we need 30, 31, 32 and 33 significant bits after downshifting for encoding. That means for 30 bits I'll have 21 + 7 + 2 encoded bits which requires 5 bytes for a 4TB device. However, 1/2 of the addresses only need 29 bits (and 1/4 need 28, etc.) So the approximate blended size is about 4.75 Bytes for a 4TB (1/4 of the addresses can save a byte) And about 4.875 Bytes for 8TB (1/8 of the addresses can save a byte). We won't need another byte until we operate on 128TB devices. If we switch to 64K alignment (reasonable for many HDD use-cases), then the #'s change to be 26, 27, 28 and 29 respectively, That's 21 + 5 for 4TB which gets encoded in 4 bytes. 8 and 16TB also take 4Bytes, you need 32TB before you need 5Bytes. If we change the encoding above so that the first chunk is 4 bytes (easier to deal with :)) and leave everything alone, then we have 39 bits of mantissa Now for a 4KB align / 4TB device you only need 4.5 Bytes which is a savings of .25 Bytes, which will could easily be significant when you have up to 1K phys addrs / oNode. I could argue for a skew on the format encoding, i.e., 0x for 4K, 110 for 16K, 111 for byte align, ,etc. and gain another bit picking up a further .5 bytes on a 4TB device. The 16-bit alignment case isn't materially affected by this. In conclusion. I think -- at a minimum -- you should switch to a first 4 bytes (rather than a first 3 bytes) for this use case. It doesn't seem to have any negative and there are significant positives. A weaker case would be to switch the two bit encoding to something that favored 4K (the likely most prevalent) alignment, picking up another bit before a multi-byte encoding is needed. > > 4) lba delta (distance between two lba's, e.g., when encoding a list of > extents) > > first byte: > 1 low bit = sign (0 = positive, 1 = negative) > 2 bits = how many low bits of zeros > 00 = none > 01 = 12 (4k alignment) > 10 = 16 (64k alignment) > 11 = 20 (256k alignment) > 4 bits = data > 1 bit = another byte follows > subsequent bytes: > 7 bits = data > 1 bit = another byte follows > > Notably on this one we have 4 bits of data *and* when we roll over to > the next value you'll get 4 trailing 0's and we ask for one > more nibble of trailing 0's... still in one encoded byte. > > > I think this'll be a decent set of building blocks to encoding the existing > structures efficiently (and still in a generic way) before getting specific with > common patterns. > > https://github.com/ceph/ceph/pull/9728/files > > sage > > > On Wed, 15 Jun 2016, Sage Weil wrote: > > > > If we have those, I'm not sure #1 will be worth it--the zeroed offset > > fields will encode with one byte. > > > > > (3) re-jiggering of blob/extents when possible. Much of the > > > two-level blob/extent map exists to support compression. When you're > > > not compressed you can collapse this into a single blob and avoid > > > the encoding overhead for it. > > > > Hmm, good idea. As long as the csum parameters match we can do this. > > The existing function > > > > int bluestore_onode_t::compress_extent_map() > > > > currently just combines consecutive lextent's that point to contiguous > > regions in the same blob. We could extend this to combine blobs that > > are combinable. > > > > > There are other potential optimizations too that are artifacts of > > > the current code. For example, we support different checksum > > > algorithms/values on a per-blob basis. Clearly moving this to a > > > per-oNode basis is acceptable and would simplify and shrink the > > > encoding even more. > > > > The latest csum branch > > > > https://github.com/ceph/ceph/pull/9526 > > > > varies csum_order on a per-blob basis (for example, larger csum chunks > > for compressed blobs and small csum chunks for uncompressed blobs with > > 4k overwrites). The alg is probably consistent across the onode, but > > the will uglify the code a bit to pass it into the blob_t csum > > methods. I'd prefer to hold off on this. With the varint encoding > > above it'll only be one byte per blob at least. > > > > sage > > > > -- > > To unsubscribe from this list: send the line "unsubscribe ceph-devel" > > in the body of a message to majordomo@xxxxxxxxxxxxxxx More > majordomo > > info at http://vger.kernel.org/majordomo-info.html > > > > -- To unsubscribe from this list: send the line "unsubscribe ceph-devel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
