[RC5] Block sizes (nkeys)

Greg Wooledge wooledge at kellnet.com
Sat Apr 4 18:45:43 EST 1998


Robert Morrison (robert at ais.net) wrote:

> Here's a list of the last 5 blocks completed by my client:
> 
> [04/04/98 14:12:02 GMT] Completed block 66DD7A92:A0000000 (1073741824 keys)
> [04/04/98 14:43:32 GMT] Completed block 66DD7A91:B0000000 (536870912 keys)
> [04/04/98 15:15:05 GMT] Completed block 66DD7A75:A0000000 (536870912 keys)
> [04/04/98 16:02:24 GMT] Completed block 66DD7A6C:10000000 (805306368 keys)
> [04/04/98 16:18:10 GMT] Completed block 66DD7A6B:B0000000 (268435456 keys)
> 
> This shows 4 different block sizes.

Yes, that's quite common.

> My "preferred block size" is set to 30.

You're getting 2^28, 2^29, 3*2^28 and 2^30 blocks -- 4 different sizes,
as you observed.  Your preferred block size is really the *maximum*
block size you will accept.  Depending on the sizes of blocks taken by
other clients right before yours, you might get a smaller block than
you asked for.

If having a precisely known amount of work in your in-buffer after a
(successful) update is important, you should set your block size to
2^28 -- that's the only way you'll be sure how much you've got.

The key proxies try to keep their blocks "aligned", much like fields
in a struct in C.  They seem to try to work in groups of 8 (2^31/2^28).
Consider this crude diagram:

	|       |       |
	|   |   |   |   |
	|.|.|.|.|.|.|.|.|
	01234567891111111
	          0123456

This shows 17 2^28 blocks in a key proxy's buffer.  If someone grabs a
2^29 block (my preferred size on my 386 and 486 systems), there will be 14
2^28 blocks left:

	        |       |
	    |   |   |   |
	  |.|.|.|.|.|.|.|
	  234567891111111
	          0123456

Now, suppose that someone else tries to grab a 2^30 block.  The key
proxy won't be able to do it because that would violate the alignment
constraints.  It will give you a 2^29 block instead.  If you immediately
ask for another 2^30 block, now that the key proxy is aligned on a
position divisible by 4, it will be able to do so, and you'll get your
2^30 block, leaving the key proxy in this state.

	        |       |
	        |   |   |
	        |.|.|.|.|
	        891111111
	          0123456

A similar explanation demonstrates how you can get the other two block
sizes you're seeing as well.  If the key proxy is aligned on a 2^30
bounday and someone grabs a 2^28 block, your request for a 2^30 block
will be met with a 3*2^28 block, bringing the key proxy back to a 2^30
boundary.  If the key proxy is on a 2^30 boundary and someone grabs 3 2^28
blocks, and then you ask for a 2^30 block, you'll only get a 2^28 block.

-- 
"Daddy, why do those people have to    |   Greg Wooledge
  use Microsoft Windows?"              |   wooledge at kellnet.com
"Don't stare, son; it's not polite."   |   http://www.kellnet.com/wooledge/
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list