Disseration 101: spanning data across multiple cookies

Cookies have are spec'd to hold a max of 4KB. Thats a lot of data. 4096 ascii characters to be exact. However this is 2009, and my ideas of 'a lot' are laughable. Well since we know that one cookie holds x, how about 2x?

Well thats great, but how do i split data across two structures, and ensure that it remains consistent. Well clearly this problem isn't new, it's been solved in TCP, RAID, and many other situations.

TCP's approach is to assign each segment a sequence number, it divides the load based on the window size and assigns it a number.

But how would that look?
(key:value)
foo=1007; hello
bar=1007; world

the issue with the above is that i have to access random keys to get at the data, so something like the below would be better ...

x1007=foo: hello
x1008=foo; world.

in the above the name of the cookie is the sequence number, the first value is the name of the user key, and following the semicolon, the value. Still a little rough around the edges, but what isn't?

Another alternative, is to cram as much data into each cookie. This increases the amount of entries that could be assign