← Back to branch summary

~lifeless/ubuntu/lucid/bzr/2.1.2-sru

« back to all changes in this revision

Viewing changes to doc/developers/improved_chk_index.txt

  • Committer: Bazaar Package Importer
  • Author(s): Jelmer Vernooij
  • Date: 2010-02-17 17:47:40 UTC
  • mfrom: (1.5.2 upstream)
  • mto: This revision was merged to the branch mainline in revision 13.
  • Revision ID: james.westby@ubuntu.com-20100217174740-p1x5dd5uwvxtg9y6
Tags: upstream-2.1.0
Import upstream version 2.1.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/developers/improved_chk_index.txt
16
16
per key, which is the same size as the binary representation of the hash. This
17
17
means we could write an index format that gets approximately the same on-disk
18
18
size, without having the overhead of ``zlib.decompress``. Some thought would
19
 
still need to be put into how to efficiently access these records from remote. 
 
19
still need to be put into how to efficiently access these records from remote.
20
20
 
21
21
 
22
22
Required information
99
99
   offset + endpoint as a header in the group itself.)
100
100
 
101
101
5. So for 1M keys, an ideal chk+group index would be:
102
 
    
 
102
 
103
103
    a. 6-byte hash prefix
104
104
 
105
105
    b. 2-byte group number
149
149
      information to read the entire group block. For local ops, you could
150
150
      only read enough to get the header, and then only read enough to
151
151
      decompress just the content you want to get at.
152
 
      
 
152
 
153
153
      Using an offset, you also don't need to decode the entire group header.
154
154
      If we assume that things are stored in fixed-size records, you can jump
155
155
      to exactly the entry that you care about, and read its 8-byte
156
156
      (start,length in uncompressed) info.  If we wanted more redundancy we
157
157
      could store the 20-byte hash, but the content can verify itself.
158
 
      
 
158
 
159
159
   f. If the size of these mini headers becomes critical (8 bytes per record
160
160
      is 8% overhead for 100 byte records), we could also compress this mini
161
161
      header. Changing the number of bytes per entry is unlikely to be
172
172
      would also have the advantage that fixed width would be highly
173
173
      compressible itself. (Most nodes are going to have a length that fits
174
174
      1-2 bytes.)
175
 
      
 
175
 
176
176
      An alternative form would be to use the base-128 encoding.  (If the MSB
177
177
      is set, then the next byte needs to be added to the current value
178
178
      shifted by 7*n bits.) This encodes 4GiB in 5 bytes, but stores 127B in 1
470
470
group pointer, we can refer to 16.7M groups. It does add complexity, but it is
471
471
likely necessary to allow for arbitrary cases.
472
472
 
473
 
.. 
 
473
..
474
474
  vim: ft=rst tw=78 ai