Rev 3770: A bit of doc updates, start putting in tests for current behavior. in http://bzr.arbash-meinel.com/branches/bzr/1.8-dev/btree_buffer
John Arbash Meinel
john at arbash-meinel.com
Tue Oct 14 20:02:46 BST 2008
At http://bzr.arbash-meinel.com/branches/bzr/1.8-dev/btree_buffer
------------------------------------------------------------
revno: 3770
revision-id: john at arbash-meinel.com-20081014190226-xns3yk2nti9p96zd
parent: john at arbash-meinel.com-20081009205450-z4k6rnvj5j1tqcmu
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: btree_buffer
timestamp: Tue 2008-10-14 14:02:26 -0500
message:
A bit of doc updates, start putting in tests for current behavior.
-------------- next part --------------
=== modified file 'bzrlib/btree_index.py'
--- a/bzrlib/btree_index.py 2008-10-09 20:54:50 +0000
+++ b/bzrlib/btree_index.py 2008-10-14 19:02:26 +0000
@@ -607,7 +607,7 @@
self._name = name
self._size = size
self._file = None
- self._page_size = transport.recommended_page_size()
+ self._recommended_pages = self._compute_recommended_pages()
self._root_node = None
# Default max size is 100,000 leave values
self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
@@ -666,6 +666,35 @@
found[node_pos] = node
return found
+ def _compute_recommended_pages(self):
+ """Given the transport's recommended_page_size, determine num pages."""
+ recommended_read = self._transport.recommended_page_size()
+ recommended_pages = int(math.ceil(recommended_read /
+ float(_PAGE_SIZE)))
+ return recommended_pages
+
+ def _compute_num_pages(self):
+ """Determine the offset to the last page in this index."""
+ if self._size is None:
+ raise AssertionError('_compute_num_pages should not be called'
+ ' when self._size is None')
+ if self._root_node is not None:
+ # This is the number of pages as defined by the header
+ return self._row_offsets[-1]
+ # This is the number of pages as defined by the size of the index. They
+ # should be indentical.
+ num_pages = int(math.ceil(self._size / float(_PAGE_SIZE)))
+ return num_pages
+
+ def _get_cached_nodes(self):
+ """Determine what nodes we already have cached."""
+ # XXX: Update the LRUCache interface to have a .keys() attribute
+ cached_nodes = set(self._internal_node_cache._cache.keys())
+ cached_nodes.update(self._leaf_node_cache._cache.keys())
+ if self._root_node is not None:
+ cached_nodes.add(0)
+ return cached_nodes
+
def _expand_nodes(self, node_indexes):
"""Find extra nodes to download.
@@ -675,94 +704,85 @@
out what other pages we might want to read.
:param node_indexes: The nodes that have been requested to read.
- # :param recommended_size: The size of download we want, this assumes
- # that readv() is accomplished in a single round trip (which is true
- # for http and bzr+ssh, and sftp uses async to get close
- # performance.)
- # :param max_page: The last possible page to read, possibly max_size is
- # better?
:return: A new list of nodes to download
"""
- trace.note('request: %s\tnodes: %s', self._name[-14:], node_indexes)
- # return node_indexes
+ if 'index' in debug.debug_flags:
+ trace.mutter('expanding: %s\tnodes: %s', self._name, node_indexes)
- # TODO: This could be cached
- recommended_read = self._transport.recommended_page_size()
- recommended_pages = int(math.ceil(recommended_read /
- float(_PAGE_SIZE)))
- # Disable the algorithm
- # recommended_pages = 1
- if len(node_indexes) >= recommended_pages:
+ if len(node_indexes) >= self._recommended_pages:
# Don't add more, we are already requesting more than enough
+ if 'index' in debug.debug_flags:
+ trace.mutter(' not expanding large request (%s >= %s)',
+ len(node_indexes), self._recommended_pages)
return node_indexes
if self._size is None:
# Don't try anything, because we don't know where the file ends
+ if 'index' in debug.debug_flags:
+ trace.mutter(' not expanding without knowing index size')
return node_indexes
+ # TODO: Should this be cached instead?
+ num_pages = self._compute_num_pages()
# The idea here is to get nodes "next to" the ones we are already
# getting.
- max_page = int(math.ceil(self._size / float(_PAGE_SIZE)))
- # XXX: Update the LRUCache interface to have a .keys() attribute
- cached_nodes = set(self._internal_node_cache._cache.keys())
- cached_nodes.update(self._leaf_node_cache._cache.keys())
- if self._root_node is not None:
- cached_nodes.add(0)
+ cached_nodes = self._get_cached_nodes()
- # if len(cached_nodes) < 2: # We haven't read enough to justify expansion
+ # if len(cached_nodes) < 2:
+ # # We haven't read enough to justify expansion
# return node_indexes
# If reading recommended_pages would read the rest of the index, just
# do so.
- if max_page - len(cached_nodes) <= recommended_pages:
- # Just read the whole thing
- # NOTE: this breaks a little bit with the distinction between index
- # nodes and leaf nodes (as they are cached separately). It is
- # still worthwhile to read it all, but we need to figure out what
- # cache we should really put things in when we are done.
- # However, we may not have read the index header yet to know where
- # the internal nodes break from where the leaf nodes. We are sure
- # to know *after* we've done the read.
- # This also does the wrong thing if there are bloom pages.
-
- # Further, this gives the wrong results because we have 2 caches to
- # worry about...
+ if num_pages - len(cached_nodes) <= self._recommended_pages:
+ # Read whatever is left
if cached_nodes:
- return [x for x in xrange(max_page) if x not in cached_nodes]
- return range(max_page)
+ expanded = [x for x in xrange(num_pages)
+ if x not in cached_nodes]
+ else:
+ expanded = range(num_pages)
+ if 'index' in debug.debug_flags:
+ trace.mutter(' reading all unread pages: %s', expanded)
+ return expanded
- needed_nodes = recommended_pages - len(node_indexes)
+ needed_nodes = self._recommended_pages - len(node_indexes)
final_nodes = set(node_indexes)
- if node_indexes == [0]:
- # Special case when we are reading the root node, just read the
- # first N pages along with the root node
+ if self._root_node is None:
+ # ATM on the first read of the root node of a large index, we don't
+ # bother pre-reading any other pages. This is because the
+ # likelyhood of actually reading interesting pages is very low.
+ # See doc/developers/btree_index_prefetch.txt for a discussion, and
+ # a possible implementation when we are guessing that the second
+ # layer index is small
final_nodes = node_indexes
- # for index in xrange(1, max_page):
- # if index not in final_nodes and index not in cached_nodes:
- # final_nodes.add(index)
- # if len(final_nodes) >= recommended_pages:
- # break
else:
+ # Expand requests to neighbors until we have at least
+ # recommended_pages to request. We only want to expand requests
+ # within a given layer.
new_tips = set(final_nodes)
- while len(final_nodes) < recommended_pages and new_tips:
+ while len(final_nodes) < self._recommended_pages and new_tips:
next_tips = set()
- for pos in sorted(new_tips):
+ for pos in new_tips:
if pos > 0:
previous = pos - 1
if (previous not in cached_nodes
and previous not in final_nodes):
- final_nodes.add(previous)
next_tips.add(previous)
after = pos + 1
- if after < max_page:
+ if after < num_pages:
if (after not in cached_nodes
and after not in final_nodes):
- final_nodes.add(after)
- next_tips.add(previous)
+ next_tips.add(after)
+ # This would keep us from going bigger than
+ # recommended_pages by only expanding the first nodes.
+ # However, if we are making a 'wide' request, it is
+ # reasonable to expand all points equally.
# if len(final_nodes) > recommended_pages:
# break
+ final_nodes.update(next_tips)
new_tips = next_tips
final_nodes = sorted(final_nodes)
- trace.note('\t\t%s', final_nodes)
+ if 'index' in debug.debug_flags:
+ trace.mutter('expanded: %s', final_nodes)
return final_nodes
def _get_nodes(self, cache, node_indexes):
@@ -1116,6 +1136,16 @@
self._get_root_node()
return self._key_count
+ def _compute_row_offsets(self):
+ """Fill out the _row_offsets attribute based on _row_lengths."""
+ offsets = []
+ row_offset = 0
+ for row in self._row_lengths:
+ offsets.append(row_offset)
+ row_offset += row
+ offsets.append(row_offset)
+ self._row_offsets = offsets
+
def _parse_header_from_bytes(self, bytes):
"""Parse the header from a region of bytes.
@@ -1157,13 +1187,7 @@
if len(length)])
except ValueError:
raise errors.BadIndexOptions(self)
- offsets = []
- row_offset = 0
- for row in self._row_lengths:
- offsets.append(row_offset)
- row_offset += row
- offsets.append(row_offset)
- self._row_offsets = offsets
+ self._compute_row_offsets()
# calculate the bytes we have processed
header_end = (len(signature) + sum(map(len, lines[0:4])) + 4)
=== modified file 'bzrlib/tests/test_btree_index.py'
--- a/bzrlib/tests/test_btree_index.py 2008-08-28 20:13:31 +0000
+++ b/bzrlib/tests/test_btree_index.py 2008-10-14 19:02:26 +0000
@@ -996,3 +996,125 @@
(4, ['g', 'h'])],
['a', 'b', 'd', 'e', 'g', 'h'],
['c', 'd', 'f', 'g'])
+
+
+class TestExpandNodes(tests.TestCase):
+
+ def make_index(self, size, recommended_pages=None):
+ """Make an index with a generic size.
+
+ This doesn't actually create anything on disk, it just primes a
+ BTreeGraphIndex with the recommended information.
+ """
+ index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
+ 'test-index', size=size)
+ if recommended_pages is not None:
+ index._recommended_pages = recommended_pages
+ return index
+
+ def set_cached_nodes(self, index, cached_nodes):
+ """Modify the index to give a canned answer for _get_cached_nodes()."""
+ def _get_cached_nodes():
+ cached = set(cached_nodes)
+ return cached
+ index._get_cached_nodes = _get_cached_nodes
+
+ def prepare_index(self, index, node_ref_lists, key_length, key_count,
+ row_lengths, cached_nodes):
+ """Setup the BTreeGraphIndex with some pre-canned information."""
+ index.node_ref_lists = node_ref_lists
+ index._key_length = key_length
+ index._key_count = key_count
+ index._row_lengths = row_lengths
+ index._compute_row_offsets()
+ index._root_node = btree_index._InternalNode('internal\noffset=0\n')
+ self.set_cached_nodes(index, cached_nodes)
+
+ def make_100_node_index(self):
+ index = self.make_index(4096*100, 6)
+ self.prepare_index(index, node_ref_lists=0, key_length=1,
+ key_count=1000, row_lengths=[1, 99],
+ cached_nodes=[0])
+ return index
+
+ def assertNumPages(self, expected_pages, index, size):
+ index._size = size
+ self.assertEqual(expected_pages, index._compute_num_pages())
+
+ def assertExpandNodes(self, expected, index, node_indexes):
+ self.assertEqual(expected, index._expand_nodes(node_indexes))
+
+ def test_default_recommended_pages(self):
+ index = self.make_index(None)
+ # local transport recommends 4096 byte reads, which is 1 page
+ self.assertEqual(1, index._recommended_pages)
+
+ def test__compute_num_pages(self):
+ index = self.make_index(None)
+ self.assertNumPages(1, index, 1024)
+ self.assertNumPages(1, index, 4095)
+ self.assertNumPages(1, index, 4096)
+ self.assertNumPages(2, index, 4097)
+ self.assertNumPages(2, index, 8192)
+ self.assertNumPages(76, index, 4096*75 + 10)
+
+ def test_unknown_size(self):
+ # We should not expand if we don't know the file size
+ index = self.make_index(None, 10)
+ self.assertExpandNodes([0], index, [0])
+ self.assertExpandNodes([1, 4, 9], index, [1, 4, 9])
+
+ def test_more_than_recommended(self):
+ index = self.make_index(4096*100, 2)
+ self.assertExpandNodes([1, 10], index, [1, 10])
+ self.assertExpandNodes([1, 10, 20], index, [1, 10, 20])
+
+ def test_read_all_from_root(self):
+ index = self.make_index(4096*10, 20)
+ self.assertExpandNodes(range(10), index, [0])
+
+ def test_read_all_when_cached(self):
+ # We've read enough that we can grab all the rest in a single request
+ index = self.make_index(4096*10, 5)
+ self.prepare_index(index, node_ref_lists=0, key_length=1,
+ key_count=1000, row_lengths=[1, 9],
+ cached_nodes=[0, 1, 2, 5, 6])
+ # It should fill the remaining nodes, regardless of the one requested
+ self.assertExpandNodes([3, 4, 7, 8, 9], index, [3])
+ self.assertExpandNodes([3, 4, 7, 8, 9], index, [8])
+ self.assertExpandNodes([3, 4, 7, 8, 9], index, [9])
+
+ def test_no_root_node(self):
+ index = self.make_index(4096*10, 5)
+ self.assertExpandNodes([0], index, [0])
+
+ def test_include_neighbors(self):
+ index = self.make_100_node_index()
+ # We expand in both directions, until we have at least 'recommended'
+ # pages
+ self.assertExpandNodes([9, 10, 11, 12, 13, 14, 15], index, [12])
+ self.assertExpandNodes([88, 89, 90, 91, 92, 93, 94], index, [91])
+ # If we hit an 'edge' we continue in the other direction
+ self.assertExpandNodes([1, 2, 3, 4, 5, 6], index, [2])
+ self.assertExpandNodes([94, 95, 96, 97, 98, 99], index, [98])
+
+ # Requesting many nodes will expand all locations equally
+ self.assertExpandNodes([1, 2, 3, 80, 81, 82], index, [2, 81])
+ self.assertExpandNodes([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
+ [2, 10, 81])
+
+ def test_expand_to_cached(self):
+ index = self.make_100_node_index()
+ self.set_cached_nodes(index, [0, 10, 19])
+ self.assertExpandNodes([11, 12, 13, 14, 15, 16], index, [11])
+ self.assertExpandNodes([11, 12, 13, 14, 15, 16], index, [12])
+ self.assertExpandNodes([12, 13, 14, 15, 16, 17, 18], index, [15])
+ self.assertExpandNodes([13, 14, 15, 16, 17, 18], index, [16])
+ self.assertExpandNodes([13, 14, 15, 16, 17, 18], index, [17])
+ self.assertExpandNodes([13, 14, 15, 16, 17, 18], index, [18])
+
+ def test_expand_limited(self):
+ index = self.make_100_node_index()
+ self.set_cached_nodes(index, [0, 10, 12])
+ # We don't go into an endless loop if we are bound by cached nodes
+ self.assertExpandNodes([11], index, [11])
=== renamed file 'doc/developers/btree_index_request_expansion.txt' => 'doc/developers/btree_index_prefetch.txt'
--- a/doc/developers/btree_index_request_expansion.txt 2008-10-07 21:41:12 +0000
+++ b/doc/developers/btree_index_prefetch.txt 2008-10-14 19:02:26 +0000
@@ -1,6 +1,6 @@
-=============================
-BTree Index Request Expansion
-=============================
+====================
+BTree Index Prefetch
+====================
This document outlines how we decide to pre-read extra nodes in the btree
index.
@@ -11,7 +11,7 @@
Because of the latency involved in making a request, it is often better to make
fewer large requests, rather than more small requests, even if some of the
-extra data will be wasted.
+extra data will be wasted.
Example
-------
@@ -123,7 +123,7 @@
* We generally assume locality of reference. So if we are currently reading
page 10, we are more likely to read page 9 or 11 than we are page 20.
-
+
* However, locality of reference only really holds within a layer. If we are
reading the last node in a layer, we are unlikely to read the first node of
the next layer. In fact, we are most likely to read the *last* node of the
@@ -176,7 +176,7 @@
This is because a command like ``bzr pack`` will combine everything into a
single large file. Commands like ``bzr commit`` will create an index with a
single new record, though these will be packaged together by autopack.
- Commands like ``bzr push`` and ``bzr pull`` will create indexes with more
+ Commands like ``bzr push`` and ``bzr pull`` will create indexes with more
records, but these are unlikely to be a significant portion of the history.
Consider bzr has 20,000 revisions, a single push/pull is likely to only be
100-200 revisions, or 1% of the history.
@@ -235,6 +235,11 @@
powers of 100, etc. The basic idea is that if we are *close* to a layer
split, go ahead and read a small number of extra pages.
+* The previous discussion applies whenever we have an upper layer that is not
+ completely full. So the pages referenced by the last node from the upper
+ layer will often not have a full 100-way fan out. Probably not worthwhile
+ very often, though.
+
Suggested Algorithm
===================
More information about the bazaar-commits
mailing list