659
738
if start_of_leaves is None:
660
739
start_of_leaves = self._row_offsets[-2]
661
740
if node_pos < start_of_leaves:
662
self._internal_node_cache.add(node_pos, node)
741
self._internal_node_cache[node_pos] = node
664
self._leaf_node_cache.add(node_pos, node)
665
cache.add(node_pos, node)
743
self._leaf_node_cache[node_pos] = node
666
744
found[node_pos] = node
669
def _expand_nodes(self, node_indexes):
670
"""Find extra nodes to download.
747
def _compute_recommended_pages(self):
748
"""Convert transport's recommended_page_size into btree pages.
750
recommended_page_size is in bytes, we want to know how many _PAGE_SIZE
751
pages fit in that length.
753
recommended_read = self._transport.recommended_page_size()
754
recommended_pages = int(math.ceil(recommended_read /
756
return recommended_pages
758
def _compute_total_pages_in_index(self):
759
"""How many pages are in the index.
761
If we have read the header we will use the value stored there.
762
Otherwise it will be computed based on the length of the index.
764
if self._size is None:
765
raise AssertionError('_compute_total_pages_in_index should not be'
766
' called when self._size is None')
767
if self._root_node is not None:
768
# This is the number of pages as defined by the header
769
return self._row_offsets[-1]
770
# This is the number of pages as defined by the size of the index. They
771
# should be indentical.
772
total_pages = int(math.ceil(self._size / float(_PAGE_SIZE)))
775
def _expand_offsets(self, offsets):
776
"""Find extra pages to download.
672
778
The idea is that we always want to make big-enough requests (like 64kB
673
779
for http), so that we don't waste round trips. So given the entries
674
that we already have cached, and the new nodes being downloaded, figure
780
that we already have cached and the new pages being downloaded figure
675
781
out what other pages we might want to read.
677
:param node_indexes: The nodes that have been requested to read.
678
# :param recommended_size: The size of download we want, this assumes
679
# that readv() is accomplished in a single round trip (which is true
680
# for http and bzr+ssh, and sftp uses async to get close
682
# :param max_page: The last possible page to read, possibly max_size is
684
:return: A new list of nodes to download
783
See also doc/developers/btree_index_prefetch.txt for more details.
785
:param offsets: The offsets to be read
786
:return: A list of offsets to download
686
trace.note('request: %s\tnodes: %s', self._name[-14:], node_indexes)
687
# return node_indexes
788
if 'index' in debug.debug_flags:
789
trace.mutter('expanding: %s\toffsets: %s', self._name, offsets)
689
# TODO: This could be cached
690
recommended_read = self._transport.recommended_page_size() / 4
691
recommended_pages = int(math.ceil(recommended_read /
693
if len(node_indexes) >= recommended_pages:
791
if len(offsets) >= self._recommended_pages:
694
792
# Don't add more, we are already requesting more than enough
793
if 'index' in debug.debug_flags:
794
trace.mutter(' not expanding large request (%s >= %s)',
795
len(offsets), self._recommended_pages)
696
797
if self._size is None:
697
798
# Don't try anything, because we don't know where the file ends
699
# The idea here is to get nodes "next to" the ones we are already
701
max_page = int(math.ceil(self._size / float(_PAGE_SIZE)))
702
# XXX: Update the LRUCache interface to have a .keys() attribute
703
cached_nodes = set(self._internal_node_cache._cache.keys())
704
cached_nodes.update(self._leaf_node_cache._cache.keys())
705
if self._root_node is not None:
799
if 'index' in debug.debug_flags:
800
trace.mutter(' not expanding without knowing index size')
802
total_pages = self._compute_total_pages_in_index()
803
cached_offsets = self._get_offsets_to_cached_pages()
708
804
# If reading recommended_pages would read the rest of the index, just
710
if max_page - len(cached_nodes) <= recommended_pages:
711
# Just read the whole thing
712
# NOTE: this breaks a little bit with the distinction between index
713
# nodes and leaf nodes (as they are cached separately). It is
714
# still worthwhile to read it all, but we need to figure out what
715
# cache we should really put things in when we are done.
716
# However, we may not have read the index header yet to know where
717
# the internal nodes break from where the leaf nodes. We are sure
718
# to know *after* we've done the read.
719
# This also does the wrong thing if there are bloom pages.
721
# Further, this gives the wrong results because we have 2 caches to
724
return [x for x in xrange(max_page) if x not in cached_nodes]
725
return range(max_page)
727
needed_nodes = recommended_pages - len(node_indexes)
728
final_nodes = set(node_indexes)
729
if node_indexes == [0]:
730
# Special case when we are reading the root node, just read the
731
# first N pages along with the root node
732
final_nodes = node_indexes
733
# for index in xrange(1, max_page):
734
# if index not in final_nodes and index not in cached_nodes:
735
# final_nodes.add(index)
736
# if len(final_nodes) >= recommended_pages:
806
if total_pages - len(cached_offsets) <= self._recommended_pages:
807
# Read whatever is left
809
expanded = [x for x in xrange(total_pages)
810
if x not in cached_offsets]
812
expanded = range(total_pages)
813
if 'index' in debug.debug_flags:
814
trace.mutter(' reading all unread pages: %s', expanded)
817
if self._root_node is None:
818
# ATM on the first read of the root node of a large index, we don't
819
# bother pre-reading any other pages. This is because the
820
# likelyhood of actually reading interesting pages is very low.
821
# See doc/developers/btree_index_prefetch.txt for a discussion, and
822
# a possible implementation when we are guessing that the second
823
# layer index is small
824
final_offsets = offsets
739
while len(final_nodes) < recommended_pages:
740
for pos in sorted(final_nodes):
743
if previous not in cached_nodes:
744
final_nodes.add(previous)
747
if after not in cached_nodes:
748
final_nodes.add(after)
749
# if len(final_nodes) > recommended_pages:
752
final_nodes = sorted(final_nodes)
753
trace.note('\t\t\t\t%s', final_nodes)
826
tree_depth = len(self._row_lengths)
827
if len(cached_offsets) < tree_depth and len(offsets) == 1:
828
# We haven't read enough to justify expansion
829
# If we are only going to read the root node, and 1 leaf node,
830
# then it isn't worth expanding our request. Once we've read at
831
# least 2 nodes, then we are probably doing a search, and we
832
# start expanding our requests.
833
if 'index' in debug.debug_flags:
834
trace.mutter(' not expanding on first reads')
836
final_offsets = self._expand_to_neighbors(offsets, cached_offsets,
839
final_offsets = sorted(final_offsets)
840
if 'index' in debug.debug_flags:
841
trace.mutter('expanded: %s', final_offsets)
844
def _expand_to_neighbors(self, offsets, cached_offsets, total_pages):
845
"""Expand requests to neighbors until we have enough pages.
847
This is called from _expand_offsets after policy has determined that we
849
We only want to expand requests within a given layer. We cheat a little
850
bit and assume all requests will be in the same layer. This is true
851
given the current design, but if it changes this algorithm may perform
854
:param offsets: requested offsets
855
:param cached_offsets: offsets for pages we currently have cached
856
:return: A set() of offsets after expansion
858
final_offsets = set(offsets)
860
new_tips = set(final_offsets)
861
while len(final_offsets) < self._recommended_pages and new_tips:
865
first, end = self._find_layer_first_and_end(pos)
868
and previous not in cached_offsets
869
and previous not in final_offsets
870
and previous >= first):
871
next_tips.add(previous)
873
if (after < total_pages
874
and after not in cached_offsets
875
and after not in final_offsets
878
# This would keep us from going bigger than
879
# recommended_pages by only expanding the first offsets.
880
# However, if we are making a 'wide' request, it is
881
# reasonable to expand all points equally.
882
# if len(final_offsets) > recommended_pages:
884
final_offsets.update(next_tips)
888
def clear_cache(self):
889
"""Clear out any cached/memoized values.
891
This can be called at any time, but generally it is used when we have
892
extracted some information, but don't expect to be requesting any more
895
# Note that we don't touch self._root_node or self._internal_node_cache
896
# We don't expect either of those to be big, and it can save
897
# round-trips in the future. We may re-evaluate this if InternalNode
898
# memory starts to be an issue.
899
self._leaf_node_cache.clear()
901
def external_references(self, ref_list_num):
902
if self._root_node is None:
903
self._get_root_node()
904
if ref_list_num + 1 > self.node_ref_lists:
905
raise ValueError('No ref list %d, index has %d ref lists'
906
% (ref_list_num, self.node_ref_lists))
909
for node in self.iter_all_entries():
911
refs.update(node[3][ref_list_num])
914
def _find_layer_first_and_end(self, offset):
915
"""Find the start/stop nodes for the layer corresponding to offset.
917
:return: (first, end)
918
first is the first node in this layer
919
end is the first node of the next layer
922
for roffset in self._row_offsets:
929
def _get_offsets_to_cached_pages(self):
930
"""Determine what nodes we already have cached."""
931
cached_offsets = set(self._internal_node_cache.keys())
932
cached_offsets.update(self._leaf_node_cache.keys())
933
if self._root_node is not None:
934
cached_offsets.add(0)
935
return cached_offsets
937
def _get_root_node(self):
938
if self._root_node is None:
939
# We may not have a root node yet
940
self._get_internal_nodes([0])
941
return self._root_node
756
943
def _get_nodes(self, cache, node_indexes):
943
1182
needed_keys = keys
944
1183
if not needed_keys:
946
# 6 seconds spent in miss_torture using the sorted() line.
947
# Even with out of order disk IO it seems faster not to sort it when
948
# large queries are being made.
949
needed_keys = sorted(needed_keys)
951
nodes_and_keys = [(0, needed_keys)]
953
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
954
node_indexes = [idx for idx, s_keys in nodes_and_keys]
955
nodes = self._get_internal_nodes(node_indexes)
957
next_nodes_and_keys = []
958
for node_index, sub_keys in nodes_and_keys:
959
node = nodes[node_index]
960
positions = self._multi_bisect_right(sub_keys, node.keys)
961
node_offset = next_row_start + node.offset
962
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
963
for pos, s_keys in positions])
964
nodes_and_keys = next_nodes_and_keys
965
# We should now be at the _LeafNodes
966
node_indexes = [idx for idx, s_keys in nodes_and_keys]
968
# TODO: We may *not* want to always read all the nodes in one
969
# big go. Consider setting a max size on this.
971
nodes = self._get_leaf_nodes(node_indexes)
1185
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
972
1186
for node_index, sub_keys in nodes_and_keys:
973
1187
if not sub_keys:
975
1189
node = nodes[node_index]
976
1190
for next_sub_key in sub_keys:
977
if next_sub_key in node.keys:
978
value, refs = node.keys[next_sub_key]
1191
if next_sub_key in node:
1192
value, refs = node[next_sub_key]
979
1193
if self.node_ref_lists:
980
1194
yield (self, next_sub_key, value, refs)
982
1196
yield (self, next_sub_key, value)
1198
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1199
"""Find the parent_map information for the set of keys.
1201
This populates the parent_map dict and missing_keys set based on the
1202
queried keys. It also can fill out an arbitrary number of parents that
1203
it finds while searching for the supplied keys.
1205
It is unlikely that you want to call this directly. See
1206
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1208
:param keys: A keys whose ancestry we want to return
1209
Every key will either end up in 'parent_map' or 'missing_keys'.
1210
:param ref_list_num: This index in the ref_lists is the parents we
1212
:param parent_map: {key: parent_keys} for keys that are present in this
1213
index. This may contain more entries than were in 'keys', that are
1214
reachable ancestors of the keys requested.
1215
:param missing_keys: keys which are known to be missing in this index.
1216
This may include parents that were not directly requested, but we
1217
were able to determine that they are not present in this index.
1218
:return: search_keys parents that were found but not queried to know
1219
if they are missing or present. Callers can re-query this index for
1220
those keys, and they will be placed into parent_map or missing_keys
1222
if not self.key_count():
1223
# We use key_count() to trigger reading the root node and
1224
# determining info about this BTreeGraphIndex
1225
# If we don't have any keys, then everything is missing
1226
missing_keys.update(keys)
1228
if ref_list_num >= self.node_ref_lists:
1229
raise ValueError('No ref list %d, index has %d ref lists'
1230
% (ref_list_num, self.node_ref_lists))
1232
# The main trick we are trying to accomplish is that when we find a
1233
# key listing its parents, we expect that the parent key is also likely
1234
# to sit on the same page. Allowing us to expand parents quickly
1235
# without suffering the full stack of bisecting, etc.
1236
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1238
# These are parent keys which could not be immediately resolved on the
1239
# page where the child was present. Note that we may already be
1240
# searching for that key, and it may actually be present [or known
1241
# missing] on one of the other pages we are reading.
1243
# We could try searching for them in the immediate previous or next
1244
# page. If they occur "later" we could put them in a pending lookup
1245
# set, and then for each node we read thereafter we could check to
1246
# see if they are present.
1247
# However, we don't know the impact of keeping this list of things
1248
# that I'm going to search for every node I come across from here on
1250
# It doesn't handle the case when the parent key is missing on a
1251
# page that we *don't* read. So we already have to handle being
1252
# re-entrant for that.
1253
# Since most keys contain a date string, they are more likely to be
1254
# found earlier in the file than later, but we would know that right
1255
# away (key < min_key), and wouldn't keep searching it on every other
1256
# page that we read.
1257
# Mostly, it is an idea, one which should be benchmarked.
1258
parents_not_on_page = set()
1260
for node_index, sub_keys in nodes_and_keys:
1263
# sub_keys is all of the keys we are looking for that should exist
1264
# on this page, if they aren't here, then they won't be found
1265
node = nodes[node_index]
1266
parents_to_check = set()
1267
for next_sub_key in sub_keys:
1268
if next_sub_key not in node:
1269
# This one is just not present in the index at all
1270
missing_keys.add(next_sub_key)
1272
value, refs = node[next_sub_key]
1273
parent_keys = refs[ref_list_num]
1274
parent_map[next_sub_key] = parent_keys
1275
parents_to_check.update(parent_keys)
1276
# Don't look for things we've already found
1277
parents_to_check = parents_to_check.difference(parent_map)
1278
# this can be used to test the benefit of having the check loop
1280
# parents_not_on_page.update(parents_to_check)
1282
while parents_to_check:
1283
next_parents_to_check = set()
1284
for key in parents_to_check:
1286
value, refs = node[key]
1287
parent_keys = refs[ref_list_num]
1288
parent_map[key] = parent_keys
1289
next_parents_to_check.update(parent_keys)
1291
# This parent either is genuinely missing, or should be
1292
# found on another page. Perf test whether it is better
1293
# to check if this node should fit on this page or not.
1294
# in the 'everything-in-one-pack' scenario, this *not*
1295
# doing the check is 237ms vs 243ms.
1296
# So slightly better, but I assume the standard 'lots
1297
# of packs' is going to show a reasonable improvement
1298
# from the check, because it avoids 'going around
1299
# again' for everything that is in another index
1300
# parents_not_on_page.add(key)
1301
# Missing for some reason
1302
if key < node.min_key:
1303
# in the case of bzr.dev, 3.4k/5.3k misses are
1304
# 'earlier' misses (65%)
1305
parents_not_on_page.add(key)
1306
elif key > node.max_key:
1307
# This parent key would be present on a different
1309
parents_not_on_page.add(key)
1311
# assert key != node.min_key and key != node.max_key
1312
# If it was going to be present, it would be on
1313
# *this* page, so mark it missing.
1314
missing_keys.add(key)
1315
parents_to_check = next_parents_to_check.difference(parent_map)
1316
# Might want to do another .difference() from missing_keys
1317
# parents_not_on_page could have been found on a different page, or be
1318
# known to be missing. So cull out everything that has already been
1320
search_keys = parents_not_on_page.difference(
1321
parent_map).difference(missing_keys)
984
1324
def iter_entries_prefix(self, keys):
985
1325
"""Iterate over keys within the index using prefix matching.
1160
1504
"""Read some nodes from disk into the LRU cache.
1162
1506
This performs a readv to get the node data into memory, and parses each
1163
node, the yields it to the caller. The nodes are requested in the
1507
node, then yields it to the caller. The nodes are requested in the
1164
1508
supplied order. If possible doing sort() on the list before requesting
1165
1509
a read may improve performance.
1167
1511
:param nodes: The nodes to read. 0 - first node, 1 - second node etc.
1514
# may be the byte string of the whole file
1516
# list of (offset, length) regions of the file that should, evenually
1517
# be read in to data_ranges, either from 'bytes' or from the transport
1519
base_offset = self._base_offset
1171
1520
for index in nodes:
1172
offset = index * _PAGE_SIZE
1521
offset = (index * _PAGE_SIZE)
1173
1522
size = _PAGE_SIZE
1175
1524
# Root node - special case
1177
1526
size = min(_PAGE_SIZE, self._size)
1179
stream = self._transport.get(self._name)
1180
start = stream.read(_PAGE_SIZE)
1181
# Avoid doing this again
1182
self._size = len(start)
1183
size = min(_PAGE_SIZE, self._size)
1528
# The only case where we don't know the size, is for very
1529
# small indexes. So we read the whole thing
1530
bytes = self._transport.get_bytes(self._name)
1531
num_bytes = len(bytes)
1532
self._size = num_bytes - base_offset
1533
# the whole thing should be parsed out of 'bytes'
1534
ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1535
for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1538
if offset > self._size:
1539
raise AssertionError('tried to read past the end'
1540
' of the file %s > %s'
1541
% (offset, self._size))
1185
1542
size = min(size, self._size - offset)
1186
ranges.append((offset, size))
1543
ranges.append((base_offset + offset, size))
1189
if self._file is None:
1546
elif bytes is not None:
1547
# already have the whole file
1548
data_ranges = [(start, bytes[start:start+size])
1549
for start, size in ranges]
1550
elif self._file is None:
1190
1551
data_ranges = self._transport.readv(self._name, ranges)
1192
1553
data_ranges = []
added
removed
bzrlib/btree_index.py
