1
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
1
# Copyright (C) 2008, 2009 Canonical Ltd
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
27
27
Updates to a CHKMap are done preferentially via the apply_delta method, to
28
28
allow optimisation of the update operation; but individual map/unmap calls are
29
possible and supported. Individual changes via map/unmap are buffered in memory
30
until the _save method is called to force serialisation of the tree.
31
apply_delta records its changes immediately by performing an implicit _save.
29
possible and supported. All changes via map/unmap are buffered in memory until
30
the _save method is called to force serialisation of the tree. apply_delta
31
performs a _save implicitly.
43
42
from bzrlib import lazy_import
44
43
lazy_import.lazy_import(globals(), """
44
from bzrlib import versionedfile
50
46
from bzrlib import (
57
from bzrlib.static_tuple import StaticTuple
60
54
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
61
55
# out, it takes 3.1MB to cache the layer.
62
56
_PAGE_CACHE_SIZE = 4*1024*1024
63
# Per thread caches for 2 reasons:
64
# - in the server we may be serving very different content, so we get less
66
# - we avoid locking on every cache lookup.
67
_thread_caches = threading.local()
69
_thread_caches.page_cache = None
72
"""Get the per-thread page cache.
74
We need a function to do this because in a new thread the _thread_caches
75
threading.local object does not have the cache initialized yet.
77
page_cache = getattr(_thread_caches, 'page_cache', None)
78
if page_cache is None:
79
# We are caching bytes so len(value) is perfectly accurate
80
page_cache = lru_cache.LRUSizeCache(_PAGE_CACHE_SIZE)
81
_thread_caches.page_cache = page_cache
57
# We are caching bytes so len(value) is perfectly accurate
58
_page_cache = lru_cache.LRUSizeCache(_PAGE_CACHE_SIZE)
89
63
# If a ChildNode falls below this many bytes, we check for a remap
90
64
_INTERESTING_NEW_SIZE = 50
106
80
class CHKMap(object):
107
81
"""A persistent map from string to string backed by a CHK store."""
109
__slots__ = ('_store', '_root_node', '_search_key_func')
111
83
def __init__(self, store, root_key, search_key_func=None):
112
84
"""Create a CHKMap object.
136
108
of old_key is removed.
139
# Check preconditions first.
140
as_st = StaticTuple.from_sequence
141
new_items = set([as_st(key) for (old, key, value) in delta
142
if key is not None and old is None])
143
existing_new = list(self.iteritems(key_filter=new_items))
145
raise errors.InconsistentDeltaDelta(delta,
146
"New items are already in the map %r." % existing_new)
148
111
for old, new, value in delta:
149
112
if old is not None and old != new:
150
113
self.unmap(old, check_remap=False)
173
136
:param node: A tuple key or node object.
174
137
:return: A node object.
176
if type(node) is StaticTuple:
139
if type(node) is tuple:
177
140
bytes = self._read_bytes(node)
178
141
return _deserialise(bytes, node,
179
142
search_key_func=self._search_key_func)
183
146
def _read_bytes(self, key):
185
return _get_cache()[key]
148
return _page_cache[key]
187
150
stream = self._store.get_record_stream([key], 'unordered', True)
188
151
bytes = stream.next().get_bytes_as('fulltext')
189
_get_cache()[key] = bytes
152
_page_cache[key] = bytes
192
155
def _dump_tree(self, include_keys=False):
220
183
for key, value in sorted(node._items.iteritems()):
221
184
# Don't use prefix nor indent here to line up when used in
222
185
# tests in conjunction with assertEqualDiff
223
result.append(' %r %r' % (tuple(key), value))
186
result.append(' %r %r' % (key, value))
244
207
root_key = klass._create_directly(store, initial_value,
245
208
maximum_size=maximum_size, key_width=key_width,
246
209
search_key_func=search_key_func)
247
if type(root_key) is not StaticTuple:
248
raise AssertionError('we got a %s instead of a StaticTuple'
267
227
node = LeafNode(search_key_func=search_key_func)
268
228
node.set_maximum_size(maximum_size)
269
229
node._key_width = key_width
270
as_st = StaticTuple.from_sequence
271
node._items = dict([(as_st(key), val) for key, val
272
in initial_value.iteritems()])
230
node._items = dict(initial_value)
273
231
node._raw_size = sum([node._key_value_len(key, value)
274
for key,value in node._items.iteritems()])
232
for key,value in initial_value.iteritems()])
275
233
node._len = len(node._items)
276
234
node._compute_search_prefix()
277
235
node._compute_serialised_prefix()
513
471
def iteritems(self, key_filter=None):
514
472
"""Iterate over the entire CHKMap's contents."""
515
473
self._ensure_root()
516
if key_filter is not None:
517
as_st = StaticTuple.from_sequence
518
key_filter = [as_st(key) for key in key_filter]
519
474
return self._root_node.iteritems(self._store, key_filter=key_filter)
522
477
"""Return the key for this map."""
523
if type(self._root_node) is StaticTuple:
478
if type(self._root_node) is tuple:
524
479
return self._root_node
526
481
return self._root_node._key
530
485
return len(self._root_node)
532
487
def map(self, key, value):
533
"""Map a key tuple to value.
535
:param key: A key to map.
536
:param value: The value to assign to key.
538
key = StaticTuple.from_sequence(key)
488
"""Map a key tuple to value."""
539
489
# Need a root object.
540
490
self._ensure_root()
541
491
prefix, node_details = self._root_node.map(self._store, key, value)
552
502
def _node_key(self, node):
553
503
"""Get the key for a node whether it's a tuple or node."""
554
504
if type(node) is tuple:
555
node = StaticTuple.from_sequence(node)
556
if type(node) is StaticTuple:
561
509
def unmap(self, key, check_remap=True):
562
510
"""remove key from the map."""
563
key = StaticTuple.from_sequence(key)
564
511
self._ensure_root()
565
512
if type(self._root_node) is InternalNode:
566
513
unmapped = self._root_node.unmap(self._store, key,
594
541
adding the header bytes, and without prefix compression.
597
__slots__ = ('_key', '_len', '_maximum_size', '_key_width',
598
'_raw_size', '_items', '_search_prefix', '_search_key_func'
601
544
def __init__(self, key_width=1):
602
545
"""Create a node.
692
635
the key/value pairs.
695
__slots__ = ('_common_serialised_prefix',)
697
638
def __init__(self, search_key_func=None):
698
639
Node.__init__(self)
699
640
# All of the keys in this leaf node share this common prefix
700
641
self._common_serialised_prefix = None
642
self._serialise_key = '\x00'.join
701
643
if search_key_func is None:
702
644
self._search_key_func = _search_key_plain
741
683
:param bytes: The bytes of the node.
742
684
:param key: The key that the serialised node has.
744
key = static_tuple.expect_static_tuple(key)
745
686
return _deserialise_leaf_node(bytes, key,
746
687
search_key_func=search_key_func)
887
828
raise AssertionError('%r must be known' % self._search_prefix)
888
829
return self._search_prefix, [("", self)]
890
_serialise_key = '\x00'.join
892
831
def serialise(self, store):
893
832
"""Serialise the LeafNode to store.
919
858
lines.append(serialized[prefix_len:])
920
859
lines.extend(value_lines)
921
860
sha1, _, _ = store.add_lines((None,), (), lines)
922
self._key = StaticTuple("sha1:" + sha1,).intern()
861
self._key = ("sha1:" + sha1,)
923
862
bytes = ''.join(lines)
924
863
if len(bytes) != self._current_size():
925
864
raise AssertionError('Invalid _current_size')
926
_get_cache().add(self._key, bytes)
865
_page_cache.add(self._key, bytes)
927
866
return [self._key]
993
932
LeafNode or InternalNode.
996
__slots__ = ('_node_width',)
998
935
def __init__(self, prefix='', search_key_func=None):
999
936
Node.__init__(self)
1000
937
# The size of an internalnode with default values and no children.
1042
979
:param key: The key that the serialised node has.
1043
980
:return: An InternalNode instance.
1045
key = static_tuple.expect_static_tuple(key)
1046
982
return _deserialise_internal_node(bytes, key,
1047
983
search_key_func=search_key_func)
1073
1009
# for whatever we are missing
1074
1010
shortcut = True
1075
1011
for prefix, node in self._items.iteritems():
1076
if node.__class__ is StaticTuple:
1012
if node.__class__ is tuple:
1077
1013
keys[node] = (prefix, None)
1079
1015
yield node, None
1108
1044
# A given key can only match 1 child node, if it isn't
1109
1045
# there, then we can just return nothing
1111
if node.__class__ is StaticTuple:
1047
if node.__class__ is tuple:
1112
1048
keys[node] = (search_prefix, [key])
1114
1050
# This is loaded, and the only thing that can match,
1141
1077
# We can ignore this one
1143
1079
node_key_filter = prefix_to_keys[search_prefix]
1144
if node.__class__ is StaticTuple:
1080
if node.__class__ is tuple:
1145
1081
keys[node] = (search_prefix, node_key_filter)
1147
1083
yield node, node_key_filter
1156
1092
if sub_prefix in length_filter:
1157
1093
node_key_filter.extend(prefix_to_keys[sub_prefix])
1158
1094
if node_key_filter: # this key matched something, yield it
1159
if node.__class__ is StaticTuple:
1095
if node.__class__ is tuple:
1160
1096
keys[node] = (prefix, node_key_filter)
1162
1098
yield node, node_key_filter
1196
1132
prefix, node_key_filter = keys[record.key]
1197
1133
node_and_filters.append((node, node_key_filter))
1198
1134
self._items[prefix] = node
1199
_get_cache().add(record.key, bytes)
1135
_page_cache.add(record.key, bytes)
1200
1136
for info in node_and_filters:
1311
1247
lines.append('%s\n' % (self._search_prefix,))
1312
1248
prefix_len = len(self._search_prefix)
1313
1249
for prefix, node in sorted(self._items.items()):
1314
if type(node) is StaticTuple:
1250
if type(node) is tuple:
1317
1253
key = node._key[0]
1321
1257
% (serialised, self._search_prefix))
1322
1258
lines.append(serialised[prefix_len:])
1323
1259
sha1, _, _ = store.add_lines((None,), (), lines)
1324
self._key = StaticTuple("sha1:" + sha1,).intern()
1325
_get_cache().add(self._key, ''.join(lines))
1260
self._key = ("sha1:" + sha1,)
1261
_page_cache.add(self._key, ''.join(lines))
1326
1262
yield self._key
1328
1264
def _search_key(self, key):
1477
1413
def __init__(self, store, new_root_keys, old_root_keys,
1478
1414
search_key_func, pb=None):
1479
# TODO: Should we add a StaticTuple barrier here? It would be nice to
1480
# force callers to use StaticTuple, because there will often be
1481
# lots of keys passed in here. And even if we cast it locally,
1482
# that just meanst that we will have *both* a StaticTuple and a
1483
# tuple() in memory, referring to the same object. (so a net
1484
# increase in memory, not a decrease.)
1485
1415
self._store = store
1486
1416
self._new_root_keys = new_root_keys
1487
1417
self._old_root_keys = old_root_keys
1489
1419
# All uninteresting chks that we have seen. By the time they are added
1490
1420
# here, they should be either fully ignored, or queued up for
1492
# TODO: This might grow to a large size if there are lots of merge
1493
# parents, etc. However, it probably doesn't scale to O(history)
1494
# like _processed_new_refs does.
1495
1422
self._all_old_chks = set(self._old_root_keys)
1496
1423
# All items that we have seen from the old_root_keys
1497
1424
self._all_old_items = set()
1498
1425
# These are interesting items which were either read, or already in the
1499
1426
# interesting queue (so we don't need to walk them again)
1500
# TODO: processed_new_refs becomes O(all_chks), consider switching to
1502
1427
self._processed_new_refs = set()
1503
1428
self._search_key_func = search_key_func
1511
1436
self._state = None
1513
1438
def _read_nodes_from_store(self, keys):
1514
# We chose not to use _get_cache(), because we think in
1515
# terms of records to be yielded. Also, we expect to touch each page
1516
# only 1 time during this code. (We may want to evaluate saving the
1517
# raw bytes into the page cache, which would allow a working tree
1518
# update after the fetch to not have to read the bytes again.)
1519
as_st = StaticTuple.from_sequence
1439
# We chose not to use _page_cache, because we think in terms of records
1440
# to be yielded. Also, we expect to touch each page only 1 time during
1441
# this code. (We may want to evaluate saving the raw bytes into the
1442
# page cache, which would allow a working tree update after the fetch
1443
# to not have to read the bytes again.)
1520
1444
stream = self._store.get_record_stream(keys, 'unordered', True)
1521
1445
for record in stream:
1522
1446
if self._pb is not None:
1529
1453
if type(node) is InternalNode:
1530
1454
# Note we don't have to do node.refs() because we know that
1531
1455
# there are no children that have been pushed into this node
1532
# Note: Using as_st() here seemed to save 1.2MB, which would
1533
# indicate that we keep 100k prefix_refs around while
1534
# processing. They *should* be shorter lived than that...
1535
# It does cost us ~10s of processing time
1536
#prefix_refs = [as_st(item) for item in node._items.iteritems()]
1537
1456
prefix_refs = node._items.items()
1540
1459
prefix_refs = []
1541
# Note: We don't use a StaticTuple here. Profiling showed a
1542
# minor memory improvement (0.8MB out of 335MB peak 0.2%)
1543
# But a significant slowdown (15s / 145s, or 10%)
1544
1460
items = node._items.items()
1545
1461
yield record, node, prefix_refs, items
1554
1470
if p_r[1] not in all_old_chks]
1555
1471
new_refs = [p_r[1] for p_r in prefix_refs]
1556
1472
all_old_chks.update(new_refs)
1557
# TODO: This might be a good time to turn items into StaticTuple
1558
# instances and possibly intern them. However, this does not
1559
# impact 'initial branch' performance, so I'm not worrying
1561
1473
self._all_old_items.update(items)
1562
1474
# Queue up the uninteresting references
1563
1475
# Don't actually put them in the 'to-read' queue until we have
1616
1528
# current design allows for this, as callers will do the work
1617
1529
# to make the results unique. We might profile whether we
1618
1530
# gain anything by ensuring unique return values for items
1619
# TODO: This might be a good time to cast to StaticTuple, as
1620
# self._new_item_queue will hold the contents of multiple
1621
# records for an extended lifetime
1622
1531
new_items = [item for item in items
1623
1532
if item not in self._all_old_items]
1624
1533
self._new_item_queue.extend(new_items)
1650
1559
yield None, new_items
1651
1560
refs = refs.difference(all_old_chks)
1652
processed_new_refs.update(refs)
1654
# TODO: Using a SimpleSet for self._processed_new_refs and
1655
# saved as much as 10MB of peak memory. However, it requires
1656
# implementing a non-pyrex version.
1657
1562
next_refs = set()
1658
1563
next_refs_update = next_refs.update
1659
1564
# Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'
1660
1565
# from 1m54s to 1m51s. Consider it.
1661
1566
for record, _, p_refs, items in self._read_nodes_from_store(refs):
1663
# using the 'if' check saves about 145s => 141s, when
1664
# streaming initial branch of Launchpad data.
1665
items = [item for item in items
1666
if item not in all_old_items]
1567
items = [item for item in items
1568
if item not in all_old_items]
1667
1569
yield record, items
1668
1570
next_refs_update([p_r[1] for p_r in p_refs])
1670
# set1.difference(set/dict) walks all of set1, and checks if it
1671
# exists in 'other'.
1672
# set1.difference(iterable) walks all of iterable, and does a
1673
# 'difference_update' on a clone of set1. Pick wisely based on the
1674
# expected sizes of objects.
1675
# in our case it is expected that 'new_refs' will always be quite
1677
1571
next_refs = next_refs.difference(all_old_chks)
1678
1572
next_refs = next_refs.difference(processed_new_refs)
1679
1573
processed_new_refs.update(next_refs)
1686
1580
self._old_queue = []
1687
1581
all_old_chks = self._all_old_chks
1688
1582
for record, _, prefix_refs, items in self._read_nodes_from_store(refs):
1689
# TODO: Use StaticTuple here?
1690
1583
self._all_old_items.update(items)
1691
1584
refs = [r for _,r in prefix_refs if r not in all_old_chks]
1692
1585
self._old_queue.extend(refs)
1743
1635
search_key_registry.register('hash-16-way', _search_key_16)
1744
1636
search_key_registry.register('hash-255-way', _search_key_255)
1747
def _check_key(key):
1748
"""Helper function to assert that a key is properly formatted.
1750
This generally shouldn't be used in production code, but it can be helpful
1753
if type(key) is not StaticTuple:
1754
raise TypeError('key %r is not StaticTuple but %s' % (key, type(key)))
1756
raise ValueError('key %r should have length 1, not %d' % (key, len(key),))
1757
if type(key[0]) is not str:
1758
raise TypeError('key %r should hold a str, not %r'
1759
% (key, type(key[0])))
1760
if not key[0].startswith('sha1:'):
1761
raise ValueError('key %r should point to a sha1:' % (key,))
added
removed
bzrlib/chk_map.py
