[ovs-dev,RFC] 1/1 Add multi-column index support for the Python IDL

Message ID	1523304183-19472-2-git-send-email-twilson@redhat.com
State	RFC
Headers	show Return-Path: <ovs-dev-bounces@openvswitch.org> From: twilson@redhat.com To: dev@openvswitch.org Date: Mon, 9 Apr 2018 15:03:03 -0500 Message-Id: <1523304183-19472-2-git-send-email-twilson@redhat.com> In-Reply-To: <1523304183-19472-1-git-send-email-twilson@redhat.com> References: <1523304183-19472-1-git-send-email-twilson@redhat.com> Subject: [ovs-dev] [RFC] [PATCH] 1/1 Add multi-column index support for the Python IDL Precedence: list MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org
Series	[ovs-dev,RFC] 1/1 Add multi-column index support for the Python IDL \| expand [ovs-dev,RFC] 1/1 Add multi-column index support for the Python IDL

diff --git a/python/automake.mk b/python/automake.mk index 9b5d3d8..583a4e9 100644 --- a/python/automake.mk +++ b/python/automake.mk @@ -13,6 +13,7 @@ ovs_pyfiles = \ python/ovs/daemon.py \ python/ovs/fcntl_win.py \ python/ovs/db/__init__.py \ + python/ovs/db/custom_index.py \ python/ovs/db/data.py \ python/ovs/db/error.py \ python/ovs/db/idl.py \ diff --git a/python/ovs/db/custom_index.py b/python/ovs/db/custom_index.py new file mode 100644 index 0000000..878cf37 --- /dev/null +++ b/python/ovs/db/custom_index.py @@ -0,0 +1,151 @@ +import collections +import functools +import operator +try: + from UserDict import IterableUserDict as DictBase +except ImportError: + from collections import UserDict as DictBase + +import sortedcontainers + +from ovs.db import data + +OVSDB_INDEX_ASC = "ASC" +OVSDB_INDEX_DESC = "DESC" +ColumnIndex = collections.namedtuple('ColumnIndex', + ['column', 'direction', 'key']) + + +class MultiColumnIndex(object): + def __init__(self, name): + self.name = name + self.columns = [] + self.clear() + + def __repr__(self): + return "{}(name={})".format(self.__class__.__name__, self.name) + + def __str__(self): + return repr(self) + " columns={} values={}".format( + self.columns, [str(v) for v in self.values]) + + def add_column(self, column, direction=OVSDB_INDEX_ASC, key=None): + self.columns.append(ColumnIndex(column, direction, + key or operator.attrgetter(column))) + + def add_columns(self, *columns): + self.columns.extend(ColumnIndex(col, OVSDB_INDEX_ASC, + operator.attrgetter(col)) + for col in columns) + + def _cmp(self, a, b): + for col, direction, key in self.columns: + aval, bval = key(a), key(b) + if aval == bval: + continue + result = (aval > bval) - (aval < bval) + return result if direction == OVSDB_INDEX_ASC else -result + return 0 + + def index_entry_from_row(self, row): + return row._table.rows.IndexEntry( + uuid=row.uuid, + **{c.column: getattr(row, c.column) for c in self.columns}) + + def add(self, row): + if not all(hasattr(row, col.column) for col in self.columns): + # This is a new row, but it hasn't had the necessary columns set + # We'll add it later + return + self.values.add(self.index_entry_from_row(row)) + + def remove(self, row): + self.values.remove(self.index_entry_from_row(row)) + + def clear(self): + self.values = sortedcontainers.SortedListWithKey( + key=functools.cmp_to_key(self._cmp)) + + def irange(self, start, end): + return iter(r._table.rows[r.uuid] + for r in self.values.irange(start, end)) + + def __iter__(self): + return iter(r._table.rows[r.uuid] for r in self.values) + + +class IndexedRows(DictBase, object): + def __init__(self, table, *args, **kwargs): + super(IndexedRows, self).__init__(*args, **kwargs) + self.table = table + self.indexes = {} + self.IndexEntry = IndexEntryClass(table) + + def index_create(self, name): + if name in self.indexes: + raise ValueError("An index named {} already exists".format(name)) + index = self.indexes[name] = MultiColumnIndex(name) + return index + + def __setitem__(self, key, item): + self.data[key] = item + for index in self.indexes.values(): + index.add(item) + + def __delitem__(self, key): + val = self.data[key] + del self.data[key] + for index in self.indexes.values(): + index.remove(val) + + def clear(self): + self.data.clear() + for index in self.indexes.values(): + index.clear() + + # Nothing uses the methods below, though they'd be easy to implement + def update(self, dict=None, **kwargs): + raise NotImplementedError() + + def setdefault(self, key, failobj=None): + raise NotImplementedError() + + def pop(self, key, *args): + raise NotImplementedError() + + def popitem(self): + raise NotImplementedError() + + @classmethod + def fromkeys(cls, iterable, value=None): + raise NotImplementedError() + + +def IndexEntryClass(table): + """Create a class used represent Rows in indexes + + ovs.db.idl.Row, being inherently tied to transaction processing and being + initialized with dicts of Datums, is not really useable as an object to + pass to and store in indexes. This method will create a class named after + the table's name that is initialized with that Table Row's default values. + For example: + + Port = IndexEntryClass(idl.tables['Port']) + + will create a Port class. This class can then be used to search custom + indexes. For example: + + for port in idx.iranage(Port(name="test1"), Port(name="test9")): + ... + """ + + def defaults_uuid_to_row(atom, base): + return atom.value + + columns = ['uuid'] + list(table.columns.keys()) + cls = collections.namedtuple(table.name, columns) + cls._table = table + cls.__new__.__defaults__ = (None,) + tuple( + data.Datum.default(c.type).to_python(defaults_uuid_to_row) + for c in table.columns.values()) + return cls diff --git a/python/ovs/db/idl.py b/python/ovs/db/idl.py index 5a4d129..564977c 100644 --- a/python/ovs/db/idl.py +++ b/python/ovs/db/idl.py @@ -22,6 +22,7 @@ import ovs.jsonrpc import ovs.ovsuuid import ovs.poller import ovs.vlog +from ovs.db import custom_index from ovs.db import error import six @@ -148,11 +149,23 @@ class Idl(object): if not hasattr(column, 'alert'): column.alert = True table.need_table = False - table.rows = {} + table.rows = custom_index.IndexedRows(table) table.idl = self table.condition = [True] table.cond_changed = False + def index_create(self, table, name): + """Create a named multi-column index on a table""" + return self.tables[table].rows.index_create(name) + + def index_irange(self, table, name, start, end): + """Return items in a named index between start/end inclusive""" + return self.tables[table].rows.indexes[name].irange(start, end) + + def index_equal(self, table, name, value): + """Return items in a named index matching a value""" + return self.tables[table].rows.indexes[name].irange(value, value) + def close(self): """Closes the connection to the database. The IDL will no longer update.""" @@ -359,7 +372,7 @@ class Idl(object): for table in six.itervalues(self.tables): if table.rows: changed = True - table.rows = {} + table.rows = custom_index.IndexedRows(table) if changed: self.change_seqno += 1 @@ -511,8 +524,9 @@ class Idl(object): else: row_update = row_update['initial'] self.__add_default(table, row_update) - if self.__row_update(table, row, row_update): - changed = True + changed = self.__row_update(table, row, row_update) + table.rows[uuid] = row + if changed: self.notify(ROW_CREATE, row) elif "modify" in row_update: if not row: @@ -542,15 +556,19 @@ class Idl(object): % (uuid, table.name)) elif not old: # Insert row. + op = ROW_CREATE if not row: row = self.__create_row(table, uuid) changed = True else: # XXX rate-limit + op = ROW_UPDATE vlog.warn("cannot add existing row %s to table %s" % (uuid, table.name)) - if self.__row_update(table, row, new): - changed = True + changed |= self.__row_update(table, row, new) + if op == ROW_CREATE: + table.rows[uuid] = row + if changed: self.notify(ROW_CREATE, row) else: op = ROW_UPDATE @@ -561,8 +579,10 @@ class Idl(object): # XXX rate-limit vlog.warn("cannot modify missing row %s in table %s" % (uuid, table.name)) - if self.__row_update(table, row, new): - changed = True + changed |= self.__row_update(table, row, new) + if op == ROW_CREATE: + table.rows[uuid] = row + if changed: self.notify(op, row, Row.from_json(self, table, uuid, old)) return changed @@ -638,8 +658,7 @@ class Idl(object): data = {} for column in six.itervalues(table.columns): data[column.name] = ovs.db.data.Datum.default(column.type) - row = table.rows[uuid] = Row(self, table, uuid, data) - return row + return Row(self, table, uuid, data) def __error(self): self._session.force_reconnect() @@ -844,7 +863,17 @@ class Row(object): vlog.err("attempting to write bad value to column %s (%s)" % (column_name, e)) return + # Remove prior version of the Row from the index if it has the indexed + # column set, and the column changing is an indexed column + if hasattr(self, column_name): + for idx in self._table.rows.indexes.values(): + if column_name in (c.column for c in idx.columns): + idx.remove(self) self._idl.txn._write(self, column, datum) + for idx in self._table.rows.indexes.values(): + # Only update the index if indexed columns change + if column_name in (c.column for c in idx.columns): + idx.add(self) def addvalue(self, column_name, key): self._idl.txn._txn_rows[self.uuid] = self @@ -972,8 +1001,8 @@ class Row(object): del self._idl.txn._txn_rows[self.uuid] else: self._idl.txn._txn_rows[self.uuid] = self - self.__dict__["_changes"] = None del self._table.rows[self.uuid] + self.__dict__["_changes"] = None def fetch(self, column_name): self._idl.txn._fetch(self, column_name) @@ -1145,6 +1174,10 @@ class Transaction(object): for row in six.itervalues(self._txn_rows): if row._changes is None: + # If we add the deleted row back to rows with _changes == None + # then __getattr__ will not work for the indexes + row.__dict__["_changes"] = {} + row.__dict__["_mutations"] = {} row._table.rows[row.uuid] = row elif row._data is None: del row._table.rows[row.uuid] diff --git a/tests/test-ovsdb.py b/tests/test-ovsdb.py index fc42a2d..8aca35b 100644 --- a/tests/test-ovsdb.py +++ b/tests/test-ovsdb.py @@ -289,10 +289,7 @@ def idltest_find_simple2(idl, i): def idltest_find_simple3(idl, i): - for row in six.itervalues(idl.tables["simple3"].rows): - if row.name == i: - return row - return None + return next(idl.index_equal("simple3", "simple3_by_name", i), None) def idl_set(idl, commands, step): @@ -579,6 +576,8 @@ def do_idl(schema_file, remote, *commands): else: schema_helper.register_all() idl = ovs.db.idl.Idl(remote, schema_helper) + if "simple3" in idl.tables: + idl.index_create("simple3", "simple3_by_name") if commands: error, stream = ovs.stream.Stream.open_block(

[ovs-dev,RFC] 1/1 Add multi-column index support for the Python IDL

Commit Message

Comments

Patch