From patchwork Mon Apr 9 20:03:03 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Terry Wilson X-Patchwork-Id: 896388 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 40Kh7t19rPz9s02 for ; Tue, 10 Apr 2018 06:03:38 +1000 (AEST) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 0BF66D8E; Mon, 9 Apr 2018 20:03:24 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 68E75D8E for ; Mon, 9 Apr 2018 20:03:22 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mx1.redhat.com (mx3-rdu2.redhat.com [66.187.233.73]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 2D70C66F for ; Mon, 9 Apr 2018 20:03:21 +0000 (UTC) Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.rdu2.redhat.com [10.11.54.3]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 7CAFC722C3 for ; Mon, 9 Apr 2018 20:03:20 +0000 (UTC) Received: from red6.localdomain (ovpn-112-44.phx2.redhat.com [10.3.112.44]) by smtp.corp.redhat.com (Postfix) with ESMTP id A43F711422D9; Mon, 9 Apr 2018 20:03:19 +0000 (UTC) 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> X-Scanned-By: MIMEDefang 2.78 on 10.11.54.3 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.11.55.2]); Mon, 09 Apr 2018 20:03:20 +0000 (UTC) X-Greylist: inspected by milter-greylist-4.5.16 (mx1.redhat.com [10.11.55.2]); Mon, 09 Apr 2018 20:03:20 +0000 (UTC) for IP:'10.11.54.3' DOMAIN:'int-mx03.intmail.prod.int.rdu2.redhat.com' HELO:'smtp.corp.redhat.com' FROM:'twilson@redhat.com' RCPT:'' X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [ovs-dev] [RFC] [PATCH] 1/1 Add multi-column index support for the Python IDL X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org From: Terry Wilson This adds multi-column index support for the Python IDL that is similar to the feature in the C IDL. Signed-off-by: Terry Wilson --- python/automake.mk | 1 + python/ovs/db/custom_index.py | 151 ++++++++++++++++++++++++++++++++++++++++++ python/ovs/db/idl.py | 55 ++++++++++++--- tests/test-ovsdb.py | 7 +- 4 files changed, 199 insertions(+), 15 deletions(-) create mode 100644 python/ovs/db/custom_index.py 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(