ovsdbapp

DbListCommand taking too long when there's too many records

Bug #1769897 reported by Daniel Alvarez
10
This bug affects 2 people
Affects Status Importance Assigned to Milestone
ovsdbapp
Fix Released
Undecided
Daniel Alvarez

Bug Description

When there are too many records and we call DbListCommand it's very likely to get a timeout exception. This is mainly because that it can be an O(n^2) operation as it will go through all the passed in records to retrieve the uuids and this operation goes through all the existing rows of the table to match by the index column.

ie.
for record in self.records:
     row_by_record()
        |
         -> row_by_value() (which iterates over all elements in the table and calls Row.getattr() that can be costly [0] as it's converting to/from Datum/Atom and creating new objects).

This O(n^2) operation can be avoided if we simply retrieve all the elements and remove all those present in the passed in arguments making the method be O(n).

For example, with 2000 ports, the following code takes 8 seconds:

import logging

from ovs.db import idl
from ovsdbapp.backend.ovs_idl import connection
from ovsdbapp.backend.ovs_idl import idlutils
from ovsdbapp.schema.open_vswitch import impl_idl as idl_ovs

TIMEOUT_SEC = 3600

def connect():
    connection_string = "tcp:127.0.0.1:6640"
    helper = idlutils.get_schema_helper(connection_string, 'Open_vSwitch')
    tables = ('Open_vSwitch', 'Bridge', 'Port', 'Interface')
    for table in tables:
        helper.register_table(table)
    ovs_idl = idl.Idl(connection_string, helper)
    conn = connection.Connection(ovs_idl, timeout=TIMEOUT_SEC)
    return idl_ovs.OvsdbIdl(conn)

def get_port_name_list(ovs_idl):
    return ovs_idl.list_ports('br-int').execute(check_error=False)

def main():
    ovs_idl = connect()
    port_names = get_port_name_list(ovs_idl)
    ovs_idl.db_list('Interface', port_names,
                    columns=['name', 'external_ids', 'ofport'], if_exists=False).execute(check_error=False)

if __name__ == "__main__":
    logging.basicConfig()
    main()

# time python dblist.py
Loop took 8.09

real 0m12.781s
user 0m12.242s
sys 0m0.166s

And with the optimizations (I'll propose the patch now):

# time python dblist.py
Loop took 0.15

real 0m4.577s
user 0m4.269s
sys 0m0.126s

[0] https://github.com/openvswitch/ovs/blob/master/python/ovs/db/idl.py#L793

Revision history for this message
Bogdan Dobrelya (bogdando) wrote :

For ocata, addressed by https://review.openstack.org/#/c/566912

Changed in ovsdbapp:
status: New → Confirmed
Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix proposed to ovsdbapp (stable/queens)

Fix proposed to branch: stable/queens
Review: https://review.openstack.org/567593

Daniel Alvarez (dalvarezs)
Changed in ovsdbapp:
assignee: nobody → Daniel Alvarez (dalvarezs)
Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix merged to ovsdbapp (master)

Reviewed: https://review.openstack.org/566901
Committed: https://git.openstack.org/cgit/openstack/ovsdbapp/commit/?id=476b174f7d303c501fa2f3b91efda659ed9b9f3d
Submitter: Zuul
Branch: master

commit 476b174f7d303c501fa2f3b91efda659ed9b9f3d
Author: Daniel Alvarez <email address hidden>
Date: Tue May 8 16:02:56 2018 +0200

    Improve DbListCommand operation from O(n^2) to O(n)

    Right now the DbListCommand retrieves the uuid's of all the elements
    passed in as argument. This is an O(n^2) operation so when the number
    of elements in a grows it's likely that we get Timeout Exceptions.

    Instead of doing this, whenever possible, we'll retrieve all the
    elements (from the in-memory replica) and only fetch those who were
    passed as arguments avoiding the O(n^2) operation.

    Change-Id: I71411e5dd68753eb3825f8b0e91009f87de1b260
    Closes-Bug: #1769897

Changed in ovsdbapp:
status: Confirmed → Fix Released
Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix proposed to ovsdbapp (stable/pike)

Fix proposed to branch: stable/pike
Review: https://review.openstack.org/567603

Revision history for this message
Miguel Angel Ajo (mangelajo) wrote :

We need to raise the importance of this bug to the maximum

Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix merged to ovsdbapp (stable/queens)

Reviewed: https://review.openstack.org/567593
Committed: https://git.openstack.org/cgit/openstack/ovsdbapp/commit/?id=fd64d41ea6f208a5752fbcd45952a04633ee1392
Submitter: Zuul
Branch: stable/queens

commit fd64d41ea6f208a5752fbcd45952a04633ee1392
Author: Daniel Alvarez <email address hidden>
Date: Tue May 8 16:02:56 2018 +0200

    Improve DbListCommand operation from O(n^2) to O(n)

    Right now the DbListCommand retrieves the uuid's of all the elements
    passed in as argument. This is an O(n^2) operation so when the number
    of elements in a grows it's likely that we get Timeout Exceptions.

    Instead of doing this, whenever possible, we'll retrieve all the
    elements (from the in-memory replica) and only fetch those who were
    passed as arguments avoiding the O(n^2) operation.

    (cherry picked from 476b174f7d303c501fa2f3b91efda659ed9b9f3d)
    Change-Id: I71411e5dd68753eb3825f8b0e91009f87de1b260
    Closes-Bug: #1769897

tags: added: in-stable-queens
Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix merged to ovsdbapp (stable/pike)

Reviewed: https://review.openstack.org/567603
Committed: https://git.openstack.org/cgit/openstack/ovsdbapp/commit/?id=ab6e1fee0c04d3adfb6f3813f1ce116d89193aad
Submitter: Zuul
Branch: stable/pike

commit ab6e1fee0c04d3adfb6f3813f1ce116d89193aad
Author: Daniel Alvarez <email address hidden>
Date: Thu May 10 16:21:22 2018 +0200

    Improve DbListCommand operation from O(n^2) to O(n)

    Right now the DbListCommand retrieves the uuid's of all the elements
    passed in as argument. This is an O(n^2) operation so when the number
    of elements in a grows it's likely that we get Timeout Exceptions.

    Instead of doing this, whenever possible, we'll retrieve all the
    elements (from the in-memory replica) and only fetch those who were
    passed as arguments avoiding the O(n^2) operation.

    NOTE: this cherry pick conflicted because in stable/pike, the commands.py
    file was in different location.

    Closes-Bug: #1769897
    (cherry picked from fd64d41ea6f208a5752fbcd45952a04633ee1392)
    Signed-off-by: Daniel Alvarez <email address hidden>

    Change-Id: Iacded885bb852315263ee926b9af5a1c3dc0dbba

tags: added: in-stable-pike
Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix included in openstack/ovsdbapp 0.10.1

This issue was fixed in the openstack/ovsdbapp 0.10.1 release.

Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix included in openstack/ovsdbapp 0.4.3

This issue was fixed in the openstack/ovsdbapp 0.4.3 release.

Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix included in openstack/ovsdbapp 0.11.0

This issue was fixed in the openstack/ovsdbapp 0.11.0 release.

Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix included in openstack/ovsdbapp 0.12.0

This issue was fixed in the openstack/ovsdbapp 0.12.0 release.

Revision history for this message
OpenStack Infra (hudson-openstack) wrote : Fix included in openstack/neutron ocata-eol

This issue was fixed in the openstack/neutron ocata-eol release.

To post a comment you must log in.
This report contains Public information  
Everyone can see this information.
Subscribing...

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.