scalability problem of router routes update

[Itsuro Oda]

Updating router routes takes long time when increasing a number of routes.
The critical problem is that it is CPU bound task of neutron-server and neutron-server can not reply for other request.

I show below a measurement example of neutron-server's CPU usage.

Setting routes to a router. (0 to N)
100 routes: 1 sec
1000 routes: 5 sec
10000 routes: 51 sec

I found validation check of parameter is inefficient. The following example support it too.

No change but just specify same routes to a router. (N to N, DB is not changed)
100 routes: <1 sec
1000 routes: 4 sec
10000 routes: 52 sec

Remove routes from a router. (N to 0)
100 routes: <1 sec
1000 routes: 8 sec
10000 routes: 750 sec

I found handling of record deletion is bad. It takes N**2 order.

[Itsuro Oda (oda-g)]

I will submit a fix.
After change the same measurement will be as follows.

Setting routes to a router. (0 to N)
100 routes: <1 sec
1000 routes: <1 sec
10000 routes: 15 sec

Remove routes from a router. (N to 0)
100 routes: <1 sec
1000 routes: <1 sec
10000 routes: 4 sec

[Openstack Gerrit (openstack-gerrit)]

Fix proposed to branch: master
Review: https://review.openstack.org/91506

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/91506
Committed: https://git.openstack.org/cgit/openstack/neutron/commit/?id=f55e451fb790b976d3fbd3a23dd8688bcc584c77
Submitter: Jenkins
Branch: master

commit f55e451fb790b976d3fbd3a23dd8688bcc584c77
Author: Itsuro Oda <email address hidden>
Date: Mon Apr 21 15:02:52 2014 +0900

    Performance improvement of router routes operations

    This patch fixes inefficiency of updating extra routes.
    * remove the code repeated by every routes in validation check.
    * remove searching a record to delete per record.

    Note: Unit tests are covered by existing ones. So no unit test added.

    Change-Id: Ia335ac21c65148063d330e4533a15a73962c43d8
    Closes-bug: #1312482