the speed of query user from ldap server is very slow

[jackning]

[Impact]

 * When using an LDAP backend for Keystone, the performance can be slow if there are
   a large number of users using the cloud. This is due in large part to querying the
   SQL database for the identity mapping information of each user in a separate transaction.
   For example, an environment with 12,000 users will result in 12,000 sql queries to the
   backend database in order to fulfill a user list request. This causes some admin
   functions in Horizon UI to take several minutes, which often exceeds the WSGI and any
   haproxy timeouts configured.

 * This is fixed by backporting a series of patches which caches previously fetched identity
   mapping information in a memcached instance and changes the logic to query all of the
   user id mapping by the domain the id mapping is in. Additionally, the keystone-manage
   command to sync the id mapping information with a backend database in an offline manner
   is included to allow offline syncing of the data.

[Test Case]

 * Install keystone using an ldap backend w/ large number of users.
 * List user information: openstack user list --domain <domain_id>
 * observe slow down

[Regression Potential]

 * For Mitaka, the caching backends such as memcached or mongodb will likely see more
   usage and an increased footprint due to additional data being cached. Caching the
   identity mapping information is now standard since Newton and no major issues have
   been seen coming from this.

 * This code affects the identity mapping between keystone user and the ldap user
   (essentially the bridge between the two). While it does not functionally alter the
   information that is mapped (e.g. no difference in how the identity mapping is calculated),
   it does alter a key code path for information regarding user identity mappings.

[Other Info]

 * These patches have been run and tested in a staging environment to production and
   have had exposure in the Mitaka path for approximately one month to show their stability.

[Original Description]

In our project, the speed of query user from ldap server is very slow,our ldap user number is 12,000,the query costs almost 45 seconds

The reason is that keystone will generate the uuid for the ldap users one by one and insert db.And second query time later,it also goes to db,not use the cache.
So adding the cache to improve the query speed

After adding @MEMOIZE to the following function
https://github.com/openstack/keystone/blob/master/keystone/identity/core.py#L580.
First query time almost costs 50 seconds,but second query time later it only costs 7 seconds.

So it is very necessary to improve this feature

[Guang Yee (guang-yee)]

You trying to list all 12,000 users at once, without filtering or list_limit? Please clarify.

[jackning (ningyougang)]

At present,we have no filtering or list_limit

[OpenStack Infra (hudson-openstack)]

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

[OpenStack Infra (hudson-openstack)]

Change abandoned by Jack Ning (<email address hidden>) on branch: master
Review: https://review.openstack.org/317307
Reason: a new review is committed, please refer to https://review.openstack.org/#/c/328820/2

[OpenStack Infra (hudson-openstack)]

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

[OpenStack Infra (hudson-openstack)]

Related fix proposed to branch: master
Review: https://review.openstack.org/343027

[OpenStack Infra (hudson-openstack)]

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

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/343027
Committed: https://git.openstack.org/cgit/openstack/keystone/commit/?id=29624d47e316d2e63f464b2d25043ec7598afa05
Submitter: Jenkins
Branch: master

commit 29624d47e316d2e63f464b2d25043ec7598afa05
Author: Boris Bobrov <email address hidden>
Date: Fri Jul 15 21:29:47 2016 +0300

    Prevent error when duplicate mapping is created

    The mapping has unique constraint and creating a mapping with the same
    local entity will fail. Creation of mapping with the same local entity
    might happen because of race condition, that would happen if 2 processes
    start mapping of the same local entity at the same time.

    Return the existing public_id if creation failed due to duplicate.

    Change-Id: Ic6e6ec9614e16a49c791dc6c06a4464d18be09be
    Related-Bug: 1582585

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/328820
Committed: https://git.openstack.org/cgit/openstack/keystone/commit/?id=53bb53a814324234aa4b798651a616e310396221
Submitter: Jenkins
Branch: master

commit 53bb53a814324234aa4b798651a616e310396221
Author: liuhongjiang <email address hidden>
Date: Mon Jun 13 08:11:16 2016 +0800

    Added cache for id mapping manager

    When using a identity driver without providing uuid, and using default
    sql id mapping driver, if there are lots of users, then it may take
    minutes to list users. Adding cache to the id mapping manager can
    improve the performance.

    After adding the cache, when listing 12000 users though the keystone
    api, and the time is reduced from about 75 seconds to 20 seconds.

    Closes-Bug: #1582585
    Change-Id: I72eeb88926d8babb09a61e99f6f594371987f393

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/343028
Committed: https://git.openstack.org/cgit/openstack/keystone/commit/?id=b1fdad9875542282abd630a6cdeed6686b0e5beb
Submitter: Jenkins
Branch: master

commit b1fdad9875542282abd630a6cdeed6686b0e5beb
Author: Boris Bobrov <email address hidden>
Date: Fri Jul 15 20:57:45 2016 +0300

    Add mapping_populate command

    Fetching users from LDAP requires creating public ids for them.
    id_mapping_api does that. Creating public ids is slow, because it
    requires performing N INSERTs for N users, and there is no way to
    work around that. It leads to very slow responses to queries like
    "list users".

    By pre-creating these public ids we improve API users' experience.

    Add keystone-manage mapping_populate command that creates id mapping entries
    for users.

    bp ldap-preprocessing
    Partial-Bug: 1582585
    Change-Id: I98f795854aee26f9e7f668372c47572d2b6d4f0f

[Thierry Carrez (ttx)]

This issue was fixed in the openstack/keystone 10.0.0.0b3 development milestone.

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/339294
Committed: https://git.openstack.org/cgit/openstack/keystone/commit/?id=f534f36246fd0b41bcdc2a664369507f9e299266
Submitter: Jenkins
Branch: master

commit f534f36246fd0b41bcdc2a664369507f9e299266
Author: Boris Bobrov <email address hidden>
Date: Fri Jul 8 02:49:03 2016 +0300

    Faster id mapping lookup

    id_mapping_api was designed to make a query per entity to fetch
    public ids. This lead to a very poor performance when there were many
    entries in LDAP. For example, for 15k entries 15k MySQL queries were
    required. For the first run 15k INSERTs were required, which makes
    things even worse.

    Change this behavior to fetch related mappings from MySQL as a list and
    perform the necessary join in-memory.

    bp ldap-preprocessing
    Partial-Bug: 1582585
    Change-Id: I2c266e91f2f05be760f8a3eea3738868243cc9c6

[Billy Olsen (billy-olsen)]

A patch for xenial-newton Ubuntu Cloud Archive

[Billy Olsen (billy-olsen)]

A patch for Mitaka version (xenial and the trusty-mitaka Ubuntu Cloud Archive)

[Billy Olsen (billy-olsen)]

[Impact]

 * When using an LDAP backend for Keystone, the performance can be slow if there are
   a large number of users using the cloud. This is due in large part to querying the
   SQL database for the identity mapping information of each user in a separate transaction.
   For example, an environment with 12,000 users will result in 12,000 sql queries to the
   backend database in order to fulfill a user list request. This causes some admin
   functions in Horizon UI to take several minutes, which often exceeds the WSGI and any
   haproxy timeouts configured.

 * This is fixed by backporting a series of patches which caches previously fetched identity
   mapping information in a memcached instance and changes the logic to query all of the
   user id mapping by the domain the id mapping is in. Additionally, the keystone-manage
   command to sync the id mapping information with a backend database in an offline manner
   is included to allow offline syncing of the data.

[Test Case]

 * Install keystone using an ldap backend w/ large number of users.
 * List user information: openstack user list --domain <domain_id>
 * observe slow down

[Regression Potential]

 * For Mitaka, the caching backends such as memcached or mongodb will likely see more
   usage and an increased footprint due to additional data being cached. Caching the
   identity mapping information is now standard since Newton and no major issues have
   been seen coming from this.

 * This code affects the identity mapping between keystone user and the ldap user
   (essentially the bridge between the two). While it does not functionally alter the
   information that is mapped (e.g. no difference in how the identity mapping is calculated),
   it does alter a key code path for information regarding user identity mappings.

[Other Info]

 * These patches have been run and tested in a staging environment to production and
   have had exposure in the Mitaka path for approximately one month to show their stability.

[Ubuntu Foundations Team Bug Bot (crichton)]

The attachment "newton-lp1582585.debdiff" seems to be a debdiff. The ubuntu-sponsors team has been subscribed to the bug report so that they can review and hopefully sponsor the debdiff. If the attachment isn't a patch, please remove the "patch" flag from the attachment, remove the "patch" tag, and if you are member of the ~ubuntu-sponsors, unsubscribe the team.

[This is an automated message performed by a Launchpad user owned by ~brian-murray, for any issue please contact him.]

[Corey Bryant (corey.bryant)]

Thanks for the patches Billy. I've reviewed the patches and I think they justify an SRU.

Some notes from my review:
* Patches 1 through 3 are fairly straight forward cherry-picks that are already in Newton and require a very minimal changes to apply to Mitaka.
* Patch 3 adds a new 'mapping_populate' subcommand to keystone-manage that enables creation of id mapping entries. This is a feature, and while we typically don't backport features, I think this case is warranted as it is an optional command that allows an admin to pre-create pubic IDs to prevent users from hitting costly CLI/API calls.
* Patch requires additional code to handle backends that don't support get_domain_mapping_list(). I want to make sure testing of the fallback path is performed in addition to the new path.

To avoid regression of existing consumers, the OpenStack team will run their continuous integration tests against the packages that are in -proposed.

[Corey Bryant (corey.bryant)]

The last bullet above is in reference to faster-id-mapping-lookup.patch and fallback-for-custom-id-map-drivers.patch.

And patch 1-3 are in reference to:
* Patch 1: prevent-error-when-duplicate-mapping-is-created.patch
* Patch 2: added-cache-for-id-mapping-manager.patch
* Patch 3: add-mapping_populate-command.patch

[Corey Bryant (corey.bryant)]

This is currently building in newton-staging, and will be promoted to newton-proposed once built. I've also uploaded the new package version for xenial to the unapproved queue where it is awaiting review by the SRU team.

[Corey Bryant (corey.bryant)]

Hello jackning, or anyone else affected,

Accepted keystone into newton-proposed. The package will build now and be available in the Ubuntu Cloud Archive in a few hours, and then in the -proposed repository.

Please help us by testing this new package. To enable the -proposed repository:

  sudo add-apt-repository cloud-archive:newton-proposed
  sudo apt-get update

Your feedback will aid us getting this update out to other Ubuntu users.

If this package fixes the bug for you, please add a comment to this bug, mentioning the version of the package you tested, and change the tag from verification-newton-needed to verification-newton-done. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification-newton-failed. In either case, details of your testing will help us make a better decision.

Further information regarding the verification process can be found at https://wiki.ubuntu.com/QATeam/PerformingSRUVerification . Thank you in advance!

[Łukasz Zemczak (sil2100)]

Hello jackning, or anyone else affected,

Accepted keystone into xenial-proposed. The package will build now and be available at https://launchpad.net/ubuntu/+source/keystone/2:9.3.0-0ubuntu3.2 in a few hours, and then in the -proposed repository.

Please help us by testing this new package. See https://wiki.ubuntu.com/Testing/EnableProposed for documentation on how to enable and use -proposed.Your feedback will aid us getting this update out to other Ubuntu users.

If this package fixes the bug for you, please add a comment to this bug, mentioning the version of the package you tested and change the tag from verification-needed-xenial to verification-done-xenial. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification-failed-xenial. In either case, without details of your testing we will not be able to proceed.

Further information regarding the verification process can be found at https://wiki.ubuntu.com/QATeam/PerformingSRUVerification . Thank you in advance!

[Corey Bryant (corey.bryant)]

Hello jackning, or anyone else affected,

Accepted keystone into mitaka-proposed. The package will build now and be available in the Ubuntu Cloud Archive in a few hours, and then in the -proposed repository.

Please help us by testing this new package. To enable the -proposed repository:

  sudo add-apt-repository cloud-archive:mitaka-proposed
  sudo apt-get update

Your feedback will aid us getting this update out to other Ubuntu users.

If this package fixes the bug for you, please add a comment to this bug, mentioning the version of the package you tested, and change the tag from verification-mitaka-needed to verification-mitaka-done. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification-mitaka-failed. In either case, details of your testing will help us make a better decision.

Further information regarding the verification process can be found at https://wiki.ubuntu.com/QATeam/PerformingSRUVerification . Thank you in advance!

[raja (jiangpch)]

for the newton-proposed:

As our ldap server has a limit exceed setting, so I configured

```
[ldap]
page_size = 20000
```

before using the keystone in proposed repo, the keystone version is:
```
root@ubuntu:~# apt-cache policy keystone
keystone:
  Installed: 2:10.0.3-0ubuntu1~cloud0
  Candidate: 2:10.0.3-0ubuntu1~cloud1
  Version table:
     2:10.0.3-0ubuntu1~cloud1 500
        500 http://ubuntu-cloud.archive.canonical.com/ubuntu xenial-proposed/newton/main amd64 Packages
        500 http://ubuntu-cloud.archive.canonical.com/ubuntu xenial-proposed/newton/main i386 Packages
 *** 2:10.0.3-0ubuntu1~cloud0 500
        500 http://ubuntu-cloud.archive.canonical.com/ubuntu xenial-updates/newton/main amd64 Packages
        500 http://ubuntu-cloud.archive.canonical.com/ubuntu xenial-updates/newton/main i386 Packages
        100 /var/lib/dpkg/status
     2:9.3.0-0ubuntu3.1 500
        500 http://archive.ubuntu.com/ubuntu xenial-updates/main amd64 Packages
        500 http://archive.ubuntu.com/ubuntu xenial-updates/main i386 Packages
        500 http://archive.ubuntu.com/ubuntu xenial-security/main amd64 Packages
        500 http://archive.ubuntu.com/ubuntu xenial-security/main i386 Packages
     2:9.0.0-0ubuntu1 500
        500 http://archive.ubuntu.com/ubuntu xenial/main amd64 Packages
        500 http://archive.ubuntu.com/ubuntu xenial/main i386 Packages

```

list users in ldap will take about 7-11 seconds:

```
root@ubuntu:~# time openstack user list --domain default
...
real 0m8.522s
user 0m1.476s
sys 0m0.108s

```

after using the package in proposed repo, it takes about 7-11 seconds:

```
root@ubuntu:~# time openstack user list --domain default
...
real 0m8.637s
user 0m1.484s
sys 0m0.108s

```

I execute above commands for several times, it seems that the patch doesn't have a strong performance improvement

[raja (jiangpch)]

the ubuntu release is: DISTRIB_DESCRIPTION="Ubuntu 16.04.3 LTS"

[raja (jiangpch)]

and for the mitaka-proposed, looks like the same.

the keystone version is:

```
root@ubuntu:~# apt-cache policy keystone
keystone:
  Installed: 2:9.3.0-0ubuntu3.1~cloud0
  Candidate: 2:9.3.0-0ubuntu3.1~cloud0
  Version table:
 *** 2:9.3.0-0ubuntu3.1~cloud0 0
        500 http://ubuntu-cloud.archive.canonical.com/ubuntu/ trusty-updates/mitaka/main amd64 Packages
        100 /var/lib/dpkg/status
     1:2014.1.5-0ubuntu1 0
        500 http://us.archive.ubuntu.com/ubuntu/ trusty-updates/main amd64 Packages
     1:2014.1.3-0ubuntu2.1 0
        500 http://security.ubuntu.com/ubuntu/ trusty-security/main amd64 Packages
     1:2014.1-0ubuntu1 0
        500 http://us.archive.ubuntu.com/ubuntu/ trusty/main amd64 Packages
```

but listing users still doesn't take much time, about 10 seconds:

```
root@ubuntu:~# time openstack user list --domain default
real 0m9.662s
user 0m1.284s
sys 0m0.232s
```

so seems that I can't reproduce this problem, do you have any suggestions?

[Billy Olsen (billy-olsen)]

@raja - can you share your keystone config (with sensitive parts redacted)? How many users are in your ldap directory which is configured as the backend domain?

[Jack Ivanov (gunph1ld)]

I have the same issue on Ocata (keystone-11.0.3), each request to keystone takes 15-20 sec.
There are more then 150000 records in the id_mapping table.
Does the patch actually fix the problem?

[Billy Olsen (billy-olsen)]

@gunph1ld - these changes are already in the ocata code you are running. While 15-20 seconds is still not fast, it is generally faster than the previous code which would issue a query per entry record in the id_mapping table.

[Billy Olsen (billy-olsen)]

Tests completed below with 12,500 users in ldap tree

=== Mitaka Results ===

$ dpkg -l | grep keystone
ii keystone 2:9.3.0-0ubuntu3.1 all OpenStack identity service - Daemons

$ time openstack user list --domain userdomain
...
real 2m3.608s
user 0m6.848s
sys 0m0.548s

==== Mitaka Proposed ====
$ dpkg -l | grep keystone
ii keystone 2:9.3.0-0ubuntu3.2 all OpenStack identity service - Daemons

$ time openstack user list --domain userdomain
...
real 0m16.695s
user 0m6.708s
sys 0m0.328s

=== Newton Results ===

$ dpkg -l | grep keystone
ii keystone 2:10.0.3-0ubuntu1~cloud0 all OpenStack identity service - Daemons

$ time openstack user list --domain userdomain
...
real 0m22.626s
user 0m6.232s
sys 0m0.492s

=== Newton-Staging Results ===

$ dpkg -l | grep keystone
ii keystone 2:10.0.3-0ubuntu1~cloud1 all OpenStack identity service - Daemons

$ time openstack user list --domain userdomain
...
real 0m16.297s
user 0m8.692s
sys 0m0.452s

[Billy Olsen (billy-olsen)]

Adding tar.gz of /etc/keystone for reference

[Łukasz Zemczak (sil2100)]

The verification of the Stable Release Update for keystone has completed successfully and the package has now been released to -updates. Subsequently, the Ubuntu Stable Release Updates Team is being unsubscribed and will not receive messages about this bug report. In the event that you encounter a regression using the package from -updates please report a new bug using ubuntu-bug and tag the bug report regression-update so we can easily find any regressions.

[Launchpad Janitor (janitor)]

This bug was fixed in the package keystone - 2:9.3.0-0ubuntu3.2

---------------
keystone (2:9.3.0-0ubuntu3.2) xenial; urgency=medium

  * LDAP backend performance improvements (LP: #1582585)
    - d/p/prevent-error-when-duplicate-mapping-is-created.patch:
      Handle races for creating id mappings.
    - d/p/added-cache-for-id-mapping-manager.patch: Add a cache to
      the id mapping manager to improve performance.
    - d/p/add-mapping_populate-command.patch: Add a keystone-manage
      command to populate id mappings between backend identity
      provider and keystone database.
    - d/p/faster-id-mapping-lookup.patch: Allow querying for all
      public ids in a domain at once instead of N queries (one per
      entity).
    - d/p/fallback-for-custom-id-map-drivers.patch: Add fallback
      path for faster-id-mapping lookup for any customer id mapping
      drivers that may be in use or existing deployments.

 -- Billy Olsen <email address hidden> Wed, 10 Jan 2018 14:24:36 -0700

[Corey Bryant (corey.bryant)]

Regression testing for newton and mitaka were successful:

xenial-newton-proposed:

Ran: 102 tests in 1448.5591 sec.
 - Passed: 94
 - Skipped: 8
 - Expected Fail: 0
 - Unexpected Success: 0
 - Failed: 0
Sum of execute time for each test: 919.5493 sec.

xenial-mitaka-proposed:

Ran: 102 tests in 1031.4567 sec.
 - Passed: 94
 - Skipped: 8
 - Expected Fail: 0
 - Unexpected Success: 0
 - Failed: 0
Sum of execute time for each test: 621.0117 sec.

trusty-mitaka-proposed:

Ran: 102 tests in 1036.5808 sec.
 - Passed: 94
 - Skipped: 8
 - Expected Fail: 0
 - Unexpected Success: 0
 - Failed: 0
Sum of execute time for each test: 603.3084 sec.

[Corey Bryant (corey.bryant)]

The verification of the Stable Release Update for keystone has completed successfully and the package has now been released to -updates. In the event that you encounter a regression using the package from -updates please report a new bug using ubuntu-bug and tag the bug report regression-update so we can easily find any regressions.

[Corey Bryant (corey.bryant)]

This bug was fixed in the package keystone - 2:10.0.3-0ubuntu1~cloud1
---------------

 keystone (2:10.0.3-0ubuntu1~cloud1) xenial-newton; urgency=medium
 .
   * LDAP backend performance improvements (LP: #1582585)
     - d/p/faster-id-mapping-lookup.patch: Allow querying for all
       public ids in a domain at once instead of N queries (one per
       entity).
     - d/p/fallback-for-custom-id-map-drivers.patch: Add fallback
       path for faster-id-mapping lookup for any customer id mapping
       drivers that may be in use or existing deployments.

[Corey Bryant (corey.bryant)]

The verification of the Stable Release Update for keystone has completed successfully and the package has now been released to -updates. In the event that you encounter a regression using the package from -updates please report a new bug using ubuntu-bug and tag the bug report regression-update so we can easily find any regressions.

[Corey Bryant (corey.bryant)]

This bug was fixed in the package keystone - 2:9.3.0-0ubuntu3.2~cloud0
---------------

 keystone (2:9.3.0-0ubuntu3.2~cloud0) trusty-mitaka; urgency=medium
 .
   * New update for the Ubuntu Cloud Archive.
 .
 keystone (2:9.3.0-0ubuntu3.2) xenial; urgency=medium
 .
   * LDAP backend performance improvements (LP: #1582585)
     - d/p/prevent-error-when-duplicate-mapping-is-created.patch:
       Handle races for creating id mappings.
     - d/p/added-cache-for-id-mapping-manager.patch: Add a cache to
       the id mapping manager to improve performance.
     - d/p/add-mapping_populate-command.patch: Add a keystone-manage
       command to populate id mappings between backend identity
       provider and keystone database.
     - d/p/faster-id-mapping-lookup.patch: Allow querying for all
       public ids in a domain at once instead of N queries (one per
       entity).
     - d/p/fallback-for-custom-id-map-drivers.patch: Add fallback
       path for faster-id-mapping lookup for any customer id mapping
       drivers that may be in use or existing deployments.