#375494: Restrict the number of nodes held in the node_load() static cache adds an LRU cache for the entity cache, I wanted to see if we could make a generic in-memory LRU cache that could maybe be used elsewhere.

Turns out to be reasonably simple to write. I haven't benchmarked this or anything yet, just wanted to get something that works first. It does not yet allow for adding multiple items to the cache at once, that may be a useful feature to add for the entity case.

Patch only adds the class and a unit test, but marking CNR for the bot and hopefully feedback.

Files: 
CommentFileSizeAuthor
#43 interdiff.txt4.16 KBdawehner
#37 1199866.patch35.82 KBcatch
#37 interdiff.txt3.96 KBcatch
#35 1199866-combined.patch34.15 KBcatch
#32 1199866-combined.patch34.15 KBcatch
#32 1199866-do-not-test.patch6.73 KBcatch
#21 13-21-interdiff.txt400 bytesalexpott
#21 1199866-21-lru-cache-backend.patch6.88 KBalexpott
PASSED: [[SimpleTest]]: [PHP 5.4 MySQL] 76,081 pass(es). View
#13 1199866-13-lru-cache-backend.patch6.8 KBalexpott
PASSED: [[SimpleTest]]: [MySQL] 40,675 pass(es). View
#10 1199866-10-lru-cache-backend.patch5.54 KBalexpott
FAILED: [[SimpleTest]]: [MySQL] 36,915 pass(es), 1 fail(s), and 0 exception(s). View
#8 1199866-8-lru-cache-backend.patch9.92 KBalexpott
PASSED: [[SimpleTest]]: [MySQL] 36,904 pass(es). View
#6 1199866-6-lru-cache-backend.patch6.7 KBalexpott
PASSED: [[SimpleTest]]: [MySQL] 36,906 pass(es). View
lru.patch4.31 KBcatch
PASSED: [[SimpleTest]]: [MySQL] 32,204 pass(es). View

Comments

franz’s picture

Just tested, seems to be working neatly.

// Replace the item in first position in the array.

I was mislead by this comment to believe the item was being replaced with the new one - which is not the case and would be nonsense. Maybe something like "Drop the first item - least recently used - to make room for the new item." would be clearer.

So currently entity controllers do like '$cache += $array_of_items;' which is not supported by ArrayObject. I guess a simple method that gets the items array as argument and iterates over them adding could do for now, right? Unless there is some performance impact in adding one by one.

catch’s picture

I've been pondering multiple add but haven't yet figure it out.

There's two issues:

- iterating is probably going to be a bit slower than +=, although since it only happens on (static) cache misses it might be fine.

- there is a chance that more items get added to the cache than it has capacity for - say you have a 30 limit but a list of 50 items all loaded at once.

franz’s picture

I thought about the second issue. And if you merge both - iterating a number of items above limit - we would most likely get a performance issue because of all the removals.

We could have a private property "$this->bypass" that defaults to FALSE. If it is true, offsetSet() would only call parent::offsetSet(). So this property can be used by an addMultiple() method so that it would handle removals and additions to $this->positions[] on itself and only once, avoiding endless iterations.

Concerning the second issue again, a simple solution would be to just cache a chunk of the maximum size, could be the last n items of the loaded items.

pounard’s picture

Maybe this should be implemented using the cache backend interface: we could then have an in memory-lru working implementation ready to be used there #1596472: Replace hard coded static cache of entities with cache backends, which would then make #375494: Restrict the number of nodes held in the node_load() static cache a duplicate that should be closed.

One stone, two birds.

catch’s picture

Yep, beat me to it :)

alexpott’s picture

FileSize
6.7 KB
PASSED: [[SimpleTest]]: [MySQL] 36,906 pass(es). View

Moved catch's LRU implementation to a cache backend.

There's more work to do sort out getMultiple, deletePrefix, expire, garbageCollection, invalidateTags...

pounard’s picture

This should probably implement the full cache backend interface, I see some missing methods. [EDIT: Sometime I read too quickly sorry.] This also probably would mean it'd need to be decoupled from the LRU class and use its own implementation instead (because of advanced features such as tags etc)?

alexpott’s picture

FileSize
9.92 KB
PASSED: [[SimpleTest]]: [MySQL] 36,904 pass(es). View

Merged work from #1637478: Add a PHP array cache backend to fully implement CacheBackend

pounard’s picture

I think you are doing the work in the wrong way, we should first finish the work of #1637478: Add a PHP array cache backend then continue this issue on a sane basis?

alexpott’s picture

FileSize
5.54 KB
FAILED: [[SimpleTest]]: [MySQL] 36,915 pass(es), 1 fail(s), and 0 exception(s). View

Just for fun and because I'm not always sane :) ... here's is an implementation that extends Pounard's latest patch on #1637478: Add a PHP array cache backend. This will fail tests as that issue is not committed yet.

pounard’s picture

You're as sane as me, just the code from the other issue definitely wasn't.

Status: Needs review » Needs work

The last submitted patch, 1199866-10-lru-cache-backend.patch, failed testing.

alexpott’s picture

FileSize
6.8 KB
PASSED: [[SimpleTest]]: [MySQL] 40,675 pass(es). View

This patch is a reroll and extends the GenericCacheBackendUnitTestBase from #1637478: Add a PHP array cache backend

pounard’s picture

Serious stuff can now happen, good to see this.

alexpott’s picture

Status: Needs work » Needs review

Go testbot go!!!!

catch’s picture

We should use straight ArrayAccess for the LRU cache, doesn't need to be an ArrayObject I think, can't remember why I did that in the first place.

Or do we want to go as far as inlining the logic into the backend itself?

Thanks for keeping this updated!

Lars Toomre’s picture

FYI ... LRUArrayObject.php file is missing @file docblock at the top of the source code.

pounard’s picture

I'm OK with straight array access, but even better we could just implement it as a normal cache backend and use it into the CacheChain as soon as it can land. Then, the LRU usage would be fully transparent and its interface as a clear as the cache interface itself.

alexpott’s picture

Status: Needs review » Needs work

@pounard it is

+++ b/core/lib/Drupal/Core/Cache/MemoryLRUBackend.phpundefined
@@ -0,0 +1,95 @@
+class MemoryLRUBackend extends MemoryBackend {

a CacheBackend :) - because MemoryBackend is

alexpott’s picture

Status: Needs work » Needs review

dreditor changed the status... not fair.

alexpott’s picture

FileSize
6.88 KB
PASSED: [[SimpleTest]]: [PHP 5.4 MySQL] 76,081 pass(es). View
400 bytes

If I change it to ArrayAccess I get the following error:

Fatal error: Class Drupal\Component\Utility\LRUArrayObject cannot extend from interface ArrayAccess in /Users/alex/dev/sites/drupal8alt.dev/core/lib/Drupal/Component/Utility/LRUArrayObject.php on line 70

Implemented #17

catch’s picture

Should just be implements instead of extends?

catch’s picture

Hmm not quite though, we might need to add a bit more that ArrayObject gives us for free currently, but shouldn't be a big change I'd hope.

alexpott’s picture

It's extending the new MemoryBackend so it doesn't have to have exactly the same functions... otherwise it'd be implementing the CacheBackend interface.

fubhy’s picture

This might be a really stupid question but does it maybe make sense to go with memory_get_usage() and restrict the cache by memory usage instead of slots? The slots don't really resemble the actual memory usage usually.

Fabianx’s picture

#25: That IMHO would only work if several items are added to one slot, but the problem then is that those can be updated independently so I don't see how this could work.

catch’s picture

For actual memory usage I've been wanting to try using weak references (http://php.net/manual/en/book.weakref.php), I don't really see a way to take into account the memory limit without something like that. It's a PECL module so would need to be contrib though.

fubhy’s picture

We would have to track the memory usage of an item when we add it to the cache... Like so:

$before = memory_get_usage();
add_item_to_cache($item);
$after = memory_get_usage();
$usage_of_item = $after - $before;

Will get a bit more tricky once we start kicking out items once we hit the limit. But yeah, it's possible by simply using memory_get_usage(). The only question is how well that would perform in general.

Fabianx’s picture

Issue summary: View changes
Status: Needs review » Needs work

So what is nice about #28 is that we could say:

- Store only 8 MB of node objects in the static node cache, but allow a minimum of 8 slots.
- It is getting a little tricky if a reference is dropped however, as the node's object memory would be 0 effectively at time of insertion

But if we assume that its cached when loaded fresh, that should work reasonabiy well and with low memory it

To the patch itself:

Should unset() not update the positions array as well, to free up slots?

Version: 8.0.x-dev » 8.1.x-dev

Drupal 8.0.6 was released on April 6 and is the final bugfix release for the Drupal 8.0.x series. Drupal 8.0.x will not receive any further development aside from security fixes. Drupal 8.1.0-rc1 is now available and sites should prepare to update to 8.1.0.

Bug reports should be targeted against the 8.1.x-dev branch from now on, and new development or disruptive changes should be targeted against the 8.2.x-dev branch. For more information see the Drupal 8 minor version schedule and the Allowed changes during the Drupal 8 release cycle.

catch’s picture

Version: 8.1.x-dev » 8.3.x-dev
Status: Needs work » Needs review
Parent issue: » #1596472: Replace hard coded static cache of entities with cache backends
FileSize
6.73 KB
34.15 KB

Here's a re-roll just under four years later. No point doing an interdiff.

Depends on #1596472: Replace hard coded static cache of entities with cache backends.

Adds a new class LruStaticCache which extends from StaticCache. This implements the same LRU logic as the previous patches. Added support for invalidate/invalidateTags etc. and new unit tests.

Next step would be to swap the service definition for static_cache to use the LRU version.

To see if this works we really want a script that creates then loads a few thousand nodes recording the memory usage before/after.

Status: Needs review » Needs work

The last submitted patch, 32: 1199866-combined.patch, failed testing.

catch’s picture

Status: Needs work » Needs review
catch’s picture

Unit test is green.

Here's a patch that uses this for the entity cache, if the whole test suite passes then memory test should be viable.

dawehner’s picture

  1. +++ b/core/lib/Drupal/Core/Cache/StaticCache/LruStaticCache.php
    @@ -0,0 +1,164 @@
    +    // If there are still available slots, decrement the counter.
    +    if ($this->availableSlots) {
    +      $this->availableSlots--;
    +    }
    +    // Otherwise remove the least recently used item.
    +    else {
    +      $key = array_shift($this->positions);
    +      unset($this->cache[$key]);
    +    }
    

    What happens if you set a value which is already in the slots itself? Couldn't you optimize to not store one value twice?

  2. +++ b/core/lib/Drupal/Core/Cache/StaticCache/LruStaticCache.php
    @@ -0,0 +1,164 @@
    +    $this->availableSlots++;
    +    $current_position = array_search($cid, $this->positions);
    +    unset($this->positions[$current_position]);
    +    parent::delete($cid);
    

    What happens if the item doesn't exist yet. Shouldn't we check whether there is an item first?

  3. +++ b/core/lib/Drupal/Core/Cache/StaticCache/StaticCache.php
    @@ -0,0 +1,65 @@
    +/**
    + * Defines a static cache implementation.
    + *
    + * Stores cache items in memory using a PHP array.
    + *
    + * @ingroup cache
    + */
    +class StaticCache extends MemoryBackend implements StaticCacheInterface {
    

    It would be nice to explain the difference between MemoryBackend and StaticCache

  4. +++ b/core/lib/Drupal/Core/Config/Entity/ConfigEntityStorage.php
    @@ -104,9 +105,12 @@ class ConfigEntityStorage extends EntityStorageBase implements ConfigEntityStora
    +    $static_cache = isset($static_cache) ? $static_cache : \Drupal::service('static_cache');
    
    +++ b/core/lib/Drupal/Core/Entity/ContentEntityStorageBase.php
    @@ -43,9 +44,12 @@
    +    $static_cache = isset($static_cache) ? $static_cache : \Drupal::service('static_cache');
    
    +++ b/core/lib/Drupal/Core/Entity/EntityStorageBase.php
    @@ -73,18 +74,28 @@
    +  public function __construct(EntityTypeInterface $entity_type, StaticCacheInterface $static_cache = NULL) {
    ...
    +    $this->staticCache = isset($static_cache) ? $static_cache : \Drupal::service('static_cache');
    

    Do we need the BC in every of those 3 levels?

catch’s picture

Patch should fix the first three points of #36, those were bugs in the original patch from four years ago too. Added some extra test coverage for the first case.

With #4, you could extend from any one of those classes individually, so I think we do?

dawehner’s picture

With #4, you could extend from any one of those classes individually, so I think we do?

Won't ConfigEntityStorage and ContentEntityStorageBase fallback to EntityStorageBase, given that we pass along $static_cache to it?

Status: Needs review » Needs work

The last submitted patch, 37: 1199866.patch, failed testing.

dawehner’s picture

Is this really a jenkins issue?

09:03:13 Slave went offline during the build
09:03:13 ERROR: Connection was broken: java.io.EOFException
09:03:13 	at org.jenkinsci.remoting.nio.NioChannelHub$3.run(NioChannelHub.java:613)
09:03:13 	at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
09:03:13 	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
09:03:13 	at hudson.remoting.SingleLaneExecutorService$1.run(SingleLaneExecutorService.java:112)
09:03:13 	at jenkins.util.ContextResettingExecutorService$1.run(ContextResettingExecutorService.java:28)
09:03:13 	at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
09:03:13 	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
09:03:13 	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
09:03:13 	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
09:03:13 	at java.lang.Thread.run(Thread.java:745)
09:03:13 

The last submitted patch, 37: 1199866.patch, failed testing.

catch’s picture

Won't ConfigEntityStorage and ContentEntityStorageBase fallback to EntityStorageBase, given that we pass along $static_cache to it?

If you instantiate ConfigEntityStorage (which we do in unit tests), then you want to pass in the dependencies to the constructor. Without the unit test updates to pass it in, the unit tests fail on the service not being available in the \Drupal call. Not sure exactly what you think can be ditched here tbh.

dawehner’s picture

FileSize
4.16 KB

I was simply thinking of this ...

Version: 8.3.x-dev » 8.4.x-dev

Drupal 8.3.0-alpha1 will be released the week of January 30, 2017, which means new developments and disruptive changes should now be targeted against the 8.4.x-dev branch. For more information see the Drupal 8 minor version schedule and the Allowed changes during the Drupal 8 release cycle.