diff --git a/core/lib/Drupal/Core/CoreBundle.php b/core/lib/Drupal/Core/CoreBundle.php
index f0f1da4..430d47e 100644
--- a/core/lib/Drupal/Core/CoreBundle.php
+++ b/core/lib/Drupal/Core/CoreBundle.php
@@ -122,7 +122,8 @@ public function build(ContainerBuilder $container) {
       ->addArgument(new Reference('cache.cache'))
       ->addArgument(new Reference('lock'))
       ->addArgument(new Reference('keyvalue'))
-      ->addArgument('state');
+      ->addArgument('state')
+      ->addTag('needs_destruction');
 
     // Register the Queue factory.
     $container
diff --git a/core/lib/Drupal/Core/KeyValueStore/KeyValueCacheDecorator.php b/core/lib/Drupal/Core/KeyValueStore/KeyValueCacheDecorator.php
index 2735e84..55a5084 100644
--- a/core/lib/Drupal/Core/KeyValueStore/KeyValueCacheDecorator.php
+++ b/core/lib/Drupal/Core/KeyValueStore/KeyValueCacheDecorator.php
@@ -9,12 +9,13 @@
 
 use Drupal\Core\Cache\CacheBackendInterface;
 use Drupal\Core\Cache\CacheCollector;
+use Drupal\Core\DestructableInterface;
 use Drupal\Core\Lock\LockBackendInterface;
 
 /**
  * Provides a decorator for a key value store that caches all requested keys.
  */
-class KeyValueCacheDecorator extends CacheCollector implements KeyValueStoreInterface {
+class KeyValueCacheDecorator extends CacheCollector implements KeyValueStoreInterface, DestructableInterface {
 
   /**
    * The key value store to use as state.
@@ -140,20 +141,4 @@ public function set($key, $value) {
     $this->cache->delete($this->cid);
   }
 
-  /**
-   * Destruct the class, write the cache back.
-   *
-   * @todo: Remove this once the service destructor can be used.
-   */
-  public function __destruct() {
-    try {
-      $this->destruct();
-    }
-    catch (\Exception $e) {
-      // During testing the table is gone before this fires.
-      // @todo Use service destruction that directly invokes destruct(), see
-      //   http://drupal.org/node/512026.
-    }
-  }
-
 }