diff --git a/core/core.services.yml b/core/core.services.yml
index 363912d..a2f7575 100644
--- a/core/core.services.yml
+++ b/core/core.services.yml
@@ -70,9 +70,6 @@ services:
   config.manager:
     class: Drupal\Core\Config\ConfigManager
     arguments: ['@entity.manager', '@config.factory', '@config.typed', '@string_translation', '@config.storage']
-  config.storage:
-    class: Drupal\Core\Config\DatabaseStorage
-    arguments: ['@database', 'config']
   config.factory:
     class: Drupal\Core\Config\ConfigFactory
     tags:
@@ -81,6 +78,10 @@ services:
   config.installer:
     class: Drupal\Core\Config\ConfigInstaller
     arguments: ['@config.factory', '@config.storage', '@config.typed', '@config.manager', '@event_dispatcher']
+  config.storage: "@config.storage.uncached"
+  config.storage.uncached:
+    class: Drupal\Core\Config\DatabaseStorage
+    arguments: ['@database', 'config']
   config.storage.staging:
     class: Drupal\Core\Config\FileStorage
     factory_class: Drupal\Core\Config\FileStorageFactory
diff --git a/core/lib/Drupal/Core/Config/BootstrapConfigStorageFactory.php b/core/lib/Drupal/Core/Config/BootstrapConfigStorageFactory.php
index 1df8f07..bf65660 100644
--- a/core/lib/Drupal/Core/Config/BootstrapConfigStorageFactory.php
+++ b/core/lib/Drupal/Core/Config/BootstrapConfigStorageFactory.php
@@ -27,7 +27,8 @@ public static function get() {
       return call_user_func($drupal_bootstrap_config_storage);
     }
     else {
-      return new DatabaseStorage(Database::getConnection(), 'config');
+      $storage = new DatabaseStorage(Database::getConnection(), 'config');
+      return $storage->createStorage();
     }
   }
 
diff --git a/core/lib/Drupal/Core/Config/CachedStorage.php b/core/lib/Drupal/Core/Config/CachedStorage.php
index 1ff4046..f10b794 100644
--- a/core/lib/Drupal/Core/Config/CachedStorage.php
+++ b/core/lib/Drupal/Core/Config/CachedStorage.php
@@ -54,6 +54,14 @@ public function __construct(StorageInterface $storage, CacheBackendInterface $ca
   }
 
   /**
+   * {@inheritdoc}
+   */
+  public function createStorage() {
+    $this->storage->createStorage();
+    return $this;
+  }
+
+  /**
    * Implements Drupal\Core\Config\StorageInterface::exists().
    */
   public function exists($name) {
diff --git a/core/lib/Drupal/Core/Config/DatabaseStorage.php b/core/lib/Drupal/Core/Config/DatabaseStorage.php
index 9ce0cc4..fa8ad15 100644
--- a/core/lib/Drupal/Core/Config/DatabaseStorage.php
+++ b/core/lib/Drupal/Core/Config/DatabaseStorage.php
@@ -55,6 +55,14 @@ public function __construct(Connection $connection, $table, array $options = arr
   }
 
   /**
+   * {@inheritdoc}
+   */
+  public function createStorage() {
+    $this->ensureTableExists();
+    return $this;
+  }
+
+  /**
    * Implements Drupal\Core\Config\StorageInterface::exists().
    */
   public function exists($name) {
@@ -118,35 +126,10 @@ public function readMultiple(array $names) {
    * @todo Ignore slave targets for data manipulation operations.
    */
   public function write($name, array $data) {
-    $data = $this->encode($data);
-    try {
-      return $this->doWrite($name, $data);
-    }
-    catch (\Exception $e) {
-      // If there was an exception, try to create the table.
-      if (empty($this->options['throw_exception']) && $this->ensureTableExists()) {
-        return $this->doWrite($name, $data);
-      }
-      // Some other failure that we can not recover from.
-      throw $e;
-    }
-  }
-
-  /**
-   * Helper method so we can re-try a write.
-   *
-   * @param string $name
-   *   The config name.
-   * @param string $data
-   *   The config data, already dumped to a string.
-   *
-   * @return bool
-   */
-  protected function doWrite($name, $data) {
     $options = array('return' => Database::RETURN_AFFECTED) + $this->options;
     return (bool) $this->connection->merge($this->table, $options)
       ->key('name', $name)
-      ->fields(array('data' => $data))
+      ->fields(array('data' => $this->encode($data)))
       ->execute();
   }
 
@@ -156,7 +139,8 @@ protected function doWrite($name, $data) {
    * @return bool
    *   TRUE if the table was created, FALSE otherwise.
    *
-   * @throws PDOException
+   * @throws \Drupal\Core\Config\StorageException
+   *   If a database error occurs.
    */
   protected function ensureTableExists()  {
     try {
@@ -171,6 +155,9 @@ protected function ensureTableExists()  {
     catch (SchemaObjectExistsException $e) {
       return TRUE;
     }
+    catch (\Exception $e) {
+      throw new StorageException($e->getMessage(), NULL, $e);
+    }
     return FALSE;
   }
 
diff --git a/core/lib/Drupal/Core/Config/FileStorage.php b/core/lib/Drupal/Core/Config/FileStorage.php
index 4281df2..26da8d2 100644
--- a/core/lib/Drupal/Core/Config/FileStorage.php
+++ b/core/lib/Drupal/Core/Config/FileStorage.php
@@ -69,6 +69,19 @@ public static function getFileExtension() {
   }
 
   /**
+   * {@inheritdoc}
+   */
+  public function createStorage() {
+    // @todo: Use this method during install.
+    $success = file_prepare_directory($this->directory, FILE_CREATE_DIRECTORY | FILE_MODIFY_PERMISSIONS);
+    $success = $success && file_save_htaccess($this->directory, TRUE, TRUE);
+    if (!$success) {
+      throw new StorageException("Failed to create config directory {$this->directory}");
+    }
+    return $this;
+  }
+
+  /**
    * Implements Drupal\Core\Config\StorageInterface::exists().
    */
   public function exists($name) {
diff --git a/core/lib/Drupal/Core/Config/InstallStorage.php b/core/lib/Drupal/Core/Config/InstallStorage.php
index 124748a..89d478c 100644
--- a/core/lib/Drupal/Core/Config/InstallStorage.php
+++ b/core/lib/Drupal/Core/Config/InstallStorage.php
@@ -65,6 +65,13 @@ public function getFilePath($name) {
   }
 
   /**
+   * {@inheritdoc}
+   */
+  public function createStorage() {
+    return $this;
+  }
+
+  /**
    * Overrides Drupal\Core\Config\FileStorage::write().
    *
    * @throws \Drupal\Core\Config\StorageException
diff --git a/core/lib/Drupal/Core/Config/NullStorage.php b/core/lib/Drupal/Core/Config/NullStorage.php
index 2bf121d..5ab1fa8 100644
--- a/core/lib/Drupal/Core/Config/NullStorage.php
+++ b/core/lib/Drupal/Core/Config/NullStorage.php
@@ -24,6 +24,13 @@
 class NullStorage implements StorageInterface {
 
   /**
+   * {@inheritdoc}
+   */
+  public function createStorage() {
+    return $this;
+  }
+
+  /**
    * Implements Drupal\Core\Config\StorageInterface::exists().
    */
   public function exists($name) {
diff --git a/core/lib/Drupal/Core/Config/StorageInterface.php b/core/lib/Drupal/Core/Config/StorageInterface.php
index f4a85ea..929ed33 100644
--- a/core/lib/Drupal/Core/Config/StorageInterface.php
+++ b/core/lib/Drupal/Core/Config/StorageInterface.php
@@ -16,6 +16,17 @@
 interface StorageInterface {
 
   /**
+   * Ensure that the back-end for this storage exists (idempotent).
+   *
+   * @return \Drupal\Core\Config\StorageInterface
+   *   The called object.
+   *
+   * @throws \Drupal\Core\Config\StorageException
+   *   If the back-end storage does not exist and cannot be created.
+   */
+  public function createStorage();
+
+  /**
    * Returns whether a configuration object exists.
    *
    * @param string $name
diff --git a/core/lib/Drupal/Core/DependencyInjection/UpdateServiceProvider.php b/core/lib/Drupal/Core/DependencyInjection/UpdateServiceProvider.php
index 8d84bd6..7098bf8 100644
--- a/core/lib/Drupal/Core/DependencyInjection/UpdateServiceProvider.php
+++ b/core/lib/Drupal/Core/DependencyInjection/UpdateServiceProvider.php
@@ -28,12 +28,10 @@ public function register(ContainerBuilder $container) {
       $container
         ->register('lock', 'Drupal\Core\Lock\NullLockBackend');
 
-      // Prevent config from accessing {cache_config}.
-      // @see $conf['cache_classes'], update_prepare_d8_bootstrap()
-      $container
-        ->register('config.storage', 'Drupal\Core\Config\DataBaseStorage')
-        ->addArgument(new Reference('database'))
-        ->addArgument('config');
+      // Prevent config from being access via a cache wrapper by removing
+      // any existing definition and adding an alias to the un-cached service.
+      $container->removeDefinition('config.storage');
+      $container->setAlias('config.storage', 'config.storage.uncached');
       $container->register('module_handler', 'Drupal\Core\Extension\UpdateModuleHandler')
         ->addArgument('%container.modules%');
       $container
diff --git a/core/modules/config/lib/Drupal/config/Tests/Storage/DatabaseStorageTest.php b/core/modules/config/lib/Drupal/config/Tests/Storage/DatabaseStorageTest.php
index 28987e6..beb24da 100644
--- a/core/modules/config/lib/Drupal/config/Tests/Storage/DatabaseStorageTest.php
+++ b/core/modules/config/lib/Drupal/config/Tests/Storage/DatabaseStorageTest.php
@@ -25,7 +25,8 @@ function setUp() {
     parent::setUp();
 
     $this->storage = new DatabaseStorage($this->container->get('database'), 'config');
-    $this->invalidStorage = new DatabaseStorage($this->container->get('database'), 'invalid', array('throw_exception' => TRUE));
+    $this->storage->createStorage();
+    $this->invalidStorage = new DatabaseStorage($this->container->get('database'), 'invalid');
 
     // ::listAll() verifications require other configuration data to exist.
     $this->storage->write('system.performance', array());
diff --git a/core/modules/config/lib/Drupal/config/Tests/Storage/FileStorageTest.php b/core/modules/config/lib/Drupal/config/Tests/Storage/FileStorageTest.php
index bcd49989..4331e99 100644
--- a/core/modules/config/lib/Drupal/config/Tests/Storage/FileStorageTest.php
+++ b/core/modules/config/lib/Drupal/config/Tests/Storage/FileStorageTest.php
@@ -25,6 +25,7 @@ public static function getInfo() {
   function setUp() {
     parent::setUp();
     $this->storage = new FileStorage($this->configDirectories[CONFIG_ACTIVE_DIRECTORY]);
+    $this->storage->createStorage();
     $this->invalidStorage = new FileStorage($this->configDirectories[CONFIG_ACTIVE_DIRECTORY] . '/nonexisting');
 
     // FileStorage::listAll() requires other configuration data to exist.
diff --git a/core/modules/simpletest/lib/Drupal/simpletest/DrupalUnitTestBase.php b/core/modules/simpletest/lib/Drupal/simpletest/DrupalUnitTestBase.php
index 2be5b37..6523b10 100644
--- a/core/modules/simpletest/lib/Drupal/simpletest/DrupalUnitTestBase.php
+++ b/core/modules/simpletest/lib/Drupal/simpletest/DrupalUnitTestBase.php
@@ -225,7 +225,7 @@ public function containerBuild(ContainerBuilder $container) {
     $container->register('cache_factory', 'Drupal\Core\Cache\MemoryBackendFactory');
 
     $container
-      ->register('config.storage', 'Drupal\Core\Config\DatabaseStorage')
+      ->register('config.storage.uncached', 'Drupal\Core\Config\DatabaseStorage')
       ->addArgument(Database::getConnection())
       ->addArgument('config');