diff --git a/rhodecode/lib/db_manage.py b/rhodecode/lib/db_manage.py
--- a/rhodecode/lib/db_manage.py
+++ b/rhodecode/lib/db_manage.py
@@ -37,7 +37,7 @@ from rhodecode.lib.utils import ask_ok
 from rhodecode.model import init_model
 from rhodecode.model.db import User, Permission, RhodeCodeUi, \
     RhodeCodeSetting, UserToPerm, DbMigrateVersion, RepoGroup, \
-    UserRepoGroupToPerm
+    UserRepoGroupToPerm, CacheInvalidation
 
 from sqlalchemy.engine import create_engine
 from rhodecode.model.repos_group import ReposGroupModel
@@ -150,6 +150,10 @@ class DbManage(object):
         if curr_version == __dbversion__:
             sys.exit('This database is already at the newest version')
 
+        # clear cache keys
+        log.info("Clearing cache keys now...")
+        CacheInvalidation.clear_cache()
+
         #======================================================================
         # UPGRADE STEPS
         #======================================================================
diff --git a/rhodecode/model/db.py b/rhodecode/model/db.py
--- a/rhodecode/model/db.py
+++ b/rhodecode/model/db.py
@@ -1806,6 +1806,15 @@ class CacheInvalidation(Base, BaseModel)
         return self._cache_key_partition()[2]
 
     @classmethod
+    def clear_cache(cls):
+        """
+        Delete all cache keys from database.
+        Should only be run when all instances are down and all entries thus stale.
+        """
+        cls.query().delete()
+        Session().commit()
+
+    @classmethod
     def _get_cache_key(cls, key):
         """
         Wrapper for generating a unique cache key for this instance and "key".