diff --git a/rhodecode/lib/rc_cache/backends.py b/rhodecode/lib/rc_cache/backends.py
--- a/rhodecode/lib/rc_cache/backends.py
+++ b/rhodecode/lib/rc_cache/backends.py
@@ -41,7 +41,7 @@ from dogpile.cache.api import Serializer
 from pyramid.settings import asbool
 
 from rhodecode.lib.memory_lru_dict import LRUDict, LRUDictDebug
-from rhodecode.lib.str_utils import safe_str
+from rhodecode.lib.str_utils import safe_str, safe_bytes
 
 
 _default_max_size = 1024
@@ -146,20 +146,20 @@ class FileNamespaceBackend(PickleSeriali
     def __repr__(self):
         return '{} `{}`'.format(self.__class__, self.filename)
 
-    def list_keys(self, prefix=''):
-        prefix = '{}:{}'.format(self.key_prefix, prefix)
+    def list_keys(self, prefix: bytes = b''):
+        prefix = b'%b:%b' % (safe_bytes(self.key_prefix), safe_bytes(prefix))
 
-        def cond(v):
+        def cond(dbm_key: bytes):
             if not prefix:
                 return True
 
-            if v.startswith(prefix):
+            if dbm_key.startswith(prefix):
                 return True
             return False
 
         with self._dbm_file(True) as dbm:
             try:
-                return list(filter(cond, list(dbm.keys())))
+                return list(filter(cond, dbm.keys()))
             except Exception:
                 log.error('Failed to fetch DBM keys from DB: %s', self.get_store())
                 raise