@[email protected]

diff --git a/dist/handlers/redis-strings.js b/dist/handlers/redis-strings.js
index d6624015e6b48f34a8cf1bd62a09c997aa788538..87a25e0882482a00283293405a1bee2a152f6b8b 100644
--- a/dist/handlers/redis-strings.js
+++ b/dist/handlers/redis-strings.js
@@ -19,6 +19,8 @@ function isImplicitTag(tag) {
   return tag.startsWith(NEXT_CACHE_IMPLICIT_TAG_ID);
 }
 
+let logCounter = 0;
+
 // src/handlers/redis-strings.ts
 function createHandler({
   client,
@@ -38,7 +40,10 @@ function createHandler({
     name: "redis-strings",
     async get(key, { implicitTags }) {
       assertClientIsReady();
+      const log = logCounter++ + " - redis get, key: " + key;
+      console.time(log);
       const result = await client.get(getTimeoutRedisCommandOptions(timeoutMs), keyPrefix + key);
+      console.timeEnd(log);
       if (!result) {
         return null;
       }
@@ -91,12 +96,22 @@ function createHandler({
     },
     async revalidateTag(tag) {
       assertClientIsReady();
+
+      // If the tag is an implicit tag, we need to mark it as revalidated.
+      // The revalidation process is done by the CacheHandler class on the next get operation.
       if (isImplicitTag(tag)) {
         await client.hSet(getTimeoutRedisCommandOptions(timeoutMs), revalidatedTagsKey, tag, Date.now());
       }
+
       const tagsMap = /* @__PURE__ */ new Map();
+
       let cursor = 0;
+
       const hScanOptions = { COUNT: revalidateTagQuerySize };
+
+      const log1 = logCounter++ + " - sharedTags scan for revalidate, tag:" + tag
+      const log2 = logCounter + " - keys scan for revalidate, tag:" + tag
+      console.time(log1);
       do {
         const remoteTagsPortion = await client.hScan(
           getTimeoutRedisCommandOptions(timeoutMs),
@@ -109,23 +124,56 @@ function createHandler({
         }
         cursor = remoteTagsPortion.cursor;
       } while (cursor !== 0);
+      console.timeEnd(log1);
+
+      const scanOptions = { COUNT: revalidateTagQuerySize, MATCH: keyPrefix + "*" };
+      cursor = 0;
+      let remoteKeys = []
+      console.time(log2);
+      do {
+        const remoteKeysPortion = await client.scan(
+          getTimeoutRedisCommandOptions(timeoutMs),
+          cursor,
+          scanOptions,
+        );
+        remoteKeys = remoteKeys.concat(remoteKeysPortion.keys);
+        cursor = remoteKeysPortion.cursor;
+      } while (cursor !== 0);
+      console.timeEnd(log2);
+
+      // Trim the prefix and filter out system tags
+      const remoteKeysSet = /* @__PURE__ */ new Set(remoteKeys.map((key) => key.substring(keyPrefix.length)).filter((key) => ![
+        sharedTagsKey,
+        revalidatedTagsKey
+      ].includes(key)));
+
       const keysToDelete = [];
+
       const tagsToDelete = [];
+
+      let outdatedKeys = 0;
       for (const [key, tags] of tagsMap) {
         if (tags.includes(tag)) {
           keysToDelete.push(keyPrefix + key);
           tagsToDelete.push(key);
         }
+
+        // Remove outdated keys from shared Tag map. They could get removed because of redis volatile key eviction policy
+        if (!remoteKeysSet.has(key)) {
+          tagsToDelete.push(key);
+          outdatedKeys++;
+        }
       }
-      if (keysToDelete.length === 0) {
-        return;
-      }
-      const deleteKeysOperation = client.unlink(getTimeoutRedisCommandOptions(timeoutMs), keysToDelete);
-      const updateTagsOperation = client.hDel(
+
+      if (outdatedKeys) console.log(`Cleaning up ${outdatedKeys} outdated keys from sharedTags hash map`);
+
+      const deleteKeysOperation = keysToDelete.length > 0 ? client.unlink(getTimeoutRedisCommandOptions(timeoutMs), keysToDelete) : undefined;
+      const updateTagsOperation = tagsToDelete.length > 0 ? client.hDel(
         { isolated: true, ...getTimeoutRedisCommandOptions(timeoutMs) },
         keyPrefix + sharedTagsKey,
-        tagsToDelete
-      );
+        tagsToDelete,
+      ) : undefined;
+
       await Promise.all([deleteKeysOperation, updateTagsOperation]);
     }
   };
diff --git a/src/handlers/redis-strings.ts b/src/handlers/redis-strings.ts
index 66530edaa4086d88a46d2813779b07c16d97fa40..e3c33080d2ac9992608a68bf306f682e62cb1422 100644
--- a/src/handlers/redis-strings.ts
+++ b/src/handlers/redis-strings.ts
@@ -105,8 +105,8 @@ export default function createHandler({
                         JSON.stringify(cacheHandlerValue),
                         typeof cacheHandlerValue.lifespan?.expireAt === 'number'
                             ? {
-                                  EXAT: cacheHandlerValue.lifespan.expireAt,
-                              }
+                                EXAT: cacheHandlerValue.lifespan.expireAt,
+                            }
                             : undefined,
                     );
                     break;
@@ -142,6 +142,7 @@ export default function createHandler({
 
             const hScanOptions = { COUNT: revalidateTagQuerySize };
 
+            console.time("sharedTags scan for revalidate, tag:" + tag);
             do {
                 const remoteTagsPortion = await client.hScan(
                     getTimeoutRedisCommandOptions(timeoutMs),
@@ -156,29 +157,55 @@ export default function createHandler({
 
                 cursor = remoteTagsPortion.cursor;
             } while (cursor !== 0);
+            console.time("sharedTags scan for revalidate, tag:" + tag);
+
+            const scanOptions = { COUNT: revalidateTagQuerySize, MATCH: keyPrefix + "*" };
+            cursor = 0;
+            let remoteKeys = []
+            console.time("keys scan for revalidate, tag:" + tag);
+            do {
+                const remoteKeysPortion = await client.scan(
+                    getTimeoutRedisCommandOptions(timeoutMs),
+                    cursor,
+                    scanOptions,
+                );
+                remoteKeys = remoteKeys.concat(remoteKeysPortion.keys);
+                cursor = remoteKeysPortion.cursor;
+            } while (cursor !== 0);
+            console.time("keys scan for revalidate, tag:" + tag);
+
+            // Trim the prefix and filter out system tags
+            const remoteKeysSet = new Set(remoteKeys.map((key) => key.substring(keyPrefix.length)).filter((key) => ![
+                sharedTagsKey,
+                revalidatedTagsKey
+            ].includes(key)));
 
             const keysToDelete: string[] = [];
 
             const tagsToDelete: string[] = [];
 
+            let outdatedKeys = 0;
             for (const [key, tags] of tagsMap) {
                 if (tags.includes(tag)) {
                     keysToDelete.push(keyPrefix + key);
                     tagsToDelete.push(key);
                 }
-            }
 
-            if (keysToDelete.length === 0) {
-                return;
+                // Remove outdated keys from shared Tag map. They could get removed because of redis volatile key eviction policy
+                if (!remoteKeysSet.has(key)) {
+                    tagsToDelete.push(key);
+                    outdatedKeys++;
+                }
             }
 
-            const deleteKeysOperation = client.unlink(getTimeoutRedisCommandOptions(timeoutMs), keysToDelete);
+            if (outdatedKeys) console.log(`Cleaning up ${outdatedKeys} outdated keys from sharedTags hash map`);
 
-            const updateTagsOperation = client.hDel(
+            const deleteKeysOperation = keysToDelete.length > 0 ? client.unlink(getTimeoutRedisCommandOptions(timeoutMs), keysToDelete) : undefined;
+            const updateTagsOperation = tagsToDelete.length > 0 ? client.hDel(
                 { isolated: true, ...getTimeoutRedisCommandOptions(timeoutMs) },
                 keyPrefix + sharedTagsKey,
                 tagsToDelete,
-            );
+            ) : undefined;
 
             await Promise.all([deleteKeysOperation, updateTagsOperation]);
         },