Stateful JWT Revocation Strategies using Bloom Filters and Redis

The Senior Engineer's Dilemma: The Statelessness of JWTs

As architects of distributed systems, we appreciate JSON Web Tokens (JWTs) for their stateless nature. They decouple authentication from our services, allowing for horizontal scalability without the need for a centralized session store. However, this very strength is also a fundamental weakness. A self-contained, signed JWT is valid until its expiration (exp) claim dictates. This creates a critical vulnerability window: if a token is compromised, a user changes their password, or an administrator revokes access, the corresponding JWT remains valid, potentially for hours.

The naive solution is often the first one reached for: a database table acting as a blocklist. On every request, you check if the token's ID exists in this table. This is simple, deterministic, and wrong for any system operating at scale. The performance penalty of a database roundtrip on every single authenticated API call introduces significant latency and puts immense pressure on your primary datastore, a resource typically reserved for core business logic.

This article presents a robust, production-proven alternative. We will architect a high-throughput, low-latency JWT revocation system by leveraging Redis and a probabilistic data structure: the Bloom filter. We'll explore the intricate details of implementation, from managing the filter's lifecycle to gracefully handling its inherent false-positive rate, providing a solution that is both performant and operationally sound.

Core Components of the Architecture

Our solution rests on three pillars: the jti claim in our JWTs, the speed of Redis, and the memory efficiency of Bloom filters.

1. The `jti` (JWT ID) Claim: The Key to Revocation

To revoke a specific token, we must be able to uniquely identify it. The JWT specification (RFC 7519) provides the jti (JWT ID) claim for this exact purpose. It's a case-sensitive string that provides a unique identifier for the JWT.

When issuing a token, your authentication service must generate a unique jti. A version 4 UUID is an excellent choice.

{
  "alg": "HS256",
  "typ": "JWT"
}
{
  "sub": "user-123",
  "iss": "https://auth.myapp.com",
  "aud": "https://api.myapp.com",
  "exp": 1678886400, // Expires in the future
  "iat": 1678882800, // Issued at
  "jti": "f8a3d3a0-4b5c-4e7a-8f9b-1c2d3e4f5a6b" // The unique token identifier
}

This jti becomes the key we will add to our revocation list.

2. Redis: The In-Memory Workhorse

Redis is the ideal candidate for our revocation store due to its sub-millisecond latency for in-memory operations. Its versatility is key here, specifically its support for advanced data structures via modules. We will be using the RedisBloom module, which provides native commands for creating and interacting with Bloom and other probabilistic filters.

3. Bloom Filters: Probabilistic Membership at Scale

A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. Its core properties are what make it perfect for our use case:

* Extreme Memory Efficiency: It can represent a set of millions of items in a remarkably small amount of memory.

* Constant Time Complexity: Both adding an element and checking for its existence are O(k) operations, where k is the number of hash functions. This is independent of the number of items in the filter, making it incredibly fast.

* The Probabilistic Trade-off:

No False Negatives: If the filter says an element is not* in the set, it is definitively not there. A valid token will never be flagged as revoked.

Possible False Positives: If the filter says an element is in the set, it probably* is. There's a small, configurable probability that it's a false positive. A valid token could, on rare occasion, be flagged as revoked.

This trade-off is the crux of the architecture. We accept a tiny chance of inconveniencing a valid user (by forcing a re-login) in exchange for a massive gain in performance and scalability.

Implementation Deep Dive: Building the Revocation Middleware

Let's build this system using Node.js, Express, and the redis client library. You'll need a Redis instance with the RedisBloom module enabled. Docker makes this easy:

# Pull and run Redis Stack, which includes the RedisBloom module
docker run -d --name redis-stack -p 6379:6379 -p 8001:8001 redis/redis-stack:latest

Step 1: Configuring the Bloom Filter

Before we can use the filter, we must reserve it in Redis with specific parameters. The key command is BF.RESERVE. It takes three arguments:

Choosing these parameters is a critical design decision. Let's assume our system has a maximum token lifetime of 24 hours and we anticipate revoking up to 1,000,000 tokens within any 24-hour window. We desire a false-positive rate of 0.1%.

We can initialize this filter on application startup.

bloomFilter.js - Filter Initialization Logic

import { createClient } from 'redis';

const REDIS_URL = process.env.REDIS_URL || 'redis://localhost:6379';
const REVOCATION_FILTER_KEY = 'jwt_revocation_list';
const EXPECTED_REVOKED_COUNT = 1000000; // Expected items
const FALSE_POSITIVE_PROBABILITY = 0.001; // 0.1%

let redisClient;

async function getRedisClient() {
  if (!redisClient) {
    redisClient = createClient({ url: REDIS_URL });
    redisClient.on('error', (err) => console.error('Redis Client Error', err));
    await redisClient.connect();
  }
  return redisClient;
}

export async function initializeBloomFilter() {
  const client = await getRedisClient();
  try {
    // Check if the filter already exists
    await client.ft.info(REVOCATION_FILTER_KEY); 
    console.log('Bloom filter already exists.');
  } catch (e) {
    // If it doesn't exist, Redis throws an error. We create it.
    if (e.message.includes('Unknown index name')) {
      console.log('Creating new Bloom filter...');
      await client.bf.reserve(REVOCATION_FILTER_KEY, FALSE_POSITIVE_PROBABILITY, EXPECTED_REVOKED_COUNT);
      console.log('Bloom filter created successfully.');
    } else {
      throw e;
    }
  }
}

export async function addToBlocklist(jti) {
  const client = await getRedisClient();
  await client.bf.add(REVOCATION_FILTER_KEY, jti);
}

export async function isBlocklisted(jti) {
  const client = await getRedisClient();
  // BF.EXISTS returns 1 if the item may exist, 0 if it definitely does not.
  const result = await client.bf.exists(REVOCATION_FILTER_KEY, jti);
  return result === 1;
}

Step 2: The Revocation Endpoint (The "Write" Path)

When a user logs out or an admin revokes their session, we need an endpoint to trigger the revocation.

authService.js - Logout Logic

import { addToBlocklist } from './bloomFilter.js';
import { decode } from 'jsonwebtoken';

// This would be an authenticated endpoint, e.g., /api/auth/logout
export function handleLogout(req, res) {
  const authHeader = req.headers['authorization'];
  const token = authHeader && authHeader.split(' ')[1];

  if (!token) {
    return res.sendStatus(401);
  }

  try {
    const payload = decode(token);
    if (payload && typeof payload !== 'string' && payload.jti) {
      // Add the token's JTI to the blocklist
      addToBlocklist(payload.jti);
      console.log(`JTI ${payload.jti} added to revocation list.`);
      res.status(200).send({ message: 'Successfully logged out.' });
    } else {
      res.status(400).send({ error: 'Invalid token payload or missing jti.' });
    }
  } catch (error) {
    res.status(500).send({ error: 'Internal server error during logout.' });
  }
}

Step 3: The Authentication Middleware (The "Read" Path)

This is the most critical piece. A middleware intercepts every authenticated request, extracts the jti, and checks it against our Bloom filter before any business logic is executed.

authMiddleware.js - The Validation Logic

import jwt from 'jsonwebtoken';
import { isBlocklisted } from './bloomFilter.js';

const JWT_SECRET = process.env.JWT_SECRET || 'your-super-secret-key';

export async function authenticateToken(req, res, next) {
  const authHeader = req.headers['authorization'];
  const token = authHeader && authHeader.split(' ')[1];

  if (token == null) return res.sendStatus(401); // No token

  try {
    const payload = jwt.verify(token, JWT_SECRET);

    if (typeof payload === 'string' || !payload.jti) {
      return res.status(401).send({ error: 'Token is missing JTI claim.' });
    }

    // *** The Core Revocation Check ***
    const revoked = await isBlocklisted(payload.jti);
    if (revoked) {
      console.warn(`Revoked token used: jti=${payload.jti}`);
      return res.status(401).send({ error: 'Token has been revoked.' });
    }

    req.user = payload;
    next();
  } catch (err) {
    // This will catch expired tokens (exp claim) and invalid signatures
    return res.status(401).send({ error: 'Invalid or expired token.' });
  }
}

This middleware is now attached to all protected routes in your Express application. The revocation check adds only a single, sub-millisecond Redis call to your request latency.

Advanced Patterns for Production Environments

The basic implementation works, but production systems introduce complexities that require more sophisticated patterns.

Edge Case 1: Handling False Positives

With a 0.1% false-positive rate, 1 in every 1000 valid tokens might be incorrectly identified as revoked. While rare, this can be a frustrating user experience. How do we handle it?

Strategy A: The "Graceful Re-authentication" Flow (Acceptable for most B2C apps)

This is the simplest approach. When the API returns a 401 due to a (potentially false positive) revocation, the client-side application should treat it as a session expiry. It should clear its local token storage and redirect the user to the login page. Upon successful login, the user is issued a brand new JWT with a new jti. This new jti will not be in the Bloom filter, instantly resolving the user's issue. The momentary inconvenience is often an acceptable trade-off for the system's performance.

Strategy B: The "Double-Check" Hybrid Pattern (For mission-critical B2B or financial systems)

If false positives are unacceptable, we can combine our Bloom filter with a definitive, persistent blocklist. The Bloom filter acts as a high-speed first-pass cache.

This hybrid model gives us the best of both worlds: near-zero latency for the vast majority of valid requests, while maintaining 100% accuracy for revocation checks.

Implementation of the Hybrid Middleware:

// In your database module
async function isDefinitivelyRevoked(jti) {
  // Example with a PostgreSQL client
  const result = await pgClient.query('SELECT 1 FROM revoked_jtis WHERE jti = $1', [jti]);
  return result.rowCount > 0;
}

// Updated authMiddleware.js
export async function authenticateTokenHybrid(req, res, next) {
  // ... (token extraction and initial verification logic as before)

  const { jti } = payload;
  
  // Step 1: Fast check against the probabilistic filter
  const possiblyRevoked = await isBlocklisted(jti);

  if (possiblyRevoked) {
    // Step 2: If the fast check is positive, perform the slow, definitive check
    const actuallyRevoked = await isDefinitivelyRevoked(jti);
    if (actuallyRevoked) {
      return res.status(401).send({ error: 'Token has been revoked.' });
    }
    // If it was a false positive, we log it for monitoring and proceed
    console.log(`Bloom filter false positive for jti: ${jti}`);
  }

  req.user = payload;
  next();
}

Edge Case 2: Bloom Filter Lifecycle Management

Bloom filters have a fixed capacity. As you add more items, the false-positive probability increases beyond your configured rate. Furthermore, you cannot delete items from a standard Bloom filter. This means our jwt_revocation_list will grow indefinitely unless managed.

Solution: Rotating Time-Windowed Filters

The most effective strategy is to use a series of rolling Bloom filters, each corresponding to a specific time window. The lifecycle aligns with your maximum JWT expiry time.

Let's say your JWTs are valid for a maximum of 3 days.

Implementation of Rotating Filters:

// bloomFilter.js (updated)

const MAX_TOKEN_AGE_DAYS = 3;

function getFilterKeysForWindow() {
  const keys = [];
  const today = new Date();
  for (let i = 0; i < MAX_TOKEN_AGE_DAYS; i++) {
    const date = new Date(today);
    date.setDate(today.getDate() - i);
    const dateString = date.toISOString().split('T')[0]; // YYYY-MM-DD
    keys.push(`jwt_revocation_list:${dateString}`);
  }
  return keys;
}

export async function addToBlocklist(jti) {
  const client = await getRedisClient();
  const todayKey = getFilterKeysForWindow()[0]; // Always write to today's filter
  // Note: Ensure this filter is created daily via a scheduled job
  await client.bf.add(todayKey, jti);
}

export async function isBlocklisted(jti) {
  const client = await getRedisClient();
  const keysToCheck = getFilterKeysForWindow();

  // Use BF.MEXISTS to check multiple filters in one command
  const results = await client.bf.mExists(keysToCheck, Array(keysToCheck.length).fill(jti));

  // If any result is 1, the token might be revoked
  return results.some(result => result === 1);
}

// Scheduled Job (e.g., using node-cron)
// cron.schedule('0 0 * * *', async () => { ... })
export async function createDailyFilter() {
    const client = await getRedisClient();
    const todayKey = getFilterKeysForWindow()[0];
    const expirySeconds = (MAX_TOKEN_AGE_DAYS + 1) * 24 * 60 * 60;
    try {
        await client.bf.reserve(todayKey, FALSE_POSITIVE_PROBABILITY, EXPECTED_REVOKED_COUNT);
        await client.expire(todayKey, expirySeconds);
        console.log(`Created and set TTL for new filter: ${todayKey}`);
    } catch (e) {
        // Handle case where it might already exist if job re-runs
        console.log(`Filter ${todayKey} likely already exists.`);
    }
}

Performance and Memory Analysis

Let's quantify the benefits of this approach over alternatives for our scenario (1,000,000 revoked tokens, 0.1% FP rate).

* Memory Footprint:

PostgreSQL Table: Storing 1M UUIDs (jti) would require an indexed varchar(36) column. This would consume roughly 1,000,000 (36 bytes for UUID + index overhead) ≈ 50-70 MB of disk/memory.

Redis Set: Storing 1M UUIDs as members of a set would consume 1,000,000 36 bytes ≈ 36 MB of RAM.

* Redis Bloom Filter: For 1M items and a 0.1% FP rate, the filter requires approximately 1.44 MB of RAM. This is a ~25x reduction in memory usage compared to a Redis Set and even more compared to a relational database.

* Latency:

* PostgreSQL: A SELECT query against an indexed column will typically take 5-20ms, depending on load, connection pooling, and network.

* Redis Set (SISMEMBER): This is an O(1) operation, typically completing in <1ms.

* Redis Bloom Filter (BF.EXISTS): This is an O(k) operation, where k is small (around 10 for our parameters). It is also consistently <1ms.

The key takeaway is that the Bloom filter provides the same sub-millisecond latency as a Redis Set but at a fraction of the memory cost, making it feasible to handle tens of millions of revocations without provisioning massive Redis instances.

Conclusion: Engineering the Right Trade-offs

Implementing an immediate, scalable JWT revocation mechanism is a classic senior-level engineering problem that requires moving beyond naive solutions. By employing a Redis-backed Bloom filter, we can design a system that is both exceptionally fast and memory-efficient. The core of this advanced pattern lies in understanding and managing the trade-offs: we accept a small, controllable risk of false positives in exchange for enormous gains in performance and cost-effectiveness.

By layering on production-ready strategies like the hybrid double-check pattern to eliminate false positives in critical systems and time-windowed filter rotation for lifecycle management, we can build a truly robust and scalable security component. This approach demonstrates a key engineering principle: applying the right specialized data structure can fundamentally change the performance characteristics and feasibility of a system at scale.