Implementing Credential ID Lookup at Scale

When passkey authentication throughput exceeds 10 000 RPS, credential_id lookup becomes the primary bottleneck — long before the WebAuthn signature verification step is even reached. This page isolates the exact failure modes, prescribes covering-index and caching fixes, and shows how to confirm the resolution under sustained load. It is a direct companion to Credential Indexing and Database Schema Design, which covers the broader schema architecture.

Error Signatures and Failure Reference

Scan-match your symptom against this table before reading further.

Symptom Root trigger Diagnostic indicator
Auth latency p99 > 200 ms Sequential scan on credential_id column Seq Scan in EXPLAIN output; high shared_read buffers
Connection pool exhaustion Synchronous lookup loops under auth burst pool_wait_time > 2 s; active_connections at pgBouncer max
Cache hit ratio < 0.70 Cache layer bypassed or cold after deploy keyspace_hits / (keyspace_hits + keyspace_misses) in Redis INFO
Stale public key served Missing revocation hook on cache entry Revoked credential still resolves to a valid public_key
REDIS_PIPELINE_TIMEOUT Unbounded batch sizes in multi-GET calls Redis slowlog entries; client-side timeout on MGET

Root Cause Analysis

1. Missing or wrong index on credential_id

The credential_id column is a variable-length BYTEA value — typically 16–64 bytes for FIDO2 authenticators. Without a B-tree index scoped to non-revoked rows, PostgreSQL falls back to a sequential scan. At table sizes above ~500 k rows this pushes per-query I/O into the hundreds of 8 kB pages, and at high concurrency saturates the I/O scheduler before the query returns.

A single-column index helps but still forces a heap fetch for every matched row to retrieve public_key, sign_count, and alg — the three columns the authentication verification logic needs. The fix is a covering index using INCLUDE.

2. Synchronous lookup loops exhausting the connection pool

Some registration flows iterate over a user’s existing credentials to detect re-registration (InvalidStateError guard). When that loop runs inside an open transaction, each iteration holds a connection slot. Under concurrent auth bursts this depresses available pool capacity faster than the pool manager can reclaim idle slots.

3. Write-through caching absent or partially wired

Adding a Redis read-through cache without also wiring eviction on credential lifecycle events introduces stale-data risk: a revoked credential’s public_key remains resolvable from cache until TTL expires. The condition that triggers this is any code path that modifies credential state — revocation, public key rotation, and account recovery — without a corresponding DEL on the cache key.

4. Unpartitioned tables at 50 M+ rows

At very large scale, B-tree index traversal depth increases with table cardinality. Declarative range or list partitioning by created_at or org_id reduces the effective index tree that each query must walk, and allows PostgreSQL’s partition pruning to skip irrelevant partitions entirely.

Step-by-Step Resolution

Step 1 — Establish a query baseline

Enable slow-query logging and capture an execution plan before touching the schema:

-- Log queries slower than 50 ms
ALTER SYSTEM SET log_min_duration_statement = 50;
SELECT pg_reload_conf();

-- Capture the current execution path
EXPLAIN (ANALYZE, BUFFERS)
SELECT public_key, sign_count, alg
FROM credentials
WHERE credential_id = '\xdeadbeef...'::bytea
  AND revoked_at IS NULL;

A Seq Scan in the output confirms the missing-index root cause. A Bitmap Heap Scan with high Heap Fetches confirms a non-covering index.

Check connection pool pressure:

SELECT pid, state, query, wait_event_type
FROM pg_stat_activity
WHERE query ILIKE '%credentials%'
  AND state != 'idle';

And isolate the highest-latency queries by caller:

SELECT query, mean_exec_time, calls, rows
FROM pg_stat_statements
WHERE query ILIKE '%credentials%'
ORDER BY mean_exec_time DESC
LIMIT 10;

Step 2 — Deploy a covering partial index

Use CONCURRENTLY to build the index without holding a write lock during peak traffic. The WHERE revoked_at IS NULL predicate keeps the index small and focused on the hot path — the authentication assertion flow never needs to look up revoked credentials.

CREATE INDEX CONCURRENTLY idx_cred_lookup_v2
ON credentials (credential_id)
INCLUDE (public_key, sign_count, alg)
WHERE revoked_at IS NULL;

INCLUDE makes public_key, sign_count, and alg part of the index leaf pages. PostgreSQL can satisfy the full SELECT from the index alone — an Index-Only Scan — without a heap fetch, cutting I/O by 40–60 % on read-heavy authentication workloads.

Verify the planner picks it up:

EXPLAIN (ANALYZE, BUFFERS)
SELECT public_key, sign_count, alg
FROM credentials
WHERE credential_id = $1
  AND revoked_at IS NULL;
-- Target output: "Index Only Scan using idx_cred_lookup_v2  Heap Fetches: 0"

Check index health after deployment:

SELECT indexrelname, idx_scan, idx_tup_read, idx_tup_fetch
FROM pg_stat_user_indexes
WHERE relname = 'credentials'
ORDER BY idx_scan DESC;

idx_tup_fetch close to zero confirms Index-Only Scan is in effect.

Step 3 — Implement write-through caching with deterministic eviction

The diagram below shows the lookup path after caching is wired correctly.

Credential ID Lookup Flow Flowchart showing: authentication request → cache lookup → cache hit returns credential record; cache miss → PostgreSQL query → write to cache → return credential record. Revocation events trigger synchronous cache deletion. Auth request Redis GET cred:{id} Cache hit → return PostgreSQL lookup SETEX cred:{id} TTL 60–65 min Revocation / rotation event hit miss DEL cred:{id}

Production TypeScript implementation with jitter-based TTL to prevent cache stampedes:

import { createClient } from 'redis';
import { db } from './database';

const redis = createClient({ url: process.env.REDIS_URL });
await redis.connect();

interface CredentialRecord {
  id:        string;
  publicKey: string; // base64url-encoded COSE public key
  signCount: number;
  alg:       number; // COSE algorithm identifier, e.g. -7 (ES256) or -257 (RS256)
}

const CACHE_PREFIX = 'cred:';
const BASE_TTL_S  = 3600; // 60 min
const JITTER_S    = 300;  // +0–5 min to spread expiry across replicas

/** Resolve a credential_id to its stored record, consulting Redis before PostgreSQL. */
export async function resolveCredentialId(
  credentialIdBase64url: string
): Promise<CredentialRecord | null> {
  const key = `${CACHE_PREFIX}${credentialIdBase64url}`;

  // 1. Cache read
  const cached = await redis.get(key);
  if (cached) return JSON.parse(cached) as CredentialRecord;

  // 2. DB fallback — strict projection avoids loading attestationObject blob
  const row = await db.credentials.findUnique({
    where:  { credentialId: Buffer.from(credentialIdBase64url, 'base64url') },
    select: { id: true, publicKey: true, signCount: true, alg: true, revokedAt: true }
  });

  if (!row || row.revokedAt !== null || !row.publicKey) return null;

  const record: CredentialRecord = {
    id:        row.id,
    publicKey: row.publicKey.toString('base64url'),
    signCount: row.signCount,
    alg:       row.alg
  };

  // 3. Write-through with jitter
  const ttl = BASE_TTL_S + Math.floor(Math.random() * JITTER_S);
  await redis.setEx(key, ttl, JSON.stringify(record));

  return record;
}

/** Call synchronously inside the revocation transaction — never rely on TTL expiry alone. */
export async function evictCredentialCache(credentialIdBase64url: string): Promise<void> {
  await redis.del(`${CACHE_PREFIX}${credentialIdBase64url}`);
}

Step 4 — Batch pipeline for multi-credential lookups

signCount replay-attack checks and registration de-duplication queries often fetch multiple credential IDs for one user. Replace sequential GET calls with a pipelined MGET:

export async function resolveCredentialBatch(
  ids: string[]
): Promise<Map<string, CredentialRecord | null>> {
  if (ids.length === 0) return new Map();

  // Cap batch size — unbounded MGET can spike Redis memory and latency
  const MAX_BATCH = 100;
  if (ids.length > MAX_BATCH) throw new RangeError(`Batch exceeds ${MAX_BATCH} credential IDs`);

  const keys   = ids.map(id => `${CACHE_PREFIX}${id}`);
  const values = await redis.mGet(keys);
  const result = new Map<string, CredentialRecord | null>();
  const missed: string[] = [];

  for (let i = 0; i < ids.length; i++) {
    if (values[i]) {
      result.set(ids[i], JSON.parse(values[i]!) as CredentialRecord);
    } else {
      missed.push(ids[i]);
    }
  }

  // DB fallback for cache misses — single query with IN clause
  if (missed.length > 0) {
    const rows = await db.credentials.findMany({
      where: {
        credentialId: { in: missed.map(id => Buffer.from(id, 'base64url')) },
        revokedAt:    null
      },
      select: { id: true, credentialId: true, publicKey: true, signCount: true, alg: true }
    });

    const pipeline = redis.multi();
    for (const row of rows) {
      const idB64 = row.credentialId.toString('base64url');
      const rec: CredentialRecord = {
        id:        row.id,
        publicKey: row.publicKey.toString('base64url'),
        signCount: row.signCount,
        alg:       row.alg
      };
      result.set(idB64, rec);
      const ttl = BASE_TTL_S + Math.floor(Math.random() * JITTER_S);
      pipeline.setEx(`${CACHE_PREFIX}${idB64}`, ttl, JSON.stringify(rec));
    }
    await pipeline.exec();

    // IDs not found in DB resolve to null (unknown or revoked)
    for (const id of missed) {
      if (!result.has(id)) result.set(id, null);
    }
  }

  return result;
}

Verification and Testing

Confirm Index-Only Scan after deploy

EXPLAIN (ANALYZE, BUFFERS)
SELECT public_key, sign_count, alg
FROM credentials
WHERE credential_id = $1
  AND revoked_at IS NULL;

Expected: Index Only Scan using idx_cred_lookup_v2 on credentials Heap Fetches: 0. Any non-zero Heap Fetches value means the index’s visibility map is not yet fully populated — run VACUUM credentials; to accelerate.

Cache hit ratio assertion (Jest)

import { resolveCredentialId } from './credentialLookup';
import { redis } from './redis';

test('cache hit ratio exceeds 0.90 after warm-up', async () => {
  const id = 'dGVzdGNyZWRlbnRpYWxpZA=='; // test vector
  // Warm the cache
  await resolveCredentialId(id);

  const info     = await redis.info('stats');
  const hits     = parseInt(info.match(/keyspace_hits:(\d+)/)?.[1] ?? '0', 10);
  const misses   = parseInt(info.match(/keyspace_misses:(\d+)/)?.[1] ?? '0', 10);
  const ratio    = hits / (hits + misses);

  expect(ratio).toBeGreaterThan(0.90);
});

Load test with k6

// k6 load test — target: p99 latency < 50 ms at 10 000 RPS
import http from 'k6/http';
import { check } from 'k6';

export const options = {
  scenarios: {
    constant_rps: {
      executor: 'constant-arrival-rate',
      rate: 10000,
      timeUnit: '1s',
      duration: '2m',
      preAllocatedVUs: 200,
    },
  },
  thresholds: {
    'http_req_duration{name:assert}': ['p(99)<50'],
  },
};

export default function () {
  const res = http.post(
    'https://your-rp.example.com/webauthn/assert',
    JSON.stringify({ credentialId: __ENV.TEST_CREDENTIAL_ID }),
    { headers: { 'Content-Type': 'application/json' }, tags: { name: 'assert' } }
  );
  check(res, { 'status 200': r => r.status === 200 });
}

Weekly index health monitoring

psql "$DATABASE_URL" -c "
SELECT indexrelname,
       idx_scan,
       idx_tup_read,
       idx_tup_fetch,
       pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM   pg_stat_user_indexes
WHERE  relname = 'credentials'
ORDER  BY idx_scan DESC;
"

Pitfalls Specific to This Sub-topic

Relying solely on TTL for cache invalidation. A 60-minute TTL means a revoked passkey — or one whose public key has been rotated — remains resolvable for up to an hour. Call redis.del(key) synchronously within the same database transaction that writes the revocation or rotation record.

Not bounding MGET batch sizes. Redis processes MGET atomically in a single round-trip, but unbounded batches can stall the event loop if the returned payload is large (many full COSE key blobs). Cap at 100 IDs per batch and implement exponential backoff on REDIS_PIPELINE_TIMEOUT.

Forgetting VACUUM after building the covering index. Index-Only Scans require the visibility map to mark pages as all-visible. Until VACUUM runs, PostgreSQL falls back to heap fetches even with the new index in place. Run VACUUM (ANALYZE) credentials; immediately after building the index in production.

Validation Checklist

Related