DEV Community: Darsh Ayde

Building KNN from Scratch (Because import sklearn Feels Like Cheating)

Darsh Ayde — Sun, 14 Jun 2026 07:02:50 +0000

Building K-Nearest Neighbors (KNN) From Scratch

Let's be real: in a production machine learning environment, we all just import scikit-learn and call it a day. But treating algorithms like black boxes can come back to bite you when those abstractions leak. Building K-Nearest Neighbors (KNN) from scratch is a fantastic exercise to actually understand the mechanics working under the hood.

At its core, KNN relies on a surprisingly simple geometric premise: a data point probably belongs to the same category as its closest spatial neighbors. Rebuilding this classifier from the ground up forces you to tackle some critical engineering challenges, such as:

Computing spatial geometry efficiently
Managing state during the voting process
Handling edge cases and algorithmic ties deterministically

In this post, we'll walk through the architectural decisions behind a pure Python implementation of KNN, translating textbook math into functional code.

1. The Distance Metric

import math

def _check_length(x, y):
    """Ensure both vectors have the same length."""
    if len(x) != len(y):
        raise ValueError("Vectors must be of same length")

def euclidean_distance(x, y):
    """Compute Euclidean distance between two vectors."""
    _check_length(x, y)

    sum_of_sq = sum(
        (i - j) ** 2
        for i, j in zip(x, y)
    )

    return math.sqrt(sum_of_sq)

The Goal

Calculate spatial similarity between vectors using Euclidean distance.

How It Works

KNN is fundamentally a geometry problem. The entire algorithm hinges on quantifying exactly how far apart points are in a given space.

If we're looking at a 2D plane, Euclidean distance comes straight from the Pythagorean theorem:

d = (x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}

In machine learning, however, we're rarely dealing with just two dimensions. Fortunately, the formula generalizes neatly to an arbitrary number of dimensions:

d (x, y) = i = 1 \sum n (x_{i} - y_{i})^{2}

Where:

$n$ is the total number of dimensions.
$x_{i}$ and $y_{i}$ are the coordinates of vectors $x$ and $y$ along dimension $i$ .

In the euclidean_distance() function above, notice the generator expression inside sum(). It evaluates lazily, meaning we avoid constructing an intermediate list of squared differences in memory. This is a deliberate design choice that scales well when working with high-dimensional data.

Also, don't overlook the _check_length() guard—it is structurally critical. Comparing vectors of different dimensions is mathematically invalid. Since Python's zip() function silently truncates to the shortest iterable, omitting this check could allow the function to fail silently and return incorrect results.

2. The Voting Mechanism and Tie-Breakers

def _get_majority_vote(neighbors):
    # ... early-exit validation skipped ...

    vote_count = {}
    min_distance_per_label = {}

    for neighbor in neighbors:
        label = neighbor["label"]
        distance = neighbor["distance"]

        vote_count[label] = vote_count.get(label, 0) + 1

        min_distance_per_label[label] = min(
            distance,
            min_distance_per_label.get(label, float("inf"))
        )

    best_label = None
    best_vote = -1
    best_distance = float("inf")

    for label in vote_count:
        votes = vote_count[label]
        dist = min_distance_per_label[label]

        if votes > best_vote or (
            votes == best_vote and dist < best_distance
        ):
            best_label = label
            best_vote = votes
            best_distance = dist

    return best_label

The Goal

Tally the neighbors' labels to determine the final classification while using spatial proximity as a deterministic tie-breaker.

How It Works

Counting votes is straightforward with a hash map, but robust edge-case management is what separates a demo implementation from production-ready code.

Imagine a scenario where $k = 4$ and your query point sits exactly halfway between two Class A neighbors and two Class B neighbors. A naive implementation might simply choose whichever label appears first. That makes the classifier non-deterministic and biased by data ordering.

To address this, the implementation maintains a secondary dictionary:

min_distance_per_label

As the algorithm iterates through the neighbors, it tracks the minimum distance observed for each class label. If a voting tie occurs,

votes_{A} = votes_{B}

the algorithm chooses the class whose nearest representative is closest to the query point.

Mathematically:

ar g c min (x \in c min d (x, q))

Where:

$c$ is a class label.
$q$ is the query point.
$d (x, q)$ is the distance between a training sample and the query point.

This approach anchors tie-breaking in actual spatial proximity rather than arbitrary ordering or randomness.

3. The Orchestrator

import numpy as np

def knn_predict(training_data, labels, query_point, k):
    # ... input validation skipped ...

    distances = [
        euclidean_distance(sample, query_point)
        for sample in training_data
    ]

    nearest_idx = np.argsort(distances)[:k]

    neighbors = [
        {
            "distance": distances[i],
            "label": labels[i]
        }
        for i in nearest_idx
    ]

    return _get_majority_vote(neighbors)

The Goal

Create a controller function that computes distances, isolates the top $k$ candidates, and delegates classification to the voting logic.

How It Works

Although a production implementation would include comprehensive validation and optimization, the core algorithm relies on one key operation:

np.argsort(distances)[:k]

Keeping multiple arrays synchronized during sorting can quickly become messy. Rather than zipping distances and labels together, sorting them, and then unpacking them again, we sort only the distance values and retrieve the corresponding indices.

numpy.argsort() returns the indices that would sort an array. This allows us to select the nearest neighbors without mutating the original data structures.

Mathematically, we're selecting:

argsort (D)_{1}

where $D$ is the vector of computed distances.

This is a common scientific-computing pattern because it preserves the relationship between distances and labels while avoiding unnecessary data transformations.

After selecting the nearest indices, we package the neighbors into lightweight dictionaries and pass them directly to the voting mechanism.

Final Thoughts

K-Nearest Neighbors is a unique machine learning algorithm because it behaves less like a traditional parameter-learning model and more like a combination of geometric reasoning and voting heuristics.

Unlike algorithms such as linear regression or neural networks, KNN performs no explicit training. It simply stores the dataset and uses distance as a proxy for similarity during prediction.

Building algorithms from scratch is one of the fastest ways to demystify machine learning. You quickly discover that much of the perceived complexity comes from standard software engineering concerns:

Performance optimization
State management
Data validation
Numerical stability

The mathematics matters, but so does thoughtful implementation.

Stop Trusting Every JWT: How I Handle OIDC Claims in My Go Gateway

Darsh Ayde — Thu, 11 Jun 2026 10:06:22 +0000

Building a Secure OIDC Verification Layer in Go

Authentication is one of those things every backend engineer eventually has to build—and secretly dreads getting wrong. When I started architecting the auth layer for my Go API gateway, I naturally reached for OpenID Connect (OIDC). It’s the industry standard, so how hard could it be?

As it turns out, parsing a JWT is trivial. Trusting a JWT is where the trapdoors hide. If you blindly decode a token and trust the payload, you are exactly one spoofed signature away from a major security incident. I needed a way to dynamically discover my identity provider’s keys, cryptographically verify incoming requests, and strictly enforce the claims my backend actually cares about (like ensuring a user actually owns the email address they claim to).

In this post, I’ll walk you through how I built the OIDC verification layer for my gateway. We won't just look at the happy path; we’ll look at why I used interfaces to keep the auth logic mockable, how to avoid network traps during startup, and why an unassuming email_verified pointer is your gateway’s best friend.

High-Level Flow

Before we dive into the Go code, here is the basic verification flow this architecture follows:

Client
  |
  | ID Token (JWT)
  v
API Gateway
  |
  | 1. Discover OIDC provider metadata
  | 2. Verify JWT signature (via JWKS)
  | 3. Validate issuer and audience
  | 4. Extract strongly-typed claims
  | 5. Enforce application-specific rules (e.g., email verification)
  v
Authenticated User

(Note: The complete source code for this example is available on my GitHub: dearai-backend)

Breaking Down the Implementation

Let's look at how this breaks down in Go, starting from the core domain types and moving into runtime validation.

1. Designing for Testability

package auth

import (
    "context"
    "errors"
    "fmt"

    "github.com/coreos/go-oidc/v3/oidc"
)

type TokenVerifier interface {
    Verify(ctx context.Context, tokenString string) (*ExternalClaims, error)
}

Notice that the package exports a TokenVerifier interface rather than forcing consumers to use a concrete struct. This is classic dependency inversion.

When you're writing unit tests for your HTTP handlers or middleware, you really don't want them making live network calls to Google, Okta, or Auth0. By depending on this interface, you can easily inject a mock verifier that simply returns dummy claims for testing, keeping your test suite fast, offline, and deterministic.

2. Defining Expected Claims

type ExternalClaims struct {
    Subject       string `json:"sub"`
    Email         string `json:"email"`
    EmailVerified *bool  `json:"email_verified"`
}

type OIDCVerifier struct {
    verifier *oidc.IDTokenVerifier
}

We map the JWT payload into an ExternalClaims struct. The sub (subject) claim should always be treated as your primary user identifier. It is immutable and stable, making it the perfect key to link to your internal user records. While it's tempting to use the user's email as a unique identifier, emails change, which can break data relationships later.

You'll also notice EmailVerified is defined as a *bool (a pointer to a boolean) rather than a primitive bool. This is a deliberate choice. It allows us to differentiate between a claim that is explicitly set to false and a claim that is completely missing from the token payload (which evaluates to nil). Both scenarios should result in a rejected token, and a pointer allows us to catch both cleanly.

3. Discovery and the Network Trap

func NewOIDCVerifier(ctx context.Context, issuer, clientID string) (TokenVerifier, error) {
    if issuer == "" || clientID == "" {
        return nil, errors.New("issuer and clientID are required")
    }

    provider, err := oidc.NewProvider(ctx, issuer)
    if err != nil {
        return nil, fmt.Errorf("failed to discover OIDC configuration: %w", err)
    }

    return &OIDCVerifier{
        verifier: provider.Verifier(&oidc.Config{ClientID: clientID}),
    }, nil
}

Before any network activity occurs, the constructor validates its inputs to fail fast. Then, we call oidc.NewProvider. This is where OIDC discovery happens. The library hits the issuer's .well-known/openid-configuration endpoint to fetch metadata, including the JWKS (JSON Web Key Set) URL which contains the public keys needed to verify token signatures.

This is the only place in the setup phase where network I/O occurs. Because of this, it is critical to pass a context.Context with a reasonable timeout into this function. If the identity provider goes down during a deployment and you don't have a timeout, your application startup will block indefinitely.

4. The Verification Pipeline

func (v *OIDCVerifier) Verify(ctx context.Context, tokenString string) (*ExternalClaims, error) {
    idToken, err := v.verifier.Verify(ctx, tokenString)
    if err != nil {
        return nil, fmt.Errorf("cryptographic token verification failed: %w", err)
    }

    var claims ExternalClaims
    if err := idToken.Claims(&claims); err != nil {
        return nil, fmt.Errorf("failed to unmarshal token claims: %w", err)
    }

    if claims.Subject == "" {
        return nil, errors.New("invalid token: missing 'sub' claim")
    }

    if claims.Email == "" {
        return nil, errors.New("invalid token: missing 'email' claim")
    }

    if claims.EmailVerified == nil || !*claims.EmailVerified {
        return nil, errors.New("invalid token: email address is unverified")
    }

    return &claims, nil
}

The Verify method acts as our gatekeeper, enforcing rules in a very specific order.

First, we establish cryptographic trust by passing the raw token to v.verifier.Verify(). This leverages the provider's public keys to ensure the signature is mathematically valid, checks that the token hasn't expired, and verifies that the ClientID (Audience) matches your app. This last part is crucial—it prevents your gateway from accepting valid tokens that were actually minted for an entirely different application.

Once we trust the signature, we unmarshal the payload into our ExternalClaims struct to get strongly-typed Go values. Finally, we enforce our business logic trust. We ensure the sub and email aren't blank, and we evaluate that *bool to guarantee the identity provider has verified the user's email. If a token fails any of these steps, execution halts immediately and the request is dropped.

A Quick Note on Token Types

It’s worth mentioning that this specific implementation is designed to verify OIDC ID tokens, which are meant to communicate identity information (who the user is). Access tokens, on the other hand, are meant for API authorization (what the user can do) and often follow different validation rules depending on the provider. Make sure you are verifying the right token for your specific architecture.

Wrapping Up

Verifying an OIDC token requires a lot more rigor than just base64-decoding a JSON payload. By leveraging OIDC discovery and the go-oidc library, we get automatic key rotation handling and cryptographic certainty. Combine that with strictly typed claims and interface-driven design, and you end up with an auth layer that is secure, resilient, and highly testable.

DEV Community: Darsh Ayde

Building KNN from Scratch (Because import sklearn Feels Like Cheating)

Building K-Nearest Neighbors (KNN) From Scratch

1. The Distance Metric

The Goal

How It Works

2. The Voting Mechanism and Tie-Breakers

The Goal

How It Works

3. The Orchestrator

The Goal

How It Works

Final Thoughts

Further Reading

Stop Trusting Every JWT: How I Handle OIDC Claims in My Go Gateway

Building a Secure OIDC Verification Layer in Go

High-Level Flow

Breaking Down the Implementation

1. Designing for Testability

2. Defining Expected Claims

3. Discovery and the Network Trap

4. The Verification Pipeline

A Quick Note on Token Types

Wrapping Up

Further Reading