Algorithm For Generating a Short Link 🧮

In the previous part, we manage to set up the server using Golang Echo. In this part, we are going to work on the algorithm that creates short URL from long URL.

For the implementation, we are going to use two main schemes - a hash function and a binary-to-text encoding algorithm.

First, we will need to create two files - shortener.go and shortener_test.go, inside a folder named shortener

├── go.mod
├── go.sum
├── main.go
└── shortener
   ├── shortener.go
   └── shortener_test.go

Then, we open shortener.go file and add the SHA-256 code below. We will use the Golang built-in implementation of this hash function. SHA-256 is a patented cryptographic hash function that outputs a value that is 256 bits long.

package shortener

import (
    "crypto/sha256"
)

func sha256Of(input string) []byte {
    algorithm := sha256.New()
    algorithm.Write([]byte(input))
    return algorithm.Sum(nil)
}

Next thing is to add encoding. In this tutorial, we will go with BASE58 one. I can see you re-reading the name of the encoding and thinking "58? 🤔 Did the author make a typo?". Well no, this encoding is a modification of the classic BASE64. it makes it easier for humans to read the result by eliminating 0 (zero), O (capital o), I (capital i), l (lower L), + (plus), and / (slash) characters to avoid confusion. Well, let’s add then the BASE58 encoding.

First things first - let’s load the BASE58 dependency library.

go get github.com/itchyny/base58-go/cmd/base58

Now, we'll extend the code with another function.

func base58Encoded(bytes []byte) string {
    encoding := base58.BitcoinEncoding
    encoded, err := encoding.Encode(bytes)
    if err != nil {
        fmt.Println(err.Error())
        os.Exit(1)
    }
    return string(encoded)
}

Since we have our two main building blocks (hashing and encoding) already in place, the final algorithm is easy.

• Hashing initialLink + userId with SHA-256. We use userId for preventing similar shortened URLs to different users in case they want to shorten the same URL.
• Derive a big integer number from the hash bytes generated during the hashing.
• Apply BASE58 on the derived big integer value and pick the first 8 characters.

func GenerateShortURL(initialLink string, userId string) string {
    urlHashBytes := sha256Of(initialLink + userId)
    generatedNumber := new(big.Int).SetBytes(urlHashBytes).Uint64()
    finalString := base58Encoded([]byte(fmt.Sprintf("%d", generatedNumber)))
    return finalString[:8]
}

Our algorithm is done. Let’s do some unit testing to be sure that it works as expected. We already created our test file shortener_test.go, so now we only need to add testify toolkit

go get github.com/stretchr/testify/assert

and some pieces of code.

package shortener

import (
    "github.com/stretchr/testify/assert"
    "testing"
)

func TestShortLinkGenerator(t *testing.T) {
    initialLink := "https://go.dev/doc/tutorial/getting-started"
    userId := "UwQPr3aIf9dM5x7r"
    shortLink := GenerateShortURL(initialLink, userId)

    assert.Equal(t, shortLink, "dysg5Fas")
}

With this, we are done with the implementation of the algorithm for generating a short URL. 🥳 We can execute all tests using the command go test ./... or only those inside the shortener folder with go test ./shortener assuming we are at the root of the project (on the same level with main.go)

Originally published at projectex.dev