Algorithm For Generating a Short Link 🧮
Tags: go, redis, algorithms, development
Published: 2022-10-20 13:12:39

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](https://pkg.go.dev/crypto/sha256) of this hash function. SHA-256 is a patented cryptographic hash function that outputs a value that is 256 bits long.

```go
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. 

```go
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.

```go
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.

```go
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](https://projectex.dev/challenges/how-to-build-a-url-shortener-in-go-with-redis/)