Erasure Coded Storage Cluster with Random Linear Netork Coding --- simulated using `kodr`

go.mod

module rlnc_in_storage

go 1.16

require github.com/itzmeanjan/kodr v0.2.0

main.go

package main

import (
	"crypto/sha256"
	"encoding/hex"
	"log"
	"math/rand"
	"os"
	"time"

	"github.com/itzmeanjan/kodr"
	"github.com/itzmeanjan/kodr/full"
)

func main() {
	rand.Seed(time.Now().UnixNano())

	video, err := os.ReadFile("file.mp4")
	if err != nil {
		log.Printf("Error: %s\n", err.Error())
		os.Exit(1)
	}

	log.Printf("Encoding ::\n\n")
	log.Printf("Read %d bytes\n", len(video))

	hasher := sha256.New()
	hasher.Write(video)
	sum := hasher.Sum(nil)
	log.Printf("SHA256(original): 0x%s\n\n", hex.EncodeToString(sum))

	var (
		pieceCount   = 32
		c_pieceCount = 64
	)

	enc, err := full.NewFullRLNCEncoderWithPieceCount(video, uint(pieceCount))
	if err != nil {
		log.Printf("Error: %s\b", err.Error())
		os.Exit(1)
	}

	c_pieces := make([]*kodr.CodedPiece, 0, c_pieceCount)
	for i := 0; i < c_pieceCount; i++ {
		c_piece := enc.CodedPiece()
		c_pieces = append(c_pieces, c_piece)
	}

	log.Printf("Original Piece Size: %d bytes\n", enc.PieceSize())
	log.Printf("Padded with %d bytes\n", enc.Padding())
	log.Printf("Coded Piece Size: %d bytes\n", enc.CodedPieceLen())
	log.Printf("Required %d bytes for decoding\n", enc.DecodableLen())
	log.Printf("Coded to %d pieces\n\n", c_pieceCount)

	{
		log.Printf("Decoding ( 1 ) ::\n\n")
		// random shuffle to demonstrate coded pieces being collected from random locations
		// all over network
		rand.Shuffle(c_pieceCount, func(i, j int) {
			c_pieces[i], c_pieces[j] = c_pieces[j], c_pieces[i]
		})

		have_c_pieces := c_pieces[:pieceCount]
		dec := full.NewFullRLNCDecoder(uint(pieceCount))
		for i := 0; i < pieceCount; i++ {
			dec.AddPiece(have_c_pieces[i])
		}

		if dec.IsDecoded() {
			log.Println("Decoded !")
		} else {
			log.Println("32 random pieces were not enough !")
			return // yes just returning back, try again
		}

		d_pieces, err := dec.GetPieces()
		if err != nil {
			log.Printf("Error: %s\n", err.Error())
			os.Exit(1)
		}

		flattened := make([]byte, 0)
		for i := range d_pieces {
			flattened = append(flattened, d_pieces[i]...)
		}

		hasher.Reset()
		hasher.Write(flattened)
		sum = hasher.Sum(nil)
		log.Printf("SHA256(decoded): 0x%s\n\n", hex.EncodeToString(sum))
	}

	log.Printf("Recoding ::\n\n")
	rand.Shuffle(c_pieceCount, func(i, j int) {
		c_pieces[i], c_pieces[j] = c_pieces[j], c_pieces[i]
	})

	log.Println("24 pieces unavailable, reconstructing new coded pieces ...")
	available_c_pieces := c_pieces[:40]
	r_pieces := make([]*kodr.CodedPiece, 0, 24)
	{
		rec := full.NewFullRLNCRecoder(available_c_pieces[:20])
		for i := 0; i < 8; i++ {
			r_piece, err := rec.CodedPiece()
			if err != nil {
				log.Printf("Error: %s\n", err.Error())
				os.Exit(1)
			}

			r_pieces = append(r_pieces, r_piece)
		}
		log.Println("8 recoded pieces from 20 coded pieces")
	}
	{
		rec := full.NewFullRLNCRecoder(available_c_pieces[10:30])
		for i := 0; i < 8; i++ {
			r_piece, err := rec.CodedPiece()
			if err != nil {
				log.Printf("Error: %s\n", err.Error())
				os.Exit(1)
			}

			r_pieces = append(r_pieces, r_piece)
		}
		log.Println("8 recoded pieces from 20 coded pieces")
	}
	{
		rec := full.NewFullRLNCRecoder(available_c_pieces[20:])
		for i := 0; i < 8; i++ {
			r_piece, err := rec.CodedPiece()
			if err != nil {
				log.Printf("Error: %s\n", err.Error())
				os.Exit(1)
			}

			r_pieces = append(r_pieces, r_piece)
		}
		log.Println("8 recoded pieces from 20 coded pieces")
	}

	log.Println("24 recoded pieces made from 40 available coded pieces")
	available_c_pieces = append(available_c_pieces, r_pieces...)
	log.Printf("Total %d coded pieces available now !\n\n", len(available_c_pieces))

	{
		log.Printf("Decoding ( 2 ) ::\n\n")
		rand.Shuffle(c_pieceCount, func(i, j int) {
			available_c_pieces[i], available_c_pieces[j] = available_c_pieces[j], available_c_pieces[i]
		})

		have_c_pieces := available_c_pieces[:pieceCount]
		dec := full.NewFullRLNCDecoder(uint(pieceCount))
		for i := 0; i < pieceCount; i++ {
			dec.AddPiece(have_c_pieces[i])
		}

		if dec.IsDecoded() {
			log.Println("Decoded !")
		} else {
			log.Println("32 random pieces were not enough !")
			return // yes just returning back, try again
		}

		d_pieces, err := dec.GetPieces()
		if err != nil {
			log.Printf("Error: %s\n", err.Error())
			os.Exit(1)
		}

		flattened := make([]byte, 0)
		for i := range d_pieces {
			flattened = append(flattened, d_pieces[i]...)
		}

		hasher.Reset()
		hasher.Write(flattened)
		sum = hasher.Sum(nil)
		log.Printf("SHA256(decoded_): 0x%s\n", hex.EncodeToString(sum))
	}
}

Background

This simulation accompanies the post I wrote on possibility of using Random Linear Network Coding in storage cluster. It makes use of kodr, a RLNC library I'm writing in Golang for demonstrating so.

You may want to read aforementioned post in order to get more context.

Usage

• Download gist & make sure you've Golang >=1.16 installed.

Note: You need to have file.mp4 in project directory, which I don't supply but simulation expects, otherwise fails.

• Download dependency

go get -u

• Run simulation

go run main.go

You should see something like below in console

2021/08/09 15:24:15 Encoding ::

2021/08/09 15:24:15 Read 16265760 bytes
2021/08/09 15:24:15 SHA256(original): 0xdfc734fc40a98e8a6e041af13893f6170f073b160dfdc16621e76ad4e6b847b4

2021/08/09 15:24:19 Original Piece Size: 508305 bytes
2021/08/09 15:24:19 Padded with 0 bytes
2021/08/09 15:24:19 Coded Piece Size: 508337 bytes
2021/08/09 15:24:19 Required 16266784 bytes for decoding
2021/08/09 15:24:19 Coded to 64 pieces

2021/08/09 15:24:19 Decoding ( 1 ) ::

2021/08/09 15:24:23 Decoded !
2021/08/09 15:24:23 SHA256(decoded): 0xdfc734fc40a98e8a6e041af13893f6170f073b160dfdc16621e76ad4e6b847b4

2021/08/09 15:24:23 Recoding ::

2021/08/09 15:24:23 24 pieces unavailable, reconstructing new coded pieces ...
2021/08/09 15:24:23 8 recoded pieces from 20 coded pieces
2021/08/09 15:24:23 8 recoded pieces from 20 coded pieces
2021/08/09 15:24:24 8 recoded pieces from 20 coded pieces
2021/08/09 15:24:24 24 recoded pieces made from 40 available coded pieces
2021/08/09 15:24:24 Total 64 coded pieces available now !

2021/08/09 15:24:24 Decoding ( 2 ) ::

2021/08/09 15:24:28 Decoded !
2021/08/09 15:24:28 SHA256(decoded_): 0xdfc734fc40a98e8a6e041af13893f6170f073b160dfdc16621e76ad4e6b847b4