How I built a key value store in Go

The problem — Optimizing Disk Seeks

The Solution — Btree

// DiskNode - In memory node implementationtype DiskNode struct {keys             []*pairschildrenBlockIDs []uint64blockID          uint64blockService     *blockService}
// diskBlock -- Make sure that it is accomodated in blockSize = 4096type diskBlock struct {id                  uint64   // 4096 - 8 = 4088currentLeafSize     uint64   // 4088 - 8 = 4080currentChildrenSize uint64   // 4080 - 8 = 4072childrenBlockIds    []uint64 // 352 - (8 * 30) =  112dataSet             []*pairs // 4072 - (124 * 30) = 352}
func (bs *blockService) getBufferFromBlock(block *diskBlock) []byte {blockBuffer := make([]byte, blockSize)
blockOffset := 0
//Write Block index
copy(blockBuffer[blockOffset:], uint64ToBytes(block.id))
blockOffset += 8
copy(blockBuffer[blockOffset:], uint64ToBytes(block.currentLeafSize))
blockOffset += 8
copy(blockBuffer[blockOffset:], uint64ToBytes(block.currentChildrenSize))
blockOffset += 8
//Write actual pairs now
for i := 0; i < int(block.currentLeafSize); i++ {
copy(blockBuffer[blockOffset:], convertPairsToBytes(block.dataSet[i]))
blockOffset += pairSize
}
// Read children block indexes
for i := 0; i < int(block.currentChildrenSize); i++ {
copy(blockBuffer[blockOffset:], uint64ToBytes(block.childrenBlockIds[i]))
blockOffset += 8
}
return blockBuffer
}
func (bs *blockService) getBlockFromBuffer(blockBuffer []byte) *diskBlock {blockOffset := 0
block := &diskBlock{}
//Read Block indexblock.id = uint64FromBytes(blockBuffer[blockOffset:])blockOffset += 8block.currentLeafSize = uint64FromBytes(blockBuffer[blockOffset:])blockOffset += 8block.currentChildrenSize = uint64FromBytes(blockBuffer[blockOffset:])blockOffset += 8//Read actual pairs nowblock.dataSet = make([]*pairs, block.currentLeafSize)for i := 0; i < int(block.currentLeafSize); i++ {block.dataSet[i] = convertBytesToPair(blockBuffer[blockOffset:])blockOffset += pairSize}// Read children block indexesblock.childrenBlockIds = make([]uint64, block.currentChildrenSize)for i := 0; i < int(block.currentChildrenSize); i++ {block.childrenBlockIds[i] = uint64FromBytes(blockBuffer[blockOffset:])blockOffset += 8}return block}
func (bs *blockService) convertBlockToDiskNode(block *diskBlock) *DiskNode {node := &DiskNode{}node.blockService = bsnode.blockID = block.idnode.keys = make([]*pairs, block.currentLeafSize)for index := range node.keys {node.keys[index] = block.dataSet[index]}node.childrenBlockIDs = make([]uint64, block.currentChildrenSize)for index := range node.childrenBlockIDs {node.childrenBlockIDs[index] = block.childrenBlockIds[index]}return node}

--

--

--

Golang/Java/Node.Js

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How to create a Vulnerable Box

Ruby chip cookie: Loading and Requiring

Spring Boot H2 Database Setup

My First Engagement

Secrets to Win a Hackathon

How to secure your cloud data with Cryptomator

Compress and Decompress a . bzip2 File in Linux

Getting started with Web Development

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Syed Jafar Naqvi

Syed Jafar Naqvi

Golang/Java/Node.Js

More from Medium

gRPC-go - How are the bytes written in HTTP/2 streams?

What I Learned This Week (15-Feb-2021 to 21-Feb-2021)

Optimizing the service response time by using MapReduce

Go gRPC vs REST