blockchainDB

package
v0.0.0-...-92a6c4d Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 18, 2025 License: MIT Imports: 12 Imported by: 0

Documentation

Index

Constants

View Source 
const BufferSize = 1024 * 32 // Buffer size for values written to the BFile
View Source 
const DBKeyFullSize = 48
View Source 
const DynaDirName = "dyna"
View Source 
const IndexOffsets = 0 // byte index to a 16 bit int used to define keysets in a KFile
View Source 
const IndexShards = 4 // byte index to a 16 bit int used to define a shard for a key
View Source 
const (
	KeySetSize = 16
)
View Source 
const NumShards = 512
View Source 
const PermDirName = "perm"

Variables

This section is empty.

Functions

func ComputeTimePerOp 

func ComputeTimePerOp(tps float64) string

func ShardIndex 

func ShardIndex(key []byte) int

ShardIndex Returns the index of into the header for the given key

Types

type BFile 

type BFile struct {
	File     *os.File         // The file being buffered. It doesn't have to be kept open
	Filename string           // Fully qualified file name for the BFle
	Buffer   [BufferSize]byte // The current BFBuffer under construction
	EOB      uint64           // End within the buffer
	EOD      uint64           // Current EOD
}

Block BFile Holds the buffers and ID stuff needed to build DBBlocks (Database Blocks)

func NewBFile 

func NewBFile(filename string) (file *BFile, err error)

NewBFile Create a new BFile. An existing one will be overwritten

func OpenBFile 

func OpenBFile(filename string) (bFile *BFile, err error)

Open Open an existing BFile given a fully qualified filename

func (*BFile) Close 

func (b *BFile) Close() (err error)

Close Close the underlying file

func (*BFile) Flush 

func (b *BFile) Flush() (err error)

Flush Write out the buffer, and reset the EOB

func (*BFile) Offset 

func (b *BFile) Offset() (offset uint64, err error)

Offset Returns the current real size (file + EOB) of the BFile

func (*BFile) Open 

func (b *BFile) Open() (err error)

Open Opens the underlying file and positions the file location to the end of the file.

func (*BFile) ReadAt 

func (b *BFile) ReadAt(offset uint64, data []byte) (err error)

ReadAt Seek to the offset from start and read into the given data buffer. Note that to avoid a flush to disk, ReadAt must be smart about what is in the buffer vs what is on disk, and to open the file and read from it only if required.

func (*BFile) Write 

func (b *BFile) Write(Data []byte) (update bool, err error)

Write A Buffered Write given Data into the File. Returns:

update -- true if a actual file update occurs err -- nil on no error, the error if an error occurs

func (*BFile) WriteAt 

func (b *BFile) WriteAt(offset int64, data []byte) (err error)

WriteAt This is an unbuffered write; Does not involve the buffered writing Seek to the offset from start and write data ito the BFile

To Do: modify to allow writing to locations that overlap the buffer (Not really required as yet, since it is used to update buffers...)

type Bloom 

type Bloom struct {
	SizeOfMap float64
	NumBytes  uint64
	Map       []byte
	K         int // Number of hash functions
}

func NewBloom 

func NewBloom(size float64) *Bloom

NewBloom Create a Bloom Filter of the given size in MB

func NewBloomFilter 

func NewBloomFilter(size float64, k int) *Bloom

NewBloomFilter Create a Bloom Filter of the given size in MB with k hash functions

func (*Bloom) ByteMask 

func (b *Bloom) ByteMask(key [32]byte, hashNum int) (Index uint64, BitMask byte)

ByteMask generates an index and bitmask for a specific hash function

func (*Bloom) Set 

func (b *Bloom) Set(key [32]byte)

Set Set a bit in the Bloom Filter, because a Key is being added to the DB.

func (*Bloom) Test 

func (b *Bloom) Test(key [32]byte) bool

Test Test to see if an Address might be in the Database If Test returns false, the Address cannot be in the DB. If True, it might be, but you gotta check.

type DBBKey 

type DBBKey struct {
	Offset uint64
	Length uint64
}

func GetDBBKey 

func GetDBBKey(data []byte) (address [32]byte, dBBKey *DBBKey, err error)

GetDBBKey Converts a byte slice into an Address and a DBBKey

func (*DBBKey) Bytes 

func (d *DBBKey) Bytes(address [32]byte) []byte

Bytes Writes out the address with the offset and length of the DBBKey

func (*DBBKey) Print 

func (d *DBBKey) Print(key [32]byte) string

Print Debugging thing. Return the string representation of the Key & DBBKey

func (*DBBKey) Unmarshal 

func (d *DBBKey) Unmarshal(data []byte) (address [32]byte, err error)

Unmarshal Returns the address and the DBBKey from a slice of bytes

type DBBKeyFull 

type DBBKeyFull struct {
	Key    [32]byte //The Key
	DBBKey          // And its offset and Length
}

type FastRandom 

type FastRandom struct {
	// contains filtered or unexported fields
}

func NewFastRandom 

func NewFastRandom(seed []byte) *FastRandom

NewFastRandom() Returns a Fast Random Generator If no seed is provided, the seed will be generated by selecting a random nano second In order to make this seed near impossible to guess, we collect nano seconds in a loop which means the speed of the CPU and the load on the CPU will create unpredictable randomness in the seed.

func (FastRandom) Clone 

func (f FastRandom) Clone() *FastRandom

Make a clone of a FastRandom state as it currently exists

func (*FastRandom) NextBool 

func (f *FastRandom) NextBool() bool

func (*FastRandom) NextHash 

func (f *FastRandom) NextHash() (hash [32]byte)

NextHahs return a random 32 byte array

func (*FastRandom) RandBuff 

func (f *FastRandom) RandBuff(min uint, max uint) []byte

RandBuff Always returns a buffer of random bytes If max > 100 MB, max is set to 100 MB If max < 1, max is set to 1 If min > max, min is set to max

func (*FastRandom) RandChar 

func (f *FastRandom) RandChar(min uint, max uint) []byte

RandChar Returns a buffer of random hex characters If max > 100 MB, max is set to 100 MB If max < 1, max is set to 1 If min > max, min is set to max

func (*FastRandom) Reset 

func (f *FastRandom) Reset()

Reset() Reset the sequence produced by FastRandom to its initial state

func (*FastRandom) Step 

func (f *FastRandom) Step()

func (*FastRandom) Uint64 

func (f *FastRandom) Uint64() uint64

Uint64 Return a Uint64

func (*FastRandom) UintN 

func (f *FastRandom) UintN(N uint) uint

UintN Return an 0 >= int < N 

type Header struct {
	OffsetsCnt uint32   // Number of bins in the Offset Table
	HeaderSize uint32   // Length of the header
	Offsets    []uint64 // List of offsets
	EndOfList  uint64   // Offset marking end of the last Key section
}

Offset table for all the indexes in the KFile EndOfList is necessary because when we close the KFile, the list of keys will often be smaller. So the file will have stuff past the key list we need to ignore. This way, we have an offset to the end of valid keys.

func (*Header) Init 

func (h *Header) Init(OffsetsCnt uint64) *Header

Init Initiate a header to its default value for an empty BFile

func (*Header) Marshal 

func (h *Header) Marshal() []byte

Marshal Convert the Header to bytes

func (*Header) OffsetIndex 

func (h *Header) OffsetIndex(key []byte) int

OffsetIndex Returns the index of into the header for the given key

func (*Header) Unmarshal 

func (h *Header) Unmarshal(data []byte)

Unmarshal Convert bytes to a header

type HistoryFile 

type HistoryFile struct {
	// Not marshaled
	Mutex        sync.Mutex // Stops access to History during a reorg
	Directory    string     // Path to the file
	Filename     string     // Computed; directory + filename
	HeaderSize   uint64     // Computed based of IndexCnt
	File         *os.File   // Path to the History File
	KeySetOffset []*KeySet  // Offsets around key sets, in file offset order
	// Marshaled
	OffsetCnt int32     // Count of offsets to key sets
	KeySets   []*KeySet // Offsets around key sets, in key index order
}

func NewHistoryFile 

func NewHistoryFile(OffsetCnt uint64, Directory string) (historyFile *HistoryFile, err error)

NewHistoryFile Creates and initializes a HistoryFile. If one already exists, it is replaced with a fresh, new, empty HistoryFile

func (*HistoryFile) AddKeys 

func (hf *HistoryFile) AddKeys(keyList []byte) (err error)

AddKeys Take a buffer of Keys, sort them into bins, and add them to the History file. Assumes the keyList is already sorted into bins internally.

func (*HistoryFile) EOF 

func (hf *HistoryFile) EOF() uint64

EOF Return the last offset in the HistoryFile

func (*HistoryFile) Get 

func (hf *HistoryFile) Get(Key [32]byte) (dbBKey *DBBKey, err error)

Get Get the value for a given DBKeyFull. The value returned is free for the user to use (i.e. not part of a buffer used by the BFile)

func (*HistoryFile) Index 

func (hf *HistoryFile) Index(key [32]byte) int

Index Compute the index into the KeySets for this key

func (*HistoryFile) Marshal 

func (hf *HistoryFile) Marshal() []byte

Marshal Only marshals the header, which is written to the// Marshal Only marshals the header, which is written to the front of the History File

func (*HistoryFile) OffsetSort 

func (hf *HistoryFile) OffsetSort()

OffsetSort Sort the indexes by HistoryFile Offsets; Sort by the end, because empty keySets can have the same Start as one keySet...

func (*HistoryFile) Unmarshal 

func (hf *HistoryFile) Unmarshal(data []byte)

Unmarshal Unmarshals the header.

func (*HistoryFile) UpdateKeySet 

func (hf *HistoryFile) UpdateKeySet(index int, keyList []byte) (err error)

UpdateKeySet Add the given entries to the KeySet at the given index and update the History File

If the new keys fit where the KeySet is, just add them to the HistoryFile

If a KeySet does not fit where it is in the HistoryFile, Update it's start and end to where it can fit, and update the KeySets offsets, and the HistoryFile. Mem

type KFile 

type KFile struct {
	Header                               // kFile header (what is pushed to disk)
	Directory       string               // Directory of the BFile
	File            *BFile               // Key File
	History         *HistoryFile         // The History Database (nil if history is disabled)
	Cache           map[[32]byte]*DBBKey // Cache of DBBKey Offsets
	BlocksCached    int                  // Track blocks cached before rewritten
	HistoryMutex    sync.Mutex           // Allow the History to be merged in background
	KeyCnt          uint64               // Number of keys in the current KFile
	TotalCnt        uint64               // Total number of keys processed
	OffsetCnt       uint64               // Number of key sets in the kFile
	KeyLimit        uint64               // How many keys triggers to send keys to History
	MaxCachedBlocks int                  // Maximum number of keys cached before flushing to kfile
	HistoryOffsets  int                  // History offset cnt
	BloomFilter     *Bloom               // Bloom filter for quick key existence checks
}

Block File Holds the buffers and ID stuff needed to build DBBlocks (Database Blocks)

KFile can operate in two modes based on whether history is enabled or disabled:

1. With History Enabled (used in PermKV):

  • Values are immutable - once a key is associated with a value, it cannot be changed
  • Attempting to overwrite a key with a different value will result in an error
  • Overwriting a key with the same value is allowed (no-op)
  • Suitable for content-addressed storage where keys are derived from values (e.g., hash of value)
  • Uses a Bloom filter to optimize key lookups and avoid unnecessary disk I/O

2. With History Disabled (used in DynaKV):

  • Values are mutable - keys can be freely associated with different values over time
  • Overwriting a key with a different value is allowed
  • Suitable for state storage where keys have an arbitrary relationship to values

Performance Optimizations: - Uses a Bloom filter to quickly determine if a key definitely doesn't exist - Checks the Bloom filter before any disk I/O operations - In Put operations, uses the Bloom filter to avoid unnecessary disk lookups - Memory usage is optimized by having a single Bloom filter per KFile

func NewKFile 

func NewKFile(
	history bool,
	directory string,
	offsetCnt uint64,
	keyLimit uint64,
	maxCachedBlocks int) (kFile *KFile, err error)

func OpenKFile 

func OpenKFile(directory string) (kFile *KFile, err error)

Open Open an existing k.File

func (*KFile) Close 

func (k *KFile) Close() (err error)

Close Take everything in flight and write it to disk, then close the file. Note that if an error occurs while updating the BFile, the BFile will be trashed.

func (*KFile) Flush 

func (k *KFile) Flush() (err error)

Flush Flush the buffer to disk, and clear the cache

func (*KFile) Get 

func (k *KFile) Get(Key [32]byte) (dbBKey *DBBKey, err error)

Get Get the value for a given DBKeyFull. The value returned is free for the user to use (i.e. not part of a buffer used by the BFile). If the key is not found, the code will look at the history.

func (*KFile) GetKeyList 

func (k *KFile) GetKeyList() (keyValues map[[32]byte]*DBBKey, KeyList [][32]byte, err error)

GetKeyList Returns all the keys and their values, and a list of the keys sorted by the key bins.

func (*KFile) LoadHeader 

func (k *KFile) LoadHeader() (err error)

LoadHeader Load the Header out of the Key File

func (*KFile) Open 

func (k *KFile) Open() error

Open Make sure the underlying File is open for adding keys. Sets the location in the file for writing to the end of the file.

func (*KFile) PopulateBloomFilterFromHistory 

func (k *KFile) PopulateBloomFilterFromHistory() error

PopulateBloomFilterFromHistory Populates the Bloom filter with all existing keys in the history file This should be called when opening a KFile with history enabled

func (*KFile) PushHistory 

func (k *KFile) PushHistory() (err error)

PushHistory Creates a new kFile height. Merges the keys of the current kFile into the History. Resets the KFile to accept more keys.

func (*KFile) Put 

func (k *KFile) Put(Key [32]byte, dbBKey *DBBKey) (err error)

Put Put a key value pair into the BFile, return the *DBBKeyFull

Behavior depends on whether history is enabled:

  • With history enabled (k.History != nil): Values are immutable. If the key already exists with a different value, an error is returned. Overwriting with the same value is a no-op.
  • With history disabled (k.History == nil): Values are mutable. Keys can be freely overwritten with different values.

This design supports two use cases:

  1. Content-addressed storage (history enabled): Where keys are derived from values (e.g., hash) and immutability is required.
  2. State storage (history disabled): Where keys have an arbitrary relationship to values and need to be updated over time.

func (*KFile) WriteHeader 

func (k *KFile) WriteHeader() (err error)

WriteHeader Write the Header to the Key File

type KV 

type KV struct {
	Directory string

	HistoryFile *HistoryFile
	UseHistory  bool
	// contains filtered or unexported fields
}

func NewKV 

func NewKV(history bool, directory string, offsetsCnt, KeyLimit uint64, MaxCachedBlocks int) (kv *KV, err error)

NewKV Overwrites any existing directory; directories are created for the vFile and kFile

func OpenKV 

func OpenKV(directory string) (kv *KV, err error)

OpenKV Open an existing Key/Value Database that uses separate BFiles to hold values and keys.

func (*KV) Close 

func (k *KV) Close() (err error)

func (*KV) Compress 

func (k *KV) Compress() (err error)

Compress Re-write the values file to remove trash values

func (*KV) Get 

func (k *KV) Get(key [32]byte) (value []byte, err error)

Get Get the key from the key file, then pull the value from the value file

func (*KV) Open 

func (k *KV) Open() (err error)

func (*KV) Put 

func (k *KV) Put(key [32]byte, value []byte) (err error)

Put Put the key into the kFile, and the value in the vFile

type KV2 

type KV2 struct {
	Directory string // Directory where the PermKV and DynaKV directories are
	PermKV    *KV    // The Perm KV
	DynaKV    *KV    // the Dyna KV
	DWrites   int    // Number of writes to the DynaKV since the last compress
	PWrites   int    // Number of writes to the PermKV since the last compress
}

func NewKV2 

func NewKV2(directory string, offsetsCnt, KeyLimit uint64, MaxCachedBlocks int) (kv2 *KV2, err error)

NewKV2 Create a two level KV file with different immutability characteristics:

1. PermKV: Uses KFile with history enabled (immutable values)

  • Created with history=true
  • Once a key is associated with a value, it cannot be changed
  • If a key in PermKV needs to be updated, it's moved to DynaKV

2. DynaKV: Uses KFile with history disabled (mutable values)

  • Created with history=false
  • Keys can be freely associated with different values over time

This design efficiently separates immutable data (content-addressed storage) from mutable data (state storage) in a blockchain-style database.

func OpenKV2 

func OpenKV2(directory string) (kv2 *KV2, err error)

func (*KV2) Close 

func (k *KV2) Close() error

func (*KV2) Compress 

func (k *KV2) Compress()

Compress Only DynaKV is compressed, since PermKV doesn't change. That does mean one bogus DynaKV key will exist in PermKV.

TODO: Cleanse PermKV of keys in DynaKV

func (*KV2) Get 

func (k *KV2) Get(key [32]byte) (value []byte, err error)

Get Get a value from the KV2. Checks the DynaKV first, then the PermKV

func (*KV2) GetDyna 

func (k *KV2) GetDyna(key [32]byte) (value []byte, err error)

GetDyna Get a k/v from the DynaKV db. Doesn't check the PermKV.

func (*KV2) GetPerm 

func (k *KV2) GetPerm(key [32]byte) (value []byte, err error)

GetPerm Get a k/v from the PermKV db. Doesn't check the DynaKV.

func (*KV2) Open 

func (k *KV2) Open() error

func (*KV2) Put 

func (k *KV2) Put(key [32]byte, value []byte) (writes int, err error)

Put Returns the number of writes since the last compress, and an err if the put failed

func (*KV2) PutDyna 

func (k *KV2) PutDyna(key [32]byte, value []byte) (writes int, err error)

PutDyna Use when the k/v is known to be a dynamic k/v

func (*KV2) PutPerm 

func (k *KV2) PutPerm(key [32]byte, value []byte) (writes int, err error)

PutPerm Use when the k/v is known to be a dynamic k/v

type KVShard 

type KVShard struct {
	Directory string
	Shards    [NumShards]*KV2
}

func NewKVShard 

func NewKVShard(directory string, offsetsCnt, keyLimit uint64, MaxCachedBlocks int) (kvs *KVShard, err error)

NewKVShard Create a new KVShard database. This database creates database shards to reduce the overhead of compressing large database files.

func OpenKVShard 

func OpenKVShard(directory string) (kVShard *KVShard, err error)

OpenKVShard Open an existing KVShard Database

func (*KVShard) Close 

func (k *KVShard) Close() (err error)

Close Close all the shards

func (*KVShard) Compress 

func (k *KVShard) Compress() (err error)

Compress Compress all the shards

func (*KVShard) Get 

func (k *KVShard) Get(key [32]byte) (value []byte, err error)

Get Find the right shard, and extract the value from said shard

func (*KVShard) GetDyna 

func (k *KVShard) GetDyna(key [32]byte) (value []byte, err error)

GetDyna Find the right shard, and extract the value from the DynaKV in the shard

func (*KVShard) GetPerm 

func (k *KVShard) GetPerm(key [32]byte) (value []byte, err error)

GetPerm Find the right shard, and extract the value from the PermKV in the shard

func (*KVShard) Put 

func (k *KVShard) Put(key [32]byte, value []byte) (err error)

Put Find the right shard, and put the key/value in said shard

func (*KVShard) PutDyna 

func (k *KVShard) PutDyna(key [32]byte, value []byte) (err error)

PutDyna Find the right shard, and put the key/value in the DynaKV in the shard

func (*KVShard) PutPerm 

func (k *KVShard) PutPerm(key [32]byte, value []byte) (err error)

PutPerm Find the right shard, and put the key/value in the PermKV in the shard

func (*KVShard) ShardDir 

func (k *KVShard) ShardDir(index int) string

type KVView 

type KVView struct {
	DB          *KVShard      // The underlying DB
	ViewID      int           // The next ViewID
	ActiveViews []*View       // List of all active Views, newest first
	Map         map[int]View  // Fast lookup of a view
	Timeout     time.Duration // How long before views timeout; every access resets timeout
	OffsetCnt   uint64        // KeyOffset number for the key files
	KeyLimit    uint64        // KeyLimit sets when to move keys to History
}

KVView A wrapper around a sharded DB that implements Views. Views are created in a stack. More recent views lookup values in their cache, and then in the views that come before. Later views are ignored.

func NewShardDBViews 

func NewShardDBViews(
	Directory string,
	Timeout time.Duration,
	Partition, ShardCnt,
	BufferCnt,
	OffsetCnt, KeyLimit uint64,
	MaxCachedBlocks int) (sdbV *KVView, err error)

func OpenShardDBViews 

func OpenShardDBViews(
	Directory string,
	Timeout time.Duration,
	Partition,
	BufferCnt int) (sdbV *KVView, err error)

func (*KVView) Close 

func (s *KVView) Close()

func (*KVView) Get 

func (s *KVView) Get(key [32]byte) (value []byte, err error)

func (*KVView) GetViewIndex 

func (s *KVView) GetViewIndex(view *View) int

GetViewIndex Returns the view index for a view. Returns 0 if view is closed.

func (*KVView) IsViewActive 

func (s *KVView) IsViewActive() bool

Active Views Returns true if a valid active view exists. If old views exist, but none are active, the active views are tossed.

func (*KVView) NewView 

func (s *KVView) NewView() *View

func (*KVView) Put 

func (s *KVView) Put(key [32]byte, value []byte) error

func (*KVView) ViewGet 

func (s *KVView) ViewGet(view *View, key [32]byte) (value []byte, err error)

ViewGet To a get of a key value pair using a view. The view is searched first, and all active views that were created before this view are searched in turn. If no key value pair is found in the view or older views, then return what the DB has

type KeySet 

type KeySet struct {
	OffsetIndex uint64 // Offset Order (enables KeySet Index -> Offset Index)
	KeySetIndex uint64 // KeySet Order (enables Offset Index -> KeySet Index)
	Start       uint64 // offset to the start of KeySet
	End         uint64 // offset to the first entry after the KeySet
}

KeySet The starting offset and ending offset for each KeySet Start points to the next entry in the KeySet. End points to the entry after the last entry in the KeySet.

If Start == End then the KeySet is empty.

func (*KeySet) Marshal 

func (ks *KeySet) Marshal() []byte

func (*KeySet) Unmarshal 

func (ks *KeySet) Unmarshal(buff []byte)

type View 

type View struct {
	ID         int                 // ID of a view
	KeyValues  map[[32]byte][]byte // key value pairs
	LastAccess time.Time           // time that the view was created
	Closed     bool                // true if the View is closed
	KVView     *KVView             // The KV database with views
}

View Struct Views allow one to grab a point in time in the database, and query values that were in the DB at that time (writes after creating a view do not impact the view)

func (*View) Get 

func (v *View) Get(key [32]byte) (value []byte, err error)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.