birdsnest

package
v2.3.3 Latest Latest
Warning

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

Go to latest
Published: Oct 19, 2023 License: Apache-2.0 Imports: 22 Imported by: 0

Documentation

Overview

Package birdsnest bird's nest implement

Package birdsnest configuration implement

Copyright (C) BABEC. All rights reserved.

SPDX-License-Identifier: Apache-2.0

Copyright (C) BABEC. All rights reserved.

SPDX-License-Identifier: Apache-2.0

Copyright (C) BABEC. All rights reserved.

SPDX-License-Identifier: Apache-2.0

Package birdsnest filter extension

Copyright (C) BABEC. All rights reserved.

SPDX-License-Identifier: Apache-2.0

Package birdsnest interface

Package birdsnest key

Package birdsnest rules

Package birdsnest serialize

Package birdsnest snapshot

Package birdsnest strategy

Package birdsnest test util

Package birdsnest utils

Index

Constants

View Source
const (
	// DefaultLoadFactor Default load factor
	DefaultLoadFactor = 0.98
)
View Source
const (
	Filepath = "birdsnest"
)
View Source
const TestDir = "./data/timestamp_birds_nest"

TestDir test path

Variables

View Source
var (
	// ErrKeyCannotBeEmpty key can not be empty error
	ErrKeyCannotBeEmpty = errors.New("key cannot be empty")
	// ErrCannotModifyTheNestConfiguration cannot modify the nest configuration error
	ErrCannotModifyTheNestConfiguration = errors.New("when historical data exists, you cannot modify the nest " +
		"configuration")
	// ErrBirdsNestSizeCannotBeZero bird's nest size cannot be zero error
	ErrBirdsNestSizeCannotBeZero = errors.New("the size cannot be 0")
)
View Source
var (
	// SeparatorString -
	SeparatorString = "-"
	// Separator chainmaker ca
	Separator = byte(202)

	// ErrKeyLengthCannotBeZero key length cannot be zero error
	ErrKeyLengthCannotBeZero = errors.New("the key length cannot be 0")
	// ErrNotTimestampKey not timestamp key error
	ErrNotTimestampKey = errors.New("not timestamp txid")
	// ErrTimestampKeyIsInvalid timestamp key is invalid
	ErrTimestampKeyIsInvalid = errors.New("TxId nanosecond is invalid")
)
View Source
var (
	ErrFilterExtensionNotSupportMessage = "filter extension not support type: %v"
)
View Source
var (
	// ErrKeyItsSoLongAgoError key it's so long ago error
	ErrKeyItsSoLongAgoError = errors.New("key is out of the range")
)
View Source
var (
	// ErrKeyTimeIsNotInTheFilterRange Not error; Key time is not in the filter range
	ErrKeyTimeIsNotInTheFilterRange = errors.New("key time is not in the filter range")
)
View Source
var KeyType_name = map[KeyType]string{
	KeyType_KTDefault:      "Default",
	KeyType_KTTimestampKey: "TimestampKey",
}

KeyType_name key type name map

View Source
var SerializeIntervalType_name = map[SerializeIntervalType]string{
	SerializeIntervalType_Height: "Height",
	SerializeIntervalType_Timed:  "Timed",
	SerializeIntervalType_Exit:   "Exit",
}

SerializeIntervalType_name SerializeIntervalType name map

Functions

func CurrentTimestampNano

func CurrentTimestampNano() int64

CurrentTimestampNano get current timestamp nanosecond

func Factory

func Factory() *factory

Factory return the global tx filter factory. nolint: revive

func GenTimestampKey

func GenTimestampKey() string

GenTimestampKey generate timestamp key

func GenTimestampKeyByNano

func GenTimestampKeyByNano(nano int64) string

GenTimestampKeyByNano generate timestamp key by nanosecond

func GenTxId

func GenTxId() string

GenTxId generate tx id

func LruStrategy

func LruStrategy(bn *BirdsNestImpl) error

LruStrategy Nest filter cycle elimination strategy

func ToStrings

func ToStrings(keys []Key) []string

ToStrings TimestampKey to string

func ToTimestampKeysAndNormalKeys

func ToTimestampKeysAndNormalKeys(key []string) (timestampKeys []Key, normalKeys []Key)

ToTimestampKeysAndNormalKeys string to TimestampKey return timestampKeys and normalKeys

Types

type AbsoluteExpireTimeRule

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

AbsoluteExpireTimeRule absolute expire time rule

func NewAETRule

func NewAETRule(absoluteExpireTime int64, logger Logger) AbsoluteExpireTimeRule

NewAETRule new absolute expire time rule

func (AbsoluteExpireTimeRule) Validate

func (r AbsoluteExpireTimeRule) Validate(key Key) error

Validate timestamp key

type BirdsNest

type BirdsNest interface {
	GetHeight() uint64
	SetHeight(height uint64)
	// Add the key
	Add(key Key) error
	// Adds adding Multiple Keys
	Adds(keys []Key) (result error)
	// AddsAndSetHeight Adds and SetHeight
	AddsAndSetHeight(keys []Key, height uint64) (result error)
	// Contains the key
	Contains(key Key, rules ...RuleType) (bool, error)
	ValidateRule(key Key, rules ...RuleType) error
	// Info Current cuckoos nest information and status
	Info() []uint64

	Start()
}

BirdsNest Bird's Nest

type BirdsNestConfig

type BirdsNestConfig struct {
	// ChainId
	ChainId string `json:"chain_id,omitempty"`
	// Length cuckoo numbers
	Length uint32 `json:"length,omitempty"`
	// rules configuration
	Rules *RulesConfig `json:"rules,omitempty"`
	// Cuckoo configuration
	Cuckoo *CuckooConfig `json:"cuckoo,omitempty"`
	// Snapshot configuration
	Snapshot *SnapshotSerializerConfig `json:"snapshot,omitempty"`
}

type BirdsNestImpl

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

BirdsNestImpl impl

func NewBirdsNest

func NewBirdsNest(config *BirdsNestConfig, exitC chan struct{}, strategy Strategy, logger Logger) (
	*BirdsNestImpl, error)

NewBirdsNest Create a BirdsNest

func NewBirdsNestByNumber

func NewBirdsNestByNumber(config *BirdsNestConfig, exitC chan struct{}, strategy Strategy, logger Logger,
	number int) (*BirdsNestImpl, error)

NewBirdsNestByNumber Create a numbered BirdsNest

func (*BirdsNestImpl) Add

func (b *BirdsNestImpl) Add(key Key) error

Add a Key

func (*BirdsNestImpl) Adds

func (b *BirdsNestImpl) Adds(keys []Key) error

Adds Add multiple Key

func (*BirdsNestImpl) AddsAndSetHeight

func (b *BirdsNestImpl) AddsAndSetHeight(keys []Key, height uint64) (result error)

AddsAndSetHeight Add multiple Key and set height

func (*BirdsNestImpl) Contains

func (b *BirdsNestImpl) Contains(key Key, rules ...RuleType) (bool, error)

Contains returns whether the filter exists sync

func (*BirdsNestImpl) Deserialize

func (b *BirdsNestImpl) Deserialize() error

Deserialize deserialize Bird's nest

func (*BirdsNestImpl) GetHeight

func (b *BirdsNestImpl) GetHeight() uint64

GetHeight get current height

func (*BirdsNestImpl) Info

func (b *BirdsNestImpl) Info() []uint64

Info index 0 height index 1 cuckoo size index 2 current index index 3 total cuckoo size index 4 total space occupied by cuckoo

func (*BirdsNestImpl) Serialize

func (b *BirdsNestImpl) Serialize(index int) error

Serialize cuckoo of index in current BirdsNest

func (*BirdsNestImpl) SetHeight

func (b *BirdsNestImpl) SetHeight(height uint64)

SetHeight set height

func (*BirdsNestImpl) Start

func (b *BirdsNestImpl) Start()

Start serialize monitor TODO Goroutinue should be turned off using context.Context here

func (*BirdsNestImpl) ValidateRule

func (b *BirdsNestImpl) ValidateRule(key Key, rules ...RuleType) error

type BirdsNestSerialize

type BirdsNestSerialize struct {
	// Bird's Nest config
	Config *BirdsNestConfig `protobuf:"bytes,1,opt,name=config,proto3" json:"config,omitempty"`
	// The final height
	Height uint64 `protobuf:"varint,2,opt,name=height,proto3" json:"height,omitempty"`
	// current index
	CurrentIndex uint32 `protobuf:"varint,3,opt,name=currentIndex,proto3" json:"currentIndex,omitempty"`
	// A group of cuckoos filter
	Filters []*CuckooFilterSerialize `protobuf:"bytes,4,rep,name=filters,proto3" json:"filters,omitempty"`
}

BirdsNestSerialize Bird's nest serialize

type BlockHeightSerializeIntervalConfig

type BlockHeightSerializeIntervalConfig struct {
	// Block height Interval
	Interval uint64 `json:"interval,omitempty"`
}

BlockHeightSerializeIntervalConfig Block height serialization interval configuration

type CuckooConfig

type CuckooConfig struct {
	// KeyType key type
	KeyType KeyType `json:"key_type,omitempty"`
	// TagsPerBucket num of tags for each bucket, which is b in paper. tag is fingerprint, which is f in paper.
	TagsPerBucket uint32 `json:"tags_per_bucket,omitempty"`
	// BitsPerItem num of bits for each item, which is length of tag(fingerprint)
	BitsPerItem uint32 `json:"bits_per_item,omitempty"`
	// MaxNumKeys num of keys that filter will store. this value should close to and lower
	//					 nextPow2(maxNumKeys/tagsPerBucket) * maxLoadFactor. cause table.NumBuckets is always a
	//					 power of two
	MaxNumKeys uint32 `json:"max_num_keys,omitempty"`
	// TableType has two constant parameters to choose from:
	// TableTypeSingle normal single table
	// TableTypePacked packed table, use semi-sort to save 1 bit per item
	TableType uint32 `json:"table_type,omitempty"`
}

CuckooConfig Cuckoo configuration

type CuckooFilter

type CuckooFilter interface {
	IsFull() bool
	Add(key Key) (bool, error)
	Contains(key Key) (bool, error)
	Encode() (FilterEncoder, error)
	Extension() FilterExtension
	Info() []uint64
}

func NewCuckooFilter

func NewCuckooFilter(config *CuckooConfig) CuckooFilter

NewCuckooFilter Params: common.CuckooConfig.TableType : has two constant parameters to choose from:

  1. TableTypeSingle normal single table
  2. TableTypePacked packed table, use semi-sort to save 1 bit per item

common.CuckooConfig.TagsPerBucket: num of tags for each bucket, which is b in paper. tag is fingerprint, which is f

in paper.

common.CuckooConfig.MaxNumKeys : num of keys that filter will store. this value should close to and lower

nextPow2(maxNumKeys/tagsPerBucket) * maxLoadFactor. cause table.NumBuckets is
always a power of two

common.CuckooConfig.BitsPerItem : num of bits for each item, which is length of tag(fingerprint) common.CuckooConfig.TableType : common.CuckooConfig.KeyType : 0 TableTypeSingle normal single table

1 TableTypePacked packed table, use semi-sort to save 1 bit per item
1 is recommended

Result: CuckooFilter

type CuckooFilterImpl

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

CuckooFilterImpl Cuckoo Filter

func NewCuckooFilterByDecode

func NewCuckooFilterByDecode(filter *birdsnestpb.CuckooFilter) (*CuckooFilterImpl, error)

func (*CuckooFilterImpl) Add

func (c *CuckooFilterImpl) Add(key Key) (bool, error)

Add key to cuckoo filter

func (*CuckooFilterImpl) Config

func (c *CuckooFilterImpl) Config() ([]byte, error)

func (*CuckooFilterImpl) Contains

func (c *CuckooFilterImpl) Contains(key Key) (bool, error)

Contains Whether the cuckoo filter contains keys

func (*CuckooFilterImpl) Encode

func (c *CuckooFilterImpl) Encode() (FilterEncoder, error)

func (*CuckooFilterImpl) Extension

func (c *CuckooFilterImpl) Extension() FilterExtension

func (*CuckooFilterImpl) Info

func (c *CuckooFilterImpl) Info() []uint64

Info index 0 cuckoo size index 1 Space occupied by cuckoo

func (*CuckooFilterImpl) IsFull

func (c *CuckooFilterImpl) IsFull() bool

IsFull is full

type CuckooFilterSerialize

type CuckooFilterSerialize struct {
	// The field "cuckoo" is used to hold the serialized data of the cuckoo
	// Pb limit: The size of bytes cannot be larger than 4 GB
	Cuckoo []byte `protobuf:"bytes,1,opt,name=cuckoo,proto3" json:"cuckoo,omitempty"`
	// Carries the ID of the time
	Extension []byte `protobuf:"bytes,2,opt,name=extension,proto3" json:"extension,omitempty"`
	// cuckoo configuration
	Config []byte `protobuf:"bytes,3,opt,name=config,proto3" json:"config,omitempty"`
}

type DefaultFilterExtension

type DefaultFilterExtension struct {
}

DefaultFilterExtension default filter extension

func NewDefaultFilterExtension

func NewDefaultFilterExtension() *DefaultFilterExtension

NewDefaultFilterExtension new default filter extension

func (DefaultFilterExtension) Serialize

func (d DefaultFilterExtension) Serialize() []byte

Serialize serialize

func (DefaultFilterExtension) Store

func (d DefaultFilterExtension) Store(Key) error

Store store

func (DefaultFilterExtension) Validate

func (d DefaultFilterExtension) Validate(Key, bool) error

Validate validate

type FilterEncoder

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

type FilterExtension

type FilterExtension interface {
	// Validate validate key
	Validate(key Key, full bool) error
	Store(key Key) error
	Serialize() []byte
}

FilterExtension filter extension

func DeserializeDefault

func DeserializeDefault() FilterExtension

DeserializeDefault new default deserialize extension

func ExtensionDeserialize

func ExtensionDeserialize(bytes []byte) (FilterExtension, error)

ExtensionDeserialize Extension deserialize

func NewTimestampFilterExtension

func NewTimestampFilterExtension() FilterExtension

NewTimestampFilterExtension new timestamp filter extension

type FilterExtensionType

type FilterExtensionType int32

FilterExtensionType filter extension type

const (
	// FilterExtensionType_FETDefault default filter extension type
	FilterExtensionType_FETDefault FilterExtensionType = 0
	// FilterExtensionType_FETTimestamp timestamp filter extension type
	FilterExtensionType_FETTimestamp FilterExtensionType = 1
)

type Key

type Key interface {
	// Parse the key
	Parse() ([][]byte, error)
	// Key bytes
	Key() []byte
	// Len The length of the key
	Len() int
	// String key to string
	String() string
	// GetNano get nanosecond
	GetNano() int64
}

Key filter key

func GetTimestampKey

func GetTimestampKey() Key

GetTimestampKey get timestamp key

func GetTimestampKeyByNano

func GetTimestampKeyByNano(i int64) Key

GetTimestampKeyByNano get timestamp key by nanosecond

func GetTimestampKeys

func GetTimestampKeys(n int) []Key

GetTimestampKeys get timestamp key collections

type KeyType

type KeyType int32
const (
	// KeyType_KTDefault default type
	KeyType_KTDefault KeyType = 0
	// KeyType_KTTimestampKey timestamp type
	KeyType_KTTimestampKey KeyType = 1
)

type Logger

type Logger interface {
	Debugf(format string, args ...interface{})
	Errorf(format string, args ...interface{})
	Infof(format string, args ...interface{})
	Warnf(format string, args ...interface{})
}

type Rule

type Rule interface {
	Validate(Key) error
}

type RuleType

type RuleType int32

RuleType rule type

const (
	// RuleType_AbsoluteExpireTime absolute expire time
	RuleType_AbsoluteExpireTime RuleType = 0
)

type RulesConfig

type RulesConfig struct {
	// absolute expire time second
	AbsoluteExpireTime int64 `json:"absolute_expire_time,omitempty"`
}

RulesConfig rules configuration

type SerializeIntervalType

type SerializeIntervalType int32

SerializeIntervalType Serialize interval type

const (
	// SerializeIntervalType_Height Timed serialize type
	SerializeIntervalType_Height SerializeIntervalType = 0
	// SerializeIntervalType_Timed Timed serialize type
	SerializeIntervalType_Timed SerializeIntervalType = 1
	// SerializeIntervalType_Exit  Exit serialize type
	SerializeIntervalType_Exit SerializeIntervalType = 2
)

type Serializer

type Serializer interface {
	Serialize() error
	Deserialize() error
}

type Snapshot

type Snapshot interface {
	Write(data []byte) error
	Read() ([]byte, error)
}

type SnapshotSerializerConfig

type SnapshotSerializerConfig struct {
	// Type serialize interval type
	Type SerializeIntervalType `json:"type,omitempty"`
	// Timed serialize interval configuration
	Timed *TimedSerializeIntervalConfig `json:"timed,omitempty"`
	// BlockHeight serialize interval configuration
	BlockHeight *BlockHeightSerializeIntervalConfig `json:"block_height,omitempty"`
	// Path filepath
	Path string `json:"path,omitempty"`
}

SnapshotSerializerConfig Snapshot serializer config

type SprintfError

type SprintfError string

func NewError

func NewError(s string, args ...interface{}) SprintfError

func (SprintfError) Error

func (s SprintfError) Error() string

Error error information

type Strategy

type Strategy func(bn *BirdsNestImpl) error

Strategy function

type TestLogger

type TestLogger struct {
	T *testing.T
}

TestLogger test logger

func (TestLogger) Debugf

func (t TestLogger) Debugf(format string, args ...interface{})

Debugf debug format

func (TestLogger) Errorf

func (t TestLogger) Errorf(format string, args ...interface{})

Errorf error format

func (TestLogger) Infof

func (t TestLogger) Infof(format string, args ...interface{})

Infof info format

func (TestLogger) Warnf

func (t TestLogger) Warnf(format string, args ...interface{})

Warnf warn format

type TimedSerializeIntervalConfig

type TimedSerializeIntervalConfig struct {
	// Timed Interval
	Interval int64 `json:"interval,omitempty"`
}

TimedSerializeIntervalConfig Timed serialization interval configuration

type TimestampFilterExtension

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

TimestampFilterExtension timestamp filter extension

func DeserializeTimestamp

func DeserializeTimestamp(bytes []byte) (*TimestampFilterExtension, error)

DeserializeTimestamp deserialize timestamp by bytes

func (*TimestampFilterExtension) Serialize

func (t *TimestampFilterExtension) Serialize() []byte

Serialize serialize

func (*TimestampFilterExtension) Store

func (t *TimestampFilterExtension) Store(key Key) error

Store store start time and end time

func (*TimestampFilterExtension) Validate

func (t *TimestampFilterExtension) Validate(key Key, full bool) error

Validate validate

type TimestampKey

type TimestampKey []byte

TimestampKey Converting TxId directly using TimestampKey is not allowed, see ToTimestampKey

func ToTimestampKey

func ToTimestampKey(txId string) (TimestampKey, error)

ToTimestampKey strings txid to timestamp key

func (TimestampKey) GetNano

func (k TimestampKey) GetNano() int64

GetNano get nanosecond

func (TimestampKey) Key

func (k TimestampKey) Key() []byte

Key to bytes

func (TimestampKey) Len

func (k TimestampKey) Len() int

Len length

func (TimestampKey) Parse

func (k TimestampKey) Parse() ([][]byte, error)

Parse parse

func (TimestampKey) String

func (k TimestampKey) String() string

type WalSnapshot

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

WalSnapshot wal snapshot

func NewWalSnapshot

func NewWalSnapshot(path, name string, number int) (*WalSnapshot, error)

NewWalSnapshot new wal snapshot eg: data/tx_filter/chainN/birdsnestN

func (*WalSnapshot) Read

func (s *WalSnapshot) Read() ([]byte, error)

Read safe read wal

func (*WalSnapshot) Write

func (s *WalSnapshot) Write(data []byte) error

Write safe write wal

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL