utils

package
v0.0.0-...-a38de57 Latest Latest
Warning

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

 Go to latest Published: Apr 17, 2022 License: MIT Imports: 23 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// MaxLevelNum _
	MaxLevelNum = 7
	// DefaultValueThreshold _
	DefaultValueThreshold             = 1024
	ManifestDeletionsRewriteThreshold = 10000
	ManifestDeletionsRatio            = 10
	ManifestFileName                  = "manifest"
	ReManifestFileName                = "remanifest"

	// 基于可变长编码,其最可能的编码
	MaxHeaderSize            = 21
	VlogHeaderSize           = 0
	MaxVlogFileSize   uint32 = math.MaxUint32
	Mi                int64  = 1 << 20
	KVWriteChCapacity        = 1000
)
View Source 
const (
	BitDelete       byte = 1 << 0 // Set if the key has been deleted.
	BitValuePointer byte = 1 << 1 // Set if the value is NOT stored directly next to key.
)

meta

View Source 
const (
	NodeSize = int(unsafe.Sizeof(node{}))
)
View Source 
const (
	// size of vlog header.
	// +----------------+------------------+
	// | keyID(8 bytes) |  baseIV(12 bytes)|
	// +----------------+------------------+
	ValueLogHeaderSize = 20
)

Variables

View Source 
var (
	MagicText    = [4]byte{'O', 'C', 'T', 'O'}
	MagicVersion = uint32(1)
)
View Source 
var (
	ErrChecksumMismatch = errors.New("checksum mismatch")
	ErrEmptyKey         = errors.New("Key cannot be empty")
	ErrTruncate         = errors.New("Do truncate")
	ErrKeyNotExist      = errors.New("key not exist")
	ErrKeyNotFound      = errors.New("Key not found")
	ErrStop             = errors.New("Stop")
	ErrDeleteVlogFile   = errors.New("Delete vlog file")
	// compact
	ErrFillTables = errors.New("Unable to fill tables")
	ErrTxnTooBig  = errors.New("Txn is too big to fit into one request")
	// ErrNoRewrite is returned if a call for value log GC doesn't result in a log file rewrite.
	ErrNoRewrite = errors.New("Value log GC attempt didn't result in any cleanup")
	// ErrInvalidRequest is returned if the user request is invalid.
	ErrInvalidRequest = errors.New("Invalid request")
	// ErrRejected is returned if a value log GC is called either while another GC is running, or
	// after DB::Close has been called.
	ErrRejected      = errors.New("Value log GC request rejected")
	ErrBlockedWrites = errors.New("Writes are blocked, possibly due to DropAll or Close")
)
View Source 
var (
	// CastagnoliCrcTable is a CRC32 polynomial table
	CastagnoliCrcTable = crc32.MakeTable(crc32.Castagnoli)
)

Functions

func AssertTrue 

func AssertTrue(b bool)

AssertTrue asserts that b is true. Otherwise, it would log fatal.

func AssertTruef 

func AssertTruef(b bool, format string, args ...interface{})

AssertTruef is AssertTrue with extra info.

func BitsPerKey 

func BitsPerKey(numEntries int, fp float64) int

BitsPerKey 根据计算公式，在给定假阳性false positive和确定数据量下

func BytesToU32 

func BytesToU32(buf []byte) uint32

func BytesToU32Slice 

func BytesToU32Slice(b []byte) []uint32

BytesToU32Slice converts the given byte slice to uint32 slice

func BytesToU64 

func BytesToU64(b []byte) uint64

func CalcHashNum 

func CalcHashNum(bitsPerKey int) uint32

CalcHashNum 计算出最佳的hash函数个数

func CalculateChecksum 

func CalculateChecksum(data []byte) uint64

CalculateChecksum _

func CompareKeys 

func CompareKeys(key1, key2 []byte) int

func Copy 

func Copy(a []byte) []byte

func DiscardEntry 

func DiscardEntry(e, vs *Entry) bool

func EstimateWalCodecSize 

func EstimateWalCodecSize(e *Entry) int

EstimateWalCodecSize 预估当前kv 写入wal文件占用的空间大小

func FID 

func FID(name string) uint64

FID 根据file name 获取其fid

func Hash 

func Hash(b []byte) uint32

func IsDeletedOrExpired 

func IsDeletedOrExpired(meta byte, expiresAt uint64) bool

func IsSameKey 

func IsSameKey(src, dst []byte) bool

func IsValuePtr 

func IsValuePtr(e *Entry) bool

func KeyWithTs 

func KeyWithTs(key []byte, ts uint64) []byte

KeyWithTs generates a new key by appending ts to key.

func LoadIDMap 

func LoadIDMap(dir string) map[uint64]struct{}

func ParseKey 

func ParseKey(key []byte) []byte

func ParseTimeStamp 

func ParseTimeStamp(key []byte) uint64

func RunCallBack 

func RunCallBack(cb func())

func SSTFullFileName 

func SSTFullFileName(dir string, fid uint64) string

func SafeCopy 

func SafeCopy(a, src []byte) []byte

SafeCopy does append(a[:0], src...).

func SyncDir 

func SyncDir(dir string) error

SyncDir When you create or delete a file, you have to ensure the directory entry for the file is synced in order to guarantee the file is visible (if the system crashes). (See the man page for fsync, or see https://github.com/coreos/etcd/issues/6368 for an example.)

func U32SliceToBytes 

func U32SliceToBytes(u32s []uint32) []byte

func U32ToBytes 

func U32ToBytes(v uint32) []byte

U32ToBytes converts the given Uint32 to bytes

func U64ToBytes 

func U64ToBytes(v uint64) []byte

U64ToBytes converts the given Uint64 to bytes

func ValueSize 

func ValueSize(data []byte) int64

func VerifyChecksum 

func VerifyChecksum(data []byte, expected []byte) error

VerifyChecksum crc32

func VlogFilePath 

func VlogFilePath(dirPath string, fid uint32) string

func WalCodec 

func WalCodec(buf *bytes.Buffer, e *Entry) int

WalCodec 将一条记录进行编码写入wal文件中 key-len | value-len | expires-at

Types

type Arena 

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

Arena 内存管理模块，分配一整块内存buf，对应memetable，当此buf分配完时对应memtable-->immemtable的转换

func (*Arena) Size 

func (s *Arena) Size() int64

type BloomFilter 

type BloomFilter struct {
	Filter []byte
}

func NewBloomFilter 

func NewBloomFilter(keys []uint32, bitPerKey int) BloomFilter

func (BloomFilter) MayContain 

func (b BloomFilter) MayContain(key []byte) bool

type Closer 

type Closer struct {
	CloseSignal chan struct{}
	// contains filtered or unexported fields
}

func NewCloser 

func NewCloser() *Closer

NewCloser _

func (*Closer) Add 

func (c *Closer) Add(n int)

Add 添加wait 计数

func (*Closer) Close 

func (c *Closer) Close()

Close 上游通知下游协程进行资源回收，并等待协程通知回收完毕

func (*Closer) Done 

func (c *Closer) Done()

Done 标示协程已经完成资源回收，通知上游正式关闭

type Entry 

type Entry struct {
	Key       []byte
	Value     []byte
	ExpiresAt uint64

	Meta         byte
	Version      uint64
	Offset       uint32 // offset in file
	Hlen         int    // Length of the header.
	ValThreshold int64
}

func BuildEntry 

func BuildEntry() *Entry

func NewEntry 

func NewEntry(key, value []byte) *Entry

func (*Entry) EncodedSize 

func (e *Entry) EncodedSize() uint32

func (*Entry) Entry 

func (e *Entry) Entry() *Entry

func (*Entry) EstimateSize 

func (e *Entry) EstimateSize(threshold int) int

func (*Entry) IsDeletedOrExpired 

func (e *Entry) IsDeletedOrExpired() bool

func (*Entry) IsZero 

func (e *Entry) IsZero() bool

IsZero _

func (*Entry) LogHeaderLen 

func (e *Entry) LogHeaderLen() int

LogHeaderLen _

func (*Entry) LogOffset 

func (e *Entry) LogOffset() uint32

LogOffset _

func (Entry) Size 

func (e Entry) Size() int64

func (*Entry) WithTTL 

func (e *Entry) WithTTL(duration time.Duration) *Entry

type HashReader 

type HashReader struct {
	R         io.Reader
	H         hash.Hash32
	BytesRead int // Number of bytes read.
}

func NewHashReader 

func NewHashReader(r io.Reader) *HashReader

func (*HashReader) Read 

func (t *HashReader) Read(p []byte) (int, error)

Read reads len(p) bytes from the reader. Returns the number of bytes read, error on failure.

func (*HashReader) ReadByte 

func (t *HashReader) ReadByte() (byte, error)

ReadByte reads exactly one byte from the reader. Returns error on failure.

func (*HashReader) Sum32 

func (t *HashReader) Sum32() uint32

Sum32 returns the sum32 of the underlying hash. 

type Header struct {
	KLen      uint32
	VLen      uint32
	ExpiresAt uint64
	Meta      byte // 8 bit表示是值还是指针
}

func (*Header) Decode 

func (h *Header) Decode(buf []byte) int

Decode decodes the given header from the provided byte slice. Returns the number of bytes read.

func (*Header) DecodeFrom 

func (h *Header) DecodeFrom(reader *HashReader) (int, error)

DecodeFrom reads the header from the hashReader. Returns the number of bytes read.

func (Header) Encode 

func (h Header) Encode(out []byte) int

Encode +------+----------+------------+--------------+-----------+ | Meta | UserMeta | Key Length | Value Length | ExpiresAt | +------+----------+------------+--------------+-----------+

type Item 

type Item interface {
	Entry() *Entry
}

type Iterator 

type Iterator interface {
	Next()
	Rewind()
	Valid() bool
	Close() error
	Seek([]byte)
	Item() Item
}

type LogEntry 

type LogEntry func(e *Entry, vp *ValuePtr) error

type Options 

type Options struct {
	Prefix []byte
	IsAsc  bool
}

type SkipList 

type SkipList struct {
	OnClose func()
	// contains filtered or unexported fields
}

func NewSkipList 

func NewSkipList(arenaSize int64) *SkipList

NewSkipList makes a new empty skiplist, with a given arena size

func (*SkipList) Add 

func (s *SkipList) Add(e *Entry)

Put inserts the key-value pair.

func (*SkipList) DecrRef 

func (s *SkipList) DecrRef()

DecrRef decrements the refcount, deallocating the Skiplist when done using it

func (*SkipList) Empty 

func (s *SkipList) Empty() bool

Empty returns if the Skiplist is empty.

func (*SkipList) IncrRef 

func (s *SkipList) IncrRef()

IncrRef increases the refcount

func (*SkipList) MemSize 

func (s *SkipList) MemSize() int64

MemSize returns the size of the Skiplist in terms of how much memory is used within its internal arena.

func (*SkipList) NewSkipListIterator 

func (s *SkipList) NewSkipListIterator() Iterator

NewIterator returns a skiplist iterator. You have to Close() the iterator.

func (*SkipList) Search 

func (s *SkipList) Search(key []byte) ValueStruct

Get gets the value associated with the key. It returns a valid value if it finds equal or earlier version of the same key.

type SkipListIterator 

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

Iterator is an iterator over skiplist object. For new objects, you just need to initialize Iterator.list.

func (*SkipListIterator) Close 

func (s *SkipListIterator) Close() error

Close frees the resources held by the iterator

func (*SkipListIterator) Item 

func (s *SkipListIterator) Item() Item

func (*SkipListIterator) Key 

func (s *SkipListIterator) Key() []byte

Key returns the key at the current position.

func (*SkipListIterator) Next 

func (s *SkipListIterator) Next()

Next advances to the next position.

func (*SkipListIterator) Prev 

func (s *SkipListIterator) Prev()

Prev advances to the previous position.

func (*SkipListIterator) Rewind 

func (s *SkipListIterator) Rewind()

func (*SkipListIterator) Seek 

func (s *SkipListIterator) Seek(target []byte)

Seek advances to the first entry with a key >= target.

func (*SkipListIterator) SeekForPrev 

func (s *SkipListIterator) SeekForPrev(target []byte)

SeekForPrev finds an entry with key <= target.

func (*SkipListIterator) SeekToFirst 

func (s *SkipListIterator) SeekToFirst()

SeekToFirst seeks position at the first entry in list. Final state of iterator is Valid() iff list is not empty.

func (*SkipListIterator) SeekToLast 

func (s *SkipListIterator) SeekToLast()

SeekToLast seeks position at the last entry in list. Final state of iterator is Valid() iff list is not empty.

func (*SkipListIterator) Valid 

func (s *SkipListIterator) Valid() bool

Valid returns true iff the iterator is positioned at a valid node.

func (*SkipListIterator) Value 

func (s *SkipListIterator) Value() ValueStruct

Value returns value.

func (*SkipListIterator) ValueUint64 

func (s *SkipListIterator) ValueUint64() uint64

ValueUint64 returns the uint64 value of the current node.

type Throttle 

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

Throttle allows a limited number of workers to run at a time.

func NewThrottle 

func NewThrottle(max int) *Throttle

NewThrottle creates a new throttle with a max number of workers.

func (*Throttle) Do 

func (t *Throttle) Do() error

Do should be called by workers before they start working. It blocks if there are already maximum number of workers working. If it detects an error from previously Done workers, it would return it.

func (*Throttle) Done 

func (t *Throttle) Done(err error)

Done should be called by workers when they finish working. They can also pass the error status of work done.

func (*Throttle) Finish 

func (t *Throttle) Finish() error

Finish waits until all workers have finished working. It would return any error passed by Done. If Finish is called multiple time, it will wait for workers to finish only once(first time). From next calls, it will return same error as found on first call.

type UniIterator 

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

UniIterator is a unidirectional memtable iterator. It is a thin wrapper around Iterator. We like to keep Iterator as before, because it is more powerful and we might support bidirectional iterators in the future.

type ValuePtr 

type ValuePtr struct {
	Len    uint32
	Offset uint32
	Fid    uint32
}

func NewValuePtr 

func NewValuePtr(entry *Entry) *ValuePtr

func (*ValuePtr) Decode 

func (p *ValuePtr) Decode(b []byte)

Decode decodes the value pointer into the provided byte buffer.

func (ValuePtr) Encode 

func (p ValuePtr) Encode() []byte

Encode encodes Pointer into byte buffer.

func (ValuePtr) IsZero 

func (p ValuePtr) IsZero() bool

func (ValuePtr) Less 

func (p ValuePtr) Less(o *ValuePtr) bool

type ValueStruct 

type ValueStruct struct {
	Meta      byte
	Value     []byte
	ExpiresAt uint64
	Version   uint64
}

ValueStruct 将value与expiresAt作为一个整体

func (*ValueStruct) DecodeValue 

func (vs *ValueStruct) DecodeValue(buf []byte)

DecodeValue 反序列化到结构体

func (*ValueStruct) EncodeValue 

func (vs *ValueStruct) EncodeValue(b []byte) uint32

EncodeValue 对value进行编码，并将编码后的字节写入byte

func (*ValueStruct) EncodedSize 

func (vs *ValueStruct) EncodedSize() uint32

EncodedSize value只持久化具体的value值和过期时间

type WalHeader 

type WalHeader struct {
	KeyLen    uint32
	ValueLen  uint32
	ExpiresAt uint64
}

func (*WalHeader) Decode 

func (h *WalHeader) Decode(reader *HashReader) (int, error)

func (WalHeader) Encode 

func (h WalHeader) Encode(out []byte) int

Encode format: | header | key | value | crc32 |

Source Files

View all Source files

Directories

Path Synopsis

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.