alfheimdbwal

package module
v0.0.0-...-6f954b3 Latest Latest
Warning

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

 Go to latest Published: Nov 29, 2021 License: MIT Imports: 13 Imported by: 1

README

AlfheimDB-WAL

A high performance write-ahead log.

Example

AlfheimDB-WAL-Example

Core Struct

 WAL file struct in storage:  
 ┌───────────┬───────────┐  
 │ 1K header │   logs    │  
 └───────────┴───────────┘  
 The file header struct:  
 ┌───────────────┬─────────────────────────────┐  
 │ Length 8Bytes │             Data            │  
 └───────────────┴─────────────────────────────┘  
 The log item struct:  
 ┌───────────────┬──────────────┬─────────────────────────────────┐  
 │ Length 8Bytes │ Index 8Bytes │              Data               │  
 └───────────────┴──────────────┴─────────────────────────────────┘

Truncate Func

Case 1

 The log min index is 5, max index is 13
 If start in (-,5] && end in [13,-)
 Need truncate all log, so we remove this file
 ┌─┬─┬─┬─┬─┬──┬──┬──┬──┐
 │5│6│7│8│9│10│11│12│13│
 └─┴─┴─┴─┴─┴──┴──┴──┴──┘

Case 2

 The log min index is 5, max index is 13
 If start in [5,13) && end in [13,-)
 Need truncate from start to last log
 ┌─┬─┬─┬─┬─┬──┬──┬──┬──┐
 │5│6│7│8│9│10│11│12│13│
 └─┴─┴─┴─┴─┴──┴──┴──┴──┘

Case 3

 The log min index is 5, max index is 13
 If start in (-,5] && end in [5,13]
 Need truncate from the first log to end
 Put these pos into TruncateArea
 ┌─┬─┬─┬─┬─┬──┬──┬──┬──┐
 │5│6│7│8│9│10│11│12│13│
 └─┴─┴─┴─┴─┴──┴──┴──┴──┘

Case 4

 The log min index is 5, max index is 13
 If start in [5,13] && end in [5,13]
 Need truncate from start to end
 Put these pos into TruncateArea
 ┌─┬─┬─┬─┬─┬──┬──┬──┬──┐
 │5│6│7│8│9│10│11│12│13│
 └─┴─┴─┴─┴─┴──┴──┴──┴──┘

Benchmarks

MACBOOK PRO 2020 M1 SSD

BatchWrite: 100bytes, 200 logs, loop 10000 1.6s

CENTOS 7 8C8G HDD

BatchWrite: 100bytes, 200 logs, loop 10000 5.6s

Documentation

Overview

* @Descripttion: * @version: * @Author: cm.d * @Date: 2021-11-19 12:41:33 * @LastEditors: cm.d * @LastEditTime: 2021-11-20 12:00:45

* @Descripttion: * @version: * @Author: cm.d * @Date: 2021-11-18 19:24:19 * @LastEditors: cm.d * @LastEditTime: 2021-11-26 15:14:05

* @Descripttion: * @version: * @Author: cm.d * @Date: 2021-11-18 19:38:09 * @LastEditors: cm.d * @LastEditTime: 2021-11-27 12:57:16

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func GoFuncNewAlfheimDBWALFile 

func GoFuncNewAlfheimDBWALFile(filename string, sList *skiplist.SkipList, fileMap map[int64]*AlfheimDBWALFile, aFileChan chan *AlfheimDBWALFile)

func RangeAlfheimDBWALFile 

func RangeAlfheimDBWALFile(sList *skiplist.SkipList, startIndex, endIndex int64, exec func(key int64, value *AlfheimDBWALFile) bool)

func ReadFile 

func ReadFile(file os.File, pos, length int64, buff []byte) int64

func ReadInt64FromBuff 

func ReadInt64FromBuff(buff []byte, isBigEndian bool) uint64

func WriteFile 

func WriteFile(file os.File, pos int64, data []byte, appendFlag bool)

func WriteInt64ToBuff 

func WriteInt64ToBuff(buff []byte, data int64, isBigEndian bool)

Types

type AlfheimDBWAL 

type AlfheimDBWAL struct {
	FileIndex   *skiplist.SkipList
	AFiles      map[int64]*AlfheimDBWALFile
	MinIndex    int64
	MaxIndex    int64
	MaxItems    int64
	Dirname     string
	IsBigEndian bool
	Mutex       *sync.Mutex
}

func NewWAL 

func NewWAL(waldir string) *AlfheimDBWAL

func (*AlfheimDBWAL) BatchWriteLog 

func (wal *AlfheimDBWAL) BatchWriteLog(lItems []*LogItem, data []byte)

batch write log

func (*AlfheimDBWAL) BuildDirIndex 

func (wal *AlfheimDBWAL) BuildDirIndex()

Range dir build log file index

func (*AlfheimDBWAL) CreateNewFile 

func (wal *AlfheimDBWAL) CreateNewFile(index int64) *AlfheimDBWALFile

log file name: log_${unixtimestamp}_index.dat

func (*AlfheimDBWAL) GetLog 

func (wal *AlfheimDBWAL) GetLog(index int64) []byte

Time complexity: Find file in skipList , if i = len(files) => T(i) = O(logi) Read log in file, T(j) = O(1) T(i,j) = O(logi) + O(1) = O(logi)

func (*AlfheimDBWAL) RefreshAllMinAndMaxIndex 

func (wal *AlfheimDBWAL) RefreshAllMinAndMaxIndex()

refresh min and max index from all file

func (*AlfheimDBWAL) RefreshMinAndMaxIndex 

func (wal *AlfheimDBWAL) RefreshMinAndMaxIndex(aFile *AlfheimDBWALFile)

refresh min and max index

func (*AlfheimDBWAL) TruncateLog 

func (wal *AlfheimDBWAL) TruncateLog(start, end int64)

truncate log, [start, end]

func (*AlfheimDBWAL) WriteLog 

func (wal *AlfheimDBWAL) WriteLog(lItem *LogItem, data []byte)

write single log

type AlfheimDBWALFile 

type AlfheimDBWALFile struct {
	Mutex        *sync.Mutex
	File         *os.File
	Pos          int64
	LogItems     map[int64]*LogItem
	LogIndex     *skiplist.SkipList
	MaxIndex     int64
	MinIndex     int64
	Filename     string
	Header       *AlfheimDBWALFileHeader
	HeaderLength int64
	AppendFlag   bool
}

WAL file struct in storage: ┌───────────┬───────────┐ │ 1K header │ logs │ └───────────┴───────────┘ The file header struct: ┌───────────────┬─────────────────────────────┐ │ Length 8Bytes │ Data │ └───────────────┴─────────────────────────────┘ The log item struct: ┌───────────────┬──────────────┬─────────────────────────────────┐ │ Length 8Bytes │ Index 8Bytes │ Data │ └───────────────┴──────────────┴─────────────────────────────────┘

func NewAlfheimDBWALFile 

func NewAlfheimDBWALFile(filename string) *AlfheimDBWALFile

func (*AlfheimDBWALFile) BatchWriteLogs 

func (aFile *AlfheimDBWALFile) BatchWriteLogs(lItems []*LogItem, data []byte)

func (*AlfheimDBWALFile) BuildLogIndex 

func (aFile *AlfheimDBWALFile) BuildLogIndex()

func (*AlfheimDBWALFile) Close 

func (aFile *AlfheimDBWALFile) Close()

func (*AlfheimDBWALFile) FilterTruncated 

func (aFile *AlfheimDBWALFile) FilterTruncated(pos int64) bool

true: ths pos is Truncated

func (*AlfheimDBWALFile) LoadFileHeader 

func (aFile *AlfheimDBWALFile) LoadFileHeader()

func (*AlfheimDBWALFile) ReadLog 

func (aFile *AlfheimDBWALFile) ReadLog(index int64) []byte

func (*AlfheimDBWALFile) RefreshMinAndMaxIndex 

func (aFile *AlfheimDBWALFile) RefreshMinAndMaxIndex(lItem *LogItem)

func (*AlfheimDBWALFile) SaveFileHeader 

func (aFile *AlfheimDBWALFile) SaveFileHeader()

func (*AlfheimDBWALFile) TruncateLog 

func (aFile *AlfheimDBWALFile) TruncateLog(start, end int64) TruncateStatus

func (*AlfheimDBWALFile) WriteLog 

func (aFile *AlfheimDBWALFile) WriteLog(lItem *LogItem, data []byte)

type AlfheimDBWALFileHeader 

type AlfheimDBWALFileHeader struct {
	TruncateArea []*TruncateArea `json:"truncate_area"`
}

type LogItem 

type LogItem struct {
	Length uint64
	Index  int64
	Pos    uint64
}

func CreateBatchWriteBuff 

func CreateBatchWriteBuff(batchWriteBuff []byte, execs []func(args ...interface{}) (int64, []byte), args ...[]interface{}) ([]*LogItem, []byte)

func CreateWriteBuff 

func CreateWriteBuff(writeBuff []byte, exec func(args ...interface{}) (int64, []byte), args ...interface{}) (*LogItem, []byte)

func NewLogItemBuff 

func NewLogItemBuff(index int64, data []byte, buff []byte, isBigEndian bool) *LogItem

type TruncateArea 

type TruncateArea struct {
	Start int64 `json:"start"`
	End   int64 `json:"end"`
}

[start, end)

type TruncateStatus 

type TruncateStatus int8
const (
	NO_TRUNCATED TruncateStatus = -1
	REMOVE_FILE  TruncateStatus = 1
	TRUNCATED_OK TruncateStatus = 0
)

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.