engine

package
v0.2.1 Latest Latest
Warning

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

 Go to latest Published: May 27, 2026 License: Apache-2.0 Imports: 18 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// MaxMemTableSize maximum MemTable size in bytes before flush
	MaxMemTableSize = 4 * 1024 * 1024 // 4 MB
	// MaxLevel0Files maximum number of files in Level0 before compaction
	MaxLevel0Files = 4
)
View Source 
const (
	// VLogMagic магическое число для заголовка VLog файла.
	VLogMagic uint32 = 0x53434F52 // "SCOR"
	// VLogVersion версия формата.
	VLogVersion uint32 = 1
	// MaxInlineSize максимальный размер значения для inline хранения.
	MaxInlineSize = 64
)

Variables

This section is empty.

Functions

This section is empty.

Types

type EngineOptions 

type EngineOptions struct {
	DataDir string
	WALOpts WALOptions
}

func DefaultEngineOptions 

func DefaultEngineOptions(dataDir string) EngineOptions

type LSMEngine 

type LSMEngine struct {
	LastTS uint64
	// contains filtered or unexported fields
}

func NewLSMEngine 

func NewLSMEngine(dataDir string, opts ...WALOptions) (*LSMEngine, error)

NewLSMEngine создаёт движок. Если передан параметр WALOptions, используется Group Commit.

func (*LSMEngine) ActiveMemTable 

func (e *LSMEngine) ActiveMemTable() *MemTable

func (*LSMEngine) CheckConflict 

func (e *LSMEngine) CheckConflict(key []byte, startTS uint64) (bool, error)

func (*LSMEngine) Close 

func (e *LSMEngine) Close() error

func (*LSMEngine) CollectLiveValuePointers 

func (e *LSMEngine) CollectLiveValuePointers() (map[ValuePointer]struct{}, error)

func (*LSMEngine) DeleteWithTS 

func (e *LSMEngine) DeleteWithTS(key []byte, commitTS uint64) error

func (*LSMEngine) FrozenMemTable 

func (e *LSMEngine) FrozenMemTable() *MemTable

func (*LSMEngine) GetLatestInfo 

func (e *LSMEngine) GetLatestInfo(key []byte) ([]byte, uint64, error)

func (*LSMEngine) GetMinActiveSnapshotTS 

func (e *LSMEngine) GetMinActiveSnapshotTS() uint64

func (*LSMEngine) GetWithTS 

func (e *LSMEngine) GetWithTS(key []byte, snapshotTS uint64) ([]byte, error)

func (*LSMEngine) InvalidateVLogPointers 

func (e *LSMEngine) InvalidateVLogPointers()

func (*LSMEngine) NextTimestamp 

func (e *LSMEngine) NextTimestamp() uint64

func (*LSMEngine) PutWithTS 

func (e *LSMEngine) PutWithTS(key, value []byte, commitTS uint64) error

func (*LSMEngine) ReadVLogValue 

func (e *LSMEngine) ReadVLogValue(fileID uint64, offset uint32) ([]byte, error)

func (*LSMEngine) RegisterSnapshot 

func (e *LSMEngine) RegisterSnapshot(snapshotTS uint64)

func (*LSMEngine) UnregisterSnapshot 

func (e *LSMEngine) UnregisterSnapshot(snapshotTS uint64)

func (*LSMEngine) WriteAtomicBatch 

func (e *LSMEngine) WriteAtomicBatch(data []byte, commitTS uint64) error

type Manifest 

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

Manifest управляет журналом метаданных SSTable.

func NewManifest 

func NewManifest(vfs vfs.VFS, path string) (*Manifest, error)

NewManifest создаёт новый манифест (или открывает существующий) по указанному пути.

func (*Manifest) Apply 

func (m *Manifest) Apply(edit *VersionEdit) error

Apply записывает новую VersionEdit в манифест и применяет её к состоянию.

func (*Manifest) Close 

func (m *Manifest) Close() error

Close освобождает ресурсы манифеста.

func (*Manifest) GetLevels 

func (m *Manifest) GetLevels() [][]SSTableInfo

GetLevels возвращает копию текущего распределения файлов по уровням.

func (*Manifest) NextFileNum 

func (m *Manifest) NextFileNum() uint64

NextFileNum возвращает следующий доступный номер файла.

type MemTable 

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

MemTable is a thread‑safe in‑memory structure based on btree.

func NewMemTable 

func NewMemTable() *MemTable

NewMemTable creates a new MemTable.

func (*MemTable) DeleteWithTS 

func (mt *MemTable) DeleteWithTS(key mvcc.MVCCKey)

DeleteWithTS marks a key as deleted (tombstone) at the given commit timestamp. Internally creates an entry with Deleted = true and empty value.

func (*MemTable) Get 

func (mt *MemTable) Get(key mvcc.MVCCKey) ([]byte, bool)

Get returns the value for the key with the maximum commit timestamp <= snapshotTS. If the key is not found, returns nil.

MVCC logic and timestamp inversion

ScoriaDB uses an approach similar to TiKV and BadgerDB:

  • Each key version is encoded as an MVCCKey, consisting of UserKey and inverted timestamp.
  • Inverted timestamp = math.MaxUint64 - commitTS. This guarantees that in sorted order newer versions (with larger commitTS) appear before older ones (since they have a smaller inverted timestamp). For details:
  • TiKV: “Keys and timestamps are encoded so that timestamped keys are sorted first by key (ascending), then by timestamp (descending)” (https://pkg.go.dev/github.com/pingcap-incubator/tinykv/kv/transaction/mvcc)
  • BadgerDB: “Badger uses Multi-Version Concurrency Control (MVCC)” (https://godocs.io/github.com/dgraph-io/badger)

Visibility formula

A transaction with snapshotTS sees a version if commitTS <= snapshotTS. Let T(x) = MaxUint64 - x be the inverted timestamp. Then condition commitTS <= snapshotTS is equivalent to T(commitTS) >= T(snapshotTS).

Search algorithm (corrected)

Due to sorting order (newer versions come before older) using AscendGreaterOrEqual would start iteration from the oldest visible version, not the newest. To correctly find the newest visible version we must use DescendLessOrEqual, which starts traversal from the entry closest to searchKey and moves downwards (from newer to older). This matches industrial implementations (TiKV, BadgerDB) where search is performed in reverse timestamp order.

Algorithm:

  1. Search key (key) contains inverted snapshotTS: Timestamp = T(snapshotTS).
  2. In B‑Tree entries are sorted first by UserKey (ascending), then by inverted timestamp (descending), meaning: for the same UserKey newer versions (with larger commitTS) appear before older ones, because they have a smaller inverted timestamp.
  3. Use DescendLessOrEqual, which walks entries in reverse sort order (from newer to older), starting from a version that is <= searchKey.
  4. Visibility condition: commitTS <= snapshotTS <=> inverted timestamp >= key.Timestamp.
  5. Look for the newest version satisfying the condition, i.e. the first entry with the same UserKey where entry.Key.Timestamp >= key.Timestamp.

Tombstone handling (deletion)

In ScoriaDB deletion is modeled by an entry with Deleted = true (tombstone). Semantics match industrial MVCC systems (TiKV, BadgerDB):

  • If for a given snapshotTS the visible version is a tombstone (commitTS <= snapshotTS), the key is considered deleted and must not be found (returns found = false).
  • Tombstone hides all older versions for snapshotTS >= deletion commitTS.
  • If tombstone is not visible (commitTS > snapshotTS), it is ignored and search continues for older versions.

Implementation:

  • When a visible version with Deleted = true is encountered, iteration stops, returns found = false.
  • When a visible live version is encountered, returns its value and found = true.
  • If a version is too new (commitTS > snapshotTS), iteration continues.

Detailed explanation:

  • DescendLessOrEqual guarantees we start from a version that is <= searchKey in sort order.
  • Because newer versions have smaller inverted timestamp, they will be “less” in sort order, and DescendLessOrEqual will start from the newest version that does not exceed searchKey.
  • If that version is too new (commitTS > snapshotTS), we continue iteration (move to older ones).
  • If the version is visible (commitTS <= snapshotTS), we stop because it is the newest visible version.

References: - TiKV: https://cloud.tencent.com/developer/article/1549435 (lines 29-31) - BadgerDB: https://godocs.io/github.com/dgraph-io/badger

func (*MemTable) NewIterator 

func (mt *MemTable) NewIterator() *MemTableIterator

NewIterator returns an iterator over all entries in MemTable.

func (*MemTable) Put 

func (mt *MemTable) Put(key mvcc.MVCCKey, value []byte)

Put adds or updates a key with the given timestamp.

func (*MemTable) Size 

func (mt *MemTable) Size() int

Size returns the number of elements in MemTable.

type MemTableIterator 

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

MemTableIterator iterates over MemTable entries.

func (*MemTableIterator) Close 

func (it *MemTableIterator) Close()

Close releases iterator resources.

func (*MemTableIterator) Key 

func (it *MemTableIterator) Key() mvcc.MVCCKey

Key returns the current key.

func (*MemTableIterator) Next 

func (it *MemTableIterator) Next() bool

Next moves the iterator to the next entry.

func (*MemTableIterator) Value 

func (it *MemTableIterator) Value() []byte

Value returns the current value.

type OpType 

type OpType byte

OpType тип операции в WAL. 

const (
	OpPut    OpType = 1
	OpDelete OpType = 2
	OpBatch  OpType = 3 // атомарный батч операций
)

type SSTableInfo 

type SSTableInfo struct {
	FileNum uint64 `json:"file_num"`
	Level   int    `json:"level"`
	MinKey  []byte `json:"min_key"`
	MaxKey  []byte `json:"max_key"`
	Size    uint64 `json:"size"`
}

SSTableInfo содержит метаданные одного SSTable файла.

type VLog 

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

VLog представляет Value Log с mmap для zero-copy чтения.

func OpenVLog 

func OpenVLog(vfs vfs.VFS, path string) (*VLog, error)

OpenVLog открывает или создает VLog файл.

func (*VLog) Close 

func (v *VLog) Close() error

Close закрывает VLog и освобождает ресурсы.

func (*VLog) GC 

func (v *VLog) GC(livePointers map[ValuePointer]struct{}) (map[ValuePointer]ValuePointer, error)

GC performs garbage collection on the Value Log. livePointers is a set of ValuePointers that are still referenced by the LSM tree. It creates a new VLog file, copies all live values to it, and replaces the old file. Returns a map from old ValuePointers to new ValuePointers, and any error. The caller must update references in the LSM tree accordingly.

func (*VLog) Read 

func (v *VLog) Read(vp ValuePointer) ([]byte, error)

Read читает значение по указателю.

func (*VLog) Size 

func (v *VLog) Size() int64

Size возвращает текущий размер файла VLog (в байтах).

func (*VLog) Write 

func (v *VLog) Write(value []byte) (ValuePointer, error)

Write добавляет значение в VLog и возвращает указатель на него. Если значение маленькое (<= MaxInlineSize), возвращает пустой указатель.

type ValuePointer 

type ValuePointer struct {
	Offset int64 // смещение в файле
	Size   int32 // размер значения (без заголовка)
}

ValuePointer указывает на значение в VLog.

type VersionEdit 

type VersionEdit struct {
	NewFiles     []SSTableInfo `json:"new_files,omitempty"`
	DeletedFiles []SSTableInfo `json:"deleted_files,omitempty"`
	NextFileNum  uint64        `json:"next_file_num,omitempty"`
}

VersionEdit представляет одно атомарное изменение в составе файлов.

type WAL 

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

WAL представляет Write-Ahead Log с CRC.

func OpenWAL 

func OpenWAL(path string) (*WAL, error)

OpenWAL открывает или создает WAL файл с настройками по умолчанию.

func OpenWALWithOptions 

func OpenWALWithOptions(path string, opts WALOptions) (*WAL, error)

OpenWALWithOptions открывает или создает WAL файл с указанными настройками. При включённом групповом коммите (GroupCommitEnabled = true) записи буферизуются и периодически сбрасываются на диск с интервалом GroupCommitInterval. Это значительно повышает пропускную способность, но снижает durability: записи, сделанные после последнего сброса, могут быть потеряны при краше процесса. Для критичных к durability workload'ов оставьте GroupCommitEnabled = false (режим по умолчанию), где каждая запись немедленно синхронизируется с диском.

func (*WAL) Close 

func (w *WAL) Close() error

Close закрывает WAL файл.

func (*WAL) Flush 

func (w *WAL) Flush() error

Flush принудительно сбрасывает буферизованные данные на диск. Если групповой коммит отключён, метод ничего не делает (данные уже на диске).

func (*WAL) Recover 

func (w *WAL) Recover(cb func(*WalEntry) error) error

Recover читает все записи из WAL и вызывает callback для каждой.

func (*WAL) Write 

func (w *WAL) Write(entry *WalEntry) error

Write записывает операцию в WAL.

type WALOptions 

type WALOptions struct {
	// GroupCommitEnabled включает групповой коммит (буферизацию записей).
	// По умолчанию false — каждая запись синхронно сбрасывается на диск.
	// Включение группового коммита значительно увеличивает пропускную способность записи,
	// но снижает durability: записи, сделанные после последнего сброса на диск,
	// могут быть потеряны при краше процесса или отключении питания.
	// Рекомендуется для workload'ов, где допустима потеря последних миллисекунд записей
	// (логи, метрики, кэши).
	GroupCommitEnabled bool

	// GroupCommitInterval определяет интервал сброса буфера при включённом групповом коммите.
	// По умолчанию 10 мс.
	// Меньшие значения уменьшают задержку подтверждения записи, но увеличивают нагрузку на диск.
	// Большие значения улучшают пропускную способность, но увеличивают риск потери данных при краше.
	GroupCommitInterval time.Duration

	// MaxBufferSize максимальный размер буфера в байтах перед принудительным сбросом.
	// Если 0, ограничения нет.
	// При достижении этого размера буфер будет сброшен на диск независимо от таймера.
	// Полезно для ограничения потребления памяти.
	MaxBufferSize int
}

WALOptions содержит параметры для настройки Write-Ahead Log.

func DefaultWALOptions 

func DefaultWALOptions() WALOptions

DefaultWALOptions возвращает настройки WAL по умолчанию.

type WalEntry 

type WalEntry struct {
	Op        OpType
	Key       []byte
	Value     []byte
	Timestamp uint64
}

WalEntry представляет запись в WAL.

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.