logio

Documentation

Overview

Package logio implements a failure-tolerant log, typically used as a write-ahead log. Logs are "history oblivious": new log entries do not depend on previous entries; and logs may be concatenated on block boundaries while preserving integrity. Likewise, logs may be read from a stream without seeking.

Data layout

Logio follows the leveldb log format [1] with some modifications to permit efficient re-syncing from the end of a log, as well as to use a modern checksum algorithm (xxhash).

A log file is a sequence of 32kB blocks, each containing a sequence of records and possibly followed by padding. Records may not span blocks; log entries that would straddle block boundaries are broken up into multiple records, to be reassembled at read time.

block := record* padding?

record :=
	checksum uint32     // xxhash[2] checksum of the remainder of the record
	type uint8          // the record type, detailed below
	length uint16       // the length of the record data, below
	offset uint64       // the offset (in bytes) of this record from the record that begins the entry
	data [length]uint8  // the record data

The record types are as follows:

FULL=1     // the record contains the full entry
FIRST=2    // the record is the first in an assembly
MIDDLE=3   // the record is in the middle of an assembly
LAST=4     // the record concludes an assembly

Thus, entries are assembled by reading a sequence of records:

entry :=
	  FULL
	| FIRST MIDDLE* LAST

Failure tolerance

Logio recovers from record corruption (e.g., checksum errors) and truncated writes by re-syncing at read time. If a corrupt record is encountered, the reader skips to the next block boundary (which always begins a record) and finds the first FULL or FIRST record to re-commence reading.

[1] https://github.com/google/leveldb/blob/master/doc/log_format.md [2] http://cyan4973.github.io/xxHash/

Index

• Constants
• Variables
• func Aligned(off int64) int64
• func Append(w io.Writer, off int64, data, scratch []byte) (nwrite int, err error)
• func Rewind(r io.ReaderAt, limit int64) (off int64, err error)
• type Reader
  • func NewReader(r io.Reader, offset int64) *Reader
  • func (r *Reader) Read() (data []byte, err error)
  • func (r *Reader) Reset(rd io.Reader, offset int64)
• type Writer
  • func NewWriter(wr io.Writer, offset int64) *Writer
  • func (w *Writer) Append(data []byte) error
  • func (w *Writer) Tell() int64

Constants

const Blocksz = 32 << 10

Blocksz is the size of the blocks written to the log files produced by this package. See package docs for a detailed description.

Variables

var ErrCorrupted = errors.New("corrupted log file")

ErrCorrupted is returned when log file corruption is detected.

Functions

func Aligned

func Aligned(off int64) int64

Aligned aligns the provided offset for the next write: it returns the offset at which the next record will be written, if a writer with the provided offset is provided to Append. This can be used to index into logio files.

func Append

func Append(w io.Writer, off int64, data, scratch []byte) (nwrite int, err error)

Append writes an entry to the io.Writer w. The writer must be positioned at the provided offset. If non-nil, Append will use the scratch buffer for working space, avoiding additional allocation. The scratch buffer must be at least Blocksz.

func Rewind

func Rewind(r io.ReaderAt, limit int64) (off int64, err error)

Rewind finds and returns the offset of the last log entry in the log file represented by the reader r. The provided limit is the offset of the end of the log stream; thus Rewind may be used to traverse a log file in the backwards direction (error handling is left as an exercise to the reader):

file, err := os.Open(...)
info, err := file.Stat()
off := info.Size()
for {
	off, err = logio.Rewind(file, off)
	if err == io.EOF {
		break
	}
	file.Seek(off, io.SeekStart)
	record, err := logio.NewReader(file, off).Read()
}

Rewind returns io.EOF when no records can be located in the reader limited by the provided limit.

If the passed reader is also an io.Seeker, then Rewind will seek to the returned offset.

Types

type Reader

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

Reader reads entries from a log file.

func NewReader

func NewReader(r io.Reader, offset int64) *Reader

NewReader returns a log file reader that reads log entries from the provider io.Reader. The offset must be the current offset of the io.Reader into the IO stream from which records are read.

func (*Reader) Read

func (r *Reader) Read() (data []byte, err error)

Read returns the next log entry. It returns ErrCorrupted if a corrupted log entry was encountered, in which case the next call to Read will re-sync the log file, potentially skipping entries. The returned slice should not be modified and is only valid until the next call to Read or Rewind.

func (*Reader) Reset

func (r *Reader) Reset(rd io.Reader, offset int64)

Reset resets the reader's state; subsequent entries are read from the provided reader at the provided offset.

type Writer

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

A Writer appends to a log file. Writers are thin stateful wrappers around Append.

func NewWriter

func NewWriter(wr io.Writer, offset int64) *Writer

NewWriter returns a new writer that appends log entries to the provided io.Writer. The offset given must be the offset into the underlying IO stream represented by wr.

func (*Writer) Append

func (w *Writer) Append(data []byte) error

Append appends a new entry to the log file. Appending an empty record is a no-op. Note that the writer appends only appends to the underlying stream. It is the responsibility of the caller to ensure that the writes are committed to stable storage (e.g., by calling file.Sync).

func (*Writer) Tell

func (w *Writer) Tell() int64

Tell returns the offset of the next record to be appended. This may be used to index into the log file.