iterator.go

iterator.go - Overview

This file defines the Item struct and Iterator struct, along with their associated methods, for iterating over key-value pairs in a Badger database. It also includes the IteratorOptions struct to configure the iteration behavior.

Detailed Documentation

prefetchStatus

type prefetchStatus uint8

Represents the status of prefetching an item's value.

Constants

const (
    prefetched prefetchStatus = iota + 1
)

prefetched: Indicates that the item's value has been prefetched.

Item

type Item struct {
	key       []byte
	vptr      []byte
	val       []byte
	version   uint64
	expiresAt uint64

	slice *y.Slice // Used only during prefetching.
	next  *Item
	txn   *Txn

	err      error
	wg       sync.WaitGroup
	status   prefetchStatus
	meta     byte // We need to store meta to know about bitValuePointer.
	userMeta byte
}

Item represents a key-value pair returned during iteration.

• key: The key of the item.
• vptr: Value pointer, points to the value in value log.
• val: The value of the item (only valid until iterator.Next() is called).
• version: The commit timestamp of the item.
• expiresAt: Unix timestamp when the item expires. 0 means never expires.
• slice: A slice used for temporary storage during prefetching.
• next: Pointer to the next Item in a list.
• txn: The transaction this item belongs to.
• err: Any error encountered during prefetching.
• wg: WaitGroup for prefetching.
• status: The prefetch status of the item.
• meta: Metadata about the item (e.g., whether it's a value pointer).
• userMeta: User-defined metadata.

Item.String()

func (item *Item) String() string

• Purpose: Returns a string representation of the Item.
• Returns: A string containing the key, version, and meta of the item.

Item.Key()

func (item *Item) Key() []byte

• Purpose: Returns the key of the item.
• Returns: A byte slice representing the key.

Item.KeyCopy()

func (item *Item) KeyCopy(dst []byte) []byte

• Purpose: Copies the key of the item to the provided destination slice.
• Parameters:
  • dst: The destination byte slice. If nil or capacity insufficient, a new slice is allocated.
• Returns: A byte slice containing the key (either the provided dst or a new allocation).

Item.Version()

func (item *Item) Version() uint64

• Purpose: Returns the version (commit timestamp) of the item.
• Returns: The version as a uint64.

Item.Value()

func (item *Item) Value(fn func(val []byte) error) error

• Purpose: Retrieves the value of the item and passes it to a provided function.
• Parameters:
  • fn: A function that accepts a byte slice (the value) and returns an error.
• Returns: An error, if any, encountered while retrieving the value or executing the function.

Item.ValueCopy()

func (item *Item) ValueCopy(dst []byte) ([]byte, error)

• Purpose: Copies the value of the item to the provided destination slice.
• Parameters:
  • dst: The destination byte slice. If nil or capacity insufficient, a new slice is allocated.
• Returns:
  • A byte slice containing the value (either the provided dst or a new allocation).
  • An error, if any, encountered while retrieving the value.

Item.hasValue()

func (item *Item) hasValue() bool

• Purpose: Checks if the item has a value.
• Returns: true if the item has a value, false otherwise.

Item.IsDeletedOrExpired()

func (item *Item) IsDeletedOrExpired() bool

• Purpose: Returns true if item contains deleted or expired value.
• Returns: true if the item is deleted or expired, false otherwise.

Item.DiscardEarlierVersions()

func (item *Item) DiscardEarlierVersions() bool

• Purpose: Returns whether the item was created with the option to discard earlier versions.
• Returns: true if the item was created with the discard earlier versions option, false otherwise.

Item.yieldItemValue()

func (item *Item) yieldItemValue() ([]byte, func(), error)

• Purpose: Retrieves the value of the item from the value log.
• Returns:
  • A byte slice containing the value.
  • A callback function to be executed after using the value.
  • An error, if any, encountered while retrieving the value.

Item.prefetchValue()

func (item *Item) prefetchValue()

• Purpose: Prefetches the value of the item.

Item.EstimatedSize()

func (item *Item) EstimatedSize() int64

• Purpose: Returns the approximate size of the key-value pair.
• Returns: The estimated size as an int64.

Item.KeySize()

func (item *Item) KeySize() int64

• Purpose: Returns the size of the key.
• Returns: The size of the key as an int64.

Item.ValueSize()

func (item *Item) ValueSize() int64

• Purpose: Returns the approximate size of the value.
• Returns: The estimated size of the value as an int64.

Item.UserMeta()

func (item *Item) UserMeta() byte

• Purpose: Returns the userMeta set by the user.
• Returns: The userMeta as a byte.

Item.ExpiresAt()

func (item *Item) ExpiresAt() uint64

• Purpose: Returns a Unix time value indicating when the item will be considered expired.
• Returns: The expiration timestamp as a uint64.

list

type list struct {
	head *Item
	tail *Item
}

list is a simple linked list implementation for Item structs.

• head: Pointer to the first item in the list.
• tail: Pointer to the last item in the list.

list.push()

func (l *list) push(i *Item)

• Purpose: Adds an item to the end of the list.
• Parameters:
  • i: The Item to add.

list.pop()

func (l *list) pop() *Item

• Purpose: Removes and returns the first item from the list.
• Returns: The first Item in the list, or nil if the list is empty.

IteratorOptions

type IteratorOptions struct {
	// PrefetchSize is the number of KV pairs to prefetch while iterating.
	// Valid only if PrefetchValues is true.
	PrefetchSize int
	// PrefetchValues Indicates whether we should prefetch values during
	// iteration and store them.
	PrefetchValues bool
	Reverse        bool // Direction of iteration. False is forward, true is backward.
	AllVersions    bool // Fetch all valid versions of the same key.
	InternalAccess bool // Used to allow internal access to badger keys.

	// The following option is used to narrow down the SSTables that iterator
	// picks up. If Prefix is specified, only tables which could have this
	// prefix are picked based on their range of keys.
	prefixIsKey bool   // If set, use the prefix for bloom filter lookup.
	Prefix      []byte // Only iterate over this given prefix.
	SinceTs     uint64 // Only read data that has version > SinceTs.
}

IteratorOptions configures the behavior of an Iterator.

• PrefetchSize: The number of key-value pairs to prefetch during iteration (valid only if PrefetchValues is true).
• PrefetchValues: Indicates whether to prefetch values during iteration.
• Reverse: The direction of iteration (false is forward, true is backward).
• AllVersions: Indicates whether to fetch all valid versions of the same key.
• InternalAccess: Used to allow internal access to badger keys.
• prefixIsKey: If set, use the prefix for bloom filter lookup.
• Prefix: Only iterate over keys with this prefix.
• SinceTs: Only read data that has version > SinceTs.

IteratorOptions.compareToPrefix()

func (opt *IteratorOptions) compareToPrefix(key []byte) int

• Purpose: Compares a key to the iterator's prefix.
• Parameters:
  • key: The key to compare.
• Returns: An integer indicating the comparison result (same as bytes.Compare).

IteratorOptions.pickTable()

func (opt *IteratorOptions) pickTable(t table.TableInterface) bool

• Purpose: Determines whether a given table should be included in the iteration based on the iterator's options.
• Parameters:
  • t: The table to check.
• Returns: true if the table should be included, false otherwise.

IteratorOptions.pickTables()

func (opt *IteratorOptions) pickTables(all []*table.Table) []*table.Table

• Purpose: Selects the tables to be iterated over based on the iterator options.
• Parameters:
  • all: A slice of all available tables.
• Returns: A slice of tables that should be included in the iteration.

DefaultIteratorOptions

var DefaultIteratorOptions = IteratorOptions{
	PrefetchValues: true,
	PrefetchSize:   100,
	Reverse:        false,
	AllVersions:    false,
}

DefaultIteratorOptions provides default options for iterating over Badger key-value stores.

Iterator

type Iterator struct {
	iitr   y.Iterator
	txn    *Txn
	readTs uint64

	opt   IteratorOptions
	item  *Item
	data  list
	waste list

	lastKey []byte // Used to skip over multiple versions of the same key.

	closed  bool
	scanned int // Used to estimate the size of data scanned by iterator.

	// ThreadId is an optional value that can be set to identify which goroutine created
	// the iterator. It can be used, for example, to uniquely identify each of the
	// iterators created by the stream interface
	ThreadId int

	Alloc *z.Allocator
}

Iterator facilitates iterating over key-value pairs in a lexicographically sorted order.

• iitr: Internal iterator.
• txn: The transaction this iterator belongs to.
• readTs: The read timestamp of the transaction.
• opt: The iterator options.
• item: The current item.
• data: A list of prefetched items.
• waste: A list of reusable items.
• lastKey: The last key encountered (used to skip multiple versions).
• closed: Indicates whether the iterator is closed.
• scanned: Approximate size of data scanned by iterator.
• ThreadId: Optional ID to identify the goroutine that created the iterator.
• Alloc: Allocator for memory management.

Txn.NewIterator()

func (txn *Txn) NewIterator(opt IteratorOptions) *Iterator

• Purpose: Creates a new iterator for the transaction.
• Parameters:
  • opt: The iterator options.
• Returns: A new Iterator instance.

Txn.NewKeyIterator()

func (txn *Txn) NewKeyIterator(key []byte, opt IteratorOptions) *Iterator

• Purpose: Creates a new iterator that iterates over all versions of a single key.
• Parameters:
  • key: The key to iterate over.
  • opt: The iterator options.
• Returns: A new Iterator instance.

Iterator.newItem()

func (it *Iterator) newItem() *Item

• Purpose: Gets a new or recycled Item struct.
• Returns: A pointer to an Item.

Iterator.Item()

func (it *Iterator) Item() *Item

• Purpose: Returns a pointer to the current key-value pair.
• Returns: A pointer to the current Item.

Iterator.Valid()

func (it *Iterator) Valid() bool

• Purpose: Checks if the iterator is currently pointing to a valid item.
• Returns: true if the iterator is valid, false otherwise.

Iterator.ValidForPrefix()

func (it *Iterator) ValidForPrefix(prefix []byte) bool

• Purpose: Checks if the iterator is valid and the current key has the specified prefix.
• Parameters:
  • prefix: The prefix to check.
• Returns: true if the iterator is valid and the key has the prefix, false otherwise.

Iterator.Close()

func (it *Iterator) Close()

• Purpose: Closes the iterator and releases resources.

Iterator.Next()

func (it *Iterator) Next()

• Purpose: Advances the iterator to the next key-value pair.

Iterator.parseItem()

func (it *Iterator) parseItem() bool

• Purpose: Parses the current item from the internal iterator and adds it to the data list.
• Returns: true if an item was added to the data list or the iterator is invalid, false otherwise.

Iterator.fill()

func (it *Iterator) fill(item *Item)

• Purpose: Fills an Item with data from the internal iterator.
• Parameters:
  • item: The Item to fill.

Iterator.prefetch()

func (it *Iterator) prefetch()

• Purpose: Prefetches a batch of items.

Iterator.Seek()

func (it *Iterator) Seek(key []byte)

• Purpose: Seeks to the provided key.
• Parameters:
  • key: The key to seek to.

Iterator.Rewind()

func (it *Iterator) Rewind()

• Purpose: Rewinds the iterator to the beginning.

Code Examples

No examples provided in the code.

Getting Started Relevance