Skip to main content

level_handler.go

level_handler.go - Overview​

This file defines the levelHandler struct and its associated methods for managing tables at a specific level in the LSM tree. It handles operations like adding, deleting, replacing, and retrieving tables, as well as managing their sizes and iterators.

Detailed Documentation​

levelHandler​

type levelHandler struct {
	sync.RWMutex
	tables         []*table.Table
	totalSize      int64
	totalStaleSize int64
	level    int
	strLevel string
	db       *DB
}

The levelHandler struct manages tables at a specific level.

  • sync.RWMutex: A read-write mutex to protect access to the tables and size information.
  • tables: A slice of table.Table pointers representing the tables at this level.
  • totalSize: The total size in bytes of all tables at this level.
  • totalStaleSize: The total size of stale data in tables at this level.
  • level: The level number in the LSM tree.
  • strLevel: A string representation of the level (e.g., "l0", "l1").
  • db: A pointer to the DB struct.

levelHandler.isLastLevel​

func (s *levelHandler) isLastLevel() bool {
	return s.level == s.db.opt.MaxLevels-1
}

isLastLevel checks if the level handler is for the last level in the database.

  • Returns: true if it's the last level, false otherwise.

levelHandler.getTotalStaleSize​

func (s *levelHandler) getTotalStaleSize() int64 {
	s.RLock()
	defer s.RUnlock()
	return s.totalStaleSize
}

getTotalStaleSize returns the total stale size of the level.

  • Returns: The total stale size (int64).

levelHandler.getTotalSize​

func (s *levelHandler) getTotalSize() int64 {
	s.RLock()
	defer s.RUnlock()
	return s.totalSize
}

getTotalSize returns the total size of the level.

  • Returns: The total size (int64).

levelHandler.initTables​

func (s *levelHandler) initTables(tables []*table.Table) {
	s.Lock()
	defer s.Unlock()

	s.tables = tables
	s.totalSize = 0
	s.totalStaleSize = 0
	for _, t := range tables {
		s.addSize(t)
	}

	if s.level == 0 {
		sort.Slice(s.tables, func(i, j int) bool {
			return s.tables[i].ID() < s.tables[j].ID()
		})
	} else {
		sort.Slice(s.tables, func(i, j int) bool {
			return y.CompareKeys(s.tables[i].Smallest(), s.tables[j].Smallest()) &lt; 0
		})
	}
}

initTables initializes the level handler with the given tables. It replaces the existing tables, recalculates the total size, and sorts the tables based on the level.

  • Parameters:
    • tables: A slice of table.Table pointers to initialize the level with.

levelHandler.deleteTables​

func (s *levelHandler) deleteTables(toDel []*table.Table) error {
	s.Lock()

	toDelMap := make(map[uint64]struct{})
	for _, t := range toDel {
		toDelMap[t.ID()] = struct{}{}
	}

	var newTables []*table.Table
	for _, t := range s.tables {
		_, found := toDelMap[t.ID()]
		if !found {
			newTables = append(newTables, t)
			continue
		}
		s.subtractSize(t)
	}
	s.tables = newTables

	s.Unlock()

	return decrRefs(toDel)
}

deleteTables removes the specified tables from the level.

  • Parameters:
    • toDel: A slice of table.Table pointers to delete.
  • Returns: An error, if any.

levelHandler.replaceTables​

func (s *levelHandler) replaceTables(toDel, toAdd []*table.Table) error {
	s.Lock()

	toDelMap := make(map[uint64]struct{})
	for _, t := range toDel {
		toDelMap[t.ID()] = struct{}{}
	}
	var newTables []*table.Table
	for _, t := range s.tables {
		_, found := toDelMap[t.ID()]
		if !found {
			newTables = append(newTables, t)
			continue
		}
		s.subtractSize(t)
	}

	for _, t := range toAdd {
		s.addSize(t)
		t.IncrRef()
		newTables = append(newTables, t)
	}

	s.tables = newTables
	sort.Slice(s.tables, func(i, j int) bool {
		return y.CompareKeys(s.tables[i].Smallest(), s.tables[j].Smallest()) &lt; 0
	})
	s.Unlock()
	return decrRefs(toDel)
}

replaceTables replaces a set of tables with another set of tables.

  • Parameters:
    • toDel: A slice of table.Table pointers to delete.
    • toAdd: A slice of table.Table pointers to add.
  • Returns: An error, if any.

levelHandler.addTable​

func (s *levelHandler) addTable(t *table.Table) {
	s.Lock()
	defer s.Unlock()

	s.addSize(t)
	t.IncrRef()
	s.tables = append(s.tables, t)
}

addTable adds a table to the level.

  • Parameters:
    • t: A pointer to the table.Table to add.

levelHandler.sortTables​

func (s *levelHandler) sortTables() {
	s.Lock()
	defer s.Unlock()

	sort.Slice(s.tables, func(i, j int) bool {
		return y.CompareKeys(s.tables[i].Smallest(), s.tables[j].Smallest()) &lt; 0
	})
}

sortTables sorts the tables in the level based on their smallest keys.

decrRefs​

func decrRefs(tables []*table.Table) error {
	for _, table := range tables {
		if err := table.DecrRef(); err != nil {
			return err
		}
	}
	return nil
}

decrRefs decrements the reference count of each table in the given slice.

  • Parameters:
    • tables: A slice of table.Table pointers.
  • Returns: An error, if any.

newLevelHandler​

func newLevelHandler(db *DB, level int) *levelHandler {
	return &levelHandler{
		level:    level,
		strLevel: fmt.Sprintf("l%d", level),
		db:       db,
	}
}

newLevelHandler creates a new levelHandler.

  • Parameters:
    • db: A pointer to the DB struct.
    • level: The level number.
  • Returns: A pointer to the new levelHandler.

levelHandler.tryAddLevel0Table​

func (s *levelHandler) tryAddLevel0Table(t *table.Table) bool {
	y.AssertTrue(s.level == 0)
	s.Lock()
	defer s.Unlock()
	if len(s.tables) >= s.db.opt.NumLevelZeroTablesStall {
		return false
	}

	s.tables = append(s.tables, t)
	t.IncrRef()
	s.addSize(t)

	return true
}

tryAddLevel0Table attempts to add a table to level 0. It checks if the number of tables at level 0 exceeds the stall threshold.

  • Parameters:
    • t: A pointer to the table.Table to add.
  • Returns: true if the table was added, false otherwise (if stalling).

levelHandler.addSize​

func (s *levelHandler) addSize(t *table.Table) {
	s.totalSize += t.Size()
	s.totalStaleSize += int64(t.StaleDataSize())
}

addSize adds the size of a table to the total size of the level. This should be called while holding the lock on the level.

  • Parameters:
    • t: A pointer to the table.Table.

levelHandler.subtractSize​

func (s *levelHandler) subtractSize(t *table.Table) {
	s.totalSize -= t.Size()
	s.totalStaleSize -= int64(t.StaleDataSize())
}

subtractSize subtracts the size of a table from the total size of the level. This should be called while holding the lock on the level.

  • Parameters:
    • t: A pointer to the table.Table.

levelHandler.numTables​

func (s *levelHandler) numTables() int {
	s.RLock()
	defer s.RUnlock()
	return len(s.tables)
}

numTables returns the number of tables in the level.

  • Returns: The number of tables (int).

levelHandler.close​

func (s *levelHandler) close() error {
	s.RLock()
	defer s.RUnlock()
	var err error
	for _, t := range s.tables {
		if closeErr := t.Close(-1); closeErr != nil && err == nil {
			err = closeErr
		}
	}
	return y.Wrap(err, "levelHandler.close")
}

close closes all tables in the level.

  • Returns: An error, if any.

levelHandler.getTableForKey​

func (s *levelHandler) getTableForKey(key []byte) ([]*table.Table, func() error) {
	s.RLock()
	defer s.RUnlock()

	if s.level == 0 {
		out := make([]*table.Table, 0, len(s.tables))
		for i := len(s.tables) - 1; i >= 0; i-- {
			out = append(out, s.tables[i])
			s.tables[i].IncrRef()
		}
		return out, func() error {
			for _, t := range out {
				if err := t.DecrRef(); err != nil {
					return err
				}
			}
			return nil
		}
	}
	idx := sort.Search(len(s.tables), func(i int) bool {
		return y.CompareKeys(s.tables[i].Biggest(), key) >= 0
	})
	if idx >= len(s.tables) {
		return nil, func() error { return nil }
	}
	tbl := s.tables[idx]
	tbl.IncrRef()
	return []*table.Table{tbl}, tbl.DecrRef
}

getTableForKey retrieves the tables that may contain the given key.

  • Parameters:
    • key: The key to search for.
  • Returns: A slice of table.Table pointers and a function to decrement the reference count of the tables.

levelHandler.get​

func (s *levelHandler) get(key []byte) (y.ValueStruct, error) {
	tables, decr := s.getTableForKey(key)
	keyNoTs := y.ParseKey(key)

	hash := y.Hash(keyNoTs)
	var maxVs y.ValueStruct
	for _, th := range tables {
		if th.DoesNotHave(hash) {
			y.NumLSMBloomHitsAdd(s.db.opt.MetricsEnabled, s.strLevel, 1)
			continue
		}

		it := th.NewIterator(0)
		defer it.Close()

		y.NumLSMGetsAdd(s.db.opt.MetricsEnabled, s.strLevel, 1)
		it.Seek(key)
		if !it.Valid() {
			continue
		}
		if y.SameKey(key, it.Key()) {
			if version := y.ParseTs(it.Key()); maxVs.Version &lt; version {
				maxVs = it.ValueCopy()
				maxVs.Version = version
			}
		}
	}
	return maxVs, decr()
}

get returns the value for a given key.

  • Parameters:
    • key: The key to search for.
  • Returns: The y.ValueStruct and an error, if any.

levelHandler.appendIterators​

func (s *levelHandler) appendIterators(iters []y.Iterator, opt *IteratorOptions) []y.Iterator {
	s.RLock()
	defer s.RUnlock()

	var topt int
	if opt.Reverse {
		topt = table.REVERSED
	}
	if s.level == 0 {
		var out []*table.Table
		for _, t := range s.tables {
			if opt.pickTable(t) {
				out = append(out, t)
			}
		}
		return appendIteratorsReversed(iters, out, topt)
	}

	tables := opt.pickTables(s.tables)
	if len(tables) == 0 {
		return iters
	}
	return append(iters, table.NewConcatIterator(tables, topt))
}

appendIterators appends iterators for the tables in this level to the given slice of iterators.

  • Parameters:
    • iters: A slice of y.Iterator.
    • opt: IteratorOptions for creating the iterators.
  • Returns: The updated slice of y.Iterator.

levelHandlerRLocked​

type levelHandlerRLocked struct{}

levelHandlerRLocked is an empty struct used as a signal to indicate that a read lock is already held on the levelHandler.

levelHandler.overlappingTables​

func (s *levelHandler) overlappingTables(_ levelHandlerRLocked, kr keyRange) (int, int) {
	if len(kr.left) == 0 || len(kr.right) == 0 {
		return 0, 0
	}
	left := sort.Search(len(s.tables), func(i int) bool {
		return y.CompareKeys(kr.left, s.tables[i].Biggest()) &lt;= 0
	})
	right := sort.Search(len(s.tables), func(i int) bool {
		return y.CompareKeys(kr.right, s.tables[i].Smallest()) &lt; 0
	})
	return left, right
}

overlappingTables returns the range of tables that overlap with the given key range. This function assumes a read lock is already held.

  • Parameters:
    • _: An empty levelHandlerRLocked struct to enforce that the read lock is held.
    • kr: The keyRange to check for overlaps.
  • Returns: The left and right indices of the overlapping tables (half-interval).

Code Examples​

None

Getting Started Relevance​