table

package
v0.0.0-...-cb5117c Latest Latest
Warning

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

 Go to latest Published: Jul 25, 2017 License: Apache-2.0 Imports: 17 Imported by: 0

README

BenchmarkRead

$ go test -bench Read$ -count 3

Size of table: 105843444
BenchmarkRead-8   	3	 343846914 ns/op
BenchmarkRead-8   	3	 351790907 ns/op
BenchmarkRead-8   	3	 351762823 ns/op

Size of table is 105,843,444 bytes, which is ~101M.

The rate is ~287M/s which matches our read speed. This is using mmap.

To read a 64M table, this would take ~0.22s, which is negligible.

$ go test -bench BenchmarkReadAndBuild -count 3

BenchmarkReadAndBuild-8   	       1	2341034225 ns/op
BenchmarkReadAndBuild-8   	       1	2346349671 ns/op
BenchmarkReadAndBuild-8   	       1	2364064576 ns/op

The rate is ~43M/s. To build a ~64M table, this would take ~1.5s. Note that this does NOT include the flushing of the table to disk. All we are doing above is to read one table (mmaped) and write one table in memory.

The table building takes 1.5-0.22 ~ 1.3s.

If we are writing out up to 10 tables, this would take 1.5*10 ~ 15s, and ~13s is spent building the tables.

When running populate, building one table in memory tends to take ~1.5s to ~2.5s on my system. Where does this overhead come from? Let's investigate the merging.

Below, we merge 5 tables. The total size remains unchanged at ~101M.

$ go test -bench ReadMerged -count 3
BenchmarkReadMerged-8   	       1	1321190264 ns/op
BenchmarkReadMerged-8   	       1	1296958737 ns/op
BenchmarkReadMerged-8   	       1	1314381178 ns/op

The rate is ~76M/s. To build a 64M table, this would take ~0.84s. The writing takes ~1.3s as we saw above. So in total, we expect around 0.84+1.3 ~ 2.1s. This roughly matches what we observe when running populate. There might be some additional overhead due to the concurrent writes going on, in flushing the table to disk. Also, the tables tend to be slightly bigger than 64M/s.

Documentation

Index

Constants

View Source 
const (
	Nothing = iota
	MemoryMap
	LoadToRAM
)

Variables

View Source 
var (
	ORIGIN  = 0
	CURRENT = 1
)
View Source 
var EOF = errors.New("End of mapped region")

Functions

func NewFilename 

func NewFilename(id uint64, dir string) string

func ParseFileID 

func ParseFileID(name string) (uint64, bool)

Types

type Block 

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

func (Block) NewIterator 

func (b Block) NewIterator() *BlockIterator

type BlockIterator 

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

func (*BlockIterator) Close 

func (itr *BlockIterator) Close()

func (*BlockIterator) Error 

func (itr *BlockIterator) Error() error

func (*BlockIterator) Init 

func (itr *BlockIterator) Init()

func (*BlockIterator) Key 

func (itr *BlockIterator) Key() []byte

func (*BlockIterator) Next 

func (itr *BlockIterator) Next()

func (*BlockIterator) Prev 

func (itr *BlockIterator) Prev()

func (*BlockIterator) Reset 

func (itr *BlockIterator) Reset()

func (*BlockIterator) Seek 

func (itr *BlockIterator) Seek(key []byte, whence int)

Seek brings us to the first block element that is >= input key.

func (*BlockIterator) SeekToFirst 

func (itr *BlockIterator) SeekToFirst()

func (*BlockIterator) SeekToLast 

func (itr *BlockIterator) SeekToLast()

SeekToLast brings us to the last element. Valid should return true.

func (*BlockIterator) Valid 

func (itr *BlockIterator) Valid() bool

func (*BlockIterator) Value 

func (itr *BlockIterator) Value() []byte

type ConcatIterator 

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

func NewConcatIterator 

func NewConcatIterator(tbls []*Table, reversed bool) *ConcatIterator

func (*ConcatIterator) Close 

func (s *ConcatIterator) Close() error

func (*ConcatIterator) Key 

func (s *ConcatIterator) Key() []byte

func (*ConcatIterator) Name 

func (s *ConcatIterator) Name() string

func (*ConcatIterator) Next 

func (s *ConcatIterator) Next()

Next advances our concat iterator.

func (*ConcatIterator) Rewind 

func (s *ConcatIterator) Rewind()

func (*ConcatIterator) Seek 

func (s *ConcatIterator) Seek(key []byte)

Seek brings us to element >= key if reversed is false. Otherwise, <= key.

func (*ConcatIterator) Valid 

func (s *ConcatIterator) Valid() bool

func (*ConcatIterator) Value 

func (s *ConcatIterator) Value() y.ValueStruct

type Table 

type Table struct {
	sync.Mutex
	// contains filtered or unexported fields
}

func OpenTable 

func OpenTable(fd *os.File, mapTableTo int) (*Table, error)

OpenTable assumes file has only one table and opens it. Takes ownership of fd upon function entry. Returns a table with one reference count on it (decrementing which may delete the file! -- consider t.Close() instead).

func (*Table) Biggest 

func (t *Table) Biggest() []byte

func (*Table) Close 

func (t *Table) Close() error

func (*Table) DecrRef 

func (t *Table) DecrRef() error

func (*Table) DoesNotHave 

func (t *Table) DoesNotHave(key []byte) bool

func (*Table) Filename 

func (t *Table) Filename() string

func (*Table) ID 

func (t *Table) ID() uint64

func (*Table) IncrRef 

func (t *Table) IncrRef()

func (*Table) LoadToRAM 

func (t *Table) LoadToRAM() error

func (*Table) Metadata 

func (t *Table) Metadata() []byte

Metadata returns metadata. Do not mutate this.

func (*Table) NewIterator 

func (t *Table) NewIterator(reversed bool) *TableIterator

func (*Table) Ref 

func (t *Table) Ref() int32

func (*Table) SetMetadata 

func (t *Table) SetMetadata(meta []byte) error

SetMetadata updates our metadata to the new metadata. For now, they must be of the same size.

func (*Table) Size 

func (t *Table) Size() int64

func (*Table) Smallest 

func (t *Table) Smallest() []byte

func (*Table) UpdateLevel 

func (t *Table) UpdateLevel(newLevel int)

updateLevel is called only when moving table to the next level, when there is no overlap with the next level. Here, we update the table metadata.

type TableBuilder 

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

func NewTableBuilder 

func NewTableBuilder() *TableBuilder

func (*TableBuilder) Add 

func (b *TableBuilder) Add(key []byte, value y.ValueStruct) error

Add adds a key-value pair to the block. If doNotRestart is true, we will not restart even if b.counter >= restartInterval.

func (*TableBuilder) Close 

func (b *TableBuilder) Close()

Close closes the TableBuilder. Do not use buf field anymore.

func (*TableBuilder) Empty 

func (b *TableBuilder) Empty() bool

func (*TableBuilder) Finish 

func (b *TableBuilder) Finish(metadata []byte) []byte

Finish finishes the table by appending the index.

func (*TableBuilder) ReachedCapacity 

func (b *TableBuilder) ReachedCapacity(cap int64) bool

FinalSize returns the *rough* final size of the array, counting the header which is not yet written. TODO: Look into why there is a discrepancy. I suspect it is because of Write(empty, empty) at the end. The diff can vary.

type TableIterator 

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

func (*TableIterator) Close 

func (itr *TableIterator) Close() error

func (*TableIterator) Error 

func (itr *TableIterator) Error() error

func (*TableIterator) Init 

func (itr *TableIterator) Init()

func (*TableIterator) Key 

func (itr *TableIterator) Key() []byte

func (*TableIterator) Name 

func (s *TableIterator) Name() string

func (*TableIterator) Next 

func (s *TableIterator) Next()

func (*TableIterator) Rewind 

func (s *TableIterator) Rewind()

func (*TableIterator) Seek 

func (s *TableIterator) Seek(key []byte)

func (*TableIterator) Valid 

func (itr *TableIterator) Valid() bool

func (*TableIterator) Value 

func (itr *TableIterator) Value() y.ValueStruct

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.