ristretto: github.com/dgraph-io/ristretto/z Index | Files | Directories

package z

import "github.com/dgraph-io/ristretto/z"

Index

Package Files

allocator.go bbloom.go btree.go buffer.go calloc.go calloc_64bit.go calloc_nojemalloc.go file.go file_linux.go histogram.go mmap.go mmap_linux.go rtutil.go z.go

Constants

const (
    // MaxArrayLen is a safe maximum length for slices on this architecture.
    MaxArrayLen = 1<<50 - 1
    // MaxBufferSize is the size of virtually unlimited buffer on this architecture.
    MaxBufferSize = 256 << 30
)

Variables

var NewFile = errors.New("Create a new file")

func Allocators Uses

func Allocators() string

func BytesToUint64Slice Uses

func BytesToUint64Slice(b []byte) []uint64

BytesToU32Slice converts the given byte slice to uint32 slice

func CPUTicks Uses

func CPUTicks() int64

CPUTicks is a faster alternative to NanoTime to measure time duration.

func Calloc Uses

func Calloc(n int) []byte

Calloc allocates a slice of size n.

func CallocNoRef Uses

func CallocNoRef(n int) []byte

CallocNoRef will not give you memory back without jemalloc.

func FastRand Uses

func FastRand() uint32

FastRand is a fast thread local random function.

func Free Uses

func Free(b []byte)

Free does not do anything in this mode.

func HistogramBounds Uses

func HistogramBounds(minExponent, maxExponent uint32) []float64

Creates bounds for an histogram. The bounds are powers of two of the form [2^min_exponent, ..., 2^max_exponent].

func KeyToHash Uses

func KeyToHash(key interface{}) (uint64, uint64)

TODO: Figure out a way to re-use memhash for the second uint64 hash, we

already know that appending bytes isn't reliable for generating a
second hash (see Ristretto PR #88).

We also know that while the Go runtime has a runtime memhash128
function, it's not possible to use it to generate [2]uint64 or
anything resembling a 128bit hash, even though that's exactly what
we need in this situation.

func Leaks Uses

func Leaks() string

func Madvise Uses

func Madvise(b []byte, readahead bool) error

Madvise uses the madvise system call to give advise about the use of memory when using a slice that is memory-mapped to a file. Set the readahead flag to false if page references are expected in random order.

func MemHash Uses

func MemHash(data []byte) uint64

MemHash is the hash function used by go map, it utilizes available hardware instructions(behaves as aeshash if aes instruction is available). NOTE: The hash seed changes for every process. So, this cannot be used as a persistent hash.

func MemHashString Uses

func MemHashString(str string) uint64

MemHashString is the hash function used by go map, it utilizes available hardware instructions (behaves as aeshash if aes instruction is available). NOTE: The hash seed changes for every process. So, this cannot be used as a persistent hash.

func Memclr Uses

func Memclr(b []byte)

func Mmap Uses

func Mmap(fd *os.File, writable bool, size int64) ([]byte, error)

Mmap uses the mmap system call to memory-map a file. If writable is true, memory protection of the pages is set so that they may be written to as well.

func Msync Uses

func Msync(b []byte) error

Msync would call sync on the mmapped data.

func Munmap Uses

func Munmap(b []byte) error

Munmap unmaps a previously mapped slice.

func NanoTime Uses

func NanoTime() int64

NanoTime returns the current time in nanoseconds from a monotonic clock.

func NumAllocBytes Uses

func NumAllocBytes() int64

NumAllocBytes returns the number of bytes allocated using calls to z.Calloc. The allocations could be happening via either Go or jemalloc, depending upon the build flags.

func ReadMemStats Uses

func ReadMemStats(_ *MemStats)

ReadMemStats doesn't do anything since all the memory is being managed by the Go runtime.

func SetTmpDir Uses

func SetTmpDir(dir string)

SetTmpDir sets the temporary directory for the temporary buffers.

func StatsPrint Uses

func StatsPrint()

func SyncDir Uses

func SyncDir(dir string) error

func ZeroOut Uses

func ZeroOut(dst []byte, start, end int)

ZeroOut zeroes out all the bytes in the range [start, end).

type Allocator Uses

type Allocator struct {
    sync.Mutex

    Ref uint64
    Tag string
    // contains filtered or unexported fields
}

Allocator amortizes the cost of small allocations by allocating memory in bigger chunks. Internally it uses z.Calloc to allocate memory. Once allocated, the memory is not moved, so it is safe to use the allocated bytes to unsafe cast them to Go struct pointers. Maintaining a freelist is slow. Instead, Allocator only allocates memory, with the idea that finally we would just release the entire Allocator.

func AllocatorFrom Uses

func AllocatorFrom(ref uint64) *Allocator

AllocatorFrom would return the allocator corresponding to the ref.

func NewAllocator Uses

func NewAllocator(sz int) *Allocator

NewAllocator creates an allocator starting with the given size.

func (*Allocator) Allocate Uses

func (a *Allocator) Allocate(sz int) []byte

func (*Allocator) AllocateAligned Uses

func (a *Allocator) AllocateAligned(sz int) []byte

func (*Allocator) Allocated Uses

func (a *Allocator) Allocated() uint64

func (*Allocator) Copy Uses

func (a *Allocator) Copy(buf []byte) []byte

func (*Allocator) MaxAlloc Uses

func (a *Allocator) MaxAlloc() int

func (*Allocator) Release Uses

func (a *Allocator) Release()

Release would release the memory back. Remember to make this call to avoid memory leaks.

func (*Allocator) Reset Uses

func (a *Allocator) Reset()

func (*Allocator) Size Uses

func (a *Allocator) Size() int

Size returns the size of the allocations so far.

func (*Allocator) String Uses

func (a *Allocator) String() string

func (*Allocator) TrimTo Uses

func (a *Allocator) TrimTo(max int)

type AllocatorPool Uses

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

func NewAllocatorPool Uses

func NewAllocatorPool(sz int) *AllocatorPool

func (*AllocatorPool) Get Uses

func (p *AllocatorPool) Get(sz int) *Allocator

func (*AllocatorPool) Release Uses

func (p *AllocatorPool) Release()

func (*AllocatorPool) Return Uses

func (p *AllocatorPool) Return(a *Allocator)

type Bloom Uses

type Bloom struct {
    ElemNum uint64
    // contains filtered or unexported fields
}

Bloom filter

func JSONUnmarshal Uses

func JSONUnmarshal(dbData []byte) (*Bloom, error)

JSONUnmarshal takes JSON-Object (type bloomJSONImExport) as []bytes returns bloom32 / bloom64 object.

func NewBloomFilter Uses

func NewBloomFilter(params ...float64) (bloomfilter *Bloom)

NewBloomFilter returns a new bloomfilter.

func (*Bloom) Add Uses

func (bl *Bloom) Add(hash uint64)

Add adds hash of a key to the bloomfilter.

func (*Bloom) AddIfNotHas Uses

func (bl *Bloom) AddIfNotHas(hash uint64) bool

AddIfNotHas only Adds hash, if it's not present in the bloomfilter. Returns true if hash was added. Returns false if hash was already registered in the bloomfilter.

func (*Bloom) Clear Uses

func (bl *Bloom) Clear()

Clear resets the Bloom filter.

func (Bloom) Has Uses

func (bl Bloom) Has(hash uint64) bool

Has checks if bit(s) for entry hash is/are set, returns true if the hash was added to the Bloom Filter.

func (*Bloom) IsSet Uses

func (bl *Bloom) IsSet(idx uint64) bool

IsSet checks if bit[idx] of bitset is set, returns true/false.

func (Bloom) JSONMarshal Uses

func (bl Bloom) JSONMarshal() []byte

JSONMarshal returns JSON-object (type bloomJSONImExport) as []byte.

func (*Bloom) Set Uses

func (bl *Bloom) Set(idx uint64)

Set sets the bit[idx] of bitset.

func (*Bloom) Size Uses

func (bl *Bloom) Size(sz uint64)

Size makes Bloom filter with as bitset of size sz.

func (*Bloom) TotalSize Uses

func (bl *Bloom) TotalSize() int

TotalSize returns the total size of the bloom filter.

type Buffer Uses

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

Buffer is equivalent of bytes.Buffer without the ability to read. It is NOT thread-safe.

In UseCalloc mode, z.Calloc is used to allocate memory, which depending upon how the code is compiled could use jemalloc for allocations.

In UseMmap mode, Buffer uses file mmap to allocate memory. This allows us to store big data structures without using physical memory.

MaxSize can be set to limit the memory usage.

func BufferFrom Uses

func BufferFrom(data []byte) *Buffer

func NewBuffer Uses

func NewBuffer(sz int) *Buffer

NewBuffer is a helper utility, which creates a virtually unlimited Buffer in UseCalloc mode.

func NewBufferWith Uses

func NewBufferWith(sz, maxSz int, bufType BufferType) (*Buffer, error)

NewBufferWith would allocate a buffer of size sz upfront, with the total size of the buffer not exceeding maxSz. Both sz and maxSz can be set to zero, in which case reasonable defaults would be used. Buffer can't be used without initialization via NewBuffer.

func NewBufferWithDir Uses

func NewBufferWithDir(sz, maxSz int, bufType BufferType, dir string) (*Buffer, error)

NewBufferWithDir would allocate a buffer of size sz upfront, with the total size of the buffer not exceeding maxSz. Both sz and maxSz can be set to zero, in which case reasonable defaults would be used. Buffer can't be used without initialization via NewBuffer. The buffer is created inside dir. The caller should take care of existence of dir.

func (*Buffer) Allocate Uses

func (b *Buffer) Allocate(n int) []byte

Allocate is a way to get a slice of size n back from the buffer. This slice can be directly written to. Warning: Allocate is not thread-safe. The byte slice returned MUST be used before further calls to Buffer.

func (*Buffer) AllocateOffset Uses

func (b *Buffer) AllocateOffset(n int) int

AllocateOffset works the same way as allocate, but instead of returning a byte slice, it returns the offset of the allocation.

func (*Buffer) AutoMmapAfter Uses

func (b *Buffer) AutoMmapAfter(size int)

func (*Buffer) Bytes Uses

func (b *Buffer) Bytes() []byte

Bytes would return all the written bytes as a slice.

func (*Buffer) Data Uses

func (b *Buffer) Data(offset int) []byte

func (*Buffer) Grow Uses

func (b *Buffer) Grow(n int)

Grow would grow the buffer to have at least n more bytes. In case the buffer is at capacity, it would reallocate twice the size of current capacity + n, to ensure n bytes can be written to the buffer without further allocation. In UseMmap mode, this might result in underlying file expansion.

func (*Buffer) IsEmpty Uses

func (b *Buffer) IsEmpty() bool

func (*Buffer) LenNoPadding Uses

func (b *Buffer) LenNoPadding() int

LenNoPadding would return the number of bytes written to the buffer so far (without the padding).

func (*Buffer) LenWithPadding Uses

func (b *Buffer) LenWithPadding() int

LenWithPadding would return the number of bytes written to the buffer so far plus the padding at the start of the buffer.

func (*Buffer) Release Uses

func (b *Buffer) Release() error

Release would free up the memory allocated by the buffer. Once the usage of buffer is done, it is important to call Release, otherwise a memory leak can happen.

func (*Buffer) Reset Uses

func (b *Buffer) Reset()

Reset would reset the buffer to be reused.

func (*Buffer) Slice Uses

func (b *Buffer) Slice(offset int) ([]byte, int)

Slice would return the slice written at offset.

func (*Buffer) SliceAllocate Uses

func (b *Buffer) SliceAllocate(sz int) []byte

SliceAllocate would encode the size provided into the buffer, followed by a call to Allocate, hence returning the slice of size sz. This can be used to allocate a lot of small buffers into this big buffer. Note that SliceAllocate should NOT be mixed with normal calls to Write.

func (*Buffer) SliceIterate Uses

func (b *Buffer) SliceIterate(f func(slice []byte) error) error

func (*Buffer) SliceOffsets Uses

func (b *Buffer) SliceOffsets() []int

SliceOffsets is an expensive function. Use sparingly.

func (*Buffer) SortSlice Uses

func (b *Buffer) SortSlice(less func(left, right []byte) bool)

SortSlice is like SortSliceBetween but sorting over the entire buffer.

func (*Buffer) SortSliceBetween Uses

func (b *Buffer) SortSliceBetween(start, end int, less LessFunc)

func (*Buffer) StartOffset Uses

func (b *Buffer) StartOffset() int

func (*Buffer) Write Uses

func (b *Buffer) Write(p []byte) (n int, err error)

Write would write p bytes to the buffer.

func (*Buffer) WriteSlice Uses

func (b *Buffer) WriteSlice(slice []byte)

type BufferType Uses

type BufferType int
const (
    UseCalloc BufferType = iota
    UseMmap
    UseInvalid
)

func (BufferType) String Uses

func (t BufferType) String() string

type Closer Uses

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

Closer holds the two things we need to close a goroutine and wait for it to finish: a chan to tell the goroutine to shut down, and a WaitGroup with which to wait for it to finish shutting down.

func NewCloser Uses

func NewCloser(initial int) *Closer

NewCloser constructs a new Closer, with an initial count on the WaitGroup.

func (*Closer) AddRunning Uses

func (lc *Closer) AddRunning(delta int)

AddRunning Add()'s delta to the WaitGroup.

func (*Closer) Ctx Uses

func (lc *Closer) Ctx() context.Context

Ctx can be used to get a context, which would automatically get cancelled when Signal is called.

func (*Closer) Done Uses

func (lc *Closer) Done()

Done calls Done() on the WaitGroup.

func (*Closer) HasBeenClosed Uses

func (lc *Closer) HasBeenClosed() <-chan struct{}

HasBeenClosed gets signaled when Signal() is called.

func (*Closer) Signal Uses

func (lc *Closer) Signal()

Signal signals the HasBeenClosed signal.

func (*Closer) SignalAndWait Uses

func (lc *Closer) SignalAndWait()

SignalAndWait calls Signal(), then Wait().

func (*Closer) Wait Uses

func (lc *Closer) Wait()

Wait waits on the WaitGroup. (It waits for NewCloser's initial value, AddRunning, and Done calls to balance out.)

type HistogramData Uses

type HistogramData struct {
    Bounds         []float64
    Count          int64
    CountPerBucket []int64
    Min            int64
    Max            int64
    Sum            int64
}

HistogramData stores the information needed to represent the sizes of the keys and values as a histogram.

func NewHistogramData Uses

func NewHistogramData(bounds []float64) *HistogramData

NewHistogramData returns a new instance of HistogramData with properly initialized fields.

func (*HistogramData) Copy Uses

func (histogram *HistogramData) Copy() *HistogramData

func (*HistogramData) Mean Uses

func (histogram *HistogramData) Mean() float64

Mean returns the mean value for the histogram.

func (*HistogramData) String Uses

func (histogram *HistogramData) String() string

String converts the histogram data into human-readable string.

func (*HistogramData) Update Uses

func (histogram *HistogramData) Update(value int64)

Update changes the Min and Max fields if value is less than or greater than the current values.

type LessFunc Uses

type LessFunc func(a, b []byte) bool

type MemStats Uses

type MemStats struct {
    // Total number of bytes allocated by the application.
    // http://jemalloc.net/jemalloc.3.html#stats.allocated
    Allocated uint64
    // Total number of bytes in active pages allocated by the application. This
    // is a multiple of the page size, and greater than or equal to
    // Allocated.
    // http://jemalloc.net/jemalloc.3.html#stats.active
    Active uint64
    // Maximum number of bytes in physically resident data pages mapped by the
    // allocator, comprising all pages dedicated to allocator metadata, pages
    // backing active allocations, and unused dirty pages. This is a maximum
    // rather than precise because pages may not actually be physically
    // resident if they correspond to demand-zeroed virtual memory that has not
    // yet been touched. This is a multiple of the page size, and is larger
    // than stats.active.
    // http://jemalloc.net/jemalloc.3.html#stats.resident
    Resident uint64
    // Total number of bytes in virtual memory mappings that were retained
    // rather than being returned to the operating system via e.g. munmap(2) or
    // similar. Retained virtual memory is typically untouched, decommitted, or
    // purged, so it has no strongly associated physical memory (see extent
    // hooks http://jemalloc.net/jemalloc.3.html#arena.i.extent_hooks for
    // details). Retained memory is excluded from mapped memory statistics,
    // e.g. stats.mapped (http://jemalloc.net/jemalloc.3.html#stats.mapped).
    // http://jemalloc.net/jemalloc.3.html#stats.retained
    Retained uint64
}

MemStats is used to fetch JE Malloc Stats. The stats are fetched from the mallctl namespace http://jemalloc.net/jemalloc.3.html#mallctl_namespace.

type MmapFile Uses

type MmapFile struct {
    Data []byte
    Fd   *os.File
}

MmapFile represents an mmapd file and includes both the buffer to the data and the file descriptor.

func OpenMmapFile Uses

func OpenMmapFile(filename string, flag int, maxSz int) (*MmapFile, error)

OpenMmapFile opens an existing file or creates a new file. If the file is created, it would truncate the file to maxSz. In both cases, it would mmap the file to maxSz and returned it. In case the file is created, z.NewFile is returned.

func OpenMmapFileUsing Uses

func OpenMmapFileUsing(fd *os.File, sz int, writable bool) (*MmapFile, error)

func (*MmapFile) AllocateSlice Uses

func (m *MmapFile) AllocateSlice(sz, offset int) ([]byte, int, error)

AllocateSlice allocates a slice of the given size at the given offset.

func (*MmapFile) Bytes Uses

func (m *MmapFile) Bytes(off, sz int) ([]byte, error)

Bytes returns data starting from offset off of size sz. If there's not enough data, it would return nil slice and io.EOF.

func (*MmapFile) Close Uses

func (m *MmapFile) Close(maxSz int64) error

Close would close the file. It would also truncate the file if maxSz >= 0.

func (*MmapFile) Delete Uses

func (m *MmapFile) Delete() error

func (*MmapFile) NewReader Uses

func (m *MmapFile) NewReader(offset int) io.Reader

func (*MmapFile) Slice Uses

func (m *MmapFile) Slice(offset int) []byte

Slice returns the slice at the given offset.

func (*MmapFile) Sync Uses

func (m *MmapFile) Sync() error

func (*MmapFile) Truncate Uses

func (m *MmapFile) Truncate(maxSz int64) error

Truncate would truncate the mmapped file to the given size. On Linux, we truncate the underlying file and then call mremap, but on other systems, we unmap first, then truncate, then re-map.

type Tree Uses

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

Tree represents the structure for custom mmaped B+ tree. It supports keys in range [1, math.MaxUint64-1] and values [1, math.Uint64].

func NewTree Uses

func NewTree() *Tree

NewTree returns a memory mapped B+ tree with given filename.

func (*Tree) DeleteBelow Uses

func (t *Tree) DeleteBelow(ts uint64)

DeleteBelow deletes all keys with value under ts.

func (*Tree) Get Uses

func (t *Tree) Get(k uint64) uint64

Get looks for key and returns the corresponding value. If key is not found, 0 is returned.

func (*Tree) Iterate Uses

func (t *Tree) Iterate(fn func(node))

Iterate iterates over the tree and executes the fn on each node.

func (*Tree) Print Uses

func (t *Tree) Print()

Print iterates over the tree and prints all valid KVs.

func (*Tree) Reset Uses

func (t *Tree) Reset()

Reset resets the tree and truncates it to maxSz.

func (*Tree) Set Uses

func (t *Tree) Set(k, v uint64)

Set sets the key-value pair in the tree.

func (*Tree) Stats Uses

func (t *Tree) Stats() TreeStats

Stats returns stats about the tree.

type TreeStats Uses

type TreeStats struct {
    Allocated    int     // Derived.
    Bytes        int     // Derived.
    NumLeafKeys  int     // Calculated.
    NumPages     int     // Derived.
    NumPagesFree int     // Calculated.
    Occupancy    float64 // Derived.
    PageSize     int     // Derived.
}

Directories

PathSynopsis
simd

Package z imports 25 packages (graph) and is imported by 35 packages. Updated 2021-01-22. Refresh now. Tools for package owners.