data structures - Organizing disk file for very fast access -

-

i developing key value database similar apache cassandra , leveldb.

it utilize lsm trees (https://en.wikipedia.org/wiki/log-structured_merge-tree)

keys strings , using c++.

currently data stored on disk in several immutable "sstables", each 2 files.

  • data file - "flat" file - record after record, sorted key, without disk block alignment.

  • index file - contains number of records , array of 8 byte numbers (uint64_t) offcets each record. can position (seek) , find offset record data file.

i have mmap-ed these 2 files in memory.

if program need locate record binary search. means program lots of disk seeks. did optimizations, example jump search , sequentially read last 40-50 records. on file 1 billion keys, still 20-25 seeks (instead of 30).

this works pretty fast - 4-5 seconds 1 billion keys without virtual memory cache (e.g. first ever request) , way under 1 second virtual memory cache.

however thinking of building additional data structure on disk can speed lookup more. thought use "level ordered array", e.g. instead of:

1, 2, 3, 4, 5, 6, 7

to be

4, 2, 6, 1, 3, 5, 7

in case, used keys @ beginning of file, not 100% sure much.

second though b tree or b+tree, creation seems complex lot of disk syncs - or @ least how see it.

apache cassandra using key samples - have every 1024th key in memory - not want go way, because of memory consumption. however, if have them on disk in "flat" file, still needs lots of seeks find "sample" key.

is there alternative missing?


Comments

Post a Comment

Popular posts from this blog

Spring Boot + JPA + Hibernate: Unable to locate persister -

-
i trying work entity inside request method of spring boot application. entity in project , pom.xml has dependencies it. why error message?: org.hibernate.unknownentitytypeexception: unable locate persister: com.ric.bill.model.bs.par package com.ric.web; import java.util.concurrent.atomic.atomiclong; import javax.persistence.entitymanager; import javax.persistence.persistencecontext; import net.sf.ehcache.cachemanager; import net.sf.ehcache.management.cache; import net.sf.ehcache.management.cachestatistics; import org.hibernate.stat.statistics; import org.springframework.beans.factory.annotation.autowired; import org.springframework.boot.autoconfigure.domain.entityscan; import org.springframework.cache.annotation.enablecaching; import org.springframework.transaction.annotation.enabletransactionmanagement; import org.springframework.transaction.annotation.propagation; import org.springframework.transaction.annotation.transactional; import org.springframework.web.bind.annotati
Read more

go - Golang: panic: runtime error: invalid memory address or nil pointer dereference using bufio.Scanner -

-
i implementing go program uses bufio.scanner , bufio.writer have packaged code follows package main import ( "fmt" "player/command" "strings" ) func main() { //enter code here. read input stdin. print output stdout commands.scanner.scan() { //scan new line , send comand variable check command exist or not input := strings.split(strings.trim(commands.scanner.text(), " "), " ") command := input[0] if command == "" { fmt.printf("$ %s:", commands.pwd) continue } if !commands.commands[command] { commands.throwerror("cannot recognize input.") } else { commands.execute(command, input[1:], nil) } fmt.printf("$ %s:", commands.pwd) } } i using init.go file in main package follows package main import ( "flag" "player/sourc
Read more

c - double free or corruption (fasttop) -

-
this code reads null terminated string file (file containing null terminated strings & should provide index wanted string). error: *** error in `./main': double free or corruption (fasttop): 0x090a4a80 *** aborted code: char *tmp_realloc=null; char *sstring=null; int i=1; /*set file pointer point string*/ fseek(fh,index,seek_set); sstring=(char*)malloc(sizeof(char)); if(sstring == null) return null; tmp_realloc=sstring; while( (*(sstring+i-1)=(char)fgetc((file*)fh)) != 0x0 ) { /*reallocate more memory*/ tmp_realloc=(char*)realloc((char*)sstring,++i); /*if not same address copy old new & set old point new*/ if(tmp_realloc != sstring){ strcpy((char*)tmp_realloc,(char*)sstring); free(sstring); sstring=tmp_realloc; } } could tell me pointer causing issue (& reason) ? remove part /*if not same address copy old new & set old point new*/ if(tmp_realloc != sstring){ strc
Read more