After inserting a specific set of KV pairs in lexicographic key order (sorted with bytes.Compare, as used by the DB), seeking for some key prefixes stops to work (returns io.EOF immediately). Inserting one more KV pair undoes the damage while e.g. closing and reopening the DB does not.

I can reliably produce such state by inserting the first 796 (when sorted by their SHA1 hash) fortunes from the plan9port fortune file, using the SHA1 hash as the key. The value used doesn't seem to matter.

A program demonstrating the issue can be found at:
http://play.golang.org/p/nvBij8buMA
https://gist.github.com/slrz/a80bdbc7af5c0753091f

Actual output:
got: 511 (expected: 511) (for n=795)
got: 0 (expected: 512) (for n=796)
got: 513 (expected: 513) (for n=797)

Expected output:
got: 511 (expected: 511) (for n=795)
got: 512 (expected: 512) (for n=796)
got: 513 (expected: 513) (for n=797)

Enumerating the full DB using SeekFirst still seems to work. Replacing the 0x10 key prefix in the program with 0x09 or 0x11 also shows the expected behaviour.

Neither DB.Verify nor kvaudit report any issues with the DB.

If you don't have plan9port installed, the file referenced in the test program is this one:
https://github.com/9fans/plan9port/raw/ca9ae08876bc9ce2107fac50cf703760ecf10901/lib/fortunes

Go compiler and runtime are today's tip on Linux but trying with go1.4 shows the same behaviour, as does OS X.

http://godoc.org/github.com/cznic/kv returns Not Found for me.

Is this a known issue or should I report it at godoc.org?

https://github.com/camlistore/lock

It's better:

• Selects approach per platforrm.
• Handles stale lock files.

As I understand the docs, this code should not print any entries
because the added entries were part of a transaction that is
rolled back. But it actually prints x=y - the Set operation
has actually been committed.

What am I doing wrong?

package main

import (
    "fmt"
    "io"
    "log"

    "github.com/cznic/kv"
)

func main() {
    db, err := kv.CreateMem(&kv.Options{})
    if err != nil {
        log.Fatal("create:", err)
    }
    if err := db.BeginTransaction(); err != nil {
        log.Fatal("begin transaction:", err)
    }
    if err := db.Set([]byte("x"), []byte("y")); err != nil {
        log.Fatal("set:", err)
    }
    if err := db.Rollback(); err != nil {
        log.Fatal("rollback:", err)
    }
    if err := printKeys(db); err != nil {
        log.Fatal("print keys:", err)
    }
}

func printKeys(db *kv.DB) error {
    enum, err := db.SeekFirst()
    if err != nil {
        return err
    }
    for {
        k, v, err := enum.Next()
        if err == io.EOF {
            break
        }
        if err != nil {
            return err
        }
        fmt.Printf("%s=%s\n", k, v)
    }
    return nil
}

returend is misspelled twice in the docs.

I have a usecase where my encoded struct would be at maximum ~124k big. To use kv i need to split the data into several keys and store it, but when reading/writing i would need access to the whole object at a time. It sounds a little ineffecient retrieving and writing several keys for a single operation.

Any plans to increase the size limit?

Hello,

When calling Get() on a missing key it always return nil data. The same thing happens with records with empty value. How do you tell one from another?

Here is a test describing the problem:

pmezard@28a08e2

The last two checks currently fail. The empty record can be seeked so it actually exists.

What do you think of changing Get() so that:

• missing records always return nil
• empty records return an empty slice
  (This is boltdb behaviour).

I can try to make a PR on lldb if the change is ok for you.

I have a situation where I'm hoping to make the DB file more portable, and I was hoping to be able to just pick up and move the main DB file and be able to open it again. But I'm seeing that even when I close the DB, then move the DB file and try to re-open it, it fails WAL file does not exist.

According to the documentation:

WALName returns the name of the WAL file in use or an empty string for memory or closed databases.

It appears that the WAL file shouldn't be needed anymore when closed, is that not accurate, or am I misunderstanding?

FreeBSD and Windows both fail to compile kv, both with different errors.

Hi, after update, I catch panic.
panic: runtime error: index out of range
goroutine 7957 [running]:
panic(0x452e0e0, 0xc42000c0f0)
/Users/billyfbrain/coding/go/go/src/runtime/panic.go:500 +0x1a1
cern/vendor/github.com/cznic/lldb.btreePage.find(0x0, 0x0, 0x0, 0x4836b20, 0xc4203eab00, 0x0, 0xc42016e190, 0xf, 0x10, 0x0, ...)
/Users/billyfbrain/coding/go/src/cern/vendor/github.com/cznic/lldb/btree.go:1599 +0x334
cern/vendor/github.com/cznic/lldb.btree.get(0x1, 0x4836b20, 0xc4203eab00, 0xc420296000, 0x1010f, 0x20000, 0x0, 0xc42016e190, 0xf, 0x10, ...)
/Users/billyfbrain/coding/go/src/cern/vendor/github.com/cznic/lldb/btree.go:2018 +0x19c
cern/vendor/github.com/cznic/lldb.(_BTree).Get(0xc4204e9770, 0x0, 0x0, 0x0, 0xc42016e190, 0xf, 0x10, 0x0, 0x0, 0x0, ...)
/Users/billyfbrain/coding/go/src/cern/vendor/github.com/cznic/lldb/btree.go:251 +0x157
cern/vendor/github.com/cznic/kv.(_DB).Get(0xc4201c1b90, 0x0, 0x0, 0x0, 0xc42016e190, 0xf, 0x10, 0x0, 0x0, 0x0, ...)
/Users/billyfbrain/coding/go/src/cern/vendor/github.com/cznic/kv/kv.go:657 +0x127
cern/storage/blob.Open(0xc4202eeba0, 0x51, 0xc42004d7e6, 0x45328e0, 0x37, 0xc42052e680)

Hi,

I'm using (*kv.DB).Seek() and enum.Next() on the returned *kv.Enumerator.
During this I see high RSS - after finishing with the enumerator, pprof registered mem usage drops to 4Mb.

With the help of the attached pprof heap diagram, I've found in lldb/xact.go that ReadAt stored the read pages - for what?
Why not leave this to the OS' page cache? Or use an LFU cache?

Thanks,
Tamás Gulácsi

I'm test github.com/syndtr/goleveldb/leveldb and github.com/cznic/kv
https://play.golang.org/p/EMAWeQWCdsY

go1.10beta1 test -bench .
goos: linux
goarch: amd64
pkg: sdstack.com/storage/storage/test/tt
BenchmarkLevelDB-16     2000000000               0.09 ns/op     11858927.40 MB/s
BenchmarkKV-16          2000000000               0.36 ns/op     2845198.15 MB/s

Or make it safe and never mutate it (make a copy first). Probably better as easier for clients.

basic test case:
https://gist.github.com/mpl/6366649

The title says it all.

Can we get a CreateFromFiler(filer lldb.Filer, opts *Options) (db *DB, err error), which allows me to experiment with different kinds of backing storage?

A standard idiom for enumerators seems to have emerged [1],[2],
which makes for quite nice looking code. Perhaps consider
using that here.

Something like this perhaps?

type Enumerator struct {...}

// Next moves to the next element in the enumeration.
// It returns false when there are no more entries
// or if there's an error.
func (*Enumerator) Next() bool

// Prev moves to the previous element in the enumeration.
// It returns false when there are no more entries
// or if there's an error.
func (*Enumerator) Prev() bool

// Key returns the key at the current enumerator position.
func (*Enumerator) Key() []byte

// Value returns the value at the current enumerator position.
func (*Enumerator) Value() []byte

// Err returns any error encountered during the enumeration.
func (*Enumerator) Err() error

Example usage:

enum := db.SeekFirst()
for enum.Next() {
    fmt.Printf("%s=%s\n", enum.Key(), enum.Value())
}
if err := enum.Err(); err != nil {
    log.Fatal(err)
}

[1] http://golang.org/pkg/bufio/#Scanner
[2] http://godoc.org/gopkg.in/mgo.v2#Iter

I'm not sure if I'm missing something with how the code is supposed to be called but I notice that with when I execute:

http://play.golang.org/p/sc-KI41oub

it appears that kv ends up leaving garbage files on the filesystem:

$ ls -la /tmp/kv/1
total 0
drwxr-xr-x 2 jimr wheel 68 Aug 2 14:20 .
drwxr-xr-x 3 jimr wheel 102 Aug 2 14:20 ..

$ ./test /tmp/kv/1
2013/08/02 14:21:08 a: /tmp/kv/1
2013/08/02 14:21:08 b: /tmp/kv/1
2013/08/02 14:21:08 b: /tmp/kv/1/.bc0939a070bf34b982567b7a384db75ec5d29812
2013/08/02 14:21:08 b: /tmp/kv/1/.fdbe33d0292d0f6cfce3e8240d51f49f1fa90284
2013/08/02 14:21:08 b: /tmp/kv/1/kv.074994926.db
2013/08/02 14:21:08 c: /tmp/kv/1
2013/08/02 14:21:08 c: /tmp/kv/1/.bc0939a070bf34b982567b7a384db75ec5d29812
2013/08/02 14:21:08 c: /tmp/kv/1/.fdbe33d0292d0f6cfce3e8240d51f49f1fa90284
2013/08/02 14:21:08 c: /tmp/kv/1/kv.074994926.db
2013/08/02 14:21:08 d: /tmp/kv/1
2013/08/02 14:21:08 d: /tmp/kv/1/.bc0939a070bf34b982567b7a384db75ec5d29812
2013/08/02 14:21:08 d: /tmp/kv/1/.fdbe33d0292d0f6cfce3e8240d51f49f1fa90284
2013/08/02 14:21:08 d: /tmp/kv/1/kv.074994926.db
2013/08/02 14:21:08 e: /tmp/kv/1
2013/08/02 14:21:08 e: /tmp/kv/1/.fdbe33d0292d0f6cfce3e8240d51f49f1fa90284
2013/08/02 14:21:08 e: /tmp/kv/1/kv.074994926.db

$ ls -la /tmp/kv/1
total 8
drwxr-xr-x 4 jimr wheel 136 Aug 2 14:21 .
drwxr-xr-x 3 jimr wheel 102 Aug 2 14:20 ..
-rw-r--r-- 1 jimr wheel 0 Aug 2 14:21 .fdbe33d0292d0f6cfce3e8240d51f49f1fa90284
-rw------- 1 jimr wheel 176 Aug 2 14:21 kv.074994926.db

I was testing this because I had a benchmark that was running a number of Set and Get operations, and it came back reporting that it was out of filehandles:

tsv_test.go:140: unable to create kv temp index db: open /var/folders/kh/2l9gqrs54b118zpxc5bd3s4w0000gn/T/.cf5f02dcd9cb6a51c7efa5b6aa1b9ad1ac8066d0: too many open files

This is executed on a Mac OS X system, running

go version devel +b43eb215afd3 Fri Jun 28 18:37:06 2013 +0400 darwin/amd64

kv has a data race in *DB.Close.

This is especially a problem because kv installs its own signal handler:

func (db *DB) boot() (err error) {
if !db.isMem {
c := make(chan os.Signal, 1)
signal.Notify(c, os.Interrupt, os.Kill)
go func() {
<-c
db.Close()
}()
}
return
}

So then on Control-C (SIGINT), both Camlistore's signal handler and kv's own both compete to call DB.Close in different goroutines.

I'm okay with kv having its own signal handler, but there should be a sync.Once or sync.Mutex around DB.Close.

Also, this is frowned upon Go style:

func (db *DB) Close() (err error) {

Never name return parameters on public types just to permit naked returns. The cleanliness of the godoc is a higher priority, and not stuttering. Naked returns are generally frowned upon for all but the smallest functions, and this Close method doesn't look too small. Explicit returns would be better.

Camlistore bug is https://code.google.com/p/camlistore/issues/detail?id=332

The lack of it allowed a (newly introduced) bug in Options.clone to slip through.

Given that Get returns a nil value when the entry doesn't
exist, then why not run with that and make a nil value exactly the same
as a deleted value? That is, if you do db.Set(key, nil),
it would be the same as db.Delete(key).

This would also make it easy to allow DB.Put to
delete values as well as create and update them - if
upd returns (true, nil, nil).

Would be very useful to have a PutIfAbsent function. Something that only inserts if there is no value at that key.

kv intercepts a couple of signals and causes a bit of confusion. If a program ever uses kv, it can never shut down on SIGINT. It's also tries to handle SIGKILL.

I could understand trying to keep things clean during a sensitive part, but the program could crash anyway, so it's probably best just to expect that.

Great job, and any benchmark vs other pure Golang KV storege like goleveldb (https://github.com/syndtr/goleveldb)?

I currently have some indexes and I need to access them in ascending and descending order.
Current solution is that I use is of place holder key that is always sorted after my index.So I can use Seek function to seek to it and then use Prev to use index in reverse order.

I tested FoundationDB go driver and it had way to seek to last key that matches key prefix.
Is this something that could be added to kv without scanning every key between first seeked and last matching key prefix?

I think the update to lldb stable in 48b826e broke kvaudit.

github.com/cznic/kv/kvaudit (master u=) $ go test .
--- FAIL: TestBad (0.00s)
panic: runtime error: invalid memory address or nil pointer dereference [recovered]
	panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x4e7e56]

goroutine 5 [running]:
panic(0x53fb20, 0xc42000c120)
	/usr/lib/go-1.7/src/runtime/panic.go:500 +0x1a1
testing.tRunner.func1(0xc420090180)
	/usr/lib/go-1.7/src/testing/testing.go:579 +0x25d
panic(0x53fb20, 0xc42000c120)
	/usr/lib/go-1.7/src/runtime/panic.go:458 +0x243
github.com/cznic/lldb.(*SimpleFileFiler).Size(0x0, 0x0, 0x0, 0x0)
	$GOPATH/src/github.com/cznic/lldb/simplefilefiler.go:84 +0x26
github.com/cznic/lldb.(*InnerFiler).Size(0xc420011680, 0xc42009e000, 0x0, 0x816c20)
	$GOPATH/src/github.com/cznic/lldb/filer.go:161 +0x37
github.com/cznic/lldb.NewAllocator(0x804940, 0xc420011680, 0xc420053978, 0x8, 0xc420032038, 0x0)
	$GOPATH/src/github.com/cznic/lldb/falloc.go:328 +0x18c
github.com/cznic/kv/kvaudit.main0(0xc42000c620, 0x10, 0x0, 0x578380, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, ...)
	$GOPATH/src/github.com/cznic/kv/kvaudit/main.go:133 +0x1d6
github.com/cznic/kv/kvaudit.TestBad(0xc420090180)
	$GOPATH/src/github.com/cznic/kv/kvaudit/all_test.go:21 +0xd1
testing.tRunner(0xc420090180, 0x578358)
	/usr/lib/go-1.7/src/testing/testing.go:610 +0x81
created by testing.(*T).Run
	/usr/lib/go-1.7/src/testing/testing.go:646 +0x2ec
FAIL	github.com/cznic/kv/kvaudit	0.004s

If I replace the import in kvaudit/main.go with exp/lldb, the tests run as expected.

# import lldb -> import exp/lldb
github.com/cznic/kv/kvaudit (master * u=) $ go test .
ok  	github.com/cznic/kv/kvaudit	0.002s

I am getting the following error when I try to install the library. Any thoughts? I am using Ubuntu 13.04 with Go 1.0.2

sudo go get github.com/cznic/kv

github.com/cznic/bufs

/usr/lib/go/src/pkg/github.com/cznic/bufs/bufs.go:380: function ends without a return statement

github.com/cznic/zappy

encode_cgo.go:121[/tmp/go-build080741296/github.com/cznic/zappy/_obj/encode_cgo.cgo1.go:23]: constant 4294967295 overflows int

github.com/cznic/mathutil

/usr/lib/go/src/pkg/github.com/cznic/mathutil/envelope.go:30: function ends without a return statement
/usr/lib/go/src/pkg/github.com/cznic/mathutil/mathutil.go:363: function ends without a return statement
/usr/lib/go/src/pkg/github.com/cznic/mathutil/mathutil.go:431: function ends without a return statement
/usr/lib/go/src/pkg/github.com/cznic/mathutil/primes.go:28: function ends without a return statement
/usr/lib/go/src/pkg/github.com/cznic/mathutil/primes.go:91: function ends without a return statement
/usr/lib/go/src/pkg/github.com/cznic/mathutil/rat.go:13: function ends without a return statement
/usr/lib/go/src/pkg/github.com/cznic/mathutil/rnd.go:145: function ends without a return statement
/usr/lib/go/src/pkg/github.com/cznic/mathutil/rnd.go:337: function ends without a return statement

It's unclear if some operations need synchronization. For example, it's clear that the Enumerator implementation tracks modifications between enumeration steps, but it's unclear whether those modifications can happen concurrently with enumeration steps.

The requirement of operations performed in isolation to maintain the appearance of atomicity is likewise vague: what precisely do you mean by isolation (must we make sure our transactions hold a mutex or are equivalently and exclusively synchronized in order for them to be atomic)?

It may be cleaner to describe the circumstances in which kv isn't concurrent safe (or has different semantics when ops are done concurrently) rather than describing the situations in which concurrent access is safe/predictable.

The docs declare only os.PathError can ever be returned, but that's (no longer) true. Actually it was not true in the moment of the first public release.

Thanks for making this package. I noticed that this package and its cznic/* dependencies have the following cluase in their source files:

// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

However the actual LICENSE file appears to be absent. Would you consider addressing this? Thanks!