Git Product home page Git Product logo

go-memdb's Introduction

go-memdb CircleCI

Provides the memdb package that implements a simple in-memory database built on immutable radix trees. The database provides Atomicity, Consistency and Isolation from ACID. Being that it is in-memory, it does not provide durability. The database is instantiated with a schema that specifies the tables and indices that exist and allows transactions to be executed.

The database provides the following:

  • Multi-Version Concurrency Control (MVCC) - By leveraging immutable radix trees the database is able to support any number of concurrent readers without locking, and allows a writer to make progress.

  • Transaction Support - The database allows for rich transactions, in which multiple objects are inserted, updated or deleted. The transactions can span multiple tables, and are applied atomically. The database provides atomicity and isolation in ACID terminology, such that until commit the updates are not visible.

  • Rich Indexing - Tables can support any number of indexes, which can be simple like a single field index, or more advanced compound field indexes. Certain types like UUID can be efficiently compressed from strings into byte indexes for reduced storage requirements.

  • Watches - Callers can populate a watch set as part of a query, which can be used to detect when a modification has been made to the database which affects the query results. This lets callers easily watch for changes in the database in a very general way.

For the underlying immutable radix trees, see go-immutable-radix.

Documentation

The full documentation is available on Godoc.

Example

Below is a simple example of usage

// Create a sample struct
type Person struct {
	Email string
	Name  string
	Age   int
}

// Create the DB schema
schema := &memdb.DBSchema{
	Tables: map[string]*memdb.TableSchema{
		"person": &memdb.TableSchema{
			Name: "person",
			Indexes: map[string]*memdb.IndexSchema{
				"id": &memdb.IndexSchema{
					Name:    "id",
					Unique:  true,
					Indexer: &memdb.StringFieldIndex{Field: "Email"},
				},
				"age": &memdb.IndexSchema{
					Name:    "age",
					Unique:  false,
					Indexer: &memdb.IntFieldIndex{Field: "Age"},
				},
			},
		},
	},
}

// Create a new data base
db, err := memdb.NewMemDB(schema)
if err != nil {
	panic(err)
}

// Create a write transaction
txn := db.Txn(true)

// Insert some people
people := []*Person{
	&Person{"[email protected]", "Joe", 30},
	&Person{"[email protected]", "Lucy", 35},
	&Person{"[email protected]", "Tariq", 21},
	&Person{"[email protected]", "Dorothy", 53},
}
for _, p := range people {
	if err := txn.Insert("person", p); err != nil {
		panic(err)
	}
}

// Commit the transaction
txn.Commit()

// Create read-only transaction
txn = db.Txn(false)
defer txn.Abort()

// Lookup by email
raw, err := txn.First("person", "id", "[email protected]")
if err != nil {
	panic(err)
}

// Say hi!
fmt.Printf("Hello %s!\n", raw.(*Person).Name)

// List all the people
it, err := txn.Get("person", "id")
if err != nil {
	panic(err)
}

fmt.Println("All the people:")
for obj := it.Next(); obj != nil; obj = it.Next() {
	p := obj.(*Person)
	fmt.Printf("  %s\n", p.Name)
}

// Range scan over people with ages between 25 and 35 inclusive
it, err = txn.LowerBound("person", "age", 25)
if err != nil {
	panic(err)
}

fmt.Println("People aged 25 - 35:")
for obj := it.Next(); obj != nil; obj = it.Next() {
	p := obj.(*Person)
	if p.Age > 35 {
		break
	}
	fmt.Printf("  %s is aged %d\n", p.Name, p.Age)
}
// Output:
// Hello Joe!
// All the people:
//   Dorothy
//   Joe
//   Lucy
//   Tariq
// People aged 25 - 35:
//   Joe is aged 30
//   Lucy is aged 35

go-memdb's People

Contributors

abennett avatar allencloud avatar alvin-huang avatar armon avatar banks avatar claire-labry avatar dadgar avatar dependabot[bot] avatar dnephin avatar drewbailey avatar eculver avatar edwardbetts avatar hashicorp-copywrite[bot] avatar hbagdi avatar hc-github-team-es-release-engineering avatar jakedt avatar jefferai avatar jorygeerts avatar kisunji avatar kyhavlov avatar mdeggies avatar mechpen avatar mitchellh avatar preetapan avatar radeksimko avatar ryanuber avatar saromanov avatar shore avatar slackpad avatar vishalnayak avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

go-memdb's Issues

How to use Get() and the ResultIterator?

Hi all,

I'm kinda stuck on using the Get() function.

My result should return three DB entries which I try to retrieve like this:
result, err := txn.Get("foobar", "RefType", refType)

How do I go over the results one by one?

Thanks!

Index out of order for `IntFieldIndex`

With the following code (slight modification of example code), I found results of the rows being out of order.

Based on the example I would assume that the results would be in order.

Code:

package main

import (
	"fmt"
	"time"

	"github.com/hashicorp/go-memdb"
	"github.com/segmentio/ksuid"
)

func main() {
	// Create a sample struct
	type Person struct {
		Email string
		Name  string
		Age   int
	}

	// Create the DB schema
	schema := &memdb.DBSchema{
		Tables: map[string]*memdb.TableSchema{
			"person": {
				Name: "person",
				Indexes: map[string]*memdb.IndexSchema{
					"id": {
						Name:    "id",
						Unique:  true,
						Indexer: &memdb.StringFieldIndex{Field: "Email"},
					},
					"age": {
						Name:    "age",
						Unique:  false,
						Indexer: &memdb.IntFieldIndex{Field: "Age"},
					},
				},
			},
		},
	}

	// Create a new data base
	db, err := memdb.NewMemDB(schema)
	if err != nil {
		panic(err)
	}

	// Create a write transaction
	txn := db.Txn(true)

	// Insert very many people
	for i := 0; i < 1000; i++ {
		p := &Person{
			Email: ksuid.New().String(),
			Age:   i,
		}
		if err := txn.Insert("person", p); err != nil {
			panic(err)
		}
		// fmt.Println("INserted", i)
	}
	fmt.Println("inserted")

	// Commit the transaction
	txn.Commit()

	// Create read-only transaction
	txn = db.Txn(false)
	defer txn.Abort()

	// Range scan over people with ages between 25 and 35 inclusive
	start := time.Now()
	it, err := txn.LowerBound("person", "age", 1)
	if err != nil {
		panic(err)
	}

	fmt.Println("People aged 25 - 35:")
	i := 0
	for obj := it.Next(); obj != nil; obj = it.Next() {
		p := obj.(*Person)
		fmt.Printf("  %s is aged %d\n", p.Email, p.Age)
		// if p.Age > 200 {
		// 	break
		// }
		i++
		if i == 100 {
			break
		}
	}
	fmt.Println(time.Since(start))
}

Output:

inserted
People aged 25 - 35:
  21ZfMMKi3eIPU3bZOXN2MueNVFC is aged 1
  21ZfMLObHa1548szSMA4t4stgMh is aged 2
  21ZfMG9Wn7AQttLuhv54A3wcjdq is aged 3
  21ZfMMoydQX1MocpnLR9koVsbOO is aged 4
  21ZfMLbElyEiw8oqSoLoP6CcTtU is aged 5
  21ZfMIHZfEqLar18hb6MyVTptSz is aged 6
  21ZfMNNDLrsrUp4CsQvVyzE9hO1 is aged 7
  21ZfMGGz9D84sx0lGNZNM4KefFU is aged 8
  21ZfMLX1HPc9luyo3qEA4D92mh4 is aged 9
  21ZfMMkFCvTqD3h0eLKyytVyL9l is aged 10
  21ZfMFkBm7dwi3EPln2VLHnwob5 is aged 11
  21ZfMFgIMjvt8m3Kt7OcGcrFSNi is aged 12
  21ZfMJw348zQ0zzdtfB7wuAnZ0n is aged 13
  21ZfMJEKCmOyyDpYWYsPsB4TYT4 is aged 14
  21ZfMFhfwNq5DsB7b8yTwL8e242 is aged 15
  21ZfMIiklNhWrfZKSw85J5lB88n is aged 16
  21ZfMIEjiSS5OF0jL45zo4uw4cN is aged 17
  21ZfMKR0phJOhwcQw1uVgwUw58z is aged 18
  21ZfMJn8F8ix9vQ3eXz9TmeP8Jr is aged 19
  21ZfMMuJdacG1Ns3XRzx1fiWyio is aged 20
  21ZfMJsT309ghr2UJdgWNxfYif6 is aged 21
  21ZfMGMNrW7a1fpLnjQYK5goMLK is aged 22
  21ZfMMBC5d7fRGRZHBygY8p0RVH is aged 23
  21ZfMFyUVofmkDOXXjsT0yf2NaC is aged 24
  21ZfMLeEhUXKeI1LdCDOUung68u is aged 25
  21ZfML3QnDhUkNLDP59rma1lS7z is aged 26
  21ZfMNBtH47fZLVjyrZekP2d7ju is aged 27
  21ZfMJTWv9u2VbqR4F5B7wXIpIx is aged 28
  21ZfMJO8NbfsEF7Xu6PzbyP3lw3 is aged 29
  21ZfMJ56lOXMV8WdWnBPgzW9kYO is aged 30
  21ZfMFvSItxvMvuJh8Z5el0x0vC is aged 31
  21ZfMKc7cTdDKxFaigQ6csXlT9f is aged 32
  21ZfMI5njSIOtmeZPYEaw0VUKVk is aged 33
  21ZfMIKLK4BH9k2j8oJGnnLgDDl is aged 34
  21ZfMJKu6LaogaZzvS57AIOTWa3 is aged 35
  21ZfMGOd9lcMDdRVWlFR9yyvMHz is aged 36
  21ZfMFwONDqAfh5UuSKQyFyo6mV is aged 37
  21ZfMK5TXeFVLJVjsANXidatBic is aged 38
  21ZfMHSkeVxEETr3b04mPSVjUQl is aged 39
  21ZfMIvFosiaEHQXEV3IqLWpHNl is aged 40
  21ZfMJjYKiHHUeqTcWKw1oWKIE2 is aged 41
  21ZfMKMujeeCzJziK1IltGV9ZrQ is aged 42
  21ZfMLPQLmwcbCpntzxQLl9AY2e is aged 43
  21ZfMJOsp4XWqQ5GxL6449nbPq0 is aged 44
  21ZfMKarrJ8pJqlRELJV2ztyzMb is aged 45
  21ZfMIKgiiMJGcxFhQKndcOO9QX is aged 46
  21ZfMKYxGCJxHvjtjJcEB9AHrxA is aged 47
  21ZfMMlBDe4CiAc2ncX0TQYWEX6 is aged 48
  21ZfMHIL1Z9dALZStOJIXPss1ie is aged 49
  21ZfMMsh7dvzqXTV5j0YchSXQ0p is aged 50
  21ZfMIjHK4KTWpRnOYkopppzfIF is aged 51
  21ZfMLkemfP2f7dCDk8k2XcvZHY is aged 52
  21ZfMIlLYbF5fesjH71qUm8L1Tu is aged 53
  21ZfMJaAhu5RXB31xJaWmy0rYSu is aged 54
  21ZfMGT8a1WsoXvaVy7aCni8WLk is aged 55
  21ZfMNJLw41lx23iLOvM3vlabjF is aged 56
  21ZfMMi8MYqnrvCa4EWUTKQNAGC is aged 57
  21ZfMJPplhdf1TbVtymnB6a0AHd is aged 58
  21ZfMLJtnT5jnRKYljfFN7gAIIC is aged 59
  21ZfMHbs0SDoDCSxbku7toPGPhR is aged 60
  21ZfMIB9QE49c3AtVg7qvN8yDZ7 is aged 61
  21ZfMMeGTeuUU6KAJ8h8LRb5XNM is aged 62
  21ZfMIE9od85kp89U4y7vB2hAVl is aged 63
  21ZfMMxNoT5kyDNB7OVq2BL2foB is aged 64
  21ZfMGa0JbhDYTS2N4HoqB1C6p0 is aged 128
  21ZfMK4v8dJ7h1M3xDuoabZU6QD is aged 192
  21ZfMGDbQjaFYpJ9LJ89kQIb5tp is aged 256
  21ZfMIujwXJU8xfjkRWTScnNTHp is aged 320
  21ZfMICYjUJ3kz5X1cSONVwtx0g is aged 384
  21ZfMMVcMMpLrnaapM4VxMx1fSF is aged 448
  21ZfMGbTsmgYg0MHea4fsmV5XCn is aged 512
  21ZfMKC9iUdS7fXNHCGrgiENnCu is aged 576
  21ZfMHsvapaO4Ho97oMQrTaktw1 is aged 640
  21ZfMICIqVxOcp4OfEea915Q46r is aged 704
  21ZfMGUDI2fyVdYcm0WwdgdfUQV is aged 768
  21ZfMImVF18NB7GXncR0gec7haO is aged 832
  21ZfMKDCnGRv1BnDqad14rzmwpb is aged 896
  21ZfMNNtiBWhwOn2gDpqAc7EZSb is aged 960
  21ZfMKnGTiF8YRMycIFpq0tRzxa is aged 65
  21ZfMJjxf82foQmcCom66hXoEaC is aged 129
  21ZfMJk0PVaUlns8z00OHsczZz5 is aged 193
  21ZfMM1PKTQaktWBzc7ahOKlLzT is aged 257
  21ZfMJ2yhE6qKVJJvL65NeCdnjz is aged 321
  21ZfMHsCDeOcVgn6RINlxjbeIMi is aged 385
  21ZfMMLYCd2kBKMXCMLYqGV7y69 is aged 449
  21ZfMHxl2gIZIE1KRSnEAck7WCm is aged 513
  21ZfMNEBTld9vkQIhteZVoOuYeh is aged 577
  21ZfMLVNVbHOsf8lKiCw6Aw5ria is aged 641
  21ZfMMthuNgtsUQgU0gGea4UMqq is aged 705
  21ZfMGbBbTLAOCIFxZGwS5qsS0N is aged 769
  21ZfMIlfnhTPrheY3PqiUoZKWpE is aged 833
  21ZfMHD4e4yLZEQ2N3j5DJ2KU8x is aged 897
  21ZfMFeW56O1TAh9LeMZdCWEMSw is aged 961
  21ZfMKZwIouXKp8N4TvVPdGe1ga is aged 66
  21ZfMKx1NyfYTI8z4HFplydPO1C is aged 130
  21ZfMKrhq9yyi76X10tTjBIUzDz is aged 194
  21ZfMLlD8q6MHLh42HLcIK4OemN is aged 258
  21ZfMNJjsfcA3Y5WLItkLSN1Uyt is aged 322
  21ZfMJTy6LNDMhhB22VZ1P2YW1i is aged 386
  21ZfMI5oGGhoFF33enXVvBTCL3f is aged 450

IntFieldIndex does not order correctly when number is bigger than 64.

Thanks for a great library!

I tried to write some code using IntFieldIndex, but it seems that the numbers are not ordered correctly.

This is the code.

package main

import (
	"fmt"

	"github.com/hashicorp/go-memdb"
)

func main() {
	type Item struct {
		Number int
	}
	schema := &memdb.DBSchema{
		Tables: map[string]*memdb.TableSchema{
			"item": &memdb.TableSchema{
				Name: "item",
				Indexes: map[string]*memdb.IndexSchema{
					"id": &memdb.IndexSchema{
						Name:    "id",
						Unique:  true,
						Indexer: &memdb.IntFieldIndex{Field: "Number"},
					},
				},
			},
		},
	}
	db, err := memdb.NewMemDB(schema)
	if err != nil {
		panic(err)
	}
	txn := db.Txn(true)
	for i := 0; i < 256; i++ {
		if err := txn.Insert("item", &Item{Number: i}); err != nil {
			panic(err)
		}
	}
	txn.Commit()
	txn = db.Txn(false)
	defer txn.Abort()
	it, err := txn.Get("item", "id")
	if err != nil {
		panic(err)
	}
	for obj := it.Next(); obj != nil; obj = it.Next() {
		p := obj.(*Item)
		fmt.Printf("%d\n", p.Number)
	}
}

and this is output log. The log shows that numbers greater than 64 are not ordered correctly.
stdout.log

Thanks!

`StringFieldIndex` fails on types that are based on strings

If a custom string-based type is created:

type X string

then StringFieldIndex can successfully index it (by using reflect and calling String() on the value), but Search will not work, as the code in Search tries to convert value to string.

Ordered results

Is it possible to order/sort a transaction result?

Ideally able to order by multiple columns, ascending or descending.

I'm interested in partial results so it has to be at the go-memdb layer before the caller starts iterating over results.

Are there any benchmarks?

Hi. Maybe someone can share their performance benchmarks of go-memdb?

It is especially interesting to look at a comparison of go-memdb and other in-memory databases (not necessarily written in Go).

watchCtx() non-blocking after being triggered once

I have noticed that once a watchset was triggered, its watchCtx() method is not blocking anymore. I am not sure if this is by purpose or it is an actual issue. If this is by purpose, ignore my request. The following code snippet is (a bit simplified) the workaround to achieve the desired behavior. Every time the watchset was triggered, a new watchset is initialized.
`func main() {
// ..
go handle(ctx)
}

func handle(ctx context.Context) {
if ws, al, err := Watch(); err != nil {
// log
} else {

    for {
        // blocking call according to documentation
        if err = ws.WatchCtx(ctx); err != nil {
            fmt.Println("received cancel, exit loop")
            break
        } else {
            fmt.Println("received update")

            // reinit watcher to prevent being retriggered by the same event
            if ws, al, err = Watch(); err != nil {
                // log
                break
            } else {
                fmt.Println(al)
            }
        }
    }
}

}

func Watch() (ws memdb.WatchSet, al AccessList, err error) {
txn := db.Txn(false)

if wc, v, e := txn.FirstWatch(accessTable, idIndex, id); e != nil {
    err = e
} else if v == nil {
    err = memdb.ErrNotFound
} else {
    ws = memdb.NewWatchSet()
    ws.Add(wc)
    al = v.(AccessList)
}

return

}
`

JSONUnmarshal

Maybe it could be useful to unmarshal json object to memdb as if root object properties are "tables" and root properties values are arrays of records (objects). How do you think?
example json:

{
    "table1": [
        {"id": "1", "field1": "value1"},
        {"id": "2", "field1": "value2"}
    ]
}

`CompoundMultiIndex` returns duplicate entries with `SingleIndexer`s

I'm not 100% sure this (mis)behaviour can be attributed to the combination of CompoundMultiIndex and single indexers actually, but I have a repro case which looks simple enough that it's hard to find any other cause there.

&memdb.CompoundMultiIndex{
	Indexes: []memdb.Indexer{
		&memdb.StringFieldIndex{Field: "Address"},
		&memdb.StringFieldIndex{Field: "Version"},
	},
	AllowMissing: true,
}

when a single entry is inserted into a table with such an index:

txn.Insert("providers", &entry{
	Address: "aws",
	Version: "1.0.0",
})

and subsequently looked up (in a separate transaction)

txn.Get("providers", "provider")

then the same entry is returned twice:

&entry{Address:"aws", Version:"1.0.0"}
&entry{Address:"aws", Version:"1.0.0"}

I can confirm it is the exact same entry by comparing the pointer address, which consequently also makes such index impossible to use in DeleteAll where each individual entry would be looked up again via id index (as part of Delete) while iterating over results and (obviously) the second duplicate no longer exists once the first (original) entry is deleted, so DeleteAll then returns "not found" error.

go-memdb/txn.go

Lines 313 to 329 in 542a580

// Get the primary ID of the object
idSchema := tableSchema.Indexes[id]
idIndexer := idSchema.Indexer.(SingleIndexer)
ok, idVal, err := idIndexer.FromObject(obj)
if err != nil {
return fmt.Errorf("failed to build primary index: %v", err)
}
if !ok {
return fmt.Errorf("object missing primary index")
}
// Lookup the object by ID first, check fi we should continue
idTxn := txn.writableIndex(table, id)
existing, ok := idTxn.Get(idVal)
if !ok {
return ErrNotFound
}

Here is a full repro case:

It can cause panic while running test data with some special

I found the test code below can cause the panic of DB, is any wrong with the test code?

type ritem struct {
	Key   string
	Value []byte
}
	base := []byte{1, 0, 1, 0}
	key := append([]byte{}, base...)
	minKey := []byte{1, 0, 1}

	schema := &memdb.DBSchema{
		Tables: map[string]*memdb.TableSchema{
			"0": &memdb.TableSchema{
				Name: "0",
				Indexes: map[string]*memdb.IndexSchema{
					"id": &memdb.IndexSchema{
						Name:    "id",
						Unique:  true,
						Indexer: &memdb.StringFieldIndex{Field: "Key"},
					},
				},
			},
		},
	}
	mdb, err := memdb.NewMemDB(schema)
	assert.Nil(t, err)

	txn := mdb.Txn(true)
	txn.Insert("0", &ritem{Key: string(key), Value: []byte("1")})
	txn.Insert("0", &ritem{Key: string(append(key, byte(1))), Value: []byte("1")})
	txn.Commit()

	txn = mdb.Txn(false)
	defer txn.Abort()
	resIter, err := txn.LowerBound("0", "id", string(minKey))  // panic happened here
	assert.Nil(t, err)

How to vacuum old data?

On my project, memdb consume x10 memory that it really need. (old versions of rows).
I not found any way to configure vacum in library, its supported?

Watching all changes to a table including deletes

Is there a way to monitor all updates to a table including deletes?

I want to back-end updates to the table with event notifications. I've been attempting to do this using the channel returned from FirstWatch. I believe I have a fundamental misunderstanding of how this channel should be used. By the time I read anything off of this channel, from an update the channel is indicating it is closed.

What's memdb.WatchSet do?

Apologies for the noob question, but I've been trying to figure it out for the last 20 or so minutes. I'm noticing it being used all around Nomad and Consul codebases, but I'm not really seeing it be used for anything, other than creating the watchset and adding items to the set.

Is it sort of like a WaitGroup for synchronization? Or used to inform subscribers of changes? Or something else entirely? :-)

Bug in walkVals function expanding the possible values in a compoundMultiIndex

When inserting an entry into a table with a compound multi index with a few multi indexers the walkVals function tries to expand all the possible values for a given entry which has multiple string slices. There is a bug in the recursive algoritm. In the example there is 36 possible values for the criterias index with 12 each of the last values of 301, 302 and 303 but this is not the case when the values are expanded.

package main

import (
"fmt"
"github.com/hashicorp/go-memdb"
)

func main() {
// Create a sample struct
type LineItem struct {
Id int
CreativeType string
DeviceType []string
InventoryType []string
Partners []string
Dayparts []string
}

// Create the DB schema
schema := &memdb.DBSchema{
	Tables: map[string]*memdb.TableSchema{
		"lineItem": &memdb.TableSchema{
			Name: "lineItem",
			Indexes: map[string]*memdb.IndexSchema{
				"id": &memdb.IndexSchema{
					Name:    "id",
					Unique:  true,
					Indexer: &memdb.IntFieldIndex{Field: "Id"},
				},
				"criterias": &memdb.IndexSchema{
					Name:   "criterias",
					Unique: false,
					Indexer: &memdb.CompoundMultiIndex{
						Indexes: []memdb.Indexer{
							&memdb.StringFieldIndex{Field: "CreativeType"},
							&memdb.StringSliceFieldIndex{Field: "DeviceType"},
							&memdb.StringSliceFieldIndex{Field: "InventoryType"},
							&memdb.StringSliceFieldIndex{Field: "Partners"},
							&memdb.StringSliceFieldIndex{Field: "Dayparts"},
						},
					},
				},
			},
		},
	},
}

err := schema.Validate()
if err != nil {
	panic(err)
}

// Create a new data base
db, err := memdb.NewMemDB(schema)
if err != nil {
	panic(err)
}

// Create a write transaction
txn := db.Txn(true)

// Insert some people
li := []*LineItem{
	{
		Id:            1045,
		CreativeType:  "video",
		DeviceType:    []string{"tv", "desktop", "mobile"},
		InventoryType: []string{"web", "app"},
		Partners:      []string{"microsoft", "google"},
		Dayparts:      []string{"301", "302", "303"},
	},
}
for _, p := range li {
	fmt.Printf("%+v\n", p)
	if err := txn.Insert("lineItem", p); err != nil {
		panic(err)
	}
}

// Commit the transaction
txn.Commit()

// Create read-only transaction
txn = db.Txn(false)
defer txn.Abort()

// Lookup by email
raw, err := txn.First("lineItem", "id", 1045)
if err != nil {
	panic(err)
}

// Say hi!
fmt.Printf("Hello %d!\n", raw.(*LineItem).Id)

// List by criterias index
it, err := txn.Get("lineItem", "criterias", "video", "tv", "app", "microsoft", "303")
if err != nil {
	panic(err)
}

fmt.Print("Found:")
for obj := it.Next(); obj != nil; obj = it.Next() {
	p := obj.(*LineItem)
	fmt.Printf("  %v\n", p)
}

// What? Can't find it?
it, err = txn.Get("lineItem", "criterias", "video", "tv", "app", "microsoft", "301")
if err != nil {
	panic(err)
}

fmt.Print("Found:")
for obj := it.Next(); obj != nil; obj = it.Next() {
	p := obj.(*LineItem)
	fmt.Printf("  %v\n", p)
}

}

Can I store and search data in bytes?

I'm storing as bytes, but I can't search for bytes.

<Error index error: argument must be a string: []byte{0xc6, 0x1b, 0x9b, 0xb3, 0xa7, 0xa0, 0x76, 0x7e, 0x31, 0x79, 0x71, 0x3f, 0x3a, 0x5c, 0x7a, 0x9a, 0xed, 0xce, 0x19, 0x3c}

Multi index

It would be nice to be able to create multiple index entries for one object (e.g. by returning multiple values from FromObject()).

Example:

type Object struct {
    tags []string
}

If you want to have an index on the tags, that's not currently possible.

Would you be interested in a pull request for this?

IntFieldIndex LowerBound and ReverseLowerBound iterating incorrectly

When using large numbers in int field the following behavior is occuring

`

// Create a sample struct
type Person struct {
	Email string
	Name  string
	Age   int
}

// Create the DB schema
schema := &memdb.DBSchema{
	Tables: map[string]*memdb.TableSchema{
		"person": &memdb.TableSchema{
			Name: "person",
			Indexes: map[string]*memdb.IndexSchema{
				"id": &memdb.IndexSchema{
					Name:    "id",
					Unique:  true,
					Indexer: &memdb.StringFieldIndex{Field: "Email"},
				},
				"age": &memdb.IndexSchema{
					Name:    "age",
					Unique:  false,
					Indexer: &memdb.IntFieldIndex{Field: "Age"},
				},
			},
		},
	},
}

// Create a new data base
db, err := memdb.NewMemDB(schema)
if err != nil {
	panic(err)
}

// Create a write transaction
txn := db.Txn(true)

// Insert some people
people := []*Person{
	&Person{"[email protected]", "Joe", 30 * 10000000000},
	&Person{"[email protected]", "Lucy", 35* 10000000000},
	&Person{"[email protected]", "Tariq", 21* 10000000000},
	&Person{"[email protected]", "Dorothy", 53* 10000000000},
	&Person{"[email protected]", "Dorothy", 18* 10000000000},
}
for _, p := range people {
	if err := txn.Insert("person", p); err != nil {
		panic(err)
	}
}

// Commit the transaction
txn.Commit()

// Create read-only transaction
txn = db.Txn(false)
defer txn.Abort()

// Range scan over people with ages between 25 and 35 inclusive
it, err := txn.ReverseLowerBound("person", "age", 29 * 10000000000)
if err != nil {
	panic(err)
}

fmt.Println("People aged 25 - 35:")
for obj := it.Next(); obj != nil; obj = it.Next() {
	p := obj.(*Person)
	fmt.Printf("  %s is aged %d\n", p.Name, p.Age)
}

`

People aged 25 - 35:
Dorothy is aged 530000000000
Lucy is aged 350000000000
Dorothy is aged 180000000000

If we will remove * 10000000000 from the code we will get the following ouptut

People aged 25 - 35:
Tariq is aged 21
Dorothy is aged 18

Which is correct

Map[string]interface{} instead of structs.

I am just curious is that a good idea to have the support of Map[string]interface{} for Insert instead of a struct? I want to build fully configurable in-memory storage and statically typed structs make this impossible.
Thanks.

Watch improvements for many nodes

This is a follow-up of hashicorp/consul#4984

Recap

memdb provides a WatchSet.AddWithLimit(limit, nodeCh, fallbackNodeCh) feature that falls back to a higher (in the tree hierarchy) node if > limit nodes are watched. This mechanism bounds the number of goroutines used to watch a set of nodes.
Consul sets this limit to 2048 currently on master. When watching service nodes fore example the fallback is the root of all nodes. As described in the linked issue switching to this fallback greatly decreases performance as the root node constantly changes.
We'd like to increase this limit while still keeping the number of G under control.

Proposition 1

aFew is currently set to 32. We could selectively use a bigger select{} based on the number of channels to watch. My very early benchmarks show that performance is decent with aFew up to 128, it decreases rapidly after that.
This allows to cut the number by ~4, however it doesn't scale well.

Proposition 2

This is untested/unbenchmarked yet.
Currently each radix node has a ch that gets closed when a change occurs. WatchSet.Watch() blocks on these chs.
We could reverse this mechanism by having a slice of chs in each node. WatchSet would have a single ch, add it to each watched node on Add() and then block on this single ch on Watch(). On change, each of the node chs would be closed.
While being intrusive, this would allow to watch many many nodes with no additional G. Note that the two mechanisms could cohabit during the transition with the nodes holding both their current WatchCh and a slice, and two WatchSet implementations.

What do you think ?

/cc @banks @pierresouchay

How can I store nested Data?

id: 1
company: xyz
employes:

I have above structure of incoming data. I have 2 struts to store company info and employee info. So basically I have belo field in strut company

type Company strut {
Id string
Employees []Employee
}

For above structure I wonder how do I insert employee information

How to perform searching in database by multiple fields if one of them is optional?

Hello there. Currently, I'm implementing a lookup mechanism to search data in an in-memory database. But I bumped into a problem to perform searching by several fields. Let's say I have the following structure stored in a database:

type Person struct {
   FirstName         string
   SecondName    string
   LastName         string
}

And I would like to search people by either first name or second name or last name or use them together. Compound indexes don't work for this case since I can search let's say only by first name and other search criteria will be empty. Also I can't create separate index for each field since go-mem doesn't support the search by several indexes. Do you guys know any workarounds or how can I perform searching by several fields?

In-place object update doesn't delete old index values

If you you are trying to in-place update (via txn.Insert) already inserted object, the old no longer relevant values are not deleted from index.

I'm not sure is it bug or known implementation feature. Here is the test to reproduce:

func TestTxn_InsertUpdate_Inplace(t *testing.T) {
	db := testDB(t)
	txn := db.Txn(true)

	oldV := "abc"
	newV := "xyz"

	// Create object
	obj := &TestObject{
		ID:  "my-object",
		Foo: oldV,
		Qux: []string{"abc1", "abc2"},
	}
	err := txn.Insert("main", obj)
	if err != nil {
		t.Fatalf("err: %v", err)
	}

	// Insert it
	raw, err := txn.First("main", "foo", obj.Foo)
	if err != nil {
		t.Fatalf("err: %v", err)
	}

	if raw != obj {
		t.Fatalf("bad: %#v %#v", raw, obj)
	}

	// Update it in-place
	obj.Foo = newV

	// Trying to reindex object
	err = txn.Insert("main", obj)
	if err != nil {
		t.Fatalf("err: %v", err)
	}

	// Lookup of the new value
	raw, err = txn.First("main", "foo", newV)
	if err != nil {
		t.Fatalf("err: %v", err)
	}

	if raw != obj {
		t.Fatalf("bad: %#v %#v", raw, obj)
	}

	// Lookup of the old value. Should fail, but it does not
	raw, err = txn.First("main", "foo", oldV)
	if err != nil {
		t.Fatalf("err: %v", err)
	}

	if raw != nil {
		t.Fatalf("bad: %#v", raw)
	}
}

The reason for this behavior is that you you calculate existing index values (line 243 in snippet below) from indexed object (which was updated), so you always get valExist equals to val[i] and never delete the truly old existing value from index.

go-memdb/txn.go

Lines 234 to 268 in ac8c839

if update {
var (
okExist bool
valsExist [][]byte
err error
)
switch indexer := indexSchema.Indexer.(type) {
case SingleIndexer:
var valExist []byte
okExist, valExist, err = indexer.FromObject(existing)
valsExist = [][]byte{valExist}
case MultiIndexer:
okExist, valsExist, err = indexer.FromObject(existing)
}
if err != nil {
return fmt.Errorf("failed to build index '%s': %v", name, err)
}
if okExist {
for i, valExist := range valsExist {
// Handle non-unique index by computing a unique index.
// This is done by appending the primary key which must
// be unique anyways.
if !indexSchema.Unique {
valExist = append(valExist, idVal...)
}
// If we are writing to the same index with the same value,
// we can avoid the delete as the insert will overwrite the
// value anyways.
if i >= len(vals) || !bytes.Equal(valExist, vals[i]) {
indexTxn.Delete(valExist)
}
}
}
}

Documentation examples and use cases for watch channels

I need to track changes made so that I know which item is newly created or only updated.

There's no documented examples on how to do this with watch channels and I can't figure it out.

For now, I'm using txn.TrackChanges() instead so my problem is solved but it should be possible to do this using the watch channels, right?

Boolean indexer

I needed to index on a boolean field (or rather, I needed a boolean as part of a compound index) so I created a BoolFieldIndex for that.

If there is any interest, I'd be happy to create a PR that adds this index.

If there was already a good way to index on a boolean field that I've overlooked, I'd like to hear about it so I can delete my own code and use the pre-existing solution instead.

Do you have a design document?

I'm curious about the implementation of index and mvcc.
But the source code is a little hard to understand for me.
Thanks for your awesome project!

CompoundMultiIndex::FromObject will generate only one combination

Given the following code

package main

import (
	"fmt"

	"github.com/hashicorp/go-memdb"
)

type Object struct {
	Field1 string
	Field2 []string
}

func main() {
	cmi := &memdb.CompoundMultiIndex{
		Indexes: []memdb.Indexer{
			&memdb.StringFieldIndex{Field: "Field1"},
			&memdb.StringSliceFieldIndex{Field: "Field2"},
		},
	}

	_, out, _ := cmi.FromObject(Object{"a", []string{"b", "c"}})
	for _, item := range out {
		fmt.Println(string(item))
	}
}

The expected output would be:

ab
ac

The actual result is:

ac
ac

Looking at the current code when can see from line 768 of index.go:

	var walkVals func([]byte, int)
	walkVals = func(currPrefix []byte, depth int) {
		if depth == len(builder)-1 {
			// These are the "leaves", so append directly
			for _, v := range builder[depth] {
				out = append(out, append(currPrefix, v...))
			}
			return
		}
		for _, v := range builder[depth] {
			nextPrefix := append(currPrefix, v...)
			if c.AllowMissing {
				out = append(out, nextPrefix)
			}
			walkVals(nextPrefix, depth+1)
		}
	}

The problem is that with each new iteration of line 773 out = append(out, append(currPrefix, v...)), previous values are overwritten.

Possible fix could be:

	var walkVals func([]byte, int)
	walkVals = func(currPrefix []byte, depth int) {
		if depth == len(builder)-1 {
			// These are the "leaves", so append directly
			for _, v := range builder[depth] {
				outcome := make([]byte, len(currPrefix))
				copy(outcome, currPrefix)
				out = append(out, append(outcome, v...))
			}
			return
		}
...

Using nested fields for indexes.

Hi there. I see that PR #62 hasn't been merged yet. Do you know guys other workarounds to add indexes for nested fields?
Let's say I have approximately the following structure:

type MyStruct struct {
   ID int
   External ExternalDependency
   YetAnotherDependency []AnotherDependency 
}

type ExternalDependency struct {
   ExternalID string
}

type AnotherDependency struct {
  CustomID string
}

How to add indexes for ExternalID and CustomID?

Syncronize data without reload

Is it possible to synchronize data without reloading the tree? We want realtime synchronization with external data without stopping and reloading the data tree.

index out of range panic with UintFieldIndex

When I index a uint16 field with &memdb.UintFieldIndex{Field: "myfield"}, I would expect to be allowed to have values up to 2^16-1 (65535) but it panics when the value is above 16383 (0x3fff).

Here is a stack with 65534:


panic: runtime error: index out of range

goroutine 1 [running]:
panic(0x505040, 0xc82000a1a0)
	/usr/lib/go-1.6/src/runtime/panic.go:481 +0x3e6
encoding/binary.PutUvarint(0xc82000a348, 0x2, 0x2, 0xfffe, 0x2)
	/usr/lib/go-1.6/src/encoding/binary/varint.go:48 +0x69
github.com/hashicorp/go-memdb.(*UintFieldIndex).FromObject(0xc820096220, 0x4ce200, 0xc8200924c0, 0xc8200c9a88, 0x0, 0x0, 0x0, 0x0, 0x0)
	$GOPATH/src/github.com/hashicorp/go-memdb/index.go:279 +0x5a7
github.com/hashicorp/go-memdb.(*Txn).Insert(0xc820092540, 0x532eb0, 0x8, 0x4ce200, 0xc8200924c0, 0x0, 0x0)
	$GOPATH/src/github.com/hashicorp/go-memdb/txn.go:193 +0x76c

...

the culprit is:


	// Get the value and encode it
	val := fv.Uint()
	buf := make([]byte, size)
	binary.PutUvarint(buf, val)

in my case, size = 2 and binary.PutUvarint() panics

Is it possible to do range iterations ?

Hi,

I was wondering if it's possible to do range iterations in go-memdb.
If you were using this as an in-memory database it should be a fairly common operation I'm assuming.

For example ranging over all keys starting with "a" until "c". The only option I see is a prefix based query or an exact match.
How hard would it be to extend this to allow range queries ?

Different behavior of txn.Insert

schema := &DBSchema{
	Tables: map[string]*TableSchema{
		"main": {
			Name: "main",
			Indexes: map[string]*IndexSchema{
				"id": {
					Name:    "id",
					Unique:  true,
					Indexer: &StringFieldIndex{Field: "ID"},
				},
				"foo": {
					Name:    "foo",
					Indexer: &StringFieldIndex{Field: "Foo"},
				},
			},
		},
	},
}
db, err := NewMemDB(schema)
assertNilError(t, err)

key := "aaaa"
txn := db.Txn(true)
testObj := &TestObject{ID: "1", Foo: key}
assertNilError(t, txn.Insert("main", testObj))
txn.Commit()

txn = db.Txn(false)
value, err := txn.First("main", "id", "1")
assertNilError(t, err)
obj := value.(*TestObject)
if obj.Foo != "aaaa" {
	t.Fatalf("obj.Foo %#v", obj)
}

newTxn := db.Txn(true)
testObj.Foo = "bbbb"
assertNilError(t, newTxn.Insert("main", testObj))
newTxn.Commit()

value, err = txn.First("main", "id", "1")
assertNilError(t, err)
obj = value.(*TestObject)
if obj.Foo != "aaaa" {
	t.Fatalf("obj.Foo %#v", obj)
}

When running the above test case, it will report an error.

schema := &DBSchema{
	Tables: map[string]*TableSchema{
		"main": {
			Name: "main",
			Indexes: map[string]*IndexSchema{
				"id": {
					Name:    "id",
					Unique:  true,
					Indexer: &StringFieldIndex{Field: "ID"},
				},
				"foo": {
					Name:    "foo",
					Indexer: &StringFieldIndex{Field: "Foo"},
				},
			},
		},
	},
}
db, err := NewMemDB(schema)
assertNilError(t, err)

key := "aaaa"
txn := db.Txn(true)
assertNilError(t, txn.Insert("main", &TestObject{ID: "1", Foo: key}))
txn.Commit()

txn = db.Txn(false)
value, err := txn.First("main", "id", "1")
assertNilError(t, err)
obj := value.(*TestObject)
if obj.Foo != "aaaa" {
	t.Fatalf("obj.Foo %#v", obj)
}

newTxn := db.Txn(true)
assertNilError(t, newTxn.Insert("main", &TestObject{ID: "1", Foo: "bbbb"}))
newTxn.Commit()

value, err = txn.First("main", "id", "1")
assertNilError(t, err)
obj = value.(*TestObject)
if obj.Foo != "aaaa" {
	t.Fatalf("obj.Foo %#v", obj)
}

The above test case was run correctly.

Problem with LowerBound after modify a value

I'm having problems when I do the following steps:

  1. Get an object using First
  2. Modify a field of this object and Insert it again
  3. Run the LowerBound function in the object table (hoping that the modified object does not appear)
  4. The resulting iterator retrieve the object

I don't know if I'm doing something wrong or if this is expected behavior.
Please, help!

Example:

package main

import (
	"fmt"

	"github.com/hashicorp/go-memdb"
)

func main() {
	// Create a sample struct
	type Person struct {
		Email string
		Name  string
		Age   int
	}

	// Create the DB schema
	schema := &memdb.DBSchema{
		Tables: map[string]*memdb.TableSchema{
			"person": &memdb.TableSchema{
				Name: "person",
				Indexes: map[string]*memdb.IndexSchema{
					"id": &memdb.IndexSchema{
						Name:    "id",
						Unique:  true,
						Indexer: &memdb.StringFieldIndex{Field: "Email"},
					},
					"age": &memdb.IndexSchema{
						Name:    "age",
						Unique:  false,
						Indexer: &memdb.IntFieldIndex{Field: "Age"},
					},
				},
			},
		},
	}

	// Create a new data base
	db, err := memdb.NewMemDB(schema)
	if err != nil {
		panic(err)
	}

	// Create a write transaction
	txn := db.Txn(true)

	// Insert some people
	people := []*Person{
		&Person{"[email protected]", "Joe", 30},
		&Person{"[email protected]", "Lucy", 35},
		&Person{"[email protected]", "Tariq", 21},
		&Person{"[email protected]", "Dorothy", 53},
	}
	for _, p := range people {
		if err := txn.Insert("person", p); err != nil {
			panic(err)
		}
	}

	// Commit the transaction
	txn.Commit()

	// Create read-only transaction
	txn = db.Txn(false)

	// Lookup by email
	raw, err := txn.First("person", "id", "[email protected]")
	if err != nil {
		panic(err)
	}
	txn.Abort()

	// Create a write transaction
	txn = db.Txn(true)

	var first *Person
	first = raw.(*Person)

	// Modify Age field
	first.Age = 10

	// Update object
	if err := txn.Insert("person", first); err != nil {
		panic(err)
	}

	// Commit the transaction
	txn.Commit()

	txn = db.Txn(false)
	defer txn.Abort()

	// Range scan over people with ages between 25 and 35 inclusive
	it, err := txn.LowerBound("person", "age", 25)
	if err != nil {
		panic(err)
	}

	fmt.Println("People aged 25 - 35:")
	for obj := it.Next(); obj != nil; obj = it.Next() {
		p := obj.(*Person)
		if p.Age > 35 {
			break
		}
		fmt.Printf("  %s is aged %d\n", p.Name, p.Age)
	}
	// Result:
	// Hello Joe!
	// People aged 25 - 35:
	//   Joe is aged 10
	//   Lucy is aged 35

	// Expected:
	// Hello Joe!
	// People aged 25 - 35:
	//   Lucy is aged 35
}

Notify channels close early during a commit

Looking at Commit() I realized that we will fire the change notifications before we've finished committing other sub-transactions and the root transaction. This could cause other code to wake up and read the old state back if they do it quickly enough. We should modify go-immutable-radix to not notify on commit by default, and call it separately after we've done atomic.StorePointer(&txn.db.root, unsafe.Pointer(newRoot)).

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.