aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBen Johnson <benbjohnson@yahoo.com>2014-06-30 08:01:41 -0600
committerBen Johnson <benbjohnson@yahoo.com>2014-06-30 08:01:41 -0600
commitdef455554b5607ec6ccd0af51d0dea5401003e93 (patch)
tree3c866e1b594f37ae317218b3ba94965592ae8646
parentMerge pull request #214 from Shopify/fix_stats_sub (diff)
downloaddedo-def455554b5607ec6ccd0af51d0dea5401003e93.tar.gz
dedo-def455554b5607ec6ccd0af51d0dea5401003e93.tar.xz
Add freelist cache.
This commit adds a cache to the freelist which combines the available free pages and pending free pages in a single map. This was added to improve performance where freelist.isFree() was consuming 70% of CPU time for large freelists.
-rw-r--r--db.go2
-rw-r--r--db_test.go2
-rw-r--r--freelist.go96
-rw-r--r--freelist_test.go10
-rw-r--r--tx.go2
5 files changed, 67 insertions, 45 deletions
diff --git a/db.go b/db.go
index 6ef35ea..4d7ec12 100644
--- a/db.go
+++ b/db.go
@@ -144,7 +144,7 @@ func Open(path string, mode os.FileMode, options *Options) (*DB, error) {
}
// Read in the freelist.
- db.freelist = &freelist{pending: make(map[txid][]pgid)}
+ db.freelist = newFreelist()
db.freelist.read(db.page(db.meta().freelist))
// Mark the database as opened and return.
diff --git a/db_test.go b/db_test.go
index e689836..74ffcb9 100644
--- a/db_test.go
+++ b/db_test.go
@@ -418,7 +418,7 @@ func TestDB_DoubleFree(t *testing.T) {
})
}()
- assert.Equal(t, "tx 2: page 3 already freed in tx 0", msg)
+ assert.Equal(t, "assertion failed: page 3 already freed", msg)
}
func ExampleDB_Update() {
diff --git a/freelist.go b/freelist.go
index 66bc06f..27aea6a 100644
--- a/freelist.go
+++ b/freelist.go
@@ -1,7 +1,6 @@
package bolt
import (
- "fmt"
"sort"
"unsafe"
)
@@ -9,8 +8,17 @@ import (
// freelist represents a list of all pages that are available for allocation.
// It also tracks pages that have been freed but are still in use by open transactions.
type freelist struct {
- ids []pgid
- pending map[txid][]pgid
+ ids []pgid // all free and available free page ids.
+ pending map[txid][]pgid // mapping of soon-to-be free page ids by tx.
+ cache map[pgid]bool // fast lookup of all free and pending page ids.
+}
+
+// newFreelist returns an empty, initialized freelist.
+func newFreelist() *freelist {
+ return &freelist{
+ pending: make(map[txid][]pgid),
+ cache: make(map[pgid]bool),
+ }
}
// size returns the size of the page after serialization.
@@ -78,6 +86,12 @@ func (f *freelist) allocate(n int) pgid {
copy(f.ids[i-n+1:], f.ids[i+1:])
f.ids = f.ids[:len(f.ids)-n]
}
+
+ // Remove from the free cache.
+ for i := pgid(0); i < pgid(n); i++ {
+ delete(f.cache, initial+i)
+ }
+
return initial
}
@@ -91,25 +105,15 @@ func (f *freelist) allocate(n int) pgid {
func (f *freelist) free(txid txid, p *page) {
_assert(p.id > 1, "cannot free page 0 or 1: %d", p.id)
- // Verify that page is not already free.
- minid, maxid := p.id, p.id+pgid(p.overflow)
- for _, id := range f.ids {
- if id >= minid && id <= maxid {
- panic(fmt.Sprintf("page %d already freed in tx", id))
- }
- }
- for ptxid, m := range f.pending {
- for _, id := range m {
- if id >= minid && id <= maxid {
- panic(fmt.Sprintf("tx %d: page %d already freed in tx %d", txid, id, ptxid))
- }
- }
- }
-
// Free page and all its overflow pages.
var ids = f.pending[txid]
- for i := 0; i < int(p.overflow+1); i++ {
- ids = append(ids, p.id+pgid(i))
+ for id := p.id; id <= p.id+pgid(p.overflow); id++ {
+ // Verify that page is not already free.
+ _assert(!f.cache[id], "page %d already freed", id)
+
+ // Add to the freelist and cache.
+ ids = append(ids, id)
+ f.cache[id] = true
}
f.pending[txid] = ids
}
@@ -118,6 +122,8 @@ func (f *freelist) free(txid txid, p *page) {
func (f *freelist) release(txid txid) {
for tid, ids := range f.pending {
if tid <= txid {
+ // Move transaction's pending pages to the available freelist.
+ // Don't remove from the cache since the page is still free.
f.ids = append(f.ids, ids...)
delete(f.pending, tid)
}
@@ -127,24 +133,18 @@ func (f *freelist) release(txid txid) {
// rollback removes the pages from a given pending tx.
func (f *freelist) rollback(txid txid) {
+ // Remove page ids from cache.
+ for _, id := range f.pending[txid] {
+ delete(f.cache, id)
+ }
+
+ // Remove pages from pending list.
delete(f.pending, txid)
}
-// isFree returns whether a given page is in the free list.
-func (f *freelist) isFree(pgid pgid) bool {
- for _, id := range f.ids {
- if id == pgid {
- return true
- }
- }
- for _, m := range f.pending {
- for _, id := range m {
- if id == pgid {
- return true
- }
- }
- }
- return false
+// freed returns whether a given page is in the free list.
+func (f *freelist) freed(pgid pgid) bool {
+ return f.cache[pgid]
}
// read initializes the freelist from a freelist page.
@@ -153,6 +153,7 @@ func (f *freelist) read(p *page) {
f.ids = make([]pgid, len(ids))
copy(f.ids, ids)
sort.Sort(pgids(f.ids))
+ f.buildcache()
}
// write writes the page ids onto a freelist page. All free and pending ids are
@@ -179,15 +180,36 @@ func (f *freelist) write(p *page) error {
func (f *freelist) reload(p *page) {
f.read(p)
- // Filter out pending free pages.
+ // We need to filter out the pending pages from the available freelist
+ // so we rebuild the cache without the newly read freelist.
ids := f.ids
f.ids = nil
+ f.buildcache()
+ // Check each page in the freelist and build a new available freelist
+ // with any pages not in the pending lists.
var a []pgid
for _, id := range ids {
- if !f.isFree(id) {
+ if !f.freed(id) {
a = append(a, id)
}
}
f.ids = a
+
+ // Once the available list is rebuilt then rebuild the free cache so that
+ // it includes the available and pending free pages.
+ f.buildcache()
+}
+
+// buildcache rebuilds the free cache based on available and pending free lists.
+func (f *freelist) buildcache() {
+ f.cache = make(map[pgid]bool)
+ for _, id := range f.ids {
+ f.cache[id] = true
+ }
+ for _, pendingIDs := range f.pending {
+ for _, pendingID := range pendingIDs {
+ f.cache[pendingID] = true
+ }
+ }
}
diff --git a/freelist_test.go b/freelist_test.go
index 5948f3b..24ce0f6 100644
--- a/freelist_test.go
+++ b/freelist_test.go
@@ -9,21 +9,21 @@ import (
// Ensure that a page is added to a transaction's freelist.
func TestFreelist_free(t *testing.T) {
- f := &freelist{pending: make(map[txid][]pgid)}
+ f := newFreelist()
f.free(100, &page{id: 12})
assert.Equal(t, f.pending[100], []pgid{12})
}
// Ensure that a page and its overflow is added to a transaction's freelist.
func TestFreelist_free_overflow(t *testing.T) {
- f := &freelist{pending: make(map[txid][]pgid)}
+ f := newFreelist()
f.free(100, &page{id: 12, overflow: 3})
assert.Equal(t, f.pending[100], []pgid{12, 13, 14, 15})
}
// Ensure that a transaction's free pages can be released.
func TestFreelist_release(t *testing.T) {
- f := &freelist{pending: make(map[txid][]pgid)}
+ f := newFreelist()
f.free(100, &page{id: 12, overflow: 1})
f.free(100, &page{id: 9})
f.free(102, &page{id: 39})
@@ -64,7 +64,7 @@ func TestFreelist_read(t *testing.T) {
ids[1] = 50
// Deserialize page into a freelist.
- f := &freelist{pending: make(map[txid][]pgid)}
+ f := newFreelist()
f.read(page)
// Ensure that there are two page ids in the freelist.
@@ -84,7 +84,7 @@ func TestFreelist_write(t *testing.T) {
f.write(p)
// Read the page back out.
- f2 := &freelist{pending: make(map[txid][]pgid)}
+ f2 := newFreelist()
f2.read(p)
// Ensure that the freelist is correct.
diff --git a/tx.go b/tx.go
index d8ffc08..5eada65 100644
--- a/tx.go
+++ b/tx.go
@@ -496,7 +496,7 @@ func (tx *Tx) Page(id int) (*PageInfo, error) {
}
// Determine the type (or if it's free).
- if tx.db.freelist.isFree(pgid(id)) {
+ if tx.db.freelist.freed(pgid(id)) {
info.Type = "free"
} else {
info.Type = p.typ()