diff --git a/services/syncbase/server/app.go b/services/syncbase/server/app.go
new file mode 100644
index 0000000..c1c6dcd
--- /dev/null
+++ b/services/syncbase/server/app.go
@@ -0,0 +1,214 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package server
+
+import (
+	"sync"
+
+	wire "v.io/syncbase/v23/services/syncbase"
+	"v.io/syncbase/x/ref/services/syncbase/server/nosql"
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
+	"v.io/syncbase/x/ref/services/syncbase/store"
+	"v.io/v23/context"
+	"v.io/v23/rpc"
+	"v.io/v23/security/access"
+	"v.io/v23/verror"
+)
+
+type app struct {
+	name string
+	s    *service
+	// The fields below are initialized iff this app exists.
+	// Guards the fields below. Held during database Create, Delete, and
+	// SetPermissions.
+	mu  sync.Mutex
+	dbs map[string]util.Database
+}
+
+var (
+	_ wire.AppServerMethods = (*app)(nil)
+	_ util.App              = (*app)(nil)
+	_ util.Layer            = (*app)(nil)
+)
+
+////////////////////////////////////////
+// RPC methods
+
+// TODO(sadovsky): Require the app name to match the client's blessing name.
+// I.e. reserve names at the app level of the hierarchy.
+func (a *app) Create(ctx *context.T, call rpc.ServerCall, perms access.Permissions) error {
+	// This app does not yet exist; a is just an ephemeral handle that holds
+	// {name string, s *service}. a.s.createApp will create a new app handle and
+	// store it in a.s.apps[a.name].
+	return a.s.createApp(ctx, call, a.name, perms)
+}
+
+func (a *app) Delete(ctx *context.T, call rpc.ServerCall) error {
+	return a.s.deleteApp(ctx, call, a.name)
+}
+
+func (a *app) SetPermissions(ctx *context.T, call rpc.ServerCall, perms access.Permissions, version string) error {
+	return a.s.setAppPerms(ctx, call, a.name, perms, version)
+}
+
+func (a *app) GetPermissions(ctx *context.T, call rpc.ServerCall) (perms access.Permissions, version string, err error) {
+	data := &appData{}
+	if err := util.Get(ctx, call, a.s.st, a, data); err != nil {
+		return nil, "", err
+	}
+	return data.Perms, util.FormatVersion(data.Version), nil
+}
+
+// TODO(sadovsky): Implement Glob.
+
+////////////////////////////////////////
+// util.App methods
+
+func (a *app) NoSQLDatabase(ctx *context.T, call rpc.ServerCall, dbName string) (util.Database, error) {
+	// TODO(sadovsky): Record storage engine config (e.g. LevelDB directory) in
+	// dbInfo, and add API for opening and closing storage engines.
+	a.mu.Lock()
+	defer a.mu.Unlock()
+	d, ok := a.dbs[dbName]
+	if !ok {
+		return nil, verror.New(verror.ErrNoExistOrNoAccess, ctx, dbName)
+	}
+	return d, nil
+}
+
+func (a *app) CreateNoSQLDatabase(ctx *context.T, call rpc.ServerCall, dbName string, perms access.Permissions) error {
+	// TODO(sadovsky): Crash if any step fails, and use WAL to ensure that if we
+	// crash, upon restart we execute any remaining steps before we start handling
+	// client requests.
+	//
+	// Steps:
+	// 1. Check appData perms, create dbInfo record.
+	// 2. Initialize database.
+	// 3. Flip dbInfo.Initialized to true. <===== CHANGE BECOMES VISIBLE
+	a.mu.Lock()
+	defer a.mu.Unlock()
+	if _, ok := a.dbs[dbName]; ok {
+		// TODO(sadovsky): Should this be ErrExistOrNoAccess, for privacy?
+		return verror.New(verror.ErrExist, ctx, dbName)
+	}
+
+	// 1. Check appData perms, create dbInfo record.
+	aData := &appData{}
+	if err := store.RunInTransaction(a.s.st, func(st store.StoreReadWriter) error {
+		// Check appData perms.
+		if err := util.Get(ctx, call, st, a, aData); err != nil {
+			return err
+		}
+		// Check for "database already exists".
+		if _, err := a.getDbInfo(ctx, call, st, dbName); verror.ErrorID(err) != verror.ErrNoExistOrNoAccess.ID {
+			if err != nil {
+				return err
+			}
+			// TODO(sadovsky): Should this be ErrExistOrNoAccess, for privacy?
+			return verror.New(verror.ErrExist, ctx, dbName)
+		}
+		// Write new dbInfo.
+		info := &dbInfo{
+			Name: dbName,
+		}
+		return a.putDbInfo(ctx, call, st, dbName, info)
+	}); err != nil {
+		return err
+	}
+
+	// 2. Initialize database.
+	if perms == nil {
+		perms = aData.Perms
+	}
+	d, err := nosql.NewDatabase(ctx, call, a, dbName, perms)
+	if err != nil {
+		return err
+	}
+
+	// 3. Flip dbInfo.Initialized to true.
+	if err := store.RunInTransaction(a.s.st, func(st store.StoreReadWriter) error {
+		return a.updateDbInfo(ctx, call, st, dbName, func(info *dbInfo) error {
+			info.Initialized = true
+			return nil
+		})
+	}); err != nil {
+		return err
+	}
+
+	a.dbs[dbName] = d
+	return nil
+}
+
+func (a *app) DeleteNoSQLDatabase(ctx *context.T, call rpc.ServerCall, dbName string) error {
+	// TODO(sadovsky): Crash if any step fails, and use WAL to ensure that if we
+	// crash, upon restart we execute any remaining steps before we start handling
+	// client requests.
+	//
+	// Steps:
+	// 1. Check databaseData perms.
+	// 2. Flip dbInfo.Deleted to true. <===== CHANGE BECOMES VISIBLE
+	// 3. Delete database.
+	// 4. Delete dbInfo record.
+	a.mu.Lock()
+	defer a.mu.Unlock()
+	d, ok := a.dbs[dbName]
+	if !ok {
+		return verror.New(verror.ErrNoExistOrNoAccess, ctx, dbName)
+	}
+
+	// 1. Check databaseData perms.
+	if err := d.CheckPermsInternal(ctx, call); err != nil {
+		return err
+	}
+
+	// 2. Flip dbInfo.Deleted to true.
+	if err := store.RunInTransaction(a.s.st, func(st store.StoreReadWriter) error {
+		return a.updateDbInfo(ctx, call, st, dbName, func(info *dbInfo) error {
+			info.Deleted = true
+			return nil
+		})
+	}); err != nil {
+		return err
+	}
+
+	// 3. Delete database.
+	// TODO(sadovsky): Actually delete the database.
+
+	// 4. Delete dbInfo record.
+	if err := a.delDbInfo(ctx, call, a.s.st, dbName); err != nil {
+		return err
+	}
+
+	delete(a.dbs, dbName)
+	return nil
+}
+
+func (a *app) SetDatabasePerms(ctx *context.T, call rpc.ServerCall, dbName string, perms access.Permissions, version string) error {
+	a.mu.Lock()
+	defer a.mu.Unlock()
+	d, ok := a.dbs[dbName]
+	if !ok {
+		return verror.New(verror.ErrNoExistOrNoAccess, ctx, dbName)
+	}
+	return d.SetPermsInternal(ctx, call, perms, version)
+}
+
+////////////////////////////////////////
+// util.Layer methods
+
+func (a *app) Name() string {
+	return a.name
+}
+
+func (a *app) StKey() string {
+	return util.JoinKeyParts(util.AppPrefix, a.stKeyPart())
+}
+
+////////////////////////////////////////
+// Internal helpers
+
+func (a *app) stKeyPart() string {
+	return a.name
+}
diff --git a/services/syncbase/server/database.go b/services/syncbase/server/database.go
deleted file mode 100644
index 4328caa..0000000
--- a/services/syncbase/server/database.go
+++ /dev/null
@@ -1,204 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build ignore
-
-package server
-
-import (
-	"v.io/syncbase/v23/services/syncbase"
-	"v.io/syncbase/x/ref/services/syncbase/store"
-	"v.io/v23/rpc"
-	"v.io/v23/security/access"
-	"v.io/v23/verror"
-)
-
-// TODO(sadovsky): Decide whether to use the same version-aware data layout that
-// we use for Items. Relatedly, decide whether the Database Permissions should get
-// synced. (If so, that suggests we should indeed use the same version-aware
-// data layout here, and perhaps everywhere.)
-
-type database struct {
-	name string
-	u    *universe
-}
-
-var _ syncbase.DatabaseServerMethods = (*database)(nil)
-
-func (d *database) Create(call rpc.ServerCall, acl access.Permissions) error {
-	return store.RunInTransaction(d.u.s.st, func(st store.Store) error {
-		// Update universeData.
-		var uData *universeData
-		if err := d.u.update(call, st, true, func(data *universeData) error {
-			if _, ok := data.Databases[d.name]; ok {
-				return verror.New(verror.ErrExist, call.Context(), d.name)
-			}
-			// https://github.com/veyron/release-issues/issues/1145
-			if data.Databases == nil {
-				data.Databases = map[string]struct{}{}
-			}
-			data.Databases[d.name] = struct{}{}
-			uData = data
-			return nil
-		}); err != nil {
-			return err
-		}
-
-		// Blind-write databaseData.
-		if acl == nil {
-			acl = uData.Permissions
-		}
-		data := &databaseData{
-			Name:        d.name,
-			Permissions: acl,
-		}
-		return d.put(call, st, data)
-	})
-}
-
-func (d *database) Delete(call rpc.ServerCall) error {
-	return store.RunInTransaction(d.u.s.st, func(st store.Store) error {
-		// Read-check-delete databaseData.
-		if _, err := d.get(call, st, true); err != nil {
-			return err
-		}
-		// TODO(sadovsky): Delete all Tables (and Items) in this Database.
-		if err := d.del(call, st); err != nil {
-			return err
-		}
-
-		// Update universeData.
-		return d.u.update(call, st, false, func(data *universeData) error {
-			delete(data.Databases, d.name)
-			return nil
-		})
-	})
-}
-
-func (d *database) UpdateSchema(call rpc.ServerCall, schema syncbase.Schema, version string) error {
-	if schema == nil {
-		return verror.New(verror.ErrInternal, nil, "schema must be specified")
-	}
-
-	return store.RunInTransaction(d.u.s.st, func(st store.Store) error {
-		return d.update(call, st, true, func(data *databaseData) error {
-			if err := checkVersion(call, version, data.Version); err != nil {
-				return err
-			}
-			// TODO(sadovsky): Delete all Tables (and Items) that are no longer part
-			// of the schema.
-			data.Schema = schema
-			data.Version++
-			return nil
-		})
-	})
-}
-
-func (d *database) GetSchema(call rpc.ServerCall) (schema syncbase.Schema, version string, err error) {
-	data, err := d.get(call, d.u.s.st, true)
-	if err != nil {
-		return nil, "", err
-	}
-	return data.Schema, formatVersion(data.Version), nil
-}
-
-func (d *database) SetPermissions(call rpc.ServerCall, acl access.Permissions, version string) error {
-	return store.RunInTransaction(d.u.s.st, func(st store.Store) error {
-		return d.update(call, st, true, func(data *databaseData) error {
-			if err := checkVersion(call, version, data.Version); err != nil {
-				return err
-			}
-			data.Permissions = acl
-			data.Version++
-			return nil
-		})
-	})
-}
-
-func (d *database) GetPermissions(call rpc.ServerCall) (acl access.Permissions, version string, err error) {
-	data, err := d.get(call, d.u.s.st, true)
-	if err != nil {
-		return nil, "", err
-	}
-	return data.Permissions, formatVersion(data.Version), nil
-}
-
-// TODO(sadovsky): Implement Glob.
-
-////////////////////////////////////////
-// Internal helpers
-
-func (d *database) keyPart() string {
-	return joinKeyParts(d.u.keyPart(), d.name)
-}
-
-func (d *database) key() string {
-	return joinKeyParts("$database", d.keyPart())
-}
-
-// Note, the methods below use "x" as the receiver name to make find-replace
-// easier across the different levels of syncbase hierarchy.
-//
-// TODO(sadovsky): Is there any better way to share this code despite the lack
-// of generics?
-
-// Reads data from the storage engine.
-// Returns a VDL-compatible error.
-// checkAuth specifies whether to perform an authorization check.
-func (x *database) get(call rpc.ServerCall, st store.Store, checkAuth bool) (*databaseData, error) {
-	// TODO(kash): Get this to compile.
-	return nil, nil
-	// data := &databaseData{}
-	// if err := getObject(st, x.key(), data); err != nil {
-	// 	if _, ok := err.(*store.ErrUnknownKey); ok {
-	// 		// TODO(sadovsky): Return ErrNoExist if appropriate.
-	// 		return nil, verror.NewErrNoExistOrNoAccess(call.Context())
-	// 	}
-	// 	return nil, verror.New(verror.ErrInternal, call.Context(), err)
-	// }
-	// if checkAuth {
-	// 	auth, _ := access.PermissionsAuthorizer(data.Permissions, access.TypicalTagType())
-	// 	if err := auth.Authorize(call); err != nil {
-	// 		// TODO(sadovsky): Return ErrNoAccess if appropriate.
-	// 		return nil, verror.NewErrNoExistOrNoAccess(call.Context())
-	// 	}
-	// }
-	// return data, nil
-}
-
-// Writes data to the storage engine.
-// Returns a VDL-compatible error.
-// If you need to perform an authorization check, use update().
-func (x *database) put(call rpc.ServerCall, st store.Store, data *databaseData) error {
-	if err := putObject(st, x.key(), data); err != nil {
-		return verror.New(verror.ErrInternal, call.Context(), err)
-	}
-	return nil
-}
-
-// Deletes data from the storage engine.
-// Returns a VDL-compatible error.
-// If you need to perform an authorization check, call get() first.
-func (x *database) del(call rpc.ServerCall, st store.Store) error {
-	if err := st.Delete(x.key()); err != nil {
-		return verror.New(verror.ErrInternal, call.Context(), err)
-	}
-	return nil
-}
-
-// Updates data in the storage engine.
-// Returns a VDL-compatible error.
-// checkAuth specifies whether to perform an authorization check.
-// fn should perform the "modify" part of "read, modify, write", and should
-// return a VDL-compatible error.
-func (x *database) update(call rpc.ServerCall, st store.Store, checkAuth bool, fn func(data *databaseData) error) error {
-	data, err := x.get(call, st, checkAuth)
-	if err != nil {
-		return err
-	}
-	if err := fn(data); err != nil {
-		return err
-	}
-	return x.put(call, st, data)
-}
diff --git a/services/syncbase/server/db_info.go b/services/syncbase/server/db_info.go
new file mode 100644
index 0000000..6ccc664
--- /dev/null
+++ b/services/syncbase/server/db_info.go
@@ -0,0 +1,85 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package server
+
+// This file defines internal app methods for manipulating dbInfo.
+// None of these methods perform authorization checks.
+//
+// The fundamental reason why these methods are needed is that information about
+// a database is spread across two storage engines. The source of truth for the
+// existence of the database, as well as things like the database type, is the
+// service-level storage engine, while database permissions are tracked in the
+// database's storage engine.
+
+import (
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
+	"v.io/syncbase/x/ref/services/syncbase/store"
+	"v.io/v23/context"
+	"v.io/v23/rpc"
+)
+
+type dbInfoLayer struct {
+	name string
+	a    *app
+}
+
+var (
+	_ util.Layer = (*dbInfoLayer)(nil)
+)
+
+////////////////////////////////////////
+// dbInfoLayer util.Layer methods
+
+func (d *dbInfoLayer) Name() string {
+	return d.name
+}
+
+func (d *dbInfoLayer) StKey() string {
+	return util.JoinKeyParts(util.DbInfoPrefix, d.stKeyPart())
+}
+
+////////////////////////////////////////
+// Internal helpers
+
+func (d *dbInfoLayer) stKeyPart() string {
+	return util.JoinKeyParts(d.a.stKeyPart(), d.name)
+}
+
+// getDbInfo reads data from the storage engine.
+// Returns a VDL-compatible error.
+func (a *app) getDbInfo(ctx *context.T, call rpc.ServerCall, st store.StoreReader, dbName string) (*dbInfo, error) {
+	info := &dbInfo{}
+	if err := util.GetWithoutAuth(ctx, call, st, &dbInfoLayer{dbName, a}, info); err != nil {
+		return nil, err
+	}
+	return info, nil
+}
+
+// putDbInfo writes data to the storage engine.
+// Returns a VDL-compatible error.
+func (a *app) putDbInfo(ctx *context.T, call rpc.ServerCall, st store.StoreWriter, dbName string, info *dbInfo) error {
+	return util.Put(ctx, call, st, &dbInfoLayer{dbName, a}, info)
+}
+
+// delDbInfo deletes data from the storage engine.
+// Returns a VDL-compatible error.
+func (a *app) delDbInfo(ctx *context.T, call rpc.ServerCall, st store.StoreWriter, dbName string) error {
+	return util.Delete(ctx, call, st, &dbInfoLayer{dbName, a})
+}
+
+// updateDbInfo performs a read-modify-write.
+// fn should "modify" v, and should return a VDL-compatible error.
+// Returns a VDL-compatible error.
+// TODO(sadovsky): Enforce that st is in a transaction.
+func (a *app) updateDbInfo(ctx *context.T, call rpc.ServerCall, st store.StoreReadWriter, dbName string, fn func(info *dbInfo) error) error {
+	info, err := a.getDbInfo(ctx, call, st, dbName)
+	if err != nil {
+		return err
+	}
+	if err := fn(info); err != nil {
+		return err
+	}
+	return a.putDbInfo(ctx, call, st, dbName, info)
+}
diff --git a/services/syncbase/server/dispatcher.go b/services/syncbase/server/dispatcher.go
index 925d47a..a6127cd 100644
--- a/services/syncbase/server/dispatcher.go
+++ b/services/syncbase/server/dispatcher.go
@@ -2,14 +2,14 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// +build ignore
-
 package server
 
 import (
 	"strings"
 
-	"v.io/syncbase/v23/services/syncbase"
+	wire "v.io/syncbase/v23/services/syncbase"
+	"v.io/syncbase/x/ref/services/syncbase/server/nosql"
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
 	"v.io/v23/rpc"
 	"v.io/v23/security"
 	"v.io/v23/verror"
@@ -26,55 +26,49 @@
 }
 
 // TODO(sadovsky): Return a real authorizer in various places below.
-func (d *dispatcher) Lookup(suffix string) (interface{}, security.Authorizer, error) {
+func (disp *dispatcher) Lookup(suffix string) (interface{}, security.Authorizer, error) {
 	suffix = strings.TrimPrefix(suffix, "/")
-	parts := strings.Split(suffix, "/")
+	parts := strings.SplitN(suffix, "/", 2)
+
+	if len(suffix) == 0 {
+		return wire.ServiceServer(disp.s), nil, nil
+	}
 
 	// Validate all key atoms up front, so that we can avoid doing so in all our
 	// method implementations.
-	for _, s := range parts {
-		if !validKeyAtom(s) {
-			// TODO(sadovsky): Is it okay to pass a nil context to verror?
-			return nil, nil, syncbase.NewErrInvalidName(nil, suffix)
+	appName := parts[0]
+	if !util.ValidKeyAtom(appName) {
+		return nil, nil, wire.NewErrInvalidName(nil, suffix)
+	}
+
+	aExists := false
+	a, err := disp.s.app(nil, nil, appName)
+	if err == nil {
+		aExists = true
+	} else {
+		if verror.ErrorID(err) != verror.ErrNoExistOrNoAccess.ID {
+			return nil, nil, err
+		} else {
+			a = &app{
+				name: appName,
+				s:    disp.s,
+			}
 		}
 	}
 
-	if len(parts) == 0 {
-		return syncbase.ServiceServer(d.s), nil, nil
-	}
-
-	universe := &universe{
-		name: parts[0],
-		s:    d.s,
-	}
 	if len(parts) == 1 {
-		return syncbase.UniverseServer(universe), nil, nil
+		return wire.AppServer(a), nil, nil
 	}
 
-	database := &database{
-		name: parts[1],
-		u:    universe,
-	}
-	if len(parts) == 2 {
-		return syncbase.DatabaseServer(database), nil, nil
+	// All database, table, and row methods require the app to exist. If it
+	// doesn't, abort early.
+	if !aExists {
+		return nil, nil, verror.New(verror.ErrNoExistOrNoAccess, nil, a.name)
 	}
 
-	table := &table{
-		name: parts[2],
-		d:    database,
-	}
-	if len(parts) == 3 {
-		return syncbase.TableServer(table), nil, nil
-	}
-
-	item := &item{
-		encodedKey: parts[3],
-		t:          table,
-	}
-	if len(parts) == 4 {
-		return syncbase.ItemServer(item), nil, nil
-	}
-
-	// TODO(sadovsky): Is it okay to pass a nil context to verror?
-	return nil, nil, verror.NewErrNoExist(nil)
+	// Note, it's possible for the app to be deleted concurrently with downstream
+	// handling of this request. Depending on the order in which things execute,
+	// the client may not get an error, but in any case ultimately the store will
+	// end up in a consistent state.
+	return nosql.NewDispatcher(a).Lookup(parts[1])
 }
diff --git a/services/syncbase/server/item.go b/services/syncbase/server/item.go
deleted file mode 100644
index ae849c9..0000000
--- a/services/syncbase/server/item.go
+++ /dev/null
@@ -1,117 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build ignore
-
-package server
-
-import (
-	"v.io/syncbase/v23/services/syncbase"
-	"v.io/syncbase/x/ref/services/syncbase/store"
-	"v.io/v23/rpc"
-	"v.io/v23/vdl"
-	"v.io/v23/verror"
-)
-
-// TODO(sadovsky): Extend data layout to support version tracking for sync.
-// See go/vanadium-local-structured-store.
-
-type item struct {
-	encodedKey string
-	t          *table
-}
-
-var _ syncbase.ItemServerMethods = (*item)(nil)
-
-func (i *item) Get(call rpc.ServerCall) (*vdl.Value, error) {
-	var value *vdl.Value
-	if err := store.RunInTransaction(i.t.d.u.s.st, func(st store.Store) error {
-		var err error
-		value, err = i.get(call, st)
-		return err
-	}); err != nil {
-		return nil, err
-	}
-	return value, nil
-}
-
-func (i *item) Put(call rpc.ServerCall, value *vdl.Value) error {
-	return store.RunInTransaction(i.t.d.u.s.st, func(st store.Store) error {
-		return i.put(call, st, value)
-	})
-}
-
-func (i *item) Delete(call rpc.ServerCall) error {
-	return store.RunInTransaction(i.t.d.u.s.st, func(st store.Store) error {
-		return i.del(call, st)
-	})
-}
-
-////////////////////////////////////////
-// Internal helpers
-
-func (i *item) keyPart() string {
-	return joinKeyParts(i.t.keyPart(), i.encodedKey)
-}
-
-func (i *item) key() string {
-	return joinKeyParts("$item", i.keyPart())
-}
-
-// Performs authorization check (against the database Permissions) and checks that this
-// item's table exists in the database schema. Returns the schema and a
-// VDL-compatible error.
-func (i *item) checkAccess(call rpc.ServerCall, st store.Store) (syncbase.Schema, error) {
-	data, err := i.t.d.get(call, st, true)
-	if err != nil {
-		return nil, err
-	}
-	if _, ok := data.Schema[i.t.name]; !ok {
-		return nil, verror.NewErrNoExist(call.Context())
-	}
-	return data.Schema, nil
-}
-
-// Reads data from the storage engine.
-// Performs authorization check. Returns a VDL-compatible error.
-func (i *item) get(call rpc.ServerCall, st store.Store) (*vdl.Value, error) {
-	if _, err := i.checkAccess(call, st); err != nil {
-		return nil, err
-	}
-	value := &vdl.Value{}
-	if err := getObject(st, i.key(), value); err != nil {
-		if _, ok := err.(*store.ErrUnknownKey); ok {
-			// We've already done an auth check, so here we can safely return NoExist
-			// rather than NoExistOrNoAccess.
-			return nil, verror.NewErrNoExist(call.Context())
-		}
-		return nil, verror.New(verror.ErrInternal, call.Context(), err)
-	}
-	return value, nil
-}
-
-// Writes data to the storage engine.
-// Performs authorization check. Returns a VDL-compatible error.
-func (i *item) put(call rpc.ServerCall, st store.Store, value *vdl.Value) error {
-	// TODO(sadovsky): Check that value's primary key field matches i.encodedKey.
-	if _, err := i.checkAccess(call, st); err != nil {
-		return err
-	}
-	if err := putObject(st, i.key(), &value); err != nil {
-		return verror.New(verror.ErrInternal, call.Context(), err)
-	}
-	return nil
-}
-
-// Deletes data from the storage engine.
-// Performs authorization check. Returns a VDL-compatible error.
-func (i *item) del(call rpc.ServerCall, st store.Store) error {
-	if _, err := i.checkAccess(call, st); err != nil {
-		return err
-	}
-	if err := st.Delete(i.key()); err != nil {
-		return verror.New(verror.ErrInternal, call.Context(), err)
-	}
-	return nil
-}
diff --git a/services/syncbase/server/nosql/database.go b/services/syncbase/server/nosql/database.go
new file mode 100644
index 0000000..03377fc
--- /dev/null
+++ b/services/syncbase/server/nosql/database.go
@@ -0,0 +1,131 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package nosql
+
+import (
+	wire "v.io/syncbase/v23/services/syncbase/nosql"
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
+	"v.io/syncbase/x/ref/services/syncbase/store"
+	"v.io/syncbase/x/ref/services/syncbase/store/memstore"
+	"v.io/v23/context"
+	"v.io/v23/rpc"
+	"v.io/v23/security/access"
+	"v.io/v23/verror"
+	"v.io/x/lib/vlog"
+)
+
+type database struct {
+	name string
+	a    util.App
+	// The fields below are initialized iff this database exists.
+	st store.Store // stores all data for a single database
+}
+
+var (
+	_ wire.DatabaseServerMethods = (*database)(nil)
+	_ util.Database              = (*database)(nil)
+	_ util.Layer                 = (*database)(nil)
+)
+
+// NewDatabase creates a new database instance and returns it.
+// Returns a VDL-compatible error.
+// Designed for use from within App.CreateNoSQLDatabase.
+func NewDatabase(ctx *context.T, call rpc.ServerCall, a util.App, name string, perms access.Permissions) (*database, error) {
+	if perms == nil {
+		return nil, verror.New(verror.ErrInternal, nil, "perms must be specified")
+	}
+	// TODO(sadovsky): Make storage engine pluggable.
+	d := &database{
+		name: name,
+		a:    a,
+		st:   memstore.New(),
+	}
+	data := &databaseData{
+		Name:  d.name,
+		Perms: perms,
+	}
+	if err := util.Put(ctx, call, d.st, d, data); err != nil {
+		return nil, err
+	}
+	return d, nil
+}
+
+////////////////////////////////////////
+// RPC methods
+
+func (d *database) Create(ctx *context.T, call rpc.ServerCall, perms access.Permissions) error {
+	// This database does not yet exist; d is just an ephemeral handle that holds
+	// {name string, a *app}. d.a.CreateNoSQLDatabase will create a new database
+	// handle and store it in d.a.dbs[d.name].
+	return d.a.CreateNoSQLDatabase(ctx, call, d.name, perms)
+}
+
+func (d *database) Delete(ctx *context.T, call rpc.ServerCall) error {
+	return d.a.DeleteNoSQLDatabase(ctx, call, d.name)
+}
+
+func (d *database) BeginBatch(ctx *context.T, call rpc.ServerCall, bo wire.BatchOptions) (string, error) {
+	return "", verror.NewErrNotImplemented(ctx)
+}
+
+func (d *database) Commit(ctx *context.T, call rpc.ServerCall) error {
+	return verror.NewErrNotImplemented(ctx)
+}
+
+func (d *database) Abort(ctx *context.T, call rpc.ServerCall) error {
+	return verror.NewErrNotImplemented(ctx)
+}
+
+func (d *database) SetPermissions(ctx *context.T, call rpc.ServerCall, perms access.Permissions, version string) error {
+	return d.a.SetDatabasePerms(ctx, call, d.name, perms, version)
+}
+
+func (d *database) GetPermissions(ctx *context.T, call rpc.ServerCall) (perms access.Permissions, version string, err error) {
+	data := &databaseData{}
+	if err := util.Get(ctx, call, d.st, d, data); err != nil {
+		return nil, "", err
+	}
+	return data.Perms, util.FormatVersion(data.Version), nil
+}
+
+// TODO(sadovsky): Implement Glob.
+
+////////////////////////////////////////
+// util.Database methods
+
+func (d *database) CheckPermsInternal(ctx *context.T, call rpc.ServerCall) error {
+	if d.st == nil {
+		vlog.Fatalf("database %q does not exist", d.name)
+	}
+	return util.Get(ctx, call, d.st, d, &databaseData{})
+}
+
+func (d *database) SetPermsInternal(ctx *context.T, call rpc.ServerCall, perms access.Permissions, version string) error {
+	if d.st == nil {
+		vlog.Fatalf("database %q does not exist", d.name)
+	}
+	return store.RunInTransaction(d.st, func(st store.StoreReadWriter) error {
+		data := &databaseData{}
+		return util.Update(ctx, call, st, d, data, func() error {
+			if err := util.CheckVersion(ctx, version, data.Version); err != nil {
+				return err
+			}
+			data.Perms = perms
+			data.Version++
+			return nil
+		})
+	})
+}
+
+////////////////////////////////////////
+// util.Layer methods
+
+func (d *database) Name() string {
+	return d.name
+}
+
+func (d *database) StKey() string {
+	return util.DatabasePrefix
+}
diff --git a/services/syncbase/server/nosql/dispatcher.go b/services/syncbase/server/nosql/dispatcher.go
new file mode 100644
index 0000000..50737c5
--- /dev/null
+++ b/services/syncbase/server/nosql/dispatcher.go
@@ -0,0 +1,92 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package nosql
+
+import (
+	"strings"
+
+	wire "v.io/syncbase/v23/services/syncbase"
+	nosqlWire "v.io/syncbase/v23/services/syncbase/nosql"
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
+	"v.io/v23/rpc"
+	"v.io/v23/security"
+	"v.io/v23/verror"
+	"v.io/x/lib/vlog"
+)
+
+type dispatcher struct {
+	a util.App
+}
+
+var _ rpc.Dispatcher = (*dispatcher)(nil)
+
+func NewDispatcher(a util.App) *dispatcher {
+	return &dispatcher{a: a}
+}
+
+func (disp *dispatcher) Lookup(suffix string) (interface{}, security.Authorizer, error) {
+	suffix = strings.TrimPrefix(suffix, "/")
+	parts := strings.Split(suffix, "/")
+
+	if len(parts) == 0 {
+		vlog.Fatal("invalid nosql.dispatcher Lookup")
+	}
+
+	// Validate all key atoms up front, so that we can avoid doing so in all our
+	// method implementations.
+	for _, s := range parts {
+		if !util.ValidKeyAtom(s) {
+			return nil, nil, wire.NewErrInvalidName(nil, suffix)
+		}
+	}
+
+	dExists := false
+	var d *database
+	if dint, err := disp.a.NoSQLDatabase(nil, nil, parts[0]); err == nil {
+		d = dint.(*database) // panics on failure, as desired
+		dExists = true
+	} else {
+		if verror.ErrorID(err) != verror.ErrNoExistOrNoAccess.ID {
+			return nil, nil, err
+		} else {
+			d = &database{
+				name: parts[0],
+				a:    disp.a,
+			}
+		}
+	}
+
+	if len(parts) == 1 {
+		return nosqlWire.DatabaseServer(d), nil, nil
+	}
+
+	// All table and row methods require the database to exist. If it doesn't,
+	// abort early.
+	if !dExists {
+		return nil, nil, verror.New(verror.ErrNoExistOrNoAccess, nil, d.name)
+	}
+
+	// Note, it's possible for the database to be deleted concurrently with
+	// downstream handling of this request. Depending on the order in which things
+	// execute, the client may not get an error, but in any case ultimately the
+	// store will end up in a consistent state.
+	t := &table{
+		name: parts[1],
+		d:    d,
+	}
+	if len(parts) == 2 {
+		return nosqlWire.TableServer(t), nil, nil
+	}
+
+	r := &row{
+		key: parts[2],
+		t:   t,
+	}
+	if len(parts) == 3 {
+		return nosqlWire.RowServer(r), nil, nil
+	}
+
+	return nil, nil, verror.NewErrNoExist(nil)
+}
diff --git a/services/syncbase/server/nosql/row.go b/services/syncbase/server/nosql/row.go
new file mode 100644
index 0000000..c699e88
--- /dev/null
+++ b/services/syncbase/server/nosql/row.go
@@ -0,0 +1,111 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package nosql
+
+import (
+	wire "v.io/syncbase/v23/services/syncbase/nosql"
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
+	"v.io/syncbase/x/ref/services/syncbase/store"
+	"v.io/v23/context"
+	"v.io/v23/rpc"
+	"v.io/v23/vdl"
+	"v.io/v23/verror"
+)
+
+// TODO(sadovsky): Extend data layout to support version tracking for sync.
+// See go/vanadium-local-structured-store.
+
+// TODO(sadovsky): Handle the case where we're in a batch.
+
+type row struct {
+	key string
+	t   *table
+}
+
+var (
+	_ wire.RowServerMethods = (*row)(nil)
+	_ util.Layer            = (*row)(nil)
+)
+
+////////////////////////////////////////
+// RPC methods
+
+func (r *row) Get(ctx *context.T, call rpc.ServerCall) (*vdl.Value, error) {
+	return r.get(ctx, call, r.t.d.st)
+}
+
+func (r *row) Put(ctx *context.T, call rpc.ServerCall, value *vdl.Value) error {
+	return r.put(ctx, call, r.t.d.st, value)
+}
+
+func (r *row) Delete(ctx *context.T, call rpc.ServerCall) error {
+	return r.del(ctx, call, r.t.d.st)
+}
+
+////////////////////////////////////////
+// util.Layer methods
+
+func (r *row) Name() string {
+	return r.key
+}
+
+func (r *row) StKey() string {
+	return util.JoinKeyParts(util.RowPrefix, r.stKeyPart())
+}
+
+////////////////////////////////////////
+// Internal helpers
+
+func (r *row) stKeyPart() string {
+	return util.JoinKeyParts(r.t.stKeyPart(), r.key)
+}
+
+// TODO(sadovsky): Update access checks to use prefix permissions.
+
+// checkAccess checks that this row's table exists in the database and performs
+// an authorization check (currently against the table perms).
+// Returns a VDL-compatible error.
+func (r *row) checkAccess(ctx *context.T, call rpc.ServerCall, st store.StoreReader) error {
+	return util.Get(ctx, call, st, r.t.d, &databaseData{})
+}
+
+// get reads data from the storage engine.
+// Performs authorization check.
+// Returns a VDL-compatible error.
+func (r *row) get(ctx *context.T, call rpc.ServerCall, st store.StoreReader) (*vdl.Value, error) {
+	if err := r.checkAccess(ctx, call, st); err != nil {
+		return nil, err
+	}
+	value := &vdl.Value{}
+	if err := util.GetObject(st, r.StKey(), value); err != nil {
+		if _, ok := err.(*store.ErrUnknownKey); ok {
+			// We've already done an auth check, so here we can safely return NoExist
+			// rather than NoExistOrNoAccess.
+			return nil, verror.New(verror.ErrNoExist, ctx, r.Name())
+		}
+		return nil, verror.New(verror.ErrInternal, ctx, err)
+	}
+	return value, nil
+}
+
+// put writes data to the storage engine.
+// Performs authorization check.
+// Returns a VDL-compatible error.
+func (r *row) put(ctx *context.T, call rpc.ServerCall, st store.StoreReadWriter, value *vdl.Value) error {
+	if err := r.checkAccess(ctx, call, st); err != nil {
+		return err
+	}
+	return util.Put(ctx, call, st, r, value)
+}
+
+// del deletes data from the storage engine.
+// Performs authorization check.
+// Returns a VDL-compatible error.
+func (r *row) del(ctx *context.T, call rpc.ServerCall, st store.StoreReadWriter) error {
+	if err := r.checkAccess(ctx, call, st); err != nil {
+		return err
+	}
+	return util.Delete(ctx, call, st, r)
+}
diff --git a/services/syncbase/server/nosql/table.go b/services/syncbase/server/nosql/table.go
new file mode 100644
index 0000000..1983ba8
--- /dev/null
+++ b/services/syncbase/server/nosql/table.go
@@ -0,0 +1,104 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package nosql
+
+import (
+	wire "v.io/syncbase/v23/services/syncbase/nosql"
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
+	"v.io/syncbase/x/ref/services/syncbase/store"
+	"v.io/v23/context"
+	"v.io/v23/rpc"
+	"v.io/v23/security/access"
+	"v.io/v23/verror"
+)
+
+// TODO(sadovsky): Handle the case where we're in a batch.
+
+type table struct {
+	name string
+	d    *database
+}
+
+var (
+	_ wire.TableServerMethods = (*table)(nil)
+	_ util.Layer              = (*table)(nil)
+)
+
+////////////////////////////////////////
+// RPC methods
+
+func (t *table) Create(ctx *context.T, call rpc.ServerCall, perms access.Permissions) error {
+	return store.RunInTransaction(t.d.st, func(st store.StoreReadWriter) error {
+		// Check databaseData perms.
+		dData := &databaseData{}
+		if err := util.Get(ctx, call, st, t.d, dData); err != nil {
+			return err
+		}
+		// Check for "table already exists".
+		if err := util.GetWithoutAuth(ctx, call, st, t, &tableData{}); verror.ErrorID(err) != verror.ErrNoExistOrNoAccess.ID {
+			if err != nil {
+				return err
+			}
+			// TODO(sadovsky): Should this be ErrExistOrNoAccess, for privacy?
+			return verror.New(verror.ErrExist, ctx, t.name)
+		}
+		// Write new tableData.
+		if perms == nil {
+			perms = dData.Perms
+		}
+		data := &tableData{
+			Name:  t.name,
+			Perms: perms,
+		}
+		return util.Put(ctx, call, st, t, data)
+	})
+}
+
+func (t *table) Delete(ctx *context.T, call rpc.ServerCall) error {
+	return store.RunInTransaction(t.d.st, func(st store.StoreReadWriter) error {
+		// Read-check-delete tableData.
+		if err := util.Get(ctx, call, st, t, &tableData{}); err != nil {
+			return err
+		}
+		// TODO(sadovsky): Delete all rows in this table.
+		return util.Delete(ctx, call, st, t)
+	})
+}
+
+func (t *table) DeleteRowRange(ctx *context.T, call rpc.ServerCall, start, limit string) error {
+	return verror.NewErrNotImplemented(ctx)
+}
+
+func (t *table) SetPermissions(ctx *context.T, call rpc.ServerCall, prefix string, perms access.Permissions) error {
+	return verror.NewErrNotImplemented(ctx)
+}
+
+func (t *table) GetPermissions(ctx *context.T, call rpc.ServerCall, key string) ([]wire.PrefixPermissions, error) {
+	return nil, verror.NewErrNotImplemented(ctx)
+}
+
+func (t *table) DeletePermissions(ctx *context.T, call rpc.ServerCall, prefix string) error {
+	return verror.NewErrNotImplemented(ctx)
+}
+
+// TODO(sadovsky): Implement Glob.
+
+////////////////////////////////////////
+// util.Layer methods
+
+func (t *table) Name() string {
+	return t.name
+}
+
+func (t *table) StKey() string {
+	return util.JoinKeyParts(util.TablePrefix, t.stKeyPart())
+}
+
+////////////////////////////////////////
+// Internal helpers
+
+func (t *table) stKeyPart() string {
+	return t.name
+}
diff --git a/services/syncbase/server/nosql/types.go b/services/syncbase/server/nosql/types.go
new file mode 100644
index 0000000..7a87916
--- /dev/null
+++ b/services/syncbase/server/nosql/types.go
@@ -0,0 +1,23 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package nosql
+
+import (
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
+	"v.io/v23/security/access"
+)
+
+var (
+	_ util.Permser = (*databaseData)(nil)
+	_ util.Permser = (*tableData)(nil)
+)
+
+func (data *databaseData) GetPerms() access.Permissions {
+	return data.Perms
+}
+
+func (data *tableData) GetPerms() access.Permissions {
+	return data.Perms
+}
diff --git a/services/syncbase/server/nosql/types.vdl b/services/syncbase/server/nosql/types.vdl
new file mode 100644
index 0000000..4a8a328
--- /dev/null
+++ b/services/syncbase/server/nosql/types.vdl
@@ -0,0 +1,23 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package nosql
+
+import (
+	"v.io/v23/security/access"
+)
+
+// databaseData represents the persistent state of a Database.
+type databaseData struct {
+	Name    string
+	Version uint64 // covers the fields below
+	Perms   access.Permissions
+}
+
+// tableData represents the persistent state of a Table.
+// TODO(sadovsky): Decide whether to track "empty-prefix" perms here.
+type tableData struct {
+	Name  string
+	Perms access.Permissions
+}
diff --git a/services/syncbase/server/nosql/types.vdl.go b/services/syncbase/server/nosql/types.vdl.go
new file mode 100644
index 0000000..a6e62f6
--- /dev/null
+++ b/services/syncbase/server/nosql/types.vdl.go
@@ -0,0 +1,45 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file was auto-generated by the vanadium vdl tool.
+// Source: types.vdl
+
+package nosql
+
+import (
+	// VDL system imports
+	"v.io/v23/vdl"
+
+	// VDL user imports
+	"v.io/v23/security/access"
+)
+
+// databaseData represents the persistent state of a Database.
+type databaseData struct {
+	Name    string
+	Version uint64 // covers the fields below
+	Perms   access.Permissions
+}
+
+func (databaseData) __VDLReflect(struct {
+	Name string "v.io/syncbase/x/ref/services/syncbase/server/nosql.databaseData"
+}) {
+}
+
+// tableData represents the persistent state of a Table.
+// TODO(sadovsky): Decide whether to track "empty-prefix" perms here.
+type tableData struct {
+	Name  string
+	Perms access.Permissions
+}
+
+func (tableData) __VDLReflect(struct {
+	Name string "v.io/syncbase/x/ref/services/syncbase/server/nosql.tableData"
+}) {
+}
+
+func init() {
+	vdl.Register((*databaseData)(nil))
+	vdl.Register((*tableData)(nil))
+}
diff --git a/services/syncbase/server/server_test.go b/services/syncbase/server/server_test.go
index ce7ba39..b0453c8 100644
--- a/services/syncbase/server/server_test.go
+++ b/services/syncbase/server/server_test.go
@@ -2,107 +2,24 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// +build ignore
-
 package server_test
 
-// Note: core/veyron/services/security/groups/server/server_test.go has some
-// helpful code snippets to model after.
+// Note: Most of our unit tests are client-side and cover end-to-end behavior.
+// Tests of the "server" package (and below) specifically target aspects of the
+// implementation that are difficult to test from the client side.
 
 import (
 	"testing"
 
-	"v.io/v23"
-	"v.io/v23/context"
-	"v.io/v23/naming"
-	"v.io/v23/security"
-	"v.io/v23/security/access"
-	"v.io/x/lib/vlog"
-
-	"v.io/syncbase/x/ref/services/syncbase/server"
-	"v.io/syncbase/x/ref/services/syncbase/store/memstore"
+	tu "v.io/syncbase/v23/syncbase/testutil"
 	_ "v.io/x/ref/profiles"
-	tsecurity "v.io/x/ref/test/testutil"
 )
 
-func defaultPermissions() access.Permissions {
-	acl := access.Permissions{}
-	for _, tag := range access.AllTypicalTags() {
-		acl.Add(security.BlessingPattern("server/client"), string(tag))
-	}
-	return acl
-}
-
-func newServer(ctx *context.T, acl access.Permissions) (string, func()) {
-	s, err := v23.NewServer(ctx)
-	if err != nil {
-		vlog.Fatal("v23.NewServer() failed: ", err)
-	}
-	eps, err := s.Listen(v23.GetListenSpec(ctx))
-	if err != nil {
-		vlog.Fatal("s.Listen() failed: ", err)
-	}
-
-	service := server.NewService(memstore.New())
-	if acl == nil {
-		acl = defaultPermissions()
-	}
-	if err := service.Create(acl); err != nil {
-		vlog.Fatal("service.Create() failed: ", err)
-	}
-	d := server.NewDispatcher(service)
-
-	if err := s.ServeDispatcher("", d); err != nil {
-		vlog.Fatal("s.ServeDispatcher() failed: ", err)
-	}
-
-	name := naming.JoinAddressName(eps[0].String(), "")
-	return name, func() {
-		s.Stop()
-	}
-}
-
-func setupOrDie(acl access.Permissions) (clientCtx *context.T, serverName string, cleanup func()) {
-	ctx, shutdown := v23.Init()
-	cp, sp := tsecurity.NewPrincipal("client"), tsecurity.NewPrincipal("server")
-
-	// Have the server principal bless the client principal as "client".
-	blessings, err := sp.Bless(cp.PublicKey(), sp.BlessingStore().Default(), "client", security.UnconstrainedUse())
-	if err != nil {
-		vlog.Fatal("sp.Bless() failed: ", err)
-	}
-	// Have the client present its "client" blessing when talking to the server.
-	if _, err := cp.BlessingStore().Set(blessings, "server"); err != nil {
-		vlog.Fatal("cp.BlessingStore().Set() failed: ", err)
-	}
-	// Have the client treat the server's public key as an authority on all
-	// blessings that match the pattern "server".
-	if err := cp.AddToRoots(blessings); err != nil {
-		vlog.Fatal("cp.AddToRoots() failed: ", err)
-	}
-
-	clientCtx, err = v23.SetPrincipal(ctx, cp)
-	if err != nil {
-		vlog.Fatal("v23.SetPrincipal() failed: ", err)
-	}
-	serverCtx, err := v23.SetPrincipal(ctx, sp)
-	if err != nil {
-		vlog.Fatal("v23.SetPrincipal() failed: ", err)
-	}
-
-	serverName, stopServer := newServer(serverCtx, acl)
-	cleanup = func() {
-		stopServer()
-		shutdown()
-	}
-	return
-}
-
 ////////////////////////////////////////
 // Test cases
 
 // TODO(sadovsky): Write some tests.
 func TestSomething(t *testing.T) {
-	_, _, cleanup := setupOrDie(nil)
+	_, _, cleanup := tu.SetupOrDie(nil)
 	defer cleanup()
 }
diff --git a/services/syncbase/server/service.go b/services/syncbase/server/service.go
index 8f7e7d3..e268787 100644
--- a/services/syncbase/server/service.go
+++ b/services/syncbase/server/service.go
@@ -2,145 +2,190 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// +build ignore
-
 package server
 
 import (
-	"v.io/syncbase/v23/services/syncbase"
+	"sync"
+
+	wire "v.io/syncbase/v23/services/syncbase"
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
 	"v.io/syncbase/x/ref/services/syncbase/store"
+	"v.io/syncbase/x/ref/services/syncbase/store/memstore"
+	"v.io/v23/context"
 	"v.io/v23/rpc"
 	"v.io/v23/security/access"
 	"v.io/v23/verror"
 )
 
 type service struct {
-	st store.TransactableStore
+	st store.Store // keeps track of which apps and databases exist, etc.
+	// Guards the fields below. Held during app Create, Delete, and
+	// SetPermissions.
+	mu   sync.Mutex
+	apps map[string]*app
 }
 
-var _ syncbase.ServiceServerMethods = (*service)(nil)
+var (
+	_ wire.ServiceServerMethods = (*service)(nil)
+	_ util.Layer                = (*service)(nil)
+)
 
-func NewService(st store.TransactableStore) *service {
-	return &service{st: st}
-}
-
+// NewService creates a new service instance and returns it.
 // Returns a VDL-compatible error.
-// Note, this is not an RPC method.
-func (s *service) Create(acl access.Permissions) error {
-	if acl == nil {
-		return verror.New(verror.ErrInternal, nil, "acl must be specified")
+func NewService(ctx *context.T, call rpc.ServerCall, perms access.Permissions) (*service, error) {
+	if perms == nil {
+		return nil, verror.New(verror.ErrInternal, nil, "perms must be specified")
 	}
-
-	return store.RunInTransaction(s.st, func(st store.Store) error {
-		// TODO(sadovsky): Maybe add "has" method to storage engine.
-		data := &serviceData{}
-		if err := getObject(st, s.key(), data); err == nil {
-			return verror.NewErrExist(nil)
-		}
-
-		data = &serviceData{
-			Permissions: acl,
-		}
-		if err := putObject(st, s.key(), data); err != nil {
-			return verror.New(verror.ErrInternal, nil, "put failed")
-		}
-
-		return nil
-	})
+	// TODO(sadovsky): Make storage engine pluggable.
+	s := &service{
+		st:   memstore.New(),
+		apps: map[string]*app{},
+	}
+	data := &serviceData{
+		Perms: perms,
+	}
+	if err := util.Put(ctx, call, s.st, s, data); err != nil {
+		return nil, err
+	}
+	return s, nil
 }
 
-func (s *service) SetPermissions(call rpc.ServerCall, acl access.Permissions, version string) error {
-	return store.RunInTransaction(s.st, func(st store.Store) error {
-		return s.update(call, st, true, func(data *serviceData) error {
-			if err := checkVersion(call, version, data.Version); err != nil {
+////////////////////////////////////////
+// RPC methods
+
+func (s *service) SetPermissions(ctx *context.T, call rpc.ServerCall, perms access.Permissions, version string) error {
+	return store.RunInTransaction(s.st, func(st store.StoreReadWriter) error {
+		data := &serviceData{}
+		return util.Update(ctx, call, st, s, data, func() error {
+			if err := util.CheckVersion(ctx, version, data.Version); err != nil {
 				return err
 			}
-			data.Permissions = acl
+			data.Perms = perms
 			data.Version++
 			return nil
 		})
 	})
 }
 
-func (s *service) GetPermissions(call rpc.ServerCall) (acl access.Permissions, version string, err error) {
-	data, err := s.get(call, s.st, true)
-	if err != nil {
+func (s *service) GetPermissions(ctx *context.T, call rpc.ServerCall) (perms access.Permissions, version string, err error) {
+	data := &serviceData{}
+	if err := util.Get(ctx, call, s.st, s, data); err != nil {
 		return nil, "", err
 	}
-	return data.Permissions, formatVersion(data.Version), nil
+	return data.Perms, util.FormatVersion(data.Version), nil
 }
 
 // TODO(sadovsky): Implement Glob.
 
 ////////////////////////////////////////
-// Internal helpers
+// App management methods
 
-func (s *service) key() string {
-	return "$service"
-}
-
-// Note, the methods below use "x" as the receiver name to make find-replace
-// easier across the different levels of syncbase hierarchy.
-//
-// TODO(sadovsky): Is there any better way to share this code despite the lack
-// of generics?
-
-// Reads data from the storage engine.
-// Returns a VDL-compatible error.
-// checkAuth specifies whether to perform an authorization check.
-func (x *service) get(call rpc.ServerCall, st store.Store, checkAuth bool) (*serviceData, error) {
-	// TODO(kash): Get this to compile.
-	return nil, nil
-	// data := &serviceData{}
-	// if err := getObject(st, x.key(), data); err != nil {
-	// 	if _, ok := err.(*store.ErrUnknownKey); ok {
-	// 		// TODO(sadovsky): Return ErrNoExist if appropriate.
-	// 		return nil, verror.New(verror.ErrNoExistOrNoAccess, call.Context())
-	// 	}
-	// 	return nil, verror.New(verror.ErrInternal, call.Context(), err)
-	// }
-	// if checkAuth {
-	// 	auth, _ := access.PermissionsAuthorizer(data.Permissions, access.TypicalTagType())
-	// 	if err := auth.Authorize(call); err != nil {
-	// 		// TODO(sadovsky): Return ErrNoAccess if appropriate.
-	// 		return nil, verror.New(verror.ErrNoExistOrNoAccess, call.Context(), err)
-	// 	}
-	// }
-	// return data, nil
-}
-
-// Writes data to the storage engine.
-// Returns a VDL-compatible error.
-// If you need to perform an authorization check, use update().
-func (x *service) put(call rpc.ServerCall, st store.Store, data *serviceData) error {
-	if err := putObject(st, x.key(), data); err != nil {
-		return verror.New(verror.ErrInternal, call.Context(), err)
+func (s *service) app(ctx *context.T, call rpc.ServerCall, appName string) (*app, error) {
+	s.mu.Lock()
+	defer s.mu.Unlock()
+	a, ok := s.apps[appName]
+	if !ok {
+		return nil, verror.New(verror.ErrNoExistOrNoAccess, ctx, appName)
 	}
+	return a, nil
+}
+
+func (s *service) createApp(ctx *context.T, call rpc.ServerCall, appName string, perms access.Permissions) error {
+	s.mu.Lock()
+	defer s.mu.Unlock()
+	if _, ok := s.apps[appName]; ok {
+		// TODO(sadovsky): Should this be ErrExistOrNoAccess, for privacy?
+		return verror.New(verror.ErrExist, ctx, appName)
+	}
+
+	a := &app{
+		name: appName,
+		s:    s,
+		dbs:  map[string]util.Database{},
+	}
+
+	if err := store.RunInTransaction(s.st, func(st store.StoreReadWriter) error {
+		// Check serviceData perms.
+		sData := &serviceData{}
+		if err := util.Get(ctx, call, st, s, sData); err != nil {
+			return err
+		}
+		// Check for "app already exists".
+		if err := util.GetWithoutAuth(ctx, call, st, a, &appData{}); verror.ErrorID(err) != verror.ErrNoExistOrNoAccess.ID {
+			if err != nil {
+				return err
+			}
+			// TODO(sadovsky): Should this be ErrExistOrNoAccess, for privacy?
+			return verror.New(verror.ErrExist, ctx, appName)
+		}
+		// Write new appData.
+		if perms == nil {
+			perms = sData.Perms
+		}
+		data := &appData{
+			Name:  appName,
+			Perms: perms,
+		}
+		return util.Put(ctx, call, st, a, data)
+	}); err != nil {
+		return err
+	}
+
+	s.apps[appName] = a
 	return nil
 }
 
-// Deletes data from the storage engine.
-// Returns a VDL-compatible error.
-// If you need to perform an authorization check, call get() first.
-func (x *service) del(call rpc.ServerCall, st store.Store) error {
-	if err := st.Delete(x.key()); err != nil {
-		return verror.New(verror.ErrInternal, call.Context(), err)
+func (s *service) deleteApp(ctx *context.T, call rpc.ServerCall, appName string) error {
+	s.mu.Lock()
+	defer s.mu.Unlock()
+	a, ok := s.apps[appName]
+	if !ok {
+		// TODO(sadovsky): Make delete idempotent, here and elsewhere.
+		return verror.New(verror.ErrNoExistOrNoAccess, ctx, appName)
 	}
+
+	if err := store.RunInTransaction(s.st, func(st store.StoreReadWriter) error {
+		// Read-check-delete appData.
+		if err := util.Get(ctx, call, st, a, &appData{}); err != nil {
+			return err
+		}
+		// TODO(sadovsky): Delete all databases in this app.
+		return util.Delete(ctx, call, st, a)
+	}); err != nil {
+		return err
+	}
+
+	delete(s.apps, appName)
 	return nil
 }
 
-// Updates data in the storage engine.
-// Returns a VDL-compatible error.
-// checkAuth specifies whether to perform an authorization check.
-// fn should perform the "modify" part of "read, modify, write", and should
-// return a VDL-compatible error.
-func (x *service) update(call rpc.ServerCall, st store.Store, checkAuth bool, fn func(data *serviceData) error) error {
-	data, err := x.get(call, st, checkAuth)
-	if err != nil {
-		return err
+func (s *service) setAppPerms(ctx *context.T, call rpc.ServerCall, appName string, perms access.Permissions, version string) error {
+	s.mu.Lock()
+	defer s.mu.Unlock()
+	a, ok := s.apps[appName]
+	if !ok {
+		return verror.New(verror.ErrNoExistOrNoAccess, ctx, appName)
 	}
-	if err := fn(data); err != nil {
-		return err
-	}
-	return x.put(call, st, data)
+	return store.RunInTransaction(s.st, func(st store.StoreReadWriter) error {
+		data := &appData{}
+		return util.Update(ctx, call, st, a, data, func() error {
+			if err := util.CheckVersion(ctx, version, data.Version); err != nil {
+				return err
+			}
+			data.Perms = perms
+			data.Version++
+			return nil
+		})
+	})
+}
+
+////////////////////////////////////////
+// util.Layer methods
+
+func (s *service) Name() string {
+	return "service"
+}
+
+func (s *service) StKey() string {
+	return util.ServicePrefix
 }
diff --git a/services/syncbase/server/store_util.go b/services/syncbase/server/store_util.go
deleted file mode 100644
index fb09ad0..0000000
--- a/services/syncbase/server/store_util.go
+++ /dev/null
@@ -1,42 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package server
-
-import (
-	"strconv"
-
-	"v.io/v23/rpc"
-	"v.io/v23/verror"
-	"v.io/v23/vom"
-
-	"v.io/syncbase/x/ref/services/syncbase/store"
-)
-
-func getObject(st store.Store, k string, v interface{}) error {
-	bytes, err := st.Get(k)
-	if err != nil {
-		return err
-	}
-	return vom.Decode(bytes, v)
-}
-
-func putObject(st store.Store, k string, v interface{}) error {
-	bytes, err := vom.Encode(v)
-	if err != nil {
-		return err
-	}
-	return st.Put(k, bytes)
-}
-
-func formatVersion(version uint64) string {
-	return strconv.FormatUint(version, 10)
-}
-
-func checkVersion(call rpc.ServerCall, presented string, actual uint64) error {
-	if presented != "" && presented != formatVersion(actual) {
-		return verror.NewErrBadVersion(call.Context())
-	}
-	return nil
-}
diff --git a/services/syncbase/server/table.go b/services/syncbase/server/table.go
deleted file mode 100644
index 00a4cd6..0000000
--- a/services/syncbase/server/table.go
+++ /dev/null
@@ -1,25 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build ignore
-
-package server
-
-import "v.io/syncbase/v23/services/syncbase"
-
-type table struct {
-	name string
-	d    *database
-}
-
-var _ syncbase.TableServerMethods = (*table)(nil)
-
-// TODO(sadovsky): Implement Glob.
-
-////////////////////////////////////////
-// Internal helpers
-
-func (t *table) keyPart() string {
-	return joinKeyParts(t.d.keyPart(), t.name)
-}
diff --git a/services/syncbase/server/types.go b/services/syncbase/server/types.go
new file mode 100644
index 0000000..2879d56
--- /dev/null
+++ b/services/syncbase/server/types.go
@@ -0,0 +1,23 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package server
+
+import (
+	"v.io/syncbase/x/ref/services/syncbase/server/util"
+	"v.io/v23/security/access"
+)
+
+var (
+	_ util.Permser = (*serviceData)(nil)
+	_ util.Permser = (*appData)(nil)
+)
+
+func (data *serviceData) GetPerms() access.Permissions {
+	return data.Perms
+}
+
+func (data *appData) GetPerms() access.Permissions {
+	return data.Perms
+}
diff --git a/services/syncbase/server/types.vdl b/services/syncbase/server/types.vdl
index 7f53561..4a48134 100644
--- a/services/syncbase/server/types.vdl
+++ b/services/syncbase/server/types.vdl
@@ -2,8 +2,6 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// +build ignore
-
 package server
 
 import (
@@ -12,22 +10,21 @@
 
 // serviceData represents the persistent state of a Service.
 type serviceData struct {
-	Universes set[string]
-	Version   uint64 // covers the fields below
-	Acl       access.Permissions
+	Version uint64 // covers the fields below
+	Perms   access.Permissions
 }
 
-// universeData represents the persistent state of a Universe.
-type universeData struct {
-	Name      string
-	Databases set[string]
-	Version   uint64 // covers the fields below
-	Acl       access.Permissions
-}
-
-// databaseData represents the persistent state of a Database.
-type databaseData struct {
+// appData represents the persistent state of an App.
+type appData struct {
 	Name    string
 	Version uint64 // covers the fields below
-	Acl     access.Permissions
+	Perms   access.Permissions
+}
+
+// dbInfo contains information about one database for an App.
+// TODO(sadovsky): Track NoSQL vs. SQL, storage engine config, etc.
+type dbInfo struct {
+	Name        string
+	Initialized bool
+	Deleted     bool
 }
diff --git a/services/syncbase/server/types.vdl.go b/services/syncbase/server/types.vdl.go
index b99afd9..5c2b3d2 100644
--- a/services/syncbase/server/types.vdl.go
+++ b/services/syncbase/server/types.vdl.go
@@ -17,9 +17,8 @@
 
 // serviceData represents the persistent state of a Service.
 type serviceData struct {
-	Universes map[string]struct{}
-	Version   uint64 // covers the fields below
-	Acl       access.Permissions
+	Version uint64 // covers the fields below
+	Perms   access.Permissions
 }
 
 func (serviceData) __VDLReflect(struct {
@@ -27,33 +26,33 @@
 }) {
 }
 
-// universeData represents the persistent state of a Universe.
-type universeData struct {
-	Name      string
-	Databases map[string]struct{}
-	Version   uint64 // covers the fields below
-	Acl       access.Permissions
+// appData represents the persistent state of an App.
+type appData struct {
+	Name    string
+	Version uint64 // covers the fields below
+	Perms   access.Permissions
 }
 
-func (universeData) __VDLReflect(struct {
-	Name string "v.io/syncbase/x/ref/services/syncbase/server.universeData"
+func (appData) __VDLReflect(struct {
+	Name string "v.io/syncbase/x/ref/services/syncbase/server.appData"
 }) {
 }
 
-// databaseData represents the persistent state of a Database.
-type databaseData struct {
-	Name    string
-	Version uint64 // covers the fields below
-	Acl     access.Permissions
+// dbInfo contains information about one database for an App.
+// TODO(sadovsky): Track NoSQL vs. SQL, storage engine config, etc.
+type dbInfo struct {
+	Name        string
+	Initialized bool
+	Deleted     bool
 }
 
-func (databaseData) __VDLReflect(struct {
-	Name string "v.io/syncbase/x/ref/services/syncbase/server.databaseData"
+func (dbInfo) __VDLReflect(struct {
+	Name string "v.io/syncbase/x/ref/services/syncbase/server.dbInfo"
 }) {
 }
 
 func init() {
 	vdl.Register((*serviceData)(nil))
-	vdl.Register((*universeData)(nil))
-	vdl.Register((*databaseData)(nil))
+	vdl.Register((*appData)(nil))
+	vdl.Register((*dbInfo)(nil))
 }
diff --git a/services/syncbase/server/universe.go b/services/syncbase/server/universe.go
deleted file mode 100644
index 27c5a21..0000000
--- a/services/syncbase/server/universe.go
+++ /dev/null
@@ -1,172 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// +build ignore
-
-package server
-
-import (
-	"v.io/syncbase/v23/services/syncbase"
-	"v.io/syncbase/x/ref/services/syncbase/store"
-	"v.io/v23/rpc"
-	"v.io/v23/security/access"
-	"v.io/v23/verror"
-)
-
-type universe struct {
-	name string
-	s    *service
-}
-
-var _ syncbase.UniverseServerMethods = (*universe)(nil)
-
-func (u *universe) Create(call rpc.ServerCall, acl access.Permissions) error {
-	return store.RunInTransaction(u.s.st, func(st store.Store) error {
-		// Update serviceData.
-		var sData *serviceData
-		if err := u.s.update(call, st, true, func(data *serviceData) error {
-			if _, ok := data.Universes[u.name]; ok {
-				return verror.New(verror.ErrExist, call.Context(), u.name)
-			}
-			// https://github.com/veyron/release-issues/issues/1145
-			if data.Universes == nil {
-				data.Universes = map[string]struct{}{}
-			}
-			data.Universes[u.name] = struct{}{}
-			sData = data
-			return nil
-		}); err != nil {
-			return err
-		}
-
-		// Blind-write universeData.
-		if acl == nil {
-			acl = sData.Permissions
-		}
-		data := &universeData{
-			Name:        u.name,
-			Permissions: acl,
-		}
-		return u.put(call, st, data)
-	})
-}
-
-func (u *universe) Delete(call rpc.ServerCall) error {
-	return store.RunInTransaction(u.s.st, func(st store.Store) error {
-		// Read-check-delete universeData.
-		if _, err := u.get(call, st, true); err != nil {
-			return err
-		}
-		// TODO(sadovsky): Delete all Databases in this Universe.
-		if err := u.del(call, st); err != nil {
-			return err
-		}
-
-		// Update serviceData.
-		return u.s.update(call, st, false, func(data *serviceData) error {
-			delete(data.Universes, u.name)
-			return nil
-		})
-	})
-}
-
-func (u *universe) SetPermissions(call rpc.ServerCall, acl access.Permissions, version string) error {
-	return store.RunInTransaction(u.s.st, func(st store.Store) error {
-		return u.update(call, st, true, func(data *universeData) error {
-			if err := checkVersion(call, version, data.Version); err != nil {
-				return err
-			}
-			data.Permissions = acl
-			data.Version++
-			return nil
-		})
-	})
-}
-
-func (u *universe) GetPermissions(call rpc.ServerCall) (acl access.Permissions, version string, err error) {
-	data, err := u.get(call, u.s.st, true)
-	if err != nil {
-		return nil, "", err
-	}
-	return data.Permissions, formatVersion(data.Version), nil
-}
-
-// TODO(sadovsky): Implement Glob.
-
-////////////////////////////////////////
-// Internal helpers
-
-func (u *universe) keyPart() string {
-	return u.name
-}
-
-func (u *universe) key() string {
-	return joinKeyParts("$universe", u.keyPart())
-}
-
-// Note, the methods below use "x" as the receiver name to make find-replace
-// easier across the different levels of syncbase hierarchy.
-//
-// TODO(sadovsky): Is there any better way to share this code despite the lack
-// of generics?
-
-// Reads data from the storage engine.
-// Returns a VDL-compatible error.
-// checkAuth specifies whether to perform an authorization check.
-func (x *universe) get(call rpc.ServerCall, st store.Store, checkAuth bool) (*universeData, error) {
-	// TODO(kash): Get this to compile.
-	return nil, nil
-	// data := &universeData{}
-	// if err := getObject(st, x.key(), data); err != nil {
-	// 	if _, ok := err.(*store.ErrUnknownKey); ok {
-	// 		// TODO(sadovsky): Return ErrNoExist if appropriate.
-	// 		return nil, verror.NewErrNoExistOrNoAccess(call.Context())
-	// 	}
-	// 	return nil, verror.New(verror.ErrInternal, call.Context(), err)
-	// }
-	// if checkAuth {
-	// 	auth, _ := access.PermissionsAuthorizer(data.Permissions, access.TypicalTagType())
-	// 	if err := auth.Authorize(call); err != nil {
-	// 		// TODO(sadovsky): Return ErrNoAccess if appropriate.
-	// 		return nil, verror.NewErrNoExistOrNoAccess(call.Context())
-	// 	}
-	// }
-	// return data, nil
-}
-
-// Writes data to the storage engine.
-// Returns a VDL-compatible error.
-// If you need to perform an authorization check, use update().
-func (x *universe) put(call rpc.ServerCall, st store.Store, data *universeData) error {
-	if err := putObject(st, x.key(), data); err != nil {
-		return verror.New(verror.ErrInternal, call.Context(), err)
-	}
-	return nil
-}
-
-// Deletes data from the storage engine.
-// Returns a VDL-compatible error.
-// If you need to perform an authorization check, call get() first.
-func (x *universe) del(call rpc.ServerCall, st store.Store) error {
-	if err := st.Delete(x.key()); err != nil {
-		return verror.New(verror.ErrInternal, call.Context(), err)
-	}
-	return nil
-}
-
-// Updates data in the storage engine.
-// Returns a VDL-compatible error.
-// checkAuth specifies whether to perform an authorization check.
-// fn should perform the "modify" part of "read, modify, write", and should
-// return a VDL-compatible error.
-func (x *universe) update(call rpc.ServerCall, st store.Store, checkAuth bool, fn func(data *universeData) error) error {
-	data, err := x.get(call, st, checkAuth)
-	if err != nil {
-		return err
-	}
-	if err := fn(data); err != nil {
-		return err
-	}
-	return x.put(call, st, data)
-}
diff --git a/services/syncbase/server/util/app.go b/services/syncbase/server/util/app.go
new file mode 100644
index 0000000..26c3e91
--- /dev/null
+++ b/services/syncbase/server/util/app.go
@@ -0,0 +1,28 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package util
+
+import (
+	"v.io/v23/context"
+	"v.io/v23/rpc"
+	"v.io/v23/security/access"
+)
+
+// App is an internal interface that enables nosql.database to invoke methods on
+// server.app while avoiding an import cycle.
+// All methods return VDL-compatible errors.
+type App interface {
+	// NoSQLDatabase returns the Database for the specified NoSQL database.
+	NoSQLDatabase(ctx *context.T, call rpc.ServerCall, dbName string) (Database, error)
+
+	// CreateNoSQLDatabase creates the specified NoSQL database.
+	CreateNoSQLDatabase(ctx *context.T, call rpc.ServerCall, dbName string, perms access.Permissions) error
+
+	// DeleteNoSQLDatabase deletes the specified NoSQL database.
+	DeleteNoSQLDatabase(ctx *context.T, call rpc.ServerCall, dbName string) error
+
+	// SetDatabasePerms sets the perms for the specified database.
+	SetDatabasePerms(ctx *context.T, call rpc.ServerCall, dbName string, perms access.Permissions, version string) error
+}
diff --git a/services/syncbase/server/util/constants.go b/services/syncbase/server/util/constants.go
new file mode 100644
index 0000000..5e82ac1
--- /dev/null
+++ b/services/syncbase/server/util/constants.go
@@ -0,0 +1,15 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package util
+
+// TODO(sadovsky): Consider using shorter strings.
+const (
+	ServicePrefix  = "$service"
+	AppPrefix      = "$app"
+	DbInfoPrefix   = "$dbInfo"
+	DatabasePrefix = "$database"
+	TablePrefix    = "$table"
+	RowPrefix      = "$row"
+)
diff --git a/services/syncbase/server/util/database.go b/services/syncbase/server/util/database.go
new file mode 100644
index 0000000..dd79cee
--- /dev/null
+++ b/services/syncbase/server/util/database.go
@@ -0,0 +1,25 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package util
+
+import (
+	"v.io/v23/context"
+	"v.io/v23/rpc"
+	"v.io/v23/security/access"
+)
+
+// Database is an internal interface that enables server.app to invoke methods
+// on nosql.database while avoiding an import cycle.
+// All methods return VDL-compatible errors.
+type Database interface {
+	// CheckPermsInternal checks whether the given RPC (ctx, call) is allowed per
+	// the database perms.
+	// Designed for use from within App.DeleteNoSQLDatabase.
+	CheckPermsInternal(ctx *context.T, call rpc.ServerCall) error
+
+	// SetPermsInternal updates the database perms.
+	// Designed for use from within App.SetDatabasePerms.
+	SetPermsInternal(ctx *context.T, call rpc.ServerCall, perms access.Permissions, version string) error
+}
diff --git a/services/syncbase/server/key_util.go b/services/syncbase/server/util/key_util.go
similarity index 81%
rename from services/syncbase/server/key_util.go
rename to services/syncbase/server/util/key_util.go
index 39ca7b1..542a0ce 100644
--- a/services/syncbase/server/key_util.go
+++ b/services/syncbase/server/util/key_util.go
@@ -2,10 +2,10 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-package server
+package util
 
 // Note, some of the code below is copied from
-// v.io/syncbase/v23/syncbase/key_util.go.
+// v.io/syncbase/v23/syncbase/util/util.go.
 
 import (
 	"regexp"
@@ -16,11 +16,11 @@
 // http://dev.mysql.com/doc/refman/5.7/en/identifiers.html
 var keyAtomRegexp *regexp.Regexp = regexp.MustCompile("^[a-zA-Z0-9_.-]+$")
 
-func validKeyAtom(s string) bool {
+func ValidKeyAtom(s string) bool {
 	return keyAtomRegexp.MatchString(s)
 }
 
-func joinKeyParts(parts ...string) string {
+func JoinKeyParts(parts ...string) string {
 	// TODO(sadovsky): Figure out which delimeter makes the most sense.
 	return strings.Join(parts, ":")
 }
diff --git a/services/syncbase/server/util/store_util.go b/services/syncbase/server/util/store_util.go
new file mode 100644
index 0000000..5c09c13
--- /dev/null
+++ b/services/syncbase/server/util/store_util.go
@@ -0,0 +1,125 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package util
+
+import (
+	"strconv"
+
+	"v.io/syncbase/x/ref/services/syncbase/store"
+	"v.io/v23/context"
+	"v.io/v23/rpc"
+	"v.io/v23/security/access"
+	"v.io/v23/verror"
+	"v.io/v23/vom"
+)
+
+func FormatVersion(version uint64) string {
+	return strconv.FormatUint(version, 10)
+}
+
+func CheckVersion(ctx *context.T, presented string, actual uint64) error {
+	if presented != "" && presented != FormatVersion(actual) {
+		return verror.NewErrBadVersion(ctx)
+	}
+	return nil
+}
+
+////////////////////////////////////////////////////////////
+// RPC-aware, higher-level get/put
+
+type Layer interface {
+	// Name returns the name of this instance, e.g. "fooapp" or "bardb".
+	Name() string
+	// StKey returns the storage engine key to use for metadata about this layer,
+	// e.g. "$table:baztable".
+	StKey() string
+}
+
+type Permser interface {
+	// GetPerms returns the Permissions for this Layer.
+	GetPerms() access.Permissions
+}
+
+// GetWithoutAuth does st.Get(l.StKey(), v), populating v.
+// Returns a VDL-compatible error.
+func GetWithoutAuth(ctx *context.T, call rpc.ServerCall, st store.StoreReader, l Layer, v interface{}) error {
+	if err := GetObject(st, l.StKey(), v); err != nil {
+		if _, ok := err.(*store.ErrUnknownKey); ok {
+			// TODO(sadovsky): Return ErrNoExist if appropriate.
+			return verror.New(verror.ErrNoExistOrNoAccess, ctx, l.Name())
+		}
+		return verror.New(verror.ErrInternal, ctx, err)
+	}
+	return nil
+}
+
+// Get does GetWithoutAuth followed by an auth check.
+// Returns a VDL-compatible error.
+func Get(ctx *context.T, call rpc.ServerCall, st store.StoreReader, l Layer, v Permser) error {
+	if err := GetWithoutAuth(ctx, call, st, l, v); err != nil {
+		return err
+	}
+	auth, _ := access.PermissionsAuthorizer(v.GetPerms(), access.TypicalTagType())
+	if err := auth.Authorize(ctx, call.Security()); err != nil {
+		// TODO(sadovsky): Return ErrNoAccess if appropriate.
+		return verror.New(verror.ErrNoExistOrNoAccess, ctx, l.Name())
+	}
+	return nil
+}
+
+// Put does st.Put(l.StKey(), v).
+// Returns a VDL-compatible error.
+// If you need to perform an authorization check, use Update().
+func Put(ctx *context.T, _ rpc.ServerCall, st store.StoreWriter, l Layer, v interface{}) error {
+	if err := PutObject(st, l.StKey(), v); err != nil {
+		return verror.New(verror.ErrInternal, ctx, err)
+	}
+	return nil
+}
+
+// Delete does st.Delete(l.StKey()).
+// Returns a VDL-compatible error.
+// If you need to perform an authorization check, call Get() first.
+func Delete(ctx *context.T, _ rpc.ServerCall, st store.StoreWriter, l Layer) error {
+	if err := st.Delete(l.StKey()); err != nil {
+		return verror.New(verror.ErrInternal, ctx, err)
+	}
+	return nil
+}
+
+// Update performs a read-modify-write.
+// Input v is populated by the "read" step. fn should "modify" v, and should
+// return a VDL-compatible error.
+// Performs an auth check as part of the "read" step.
+// Returns a VDL-compatible error.
+// TODO(sadovsky): Enforce that st is in a transaction.
+func Update(ctx *context.T, call rpc.ServerCall, st store.StoreReadWriter, l Layer, v Permser, fn func() error) error {
+	if err := Get(ctx, call, st, l, v); err != nil {
+		return err
+	}
+	if err := fn(); err != nil {
+		return err
+	}
+	return Put(ctx, call, st, l, v)
+}
+
+////////////////////////////////////////////////////////////
+// RPC-oblivious, lower-level get/put
+
+func GetObject(st store.StoreReader, k string, v interface{}) error {
+	bytes, err := st.Get(k)
+	if err != nil {
+		return err
+	}
+	return vom.Decode(bytes, v)
+}
+
+func PutObject(st store.StoreWriter, k string, v interface{}) error {
+	bytes, err := vom.Encode(v)
+	if err != nil {
+		return err
+	}
+	return st.Put(k, bytes)
+}
diff --git a/services/syncbase/store/memstore/memstore.go b/services/syncbase/store/memstore/memstore.go
index e5a9ed8..a97370e 100644
--- a/services/syncbase/store/memstore/memstore.go
+++ b/services/syncbase/store/memstore/memstore.go
@@ -13,6 +13,7 @@
 	"time"
 
 	"v.io/syncbase/x/ref/services/syncbase/store"
+	"v.io/x/lib/vlog"
 )
 
 var (
@@ -83,7 +84,8 @@
 }
 
 func (tx *transaction) Scan(start, end string) (store.Stream, error) {
-	panic("not implemented")
+	vlog.Fatal("not implemented")
+	return nil, nil
 }
 
 func (tx *transaction) Get(k string) ([]byte, error) {
@@ -162,7 +164,8 @@
 // memstore methods
 
 func (st *memstore) Scan(start, end string) (store.Stream, error) {
-	panic("not implemented")
+	vlog.Fatal("not implemented")
+	return nil, nil
 }
 
 func (st *memstore) Get(k string) ([]byte, error) {
@@ -176,27 +179,15 @@
 }
 
 func (st *memstore) Put(k string, v []byte) error {
-	tx := st.NewTransaction()
-	err := tx.Put(k, v)
-	if err == nil {
-		err = tx.Commit()
-	}
-	if err != nil {
-		tx.Abort()
-	}
-	return err
+	return store.RunInTransaction(st, func(st store.StoreReadWriter) error {
+		return st.Put(k, v)
+	})
 }
 
 func (st *memstore) Delete(k string) error {
-	tx := st.NewTransaction()
-	err := tx.Delete(k)
-	if err == nil {
-		err = tx.Commit()
-	}
-	if err != nil {
-		tx.Abort()
-	}
-	return err
+	return store.RunInTransaction(st, func(st store.StoreReadWriter) error {
+		return st.Delete(k)
+	})
 }
 
 func (st *memstore) NewTransaction() store.Transaction {
@@ -207,5 +198,6 @@
 }
 
 func (st *memstore) NewSnapshot() store.Snapshot {
-	panic("not implemented")
+	vlog.Fatal("not implemented")
+	return nil
 }
diff --git a/services/syncbase/store/model.go b/services/syncbase/store/model.go
index 962727c..166079f 100644
--- a/services/syncbase/store/model.go
+++ b/services/syncbase/store/model.go
@@ -19,17 +19,22 @@
 // StoreWriter writes data to a CRUD-capable storage engine.
 type StoreWriter interface {
 	// Put writes the given value for the given key.
-	Put(key string, v []byte) error
+	Put(key string, value []byte) error
 
 	// Delete deletes the entry for the given key.
 	// Succeeds (no-op) if the given key is unknown.
 	Delete(key string) error
 }
 
-// Store is a CRUD-capable storage engine that supports transactions.
-type Store interface {
+// StoreReadWriter combines StoreReader and StoreWriter.
+type StoreReadWriter interface {
 	StoreReader
 	StoreWriter
+}
+
+// Store is a CRUD-capable storage engine that supports transactions.
+type Store interface {
+	StoreReadWriter
 
 	// NewTransaction creates a transaction.
 	// TODO(rogulenko): add transaction options.
@@ -50,8 +55,7 @@
 // if writes from a newly-committed transaction conflict with reads or writes
 // from this transaction.
 type Transaction interface {
-	StoreReader
-	StoreWriter
+	StoreReadWriter
 
 	// Commit commits the transaction.
 	Commit() error
@@ -65,13 +69,14 @@
 }
 
 // Snapshot is a handle to particular state in time of a Store.
-// All read operations are executed at a consistent snapshot of Store commit
-// history. Snapshots don't acquire locks and thus don't block transactions.
+// All read operations are executed against a consistent snapshot of Store
+// commit history. Snapshots don't acquire locks and thus don't block
+// transactions.
 type Snapshot interface {
 	StoreReader
 
-	// Close closes a previously acquired snapshot.
-	// Any subsequent method calls will return errors.
+	// Close closes the snapshot.
+	// Any subsequent method calls will fail.
 	Close() error
 }
 
@@ -106,6 +111,24 @@
 	Cancel()
 }
 
+// TODO(sadovsky): Add retry loop.
+func RunInTransaction(st Store, fn func(st StoreReadWriter) error) error {
+	tx := st.NewTransaction()
+	if err := fn(tx); err != nil {
+		tx.Abort()
+		return err
+	}
+	if err := tx.Commit(); err != nil {
+		// TODO(sadovsky): Commit() can fail for a number of reasons, e.g. RPC
+		// failure or ErrConcurrentTransaction. Depending on the cause of failure,
+		// it may be desirable to retry the Commit() and/or to call Abort(). For
+		// now, we always abort on a failed commit.
+		tx.Abort()
+		return err
+	}
+	return nil
+}
+
 type ErrConcurrentTransaction struct{}
 
 func (e *ErrConcurrentTransaction) Error() string {
diff --git a/services/syncbase/syncbased/main.go b/services/syncbase/syncbased/main.go
index e8f7a52..da8ecda 100644
--- a/services/syncbase/syncbased/main.go
+++ b/services/syncbase/syncbased/main.go
@@ -2,8 +2,6 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// +build ignore
-
 // syncbased is a syncbase daemon.
 package main
 
@@ -18,7 +16,6 @@
 	"v.io/x/lib/vlog"
 
 	"v.io/syncbase/x/ref/services/syncbase/server"
-	"v.io/syncbase/x/ref/services/syncbase/store/memstore"
 	"v.io/x/ref/lib/signals"
 	_ "v.io/x/ref/profiles/roaming"
 )
@@ -41,9 +38,9 @@
 	}
 
 	// TODO(sadovsky): Use a real Permissions.
-	service := server.NewService(memstore.New())
-	if err := service.Create(access.Permissions{}); err != nil {
-		vlog.Fatal("service.Create() failed: ", err)
+	service, err := server.NewService(nil, nil, access.Permissions{})
+	if err != nil {
+		vlog.Fatal("server.NewService() failed: ", err)
 	}
 	d := server.NewDispatcher(service)