Repository: scionproto/scion
Pull request #3778 (2020-06-08 13:24:21)

Colibri store backend
Introduces the storage interface.
- [x] Interface
- [x] Rebase after #3776 . First real commit here is `8c91bd7` "DB interface for storage"

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/scionproto/scion/3778)
<!-- Reviewable:end -->



Patch:
diff --git a/go/cs/reservation/segment/path.go b/go/cs/reservation/segment/path.go
index 0c45feb19..190df4521 100644
--- a/go/cs/reservation/segment/path.go
+++ b/go/cs/reservation/segment/path.go
@@ -15,6 +15,9 @@
 package segment
 
 import (
+	"encoding/binary"
+	"io"
+
 	"github.com/scionproto/scion/go/lib/addr"
 	"github.com/scionproto/scion/go/lib/common"
 	"github.com/scionproto/scion/go/lib/serrors"
@@ -23,6 +26,25 @@ import (
 // Path represents a reservation path, in the reservation order.
 type Path []PathStepWithIA
 
+var _ io.Reader = (*Path)(nil)
+
+// NewPathFromRaw constructs a new Path from the byte representation.
+func NewPathFromRaw(buff []byte) (Path, error) {
+	if len(buff)%PathStepWithIALen != 0 {
+		return nil, serrors.New("buffer input is not a multiple of a path step", "len", len(buff))
+	}
+	steps := len(buff) / PathStepWithIALen
+	p := make(Path, steps)
+	for i := 0; i < steps; i++ {
+		offset := i * PathStepWithIALen
+		p[i].Ingress = common.IFIDType(binary.BigEndian.Uint64(buff[offset:]))
+		p[i].Egress = common.IFIDType(binary.BigEndian.Uint64(buff[offset+8:]))
+		p[i].IA = addr.IAFromRaw(buff[offset+16:])
+	}
+	return p, nil
+}
+
+// Validate returns an error if there is invalid data.
 func (p Path) Validate() error {
 	if len(p) < 2 {
 		return serrors.New("invalid path length", "len", len(p))
@@ -37,35 +59,84 @@ func (p Path) Validate() error {
 	return nil
 }
 
+// Equal returns true if both Path contain the same values.
 func (p Path) Equal(o Path) bool {
 	if len(p) != len(o) {
 		return false
 	}
 	for i := 0; i < len(p); i++ {
-		if !p[i].Equal(&o[i]) {
+		if p[i] != o[i] {
 			return false
 		}
 	}
 	return true
 }
 
+// GetSrcIA returns the source IA in the path or a zero IA if the path is nil (it's not the
+// source AS of the reservation and has no access to the Path of the reservation).
+// If the Path is not nil, it assumes is valid, i.e. it has at least length 2.
+func (p Path) GetSrcIA() addr.IA {
+	if len(p) == 0 {
+		return addr.IA{}
+	}
+	return p[0].IA
+}
+
+// GetDstIA returns the source IA in the path or a zero IA if the path is nil (it's not the
+// source AS of the reservation and has no access to the Path of the reservation).
+// If the Path is not nil, it assumes is valid, i.e. it has at least length 2.
+func (p Path) GetDstIA() addr.IA {
+	if len(p) == 0 {
+		return addr.IA{}
+	}
+	return p[len(p)-1].IA
+}
+
+// Len returns the length of this Path in bytes, when serialized.
+func (p Path) Len() int {
+	if len(p) == 0 {
+		return 0
+	}
+	return len(p) * PathStepWithIALen
+}
+
+func (p Path) Read(buff []byte) (int, error) {
+	if len(p) == 0 {
+		return 0, nil
+	}
+	if len(buff) < p.Len() {
+		return 0, serrors.New("buffer too small", "min_size", p.Len(), "actual_size", len(buff))
+	}
+	for i, s := range p {
+		offset := i * PathStepWithIALen
+		binary.BigEndian.PutUint64(buff[offset:], uint64(s.Ingress))
+		binary.BigEndian.PutUint64(buff[offset+8:], uint64(s.Egress))
+		binary.BigEndian.PutUint64(buff[offset+16:], uint64(s.IA.IAInt()))
+	}
+	return p.Len(), nil
+}
+
+// ToRaw returns a buffer representing this Path.
+func (p Path) ToRaw() []byte {
+	if len(p) == 0 {
+		return []byte{}
+	}
+	buff := make([]byte, p.Len())
+	p.Read(buff)
+	return buff
+}
+
 // PathStep is one hop of the Path. For a source AS Ingress will be invalid. Conversely for dst.
 type PathStep struct {
-	// IA      addr.IA
 	Ingress common.IFIDType
 	Egress  common.IFIDType
 }
 
-func (s *PathStep) Equal(o *PathStep) bool {
-	// return s.IA == o.IA && s.Ingress == o.Ingress && s.Egress == o.Egress
-	return s.Ingress == o.Ingress && s.Egress == o.Egress
-}
-
+// PathStepWithIA is a step in a reservation path as seen from the source AS.
 type PathStepWithIA struct {
 	PathStep
 	IA addr.IA
 }
 
-func (s *PathStepWithIA) Equal(o *PathStepWithIA) bool {
-	return s.PathStep.Equal(&o.PathStep) && s.IA == o.IA
-}
+// PathStepWithIALen amounts for Ingress+Egress+IA.
+const PathStepWithIALen = 8 + 8 + 8
diff --git a/go/cs/reservation/segment/request.go b/go/cs/reservation/segment/request.go
index 506a1f40c..d33123491 100644
--- a/go/cs/reservation/segment/request.go
+++ b/go/cs/reservation/segment/request.go
@@ -30,8 +30,8 @@ type Request struct {
 	Metadata    base.RequestMetadata  // information about the request (forwarding path)
 	ID          reservation.SegmentID // the ID this request refers to
 	Timestamp   time.Time             // the mandatory timestamp
-	IngressIFID common.IFIDType       // the interface the reservation traffic uses to enter the AS
-	EgressIFID  common.IFIDType       // the interface the reservation traffic uses to leave the AS
+	Ingress     common.IFIDType       // the interface the reservation traffic uses to enter the AS
+	Egress      common.IFIDType       // the interface the reservation traffic uses to leave the AS
 	Reservation *Reservation          // nil if no reservation yet
 }
 
@@ -64,11 +64,11 @@ func NewRequest(ts time.Time, ID *colibri_mgmt.SegmentReservationID,
 		return nil, serrors.WrapStr("new segment request", err)
 	}
 	return &Request{
-		Timestamp:   ts,
-		Metadata:    *metadata,
-		ID:          *segID,
-		IngressIFID: ingressIFID,
-		EgressIFID:  egressIFID,
+		Timestamp: ts,
+		Metadata:  *metadata,
+		ID:        *segID,
+		Ingress:   ingressIFID,
+		Egress:    egressIFID,
 	}, nil
 }
 
diff --git a/go/cs/reservation/segment/reservation.go b/go/cs/reservation/segment/reservation.go
index 18c3715a7..238f0104f 100644
--- a/go/cs/reservation/segment/reservation.go
+++ b/go/cs/reservation/segment/reservation.go
@@ -19,16 +19,20 @@ import (
 
 	base "github.com/scionproto/scion/go/cs/reservation"
 	"github.com/scionproto/scion/go/lib/colibri/reservation"
+	"github.com/scionproto/scion/go/lib/common"
 	"github.com/scionproto/scion/go/lib/serrors"
 )
 
 // Reservation represents a segment reservation.
 type Reservation struct {
-	ID          reservation.SegmentID
-	Indices     Indices  // existing indices in this reservation
-	activeIndex int      // -1 <= activeIndex < len(Indices)
-	PathStep    PathStep // Ingress and Egress interfaces
-	Path        *Path    // nil if this AS is not at the source of the reservation
+	ID           reservation.SegmentID
+	Indices      Indices                  // existing indices in this reservation
+	activeIndex  int                      // -1 <= activeIndex < len(Indices)
+	Ingress      common.IFIDType          // igress interface ID: reservation packets enter
+	Egress       common.IFIDType          // egress interface ID: reservation packets leave
+	Path         Path                     // empty if not at the source of the reservation
+	PathEndProps reservation.PathEndProps // the properties for stitching and start/end
+	TrafficSplit reservation.SplitCls     // the traffic split between control and data planes
 }
 
 func NewReservation() *Reservation {
@@ -62,16 +66,23 @@ func (r *Reservation) Validate() error {
 	}
 	var err error
 	if r.Path != nil {
-		if r.PathStep.Ingress != 0 {
+		if r.Ingress != 0 {
 			return serrors.New("reservation starts in this AS but ingress interface is not zero",
-				"ingress_if", r.PathStep.Ingress)
+				"ingress_if", r.Ingress)
 			// TODO(juagargi) test
 		}
 		err = r.Path.Validate()
-	} else if r.PathStep.Ingress == 0 {
+	} else if r.Ingress == 0 {
 		return serrors.New("reservation does not start in this AS but ingress interface is zero")
 	}
-	return err
+	if err != nil {
+		return serrors.WrapStr("validating reservation, path failed", err)
+	}
+	err = r.PathEndProps.Validate()
+	if err != nil {
+		return serrors.WrapStr("validating reservation, end properties failed", err)
+	}
+	return nil
 }
 
 // ActiveIndex returns the currently active Index for this reservation, or nil if none.
diff --git a/go/cs/reservation/sqlite/BUILD.bazel b/go/cs/reservation/sqlite/BUILD.bazel
new file mode 100644
index 000000000..fda2ab149
--- /dev/null
+++ b/go/cs/reservation/sqlite/BUILD.bazel
@@ -0,0 +1,37 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+
+go_library(
+    name = "go_default_library",
+    srcs = [
+        "db.go",
+        "schema.go",
+    ],
+    importpath = "github.com/scionproto/scion/go/cs/reservation/sqlite",
+    visibility = ["//visibility:public"],
+    deps = [
+        "//go/cs/reservation/e2e:go_default_library",
+        "//go/cs/reservation/segment:go_default_library",
+        "//go/cs/reservationstorage/backend:go_default_library",
+        "//go/lib/addr:go_default_library",
+        "//go/lib/colibri/reservation:go_default_library",
+        "//go/lib/common:go_default_library",
+        "//go/lib/infra/modules/db:go_default_library",
+        "//go/lib/serrors:go_default_library",
+        "@com_github_mattn_go_sqlite3//:go_default_library",
+    ],
+)
+
+go_test(
+    name = "go_default_test",
+    srcs = ["db_test.go"],
+    embed = [":go_default_library"],
+    deps = [
+        "//go/cs/reservation/reservationdbtest:go_default_library",
+        "//go/cs/reservation/segment:go_default_library",
+        "//go/lib/addr:go_default_library",
+        "//go/lib/colibri/reservation:go_default_library",
+        "//go/lib/xtest:go_default_library",
+        "@com_github_mattn_go_sqlite3//:go_default_library",
+        "@com_github_stretchr_testify//require:go_default_library",
+    ],
+)
diff --git a/go/cs/reservation/sqlite/db.go b/go/cs/reservation/sqlite/db.go
new file mode 100644
index 000000000..a8e11bcfe
--- /dev/null
+++ b/go/cs/reservation/sqlite/db.go
@@ -0,0 +1,283 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package sqlite
+
+import (
+	"context"
+	"database/sql"
+	"encoding/binary"
+	"sync"
+	"time"
+
+	"github.com/mattn/go-sqlite3"
+	_ "github.com/mattn/go-sqlite3"
+
+	"github.com/scionproto/scion/go/cs/reservation/e2e"
+	"github.com/scionproto/scion/go/cs/reservation/segment"
+	"github.com/scionproto/scion/go/cs/reservationstorage/backend"
+	"github.com/scionproto/scion/go/lib/addr"
+	"github.com/scionproto/scion/go/lib/colibri/reservation"
+	"github.com/scionproto/scion/go/lib/common"
+	"github.com/scionproto/scion/go/lib/infra/modules/db"
+	"github.com/scionproto/scion/go/lib/serrors"
+)
+
+type Backend struct {
+	*executor
+	db *sql.DB
+}
+
+var _ backend.DB = (*Backend)(nil)
+
+// New returns a new SQLite backend opening a database at the given path. If
+// no database exists a new database is be created. If the schema version of the
+// stored database is different from the one in schema.go, an error is returned.
+func New(path string) (*Backend, error) {
+	db, err := db.NewSqlite(path, Schema, SchemaVersion)
+	if err != nil {
+		return nil, err
+	}
+	return &Backend{
+		executor: &executor{
+			db: db,
+		},
+		db: db,
+	}, nil
+}
+
+// SetMaxOpenConns sets the maximum number of open connections.
+func (b *Backend) SetMaxOpenConns(maxOpenConns int) {
+	b.db.SetMaxOpenConns(maxOpenConns)
+}
+
+// SetMaxIdleConns sets the maximum number of idle connections.
+func (b *Backend) SetMaxIdleConns(maxIdleConns int) {
+	b.db.SetMaxIdleConns(maxIdleConns)
+}
+
+// BeginTransaction begins a transaction on the database.
+func (b *Backend) BeginTransaction(ctx context.Context, opts *sql.TxOptions) (
+	backend.Transaction, error) {
+
+	b.Lock()
+	defer b.Unlock()
+	tx, err := b.db.BeginTx(ctx, opts)
+	if err != nil {
+		return nil, db.NewTxError("create tx", err)
+	}
+	return &transaction{
+		executor: &executor{
+			db: tx,
+		},
+		tx: tx,
+	}, nil
+}
+
+// Close closes the databse.
+func (b *Backend) Close() error {
+	return b.db.Close()
+}
+
+type transaction struct {
+	*executor
+	tx *sql.Tx
+}
+
+var _ backend.Transaction = (*transaction)(nil)
+
+func (t *transaction) Commit() error {
+	t.Lock()
+	defer t.Unlock()
+	return t.tx.Commit()
+}
+
+func (t *transaction) Rollback() error {
+	t.Lock()
+	defer t.Unlock()
+	return t.tx.Rollback()
+}
+
+type executor struct {
+	sync.RWMutex
+	db db.Sqler
+}
+
+func (x *executor) GetSegmentRsvFromID(ctx context.Context, ID reservation.SegmentID,
+	idx *reservation.IndexNumber) (*segment.Reservation, error) {
+
+	return nil, nil
+}
+
+// GetSegmentRsvFromSrcDstAS returns all reservations that start at src AS and end in dst AS.
+func (x *executor) GetSegmentRsvFromSrcDstAS(ctx context.Context, srcIA, dstIA addr.IA) (
+	[]*segment.Reservation, error) {
+
+	x.Lock()
+	defer x.Unlock()
+
+	query := `SELECT r.reservation_id, r.ingress, r.egress
+	FROM seg_reservation r
+	WHERE r.src_as = ?1 AND r.dst_as = ?2`
+	rows, err := x.db.QueryContext(ctx, query, srcIA.IAInt(), dstIA.IAInt())
+	if err != nil {
+		return nil, db.NewReadError("error obtaining segment reservations", err)
+	}
+	defer rows.Close()
+	for rows.Next() {
+		if err := rows.Scan(); err != nil {
+			return nil, db.NewReadError("error reading segment reservation", err)
+		}
+	}
+	return nil, nil
+}
+
+// GetSegmentRsvFromPath searches for a segment reservation with the specified path.
+func (x *executor) GetSegmentRsvFromPath(ctx context.Context, path *segment.Path) (
+	*segment.Reservation, error) {
+
+	return nil, nil
+}
+
+// GetSegmentRsvsFromIFPair returns all segment reservations that enter this AS at
+// the specified ingress and exit at that egress.
+func (x *executor) GetSegmentRsvsFromIFPair(ctx context.Context, ingress, egress common.IFIDType) (
+	[]*segment.Reservation, error) {
+
+	return nil, nil
+}
+
+func insertNewSegReservation(ctx context.Context, x db.Sqler, rsv *segment.Reservation,
+	suffix uint32) error {
+	const query = `INSERT INTO seg_reservation (id_as, id_suffix, ingress ,egress,
+		path, src_as, dst_as) VALUES ($1, $2, $3, $4, $5, $6, $7)`
+	_, err := x.ExecContext(ctx, query, rsv.Path.GetSrcIA().A, suffix,
+		rsv.Ingress, rsv.Egress,
+		rsv.Path.ToRaw(), rsv.Path.GetSrcIA().IAInt(), rsv.Path.GetDstIA().IAInt())
+	return err
+}
+
+// NewSegmentRsv creates a new segment reservation in the DB, with an unused reservation ID.
+// The created ID is set in the reservation pointer argument.
+func (x *executor) NewSegmentRsv(ctx context.Context, rsv *segment.Reservation) error {
+	var err error
+	for retries := 0; retries < 3; retries++ {
+		err = db.DoInTx(ctx, x.db, func(ctx context.Context, tx *sql.Tx) error {
+			suffix, err := newSuffix(ctx, tx, rsv.ID.ASID)
+			if err != nil {
+				return err
+			}
+			if err := insertNewSegReservation(ctx, tx, rsv, suffix); err != nil {
+				return err
+			}
+			binary.BigEndian.PutUint32(rsv.ID.Suffix[:], suffix)
+			return nil
+		})
+		if err == nil {
+			return nil
+		}
+		sqliteError, ok := err.(sqlite3.Error)
+		if !ok || sqliteError.Code != sqlite3.ErrConstraint {
+			return db.NewTxError("error inserting segment reservation", err)
+		}
+	}
+	return db.NewTxError("error inserting segment reservation after 3 retries", err)
+}
+
+// SetActiveIndex updates the active index for the segment reservation.
+func (x *executor) SetSegmentActiveIndex(ctx context.Context, rsv segment.Reservation,
+	idx reservation.IndexNumber) error {
+
+	return nil
+}
+
+// NewSegmentRsvIndex stores a new index for a segment reservation.
+func (x *executor) NewSegmentIndex(ctx context.Context, rsv *segment.Reservation,
+	idx reservation.IndexNumber) error {
+
+	return nil
+}
+
+// UpdateSegmentRsvIndex updates an index of a segment reservation.
+func (x *executor) UpdateSegmentIndex(ctx context.Context, rsv *segment.Reservation,
+	idx reservation.IndexNumber) error {
+
+	return nil
+}
+
+// DeleteSegmentIndex removes the index from the DB. Used in cleanup.
+func (x *executor) DeleteSegmentIndex(ctx context.Context, rsv *segment.Reservation,
+	idx reservation.IndexNumber) error {
+
+	return nil
+}
+
+// DeleteExpiredIndices will remove expired indices from the DB. If a reservation is left
+// without any index after removing the expired ones, it will also be removed.
+func (x *executor) DeleteExpiredIndices(ctx context.Context, now time.Time) (int, error) {
+	return 0, nil
+}
+
+// DeleteSegmentRsv removes the segment reservation
+func (x *executor) DeleteSegmentRsv(ctx context.Context, ID reservation.SegmentID) error {
+	return nil
+}
+
+// GetE2ERsvFromID finds the end to end resevation given its ID.
+func (x *executor) GetE2ERsvFromID(ctx context.Context, ID reservation.E2EID,
+	idx reservation.IndexNumber) (*e2e.Reservation, error) {
+
+	return nil, nil
+}
+
+// NewE2EIndex stores a new index in the DB.
+// If the e2e reservation does not exist, it is created.
+func (x *executor) NewE2EIndex(ctx context.Context, rsv *e2e.Reservation,
+	idx reservation.IndexNumber) error {
+
+	return nil
+}
+
+// UpdateE2EIndex updates the token in an index of the e2e reservation.
+func (x *executor) UpdateE2EIndex(ctx context.Context, rsv *e2e.Reservation,
+	idx reservation.IndexNumber) error {
+
+	return nil
+
+}
+
+// DeleteE2EIndex removes an e2e index. It is used in the cleanup process.
+func (x *executor) DeleteE2EIndex(ctx context.Context, rsv *e2e.Reservation,
+	idx reservation.IndexNumber) error {
+
+	return nil
+}
+
+// newSuffix finds a segment reservation ID suffix not being used at the moment. Should be called
+// inside a transaction so the suffix is not used in the meantime, or fail.
+func newSuffix(ctx context.Context, x db.Sqler, ASID addr.AS) (uint32, error) {
+	query := `SELECT MIN(id_suffix)+1 FROM (
+		SELECT 0 AS id_suffix UNION ALL
+		SELECT id_suffix FROM seg_reservation WHERE id_as = $1
+		) WHERE id_suffix+1 NOT IN (SELECT id_suffix FROM seg_reservation WHERE id_as = $1);`
+	var suffix uint32
+	err := x.QueryRowContext(ctx, query, uint64(ASID)).Scan(&suffix)
+	switch {
+	case err == sql.ErrNoRows:
+		return 0, serrors.New("unexpected error getting new suffix: no rows")
+	case err != nil:
+		return 0, serrors.WrapStr("unexpected error getting new suffix", err)
+	}
+	return suffix, nil
+}
diff --git a/go/cs/reservation/sqlite/schema.go b/go/cs/reservation/sqlite/schema.go
new file mode 100644
index 000000000..02e1fe5e2
--- /dev/null
+++ b/go/cs/reservation/sqlite/schema.go
@@ -0,0 +1,68 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package sqlite
+
+const (
+	// SchemaVersion is the version of the SQLite schema understood by this backend.
+	// Whenever changes to the schema are made, this version number should be increased
+	// to prevent data corruption between incompatible database schemas.
+	SchemaVersion = 1
+	// Schema is the SQLite database layout.
+	// TODO(juagargi) explain the DB structure here or in the design markdown.
+	// TODO(juagargi) create appropriate SQL indices.
+	Schema = `CREATE TABLE seg_reservation (
+		row_id	INTEGER,
+		id_as	INTEGER NOT NULL,
+		id_suffix	INTEGER NOT NULL,
+		ingress	INTEGER NOT NULL,
+		egress	INTEGER NOT NULL,
+		path	BLOB,
+		src_as INTEGER,
+		dst_as INTEGER,
+		PRIMARY KEY(row_id),
+		UNIQUE(id_as,id_suffix)
+	);
+	CREATE TABLE seg_index (
+		reservation	INTEGER NOT NULL,
+		index_number	INTEGER NOT NULL,
+		expiration	INTEGER NOT NULL,
+		state	INTEGER NOT NULL,
+		min_bw	INTEGER NOT NULL,
+		max_bw	INTEGER NOT NULL,
+		alloc_bw	INTEGER NOT NULL,
+		token	BLOB,
+		PRIMARY KEY(Reservation,index_number),
+		FOREIGN KEY(reservation) REFERENCES seg_reservation(row_id) ON DELETE CASCADE
+	);
+	CREATE TABLE e2e_reservation (
+		row_id	INTEGER,
+		reservation_id	BLOB NOT NULL,
+		PRIMARY KEY(row_id)
+	);
+	CREATE TABLE e2e_index (
+		reservation	INTEGER NOT NULL,
+		index_number	INTEGER NOT NULL,
+		expiration	INTEGER NOT NULL,
+		alloc_bw	INTEGER NOT NULL,
+		token	BLOB NOT NULL,
+		FOREIGN KEY(reservation) REFERENCES e2e_reservation(row_id) ON DELETE CASCADE
+	);
+	CREATE TABLE e2e_to_seg (
+		e2e	INTEGER NOT NULL,
+		seg	INTEGER NOT NULL,
+		FOREIGN KEY(seg) REFERENCES seg_reservation(row_id) ON DELETE CASCADE,
+		FOREIGN KEY(e2e) REFERENCES e2e_reservation(row_id) ON DELETE CASCADE
+	);`
+)
diff --git a/go/cs/reservationstorage/backend/BUILD.bazel b/go/cs/reservationstorage/backend/BUILD.bazel
new file mode 100644
index 000000000..e680baf9e
--- /dev/null
+++ b/go/cs/reservationstorage/backend/BUILD.bazel
@@ -0,0 +1,16 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library")
+
+go_library(
+    name = "go_default_library",
+    srcs = ["db.go"],
+    importpath = "github.com/scionproto/scion/go/cs/reservationstorage/backend",
+    visibility = ["//visibility:public"],
+    deps = [
+        "//go/cs/reservation/e2e:go_default_library",
+        "//go/cs/reservation/segment:go_default_library",
+        "//go/lib/addr:go_default_library",
+        "//go/lib/colibri/reservation:go_default_library",
+        "//go/lib/common:go_default_library",
+        "//go/lib/infra/modules/db:go_default_library",
+    ],
+)
diff --git a/go/cs/reservationstorage/backend/db.go b/go/cs/reservationstorage/backend/db.go
new file mode 100644
index 000000000..2afdf2467
--- /dev/null
+++ b/go/cs/reservationstorage/backend/db.go
@@ -0,0 +1,109 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package backend
+
+import (
+	"context"
+	"database/sql"
+	"io"
+	"time"
+
+	"github.com/scionproto/scion/go/cs/reservation/e2e"
+	"github.com/scionproto/scion/go/cs/reservation/segment"
+	"github.com/scionproto/scion/go/lib/addr"
+	"github.com/scionproto/scion/go/lib/colibri/reservation"
+	"github.com/scionproto/scion/go/lib/common"
+	"github.com/scionproto/scion/go/lib/infra/modules/db"
+)
+
+// ReserverOnly has the methods available to the AS that starts the reservation.
+type ReserverOnly interface {
+	// GetSegmentRsvFromSrcDstAS returns all reservations that start at src AS and end in dst AS.
+	GetSegmentRsvFromSrcDstAS(ctx context.Context, srcIA, dstIA addr.IA) (
+		[]*segment.Reservation, error)
+	// GetSegmentRsvFromPath searches for a segment reservation with the specified path.
+	GetSegmentRsvFromPath(ctx context.Context, path *segment.Path) (
+		*segment.Reservation, error)
+
+	// NewSegmentRsv creates a new segment reservation in the DB, with an unused reservation ID.
+	// The created ID is set in the reservation pointer argument. Used by setup req.
+	NewSegmentRsv(ctx context.Context, rsv *segment.Reservation) error
+}
+
+// TransitOnly represents an AS in-path of a reservation, not the one originating it.
+type TransitOnly interface {
+	// GetSegmentRsvsFromIFPair returns all segment reservations that enter this AS at
+	// the specified ingress and exit at that egress. Used by setup req.
+	GetSegmentRsvsFromIFPair(ctx context.Context, ingress, egress common.IFIDType) (
+		[]*segment.Reservation, error)
+}
+
+// ReserverAndTransit contains the functionality for any AS that has a COLIBRI service.
+type ReserverAndTransit interface {
+	// GetSegmentRsvFromID will return the reservation with that ID.
+	// If an IndexNumber is specified it will populate its indices only with that one.
+	// If the ID is not found, or the index (if specified) is not found, an error will be returned.
+	// Used by setup/renew req/resp. and any request.
+	GetSegmentRsvFromID(ctx context.Context, ID reservation.SegmentID,
+		idx *reservation.IndexNumber) (*segment.Reservation, error)
+	// SetActiveIndex updates the active index. Used in index confirmation.
+	SetSegmentActiveIndex(ctx context.Context, rsv segment.Reservation,
+		idx reservation.IndexNumber) error
+	// NewSegmentRsvIndex stores a new index for a segment reservation. Used in setup/renew.
+	NewSegmentIndex(ctx context.Context, rsv *segment.Reservation,
+		idx reservation.IndexNumber) error
+	// UpdateSegmentRsvIndex updates an index of a segment rsv. Used in setup/renew response.
+	UpdateSegmentIndex(ctx context.Context, rsv *segment.Reservation,
+		idx reservation.IndexNumber) error
+	// DeleteSegmentIndex removes the index from the DB. Used in cleanup.
+	DeleteSegmentIndex(ctx context.Context, rsv *segment.Reservation,
+		idx reservation.IndexNumber) error
+	// DeleteSegmentRsv removes the segment reservation. Used in teardown.
+	DeleteSegmentRsv(ctx context.Context, ID reservation.SegmentID) error
+
+	// DeleteExpiredIndices will remove expired indices from the DB. If a reservation is left
+	// without any index after removing the expired ones, it will also be removed.
+	// Used on schedule.
+	DeleteExpiredIndices(ctx context.Context, now time.Time) (int, error)
+
+	// GetE2ERsvFromID finds the end to end resevation given its ID.
+	GetE2ERsvFromID(ctx context.Context, ID reservation.E2EID, idx reservation.IndexNumber) (
+		*e2e.Reservation, error)
+	// NewE2EIndex stores a new index in the DB.
+	// If the e2e reservation does not exist, it is created.
+	NewE2EIndex(ctx context.Context, rsv *e2e.Reservation, idx reservation.IndexNumber) error
+	// UpdateE2EIndex updates the token in an index of the e2e reservation.
+	UpdateE2EIndex(ctx context.Context, rsv *e2e.Reservation, idx reservation.IndexNumber) error
+	// DeleteE2EIndex removes an e2e index. It is used in the cleanup process.
+	DeleteE2EIndex(ctx context.Context, rsv *e2e.Reservation, idx reservation.IndexNumber) error
+}
+
+type Transaction interface {
+	ReserverOnly
+	TransitOnly
+	ReserverAndTransit
+	Commit() error
+	Rollback() error
+}
+
+// DB is the interface for any reservation backend.
+type DB interface {
+	BeginTransaction(ctx context.Context, opts *sql.TxOptions) (Transaction, error)
+	ReserverOnly
+	TransitOnly
+	ReserverAndTransit
+	db.LimitSetter
+	io.Closer
+}


Test patch:
diff --git a/go/cs/reservation/e2e/reservation_test.go b/go/cs/reservation/e2e/reservation_test.go
index de2601409..30d2094a6 100644
--- a/go/cs/reservation/e2e/reservation_test.go
+++ b/go/cs/reservation/e2e/reservation_test.go
@@ -46,7 +46,7 @@ func TestValidate(t *testing.T) {
 
 	// invalid segment reservation
 	r = newReservation()
-	r.SegmentReservations[0].Path = &segment.Path{}
+	r.SegmentReservations[0].Path = segment.Path{}
 	err = r.Validate()
 	require.Error(t, err)
 
@@ -93,8 +93,7 @@ func newSegmentReservation(asidPath ...string) *segment.Reservation {
 		pathComponents[i*3+2] = i*2 + 1
 	}
 	pathComponents[len(pathComponents)-1] = 0
-	p := segmenttest.NewPathFromComponents(pathComponents...)
-	r.Path = &p
+	r.Path = segmenttest.NewPathFromComponents(pathComponents...)
 	return r
 }
 
diff --git a/go/cs/reservation/reservationdbtest/BUILD.bazel b/go/cs/reservation/reservationdbtest/BUILD.bazel
new file mode 100644
index 000000000..fce894ec7
--- /dev/null
+++ b/go/cs/reservation/reservationdbtest/BUILD.bazel
@@ -0,0 +1,15 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library")
+
+go_library(
+    name = "go_default_library",
+    srcs = ["reservationdbtest.go"],
+    importpath = "github.com/scionproto/scion/go/cs/reservation/reservationdbtest",
+    visibility = ["//visibility:public"],
+    deps = [
+        "//go/cs/reservation/segment:go_default_library",
+        "//go/cs/reservation/segmenttest:go_default_library",
+        "//go/cs/reservationstorage/backend:go_default_library",
+        "//go/lib/xtest:go_default_library",
+        "@com_github_stretchr_testify//require:go_default_library",
+    ],
+)
diff --git a/go/cs/reservation/reservationdbtest/reservationdbtest.go b/go/cs/reservation/reservationdbtest/reservationdbtest.go
new file mode 100644
index 000000000..c97eba3dc
--- /dev/null
+++ b/go/cs/reservation/reservationdbtest/reservationdbtest.go
@@ -0,0 +1,55 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package reservationdbtest
+
+import (
+	"context"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+
+	"github.com/scionproto/scion/go/cs/reservation/segment"
+	"github.com/scionproto/scion/go/cs/reservation/segmenttest"
+	"github.com/scionproto/scion/go/cs/reservationstorage/backend"
+	"github.com/scionproto/scion/go/lib/xtest"
+)
+
+type TestableDB interface {
+	backend.DB
+	Prepare(*testing.T, context.Context)
+}
+
+func TestDB(t *testing.T, db TestableDB) {
+	tests := map[string]func(context.Context, *testing.T, backend.DB){
+		"insert segment reservations create ID": testNewSegmentReservation,
+	}
+	for name, test := range tests {
+		t.Run(name, func(t *testing.T) {
+			ctx := context.Background()
+			db.Prepare(t, ctx)
+			test(ctx, t, db)
+		})
+	}
+}
+
+func testNewSegmentReservation(ctx context.Context, t *testing.T, db backend.DB) {
+	r := segment.NewReservation()
+	r.Egress = 1
+	r.Path = segmenttest.NewPathFromComponents(0, "1-ff00:0:1", 1, 1, "1-ff00:0:2", 0)
+	r.ID.ASID = xtest.MustParseAS("ff00:0:1")
+	err := db.NewSegmentRsv(ctx, r)
+	require.NoError(t, err)
+	require.Equal(t, xtest.MustParseHexString("00000001"), r.ID.Suffix[:])
+}
diff --git a/go/cs/reservation/segment/path_test.go b/go/cs/reservation/segment/path_test.go
index 8d9c22764..f3d83b94a 100644
--- a/go/cs/reservation/segment/path_test.go
+++ b/go/cs/reservation/segment/path_test.go
@@ -21,6 +21,7 @@ import (
 
 	"github.com/scionproto/scion/go/cs/reservation/segment"
 	"github.com/scionproto/scion/go/cs/reservation/segmenttest"
+	"github.com/scionproto/scion/go/lib/xtest"
 )
 
 func TestValidatePath(t *testing.T) {
@@ -73,6 +74,16 @@ func TestEqualPath(t *testing.T) {
 				1, "1-ff00:0:2", 0),
 			IsEqual: true,
 		},
+		"eq3": {
+			Path1:   nil,
+			Path2:   nil,
+			IsEqual: true,
+		},
+		"eq4": {
+			Path1:   nil,
+			Path2:   make(segment.Path, 0),
+			IsEqual: true,
+		},
 		"neq1": {
 			Path1:   segmenttest.NewPathFromComponents(0, "1-ff00:0:1", 1, 1, "1-ff00:0:2", 0),
 			Path2:   segmenttest.NewPathFromComponents(1, "1-ff00:0:1", 1, 1, "1-ff00:0:2", 0),
@@ -104,3 +115,62 @@ func TestEqualPath(t *testing.T) {
 		})
 	}
 }
+
+func TestGetIAs(t *testing.T) {
+	p := segmenttest.NewPathFromComponents(0, "1-ff00:0:1", 1, 1, "1-ff00:0:2", 0)
+	require.Equal(t, xtest.MustParseIA("1-ff00:0:1"), p.GetSrcIA())
+	require.Equal(t, xtest.MustParseIA("1-ff00:0:2"), p.GetDstIA())
+	p = nil
+	require.Equal(t, xtest.MustParseIA("0-0"), p.GetSrcIA())
+	require.Equal(t, xtest.MustParseIA("0-0"), p.GetDstIA())
+	p = make(segment.Path, 0)
+	require.Equal(t, xtest.MustParseIA("0-0"), p.GetSrcIA())
+	require.Equal(t, xtest.MustParseIA("0-0"), p.GetDstIA())
+}
+
+func TestPathLen(t *testing.T) {
+	p := segmenttest.NewPathFromComponents(0, "1-ff00:0:1", 1, 1, "1-ff00:0:2", 0)
+	require.Equal(t, 8*6, p.Len())
+	p = segment.Path{}
+	require.Equal(t, 0, p.Len())
+	p = nil
+	require.Equal(t, 0, p.Len())
+	p = make(segment.Path, 0)
+	require.Equal(t, 0, p.Len())
+}
+
+func TestToFromBinary(t *testing.T) {
+	p := segmenttest.NewPathFromComponents(0, "1-ff00:0:1", 1, 1, "1-ff00:0:2", 0)
+	var buff []byte
+	_, err := p.Read(buff)
+	require.Error(t, err)
+	_, err = p.Read(buff)
+	require.Error(t, err)
+	buff = make([]byte, 2*3*8)
+	c, err := p.Read(buff)
+	require.NoError(t, err)
+	require.Equal(t, 2*3*8, c)
+
+	anotherP, err := segment.NewPathFromRaw(buff)
+	require.NoError(t, err)
+	require.Equal(t, p, anotherP)
+
+	anotherBuff := p.ToRaw()
+	require.Equal(t, buff, anotherBuff)
+	// wrong buffer
+	buff = buff[:len(buff)-1]
+	_, err = segment.NewPathFromRaw(buff)
+	require.Error(t, err)
+	// empty and nil buffer
+	p, err = segment.NewPathFromRaw(nil)
+	require.NoError(t, err)
+	require.Empty(t, p)
+	p, err = segment.NewPathFromRaw([]byte{})
+	require.NoError(t, err)
+	require.Empty(t, p)
+	// empty and nil path
+	p = nil
+	require.Empty(t, p.ToRaw())
+	p = make(segment.Path, 0)
+	require.Empty(t, p.ToRaw())
+}
diff --git a/go/cs/reservation/segment/request_test.go b/go/cs/reservation/segment/request_test.go
index 259b679bd..e54d0066a 100644
--- a/go/cs/reservation/segment/request_test.go
+++ b/go/cs/reservation/segment/request_test.go
@@ -42,8 +42,8 @@ func TestNewSetupReqFromCtrlMsg(t *testing.T) {
 	require.NoError(t, err)
 	require.Equal(t, *p, r.Metadata.Path)
 	checkRequest(t, ctrlMsg, r, ts)
-	require.Equal(t, common.IFIDType(1), r.IngressIFID)
-	require.Equal(t, common.IFIDType(2), r.EgressIFID)
+	require.Equal(t, common.IFIDType(1), r.Ingress)
+	require.Equal(t, common.IFIDType(2), r.Egress)
 }
 
 func TestRequestToCtrlMsg(t *testing.T) {
diff --git a/go/cs/reservation/segment/reservation_test.go b/go/cs/reservation/segment/reservation_test.go
index 1e9e851a0..1ee97f7ac 100644
--- a/go/cs/reservation/segment/reservation_test.go
+++ b/go/cs/reservation/segment/reservation_test.go
@@ -109,7 +109,7 @@ func TestReservationValidate(t *testing.T) {
 	require.Error(t, err)
 
 	// wrong path
-	r.Path = &segment.Path{}
+	r.Path = segment.Path{}
 	err = r.Validate()
 	require.Error(t, err)
 
@@ -165,7 +165,7 @@ func TestReservationValidate(t *testing.T) {
 
 	// starts in this AS but ingress nonzero
 	r = segmenttest.NewReservation()
-	r.PathStep.Ingress = 1
+	r.Ingress = 1
 	err = r.Validate()
 	require.Error(t, err)
 
diff --git a/go/cs/reservation/segmenttest/common.go b/go/cs/reservation/segmenttest/common.go
index a581d01c1..24294f203 100644
--- a/go/cs/reservation/segmenttest/common.go
+++ b/go/cs/reservation/segmenttest/common.go
@@ -44,9 +44,8 @@ func NewReservation() *segment.Reservation {
 	if err != nil {
 		panic(err)
 	}
-	p := NewPathFromComponents(0, "1-ff00:0:1", 1, 1, "1-ff00:0:2", 0)
 	r := segment.NewReservation()
 	r.ID = *segID
-	r.Path = &p
+	r.Path = NewPathFromComponents(0, "1-ff00:0:1", 1, 1, "1-ff00:0:2", 0)
 	return r
 }
diff --git a/go/cs/reservation/sqlite/db_test.go b/go/cs/reservation/sqlite/db_test.go
new file mode 100644
index 000000000..4ae32288f
--- /dev/null
+++ b/go/cs/reservation/sqlite/db_test.go
@@ -0,0 +1,117 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package sqlite
+
+import (
+	"context"
+	"testing"
+
+	"github.com/mattn/go-sqlite3"
+	"github.com/stretchr/testify/require"
+
+	"github.com/scionproto/scion/go/cs/reservation/reservationdbtest"
+	"github.com/scionproto/scion/go/cs/reservation/segment"
+	"github.com/scionproto/scion/go/lib/addr"
+	"github.com/scionproto/scion/go/lib/colibri/reservation"
+	"github.com/scionproto/scion/go/lib/xtest"
+)
+
+type TestDB struct {
+	*Backend
+}
+
+func (b *TestDB) Prepare(t *testing.T, _ context.Context) {
+	b.Backend = newDB(t)
+}
+
+func TestReservationDBSuite(t *testing.T) {
+	db := &TestDB{}
+	reservationdbtest.TestDB(t, db)
+}
+
+func TestNewSuffix(t *testing.T) {
+	ctx := context.Background()
+	asid := xtest.MustParseAS("ff00:0:1")
+	db := newDB(t)
+	suffix, err := newSuffix(ctx, db.db, asid)
+	require.NoError(t, err)
+	require.Equal(t, uint32(1), suffix)
+	// add reservations
+	addSegRsvRows(t, db, asid, 3, 5)
+	suffix, err = newSuffix(ctx, db.db, asid)
+	require.NoError(t, err)
+	require.Equal(t, uint32(1), suffix)
+	addSegRsvRows(t, db, asid, 1, 2)
+	suffix, err = newSuffix(ctx, db.db, asid)
+	require.NoError(t, err)
+	require.Equal(t, uint32(6), suffix)
+}
+
+func TestRaceForSuffix(t *testing.T) {
+	ctx := context.Background()
+	asid := xtest.MustParseAS("ff00:0:1")
+	db := newDB(t)
+	addSegRsvRows(t, db, asid, 1, 2)
+	suffix1, err := newSuffix(ctx, db.db, asid)
+	require.NoError(t, err)
+	require.Equal(t, uint32(3), suffix1)
+	suffix2, err := newSuffix(ctx, db.db, asid)
+	require.NoError(t, err)
+	require.Equal(t, uint32(3), suffix2)
+	rsv := &segment.Reservation{
+		ID: reservation.SegmentID{ASID: asid},
+	}
+	err = insertNewSegReservation(ctx, db.db, rsv, suffix1)
+	require.NoError(t, err)
+	err = insertNewSegReservation(ctx, db.db, rsv, suffix2)
+	require.Error(t, err)
+	sqliteError, ok := err.(sqlite3.Error)
+	require.True(t, ok)
+	require.Equal(t, sqlite3.ErrConstraint, sqliteError.Code)
+}
+
+func BenchmarkNewSuffix10K(b *testing.B)  { benchmarkNewSuffix(b, 10000) }
+func BenchmarkNewSuffix100K(b *testing.B) { benchmarkNewSuffix(b, 100000) }
+func BenchmarkNewSuffix1M(b *testing.B)   { benchmarkNewSuffix(b, 1000000) }
+
+func newDB(t testing.TB) *Backend {
+	db, err := New("file::memory:")
+	require.NoError(t, err)
+	return db
+}
+
+func addSegRsvRows(t testing.TB, b *Backend, asid addr.AS, firstSuffix, lastSuffix uint32) {
+	ctx := context.Background()
+	query := `INSERT INTO seg_reservation (id_as, id_suffix, ingress, egress, path,
+		src_as, dst_as) VALUES ($1, $2, $3, $4, $5, $6, $7)`
+	for suffix := firstSuffix; suffix <= lastSuffix; suffix++ {
+		_, err := b.db.ExecContext(ctx, query, asid, suffix, 0, 0, nil, nil, nil)
+		require.NoError(t, err)
+	}
+}
+
+func benchmarkNewSuffix(b *testing.B, entries uint32) {
+	db := newDB(b)
+	ctx := context.Background()
+	asid := xtest.MustParseAS("ff00:0:1")
+	addSegRsvRows(b, db, asid, 1, entries)
+	b.ResetTimer()
+
+	for n := 0; n < b.N; n++ {
+		suffix, err := newSuffix(ctx, db.db, asid)
+		require.NoError(b, err)
+		require.Equal(b, entries+1, suffix)
+	}
+}