Bigtable
Bigtable
| a | ... |
← | b | X |
| c | ... |
|
| | ... |
|
| a | ... |
→ | b | X' |
| c | ... |
Bigtable
| a | ... |
← | b1 | ... |
← | b2 | ... |
← | b3 | ... |
| c | ... |
Bigtable
| a | ... |
← | b | ... |
← | c | ... |
← | d | ... |
| e | ... |
Contents
Best practices
- Bigtable in one slide
- The Entities table
- Queries and indexes
- Kind index
- Single-property index
- Composite index
- Merge join
- Entity groups and transactions
The Entities table
- Primary table
- Stores all entities in all apps
- Generic, schemaless
- Row name is entity key
- Only column is serialized entity
Entity keys
- Entity key based on parent entities
- Root entity, then its child, then its child, ...
Entity keys
class Grandparent(db.Model): pass
class Parent(db.Model): pass
class Child(db.Model): pass
ethel = Grandparent()
jane = Parent(parent=ethel)
timmy = Child(parent=jane)
Entity keys
class Grandparent(db.Model): pass
class Parent(db.Model): pass
class Child(db.Model): pass
ethel = Grandparent()
jane = Parent(parent=ethel)
timmy = Child(parent=jane)
/Grandparent:Ethel
/Grandparent:Ethel/Parent:Jane
/Grandparent:Ethel/Parent:Jane/Child:Timmy
Entity keys
/Grandparent:Alice
/Grandparent:Alice/Parent:Sam
/Grandparent:Ethel
/Grandparent:Ethel/Parent:Jane
/Grandparent:Ethel/Parent:Jane/Child:Timmy
/Grandparent:Ethel/Parent:Jane/Child:William
/Grandparent:Frank
Contents
Best practices
- Bigtable in one slide
- The Entities table
- Queries and indexes
- Kind index
- Single-property index
- Composite index
- Merge join
- Entity groups and transactions
Queries
- kind
- property filters
- sort orders
- ancestor
Example queries
SELECT * FROM Person ...
WHERE name = 'John';
ORDER BY name DESC;
WHERE city = 'Sonoma' AND state = 'CA'
AND country = 'USA';
WHERE ANCESTOR IS :ethel ORDER BY name;
Indexes
- Separate Bigtable tables
- Map property values to entities
- Each row includes index data and entity key
Scanning indexes
filtering in memory
sorting in memory
- not even a little!
Query planning
- Goal: convert query to dense index scan
- Pick the index
- Compute the prefix or range
- Scan!
Contents
Best practices
- Bigtable in one slide
- The Entities table
- Queries and indexes
- Kind index
- Single-property index
- Composite index
- Merge join
- Entity groups and transactions
Kind index
- Serves queries for all entities of a given kind
- e.g.
SELECT * FROM Grandparent
Kind index
- Index data is kind
Kind | Key |
Child | Jimmy |
Child | Timmy |
Grandparent | Ethel |
Grandparent | Fred |
Parent | Jane |
Parent | John |
Parent | Todd |
Kind index
SELECT * FROM Grandparent
- Scan with prefix
Grandparent
Kind | Key |
Child | Jimmy |
Child | Timmy |
Grandparent | Ethel |
Grandparent | Fred |
Parent | Jane |
Parent | John |
Parent | Todd |
Contents
Best practices
- Bigtable in one slide
- The Entities table
- Queries and indexes
- Kind index
- Single-property index
- Composite index
- Merge join
- Entity groups and transactions
Single-property index
- Serves queries on a single property:
WHERE name = 'John'
ORDER BY name DESC
WHERE name >= 'B' AND name < 'C' ORDER BY name
- One ascending, one descending
Single-property index
- Index data is kind, property name, value
Kind | Name | Value |
Parent | address | 1 Palm Dr. |
Parent | name | Alice |
Parent | name | Bob |
Parent | name | Brad |
Parent | name | Chelsea |
Parent | name | Jane |
Parent | name | John |
Parent | title | Ninja Pirate |
Single-property index
- ...or descending
Kind | Name | Value DESC |
Parent | address | 1 Palm Dr. |
Parent | name | John |
Parent | name | Jane |
Parent | name | Chelsea |
Parent | name | Brad |
Parent | name | Bob |
Parent | name | Alice |
Parent | title | Ninja Pirate |
Single-property index
WHERE name = 'John'
- Scan with prefix
Parent name John
Kind | Name | Value |
Parent | address | 1 Palm Dr. |
Parent | name | Alice |
Parent | name | Bob |
Parent | name | Brad |
Parent | name | Chelsea |
Parent | name | Jane |
Parent | name | John |
Parent | title | Ninja Pirate |
Single-property index
ORDER BY name DESC
- Scan descending index with prefix
Parent name
:
Kind | Name | Value DESC |
Parent | address | 1 Palm Dr. |
Parent | name | John |
Parent | name | Jane |
Parent | name | Chelsea |
Parent | name | Brad |
Parent | name | Bob |
Parent | name | Alice |
Parent | title | Ninja Pirate |
Single-property index
WHERE name >= 'B' AND name < 'C'
ORDER BY name
- Scan range
[Parent name B, Parent name C)
:
Kind | Name | Value |
Parent | address | 1 Palm Dr. |
Parent | name | Alice |
Parent | name | Bob |
Parent | name | Brad |
Parent | name | Chelsea |
Parent | name | Jane |
Parent | name | John |
Parent | title | Ninja Pirate |
Contents
Best practices
- Bigtable in one slide
- The Entities table
- Queries and indexes
- Kind index
- Single-property index
- Composite index
- Merge join
- Entity groups and transactions
Composite index
- Defined in index.yaml
- Serve queries on multiple properties or ancestor
WHERE firstname = 'Ryan' AND lastname = 'Barrett'
WHERE firstname >= 'B' AND firstname < 'C'
AND lastname = 'Smith'
WHERE ANCESTOR IS :ethel ORDER BY firstname
Query planning
- Add kind to prefix
- Add ancestor, if any
- Add = filters, if any
- If any inequality filters, convert to range scan
- Add sort orders, if any
Composite index
WHERE firstname = 'Ryan'
AND lastname = 'Barrett'
- Scan index with prefix
Parent Barrett Ryan
:
Kind | lastname | firstname |
Parent | Anderson | Jane |
Parent | Barrett | Ryan |
Parent | Smith | Bob |
Parent | Smith | Brad |
Parent | Smith | Chelsea |
Parent | Thomas | Alice |
Composite index
WHERE lastname = 'Smith'
AND firstname >= 'B' AND firstname < 'C'
- Scan range
[Parent Smith B, Parent Smith C)
:
Kind | lastname | firstname |
Parent | Anderson | Jane |
Parent | Barrett | Ryan |
Parent | Smith | Bob |
Parent | Smith | Brad |
Parent | Smith | Chelsea |
Parent | Thomas | Alice |
Composite index
WHERE ANCESTOR IS /Grandparent:Ethel
ORDER BY firstname
- Scan with prefix
Parent /Grandparent:Ethel
:
Kind | Ancestor | firstname |
Parent | /Grandparent:David | Jane |
Parent | /Grandparent:Ethel | Bob |
Parent | /Grandparent:Ethel | Chelsea |
Parent | /Grandparent:Ethel | Ryan |
Parent | /Grandparent:Fred | Alice |
Contents
Best practices
- Bigtable in one slide
- The Entities table
- Queries and indexes
- Kind index
- Single-property index
- Composite index
- Merge join
- Entity groups and transactions
Merge join
- Serves multiple
=
filters without a composite index
- Can include ancestor
- e.g.
WHERE firstname = 'John' AND lastname = 'Smith'
- Scan single-property index once for each filter value
- Intersect results
Merge join
WHERE firstname = 'John' AND lastname = 'Smith'
- Scan with prefix
Parent firstname John
:
Kind | Name | Value |
Parent | firstname | John |
Parent | firstname | John |
Parent | firstname | Ryan |
- ...and with prefix
Parent lastname Smith
:
Parent | lastname | Barrett |
Parent | lastname | Smith |
Parent | lastname | Smith |
Merge join
- Intersect results incrementally, using key:
Kind | Name | Value | Key |
Parent | firstname | John | X |
Parent | firstname | John | Y |
Parent | lastname | Smith | Y |
Parent | lastname | Smith | Z |
Contents
Best practices
- Bigtable in one slide
- The Entities table
- Queries and indexes
- Kind index
- Single-property index
- Composite index
- Merge join
- Entity groups and transactions
Transaction model
- All writes are transactional
- Timestamped journals
- Entity version history
- Optimistic concurrency
Example: Put
- Read "committed" timestamp
-
-
-
| Key | Entity | Journal | Committed |
← | A | X (3:00) |
... | 3:00 |
Example: Put
- Read "committed" timestamp
- Write journal
-
-
| Key | Entity | Journal | Committed |
→ | A | X (3:00) |
3:45 A←Y | 3:00 |
Example: Put
- Read "committed" timestamp
- Write journal
- Apply journal
-
| Key | Entity | Journal | Committed |
→ | A |
Y (3:45) X (3:00) |
3:45 A←Y | 3:00 |
Example: Put
- Read "committed" timestamp
- Write journal
- Apply journal
- Update committed timestamp
| Key | Entity | Journal | Committed |
←→ | A | Y (3:45) X (3:00) |
3:45 A←Y
| 3:00 3:45 |
Entity groups
- Defined by root entities
- Consists of root and all descendants
- Journal, last committed timestamp co-located with root entity
Example: paying allowance
class Parent(db.Model):
cash = db.IntegerProperty()
class Child(db.Model):
cash = db.IntegerProperty()
parent = Parent(cash=1000)
child = Child(parent=parent, cash=0)
Example: paying allowance
def pay(parent_key, child_key, amount):
parent, child = db.get(parent_key, child_key)
parent.cash -= amount
child.cash += amount
db.put(parent, child)
db.run_in_transaction(
pay, parent.key(), child.key(), 10)
Example: paying allowance
def pay(parent_key, child_key, amount):
parent, child = db.get(parent_key, child_key)
parent.cash -= amount
child.cash += amount
db.put(parent, child)
db.run_in_transaction(
pay, parent.key(), child.key(), 10)
- Read entity group for
parent
- Note committed timestamp, 3:00pm
- Read
parent
and child
entities as of 3:00pm
Example: paying allowance
def pay(parent_key, child_key, amount):
parent, child = db.get(parent_key, child_key)
parent.cash -= amount
child.cash += amount
db.put(parent, child)
db.run_in_transaction(
pay, parent.key(), child.key(), 10)
- Serialize
parent
and child
- Write to journal in
parent
's entity group row
Example: paying allowance
def pay(parent_key, child_key, amount):
parent, child = db.get(parent_key, child_key)
parent.cash -= amount
child.cash += amount
db.put(parent, child)
db.run_in_transaction(
pay, parent.key(), child.key(), 10)
- Apply journalled changes to
parent
and child
- Write new committed timestamp to entity group
- Update
parent.cash
and child.cash
index rows
Recovery
- Always check entity group first
- Unfinished txes are rolled forward
- Adds one Bigtable read to every datastore read/write
Contents, redux
Best practices
- Bigtable in one slide
- The Entities table
- Queries and indexes
- Kind index
- Single-property index
- Composite index
- Merge join
- Entity groups and transactions