javascript:void(0);


App Engine Index Building

Nov. 24, 2008
(also see the article)

What's ahead

Introduction

Index building process

  1. add new index definition (metadata) to app
  2. mark index definition "write only"
    • write to it on puts and deletes
    • don't use it for queries
  3. map over existing entities and populate index rows
  4. mark index definition "read/write"

Index deleting process

Similar to building:

  1. mark index definition "deleted"
    • don't write to it on puts or deletes
    • don't use it for queries
  2. map over existing entities and remove index rows
  3. delete index definition

Index layout

Index building

Index deleting

Parallelizing work

Parallelizing work

Parallelizing work

  • hash each entity's key
  • only operate on keys where hash(key) == k modulo n.
  • can't just operate on every kth entity, since entities are constantly being added and deleted
  • Parallelizing work

    note that each worker is still scanning over the entire tablet. however, this is relatively cheap compared to the multiple reads and writes required to build or delete the new index(es) for each entity. remember, disk bandwidth (ie large contiguous disk reads) are cheap, disk seeks are expensive!

    FAQs

    FAQs

    FAQs

    FAQs

    FAQs

    Questions? (also see the article)