DEV Community

Cover image for Feeding By Sectors
Anton Brilliantov
Anton Brilliantov

Posted on

Feeding By Sectors

A recount of a big table goes out the way food goes out in a zoo: by sectors, along the paths, one cart per sector - not one walker carrying everything through the night.


👋 Hi, I'm Anton - a software engineer. These days I work on a platform: contracts, generated code, data paths and the tooling around them. Running notes live on my GitHub: github.com/brilliant-almazov.

The backfill routine is built into the shared library as one of its thirteen generic routines; a few services use that runtime. The example of twenty windows below is an example cut, not a measurement of any real recount.

This is part 5 of the series on what a shared platform does for every service, told as a zoo. Maybe you already do it better, maybe you'd do it another way - this is how it is going, and where it stops.


In real life

Feeding time. Nora brings all the food for the whole zoo in one go and, to save time, tips it into the nearest pen. The nearest pen happens to be Ember's. Ember, a dragon, looks at the mountain and says the only thing a dragon can say: "Mine now. All of it." The rest of the zoo is hungry.

The next idea is the night walker. Biscuit takes a wheelbarrow and walks the whole zoo, pen by pen, all night: "Pen one... pen two... pen nine thousand..." It works, slowly, alone, and nobody can see how far he got or help him when he gets tired.

A four-panel comic: Nora sees the dragon sitting on all the food, the dragon says mine now; Biscuit walks pens under a lamppost all night; Pip says first pen, last pen, one note per sector; Biscuit takes pens 1 to 100 and Pickle takes 100 to 200

Then Pip does what keepers in real zoos do. Look at the first pen and the last pen. Cut the zoo into sectors. Write one note per sector, put the notes on the paths, and let whoever is free take a note: Biscuit takes pens one to a hundred, Pickle takes a hundred to two hundred. Nobody carries everything, everybody can see which notes are still waiting, and a dropped note is just picked up again.

A goroutine that walks the table

Every service eventually needs to recount something: fill a new column for old rows, rebuild a derived value, re-publish what changed. The tempting shape is a background goroutine that starts with the service, scans the table from top to bottom, and does the work as it goes.

That shape has all of Biscuit's problems. It is one walker per replica, or one walker with a lock. Nobody sees how far it got. If the process restarts, the walk restarts or needs its own bookkeeping. And it runs outside the one thing the platform already has for "work that happens later": the bus. In our platform that is not a style preference. Any asynchronous processing - a backfill, a recount, a re-publish - goes through the bus, producer to consumer; a goroutine that scans a table on its own is not an option at all.

Three tiles with faces: the producer, proud; the bus, happy; a consumer, happy; labels read a window per message and one window, one transaction; pills read built, and used by a few services

One query, then windows on the bus

The backfill routine of the library does it in two halves.

The producer asks the table one question: the smallest and the largest key. It cuts that range into windows [from, to) and publishes each window as a message. The consumer takes a window and does the work for the rows in it, in one transaction. As a form - names illustrative:

producer:  SELECT min(id), max(id) FROM <table>;      -- one query
           publish { from: 1,      to: 100001 }
           publish { from: 100001, to: 200001 }
           publish ...                                -- one window per message
consumer:  BEGIN; <work on rows where from <= id < to>; COMMIT;
Enter fullscreen mode Exit fullscreen mode

A dark card with the backfill form: the producer's min and max query, window messages, and the consumer's one transaction per window; the min and max line is highlighted; a pill reads built

Everything the night walker could not do now comes from the bus. Progress is the number of window messages still waiting. A failed window is redelivered alone, without redoing the windows before it. More consumers means more sectors fed at once. And the producer does not scan anything: it reads two numbers.

Bars: queries to plan the cut, min and max, 1; transactions per window 1; goroutines scanning the table 0; Biscuit says no more night walks; a pill reads built

Question Night walker Windows on the bus
how far did it get? inside one process's memory messages done vs waiting
what if a step fails? the walker decides, or stops that window is redelivered
can two help? only with extra locking any free consumer takes a window
what does planning cost? a scan of the whole table one query for min and max

What a window asks of the work

Moving a recount onto the bus changes one thing about the work itself: a window can arrive more than once. The bus delivers at least once, and a window whose consumer died after the commit but before the acknowledgement will come back. So the work for a window has to be safe to repeat.

For most recounts that comes for free, because they set a value rather than add to it: "fill the new column from the old ones" gives the same row the second time. For the few that add or send, the previous part of this series applies unchanged - the once-per-message routine punches the window's message id in the same transaction as the work.

There is also a question of size. A window is one transaction, and a transaction holds its locks until it commits. Wide windows mean fewer messages and longer locks; narrow windows mean more messages and shorter locks. How wide a window should be is a choice per table, and I do not claim a right number.

Window width Messages on the bus Locks held per transaction
wide few long
narrow many short

What twenty windows look like

To show the idea, an example: a key range cut into twenty windows, some done, some in flight, some still on the bus. The numbers are an example cut, not a run.

A waffle of twenty cells: twelve done, three in flight, five waiting on the bus; Pickle says each one done on its own; a pill reads an example, not a measurement

An animation: the producer reads min and max, publishes window 1 to 100001 on the bus, a consumer finishes it in one transaction, then the next window travels; a pill reads no walker at night

Before and after: a walker - 1 walker, the whole table by itself; hidden, not on the bus - and windows - N windows from-to on the bus; 1 transaction per window, any consumer

What went wrong

The thing this routine closes is a habit: the background goroutine that scans a table is the first thing anyone writes for a recount, because it is the shortest code. It is also the one shape that hides its progress, fights its own replicas and lives outside the bus. The rule that asynchronous work goes through the bus came first; the routine is what makes following that rule shorter than breaking it.

One more honest note: windows over a key range assume the keys are spread evenly enough that windows of equal width carry similar work. A range with a dense patch makes some windows heavy. The routine cuts by key, not by row count.

Service tiles with faces: the producer, the bus and two consumers are happy; the table happy; a night walker bored; a failed window worried; the retry happy; a pill reads built

What I do not claim

  • Not a measured recount. The twenty windows are an example.
  • Not that windows of equal width carry equal work. They are cut by key.
  • Not that every recount in every service uses the routine. A few services use the runtime.
  • Not the exact message shape. The form above shows the idea.
  • Not a right window width. It is a choice per table.
  • Not that the work in a window is safe to repeat by itself. That is the work's job, or the once-per-message routine's.

What of this is method

  • Plan with one query, work through the bus. Min and max, then windows as messages.
  • One window, one transaction. A failure costs one window, not the whole walk.
  • Make the right path the short one. The rule says "through the bus"; the routine makes it less code than a goroutine.

Zoo keeping, built in - Part 5. Next: Thirteen Routines, One Keeper.

If you recount big tables, does the work run as a walker or as messages? If you cut by key range, what do you do with the dense patch? If a backfill failed halfway, how did you know where to restart? Who walks your zoo at night?

Top comments (0)