TimelyDataflow / TimelyDataflow/differential-dataflow

Consider `Tombstone` trait for `Diff`

Open
#298 0 comments 3 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
3k
Forks
211
Avg merge
10h 42m
Merged PRs (30d)
34

Description

In accumulating up differences, we are often lucky and they add up to zero, and we can discard the result. In some cases, mainly tombstones, we end up with something we'd like to discard (the tombstone) but which we can only do once we are sure that it has served its purpose (clobbering preceding diffs).

It seems plausible that we could inform the diff instances when they have been merged into to the oldest batch, which would imply that there would be no further updates before them. For example, there could be a tombstone(&mut self) method that gets invoked in this setting, whose implementation is by default empty (for all current implementations) but which gets called after forming each diff in the last layer. This would give tombstone diffs the opportunity to collect themselves and vanish, and would probably substantially simplify the programming of "upsert" diffs.

Very much just a musing at this point, not knowing much about the trade-offs here.

cc: @ruchirK

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

No files or tests are named. Start by locating the diff instances, the merge path into the oldest batch, and the final-layer diff formation; then assess whether a tombstone callback can be added without breaking existing implementations. Done would require an agreed design and concrete behavior for tombstone diffs, which the issue does not yet specify.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
distributed-systems
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.