proposal for sector-packing algorithm

[porcuquine]

Although the spec doesn't necessarily need to prescribe a sector-packing algorithm, it is important that we know a viable one exists before we commit to requiring a maximum (even zero) allowable padding per sector. @jbenet has proposed 1/64 as a potentially viable maximum padding. The padding referred to here is inter-piece padding, not padding added to individual pieces (and charged for) to ensure they are a power-of-2 in size.

Here is an algorithm which I believe meets the requirements and allows for optimal packing while also making it possible to prioritize deals which will expire sooner.

If this is flawed, we should discuss and wait until we are sure a viable alternative or improvement exists. Otherwise we might create rules with unintended consequences (even if only implementation complexity as we move toward testnet).

If it is not flawed, perhaps it should be included in the spec as at least a recommended or example algorithm, since it addresses a problem miners will indeed need to solve.

Sector Packing

• Assumptions:
  • Deal proposals can expire, and we know the latest time a sector containing a given deal must begin being packed.
  • Miners can always create bogus padding deals and put them on chain after sector packing begins and still have access to the DealID before they precommit the sector.
  • So in the worst case they can always do that.
  • Pieces are always a power-of-2 in size.
• Proposed algorithm:
  • Miners store piece references in priority queues per-piece-size, with soonest expiring at the head.
  • Queues are ordered from largest-piece to smallest-piece.
  • Queues know their sizes, and miners track the total amount of storage ready to seal.
  • At any point that the total amount ready to seal exceeds one sector size, a sector can be packed.
• Ignoring the risk of stranding a piece:
  • sectors can be packed by simply always taking the next available piece from the first non-empty queue (and removing the piece from the queue).
  • This will always pack a sector perfectly, provided enough aggregate piece size (which we assumed before beginning).
• However, naively following this strategy can lead to stranded pieces which are not packed soon enough.
  • Example: a small piece may never be packed because larger pieces are always packed sooner, even if they arrive later.
  • To facilitate packing such pieces sooner, we will also track the total size of all pieces contained in each queue and all later queues (bigger pieces are in 'earlier' queues).
  • Call this 'downstream capacity'.
  • Now, when packing, we can always cheaply determine whether it is safe to pack a smaller piece ahead of an available larger piece.
  • If the total downstream capacity of the smaller-piece queue is >= the size of pieces contained in the larger-pieced ('upstream') queue, it is safe to replace one larger piece with pieces packed in the normal manner, beginning with the smaller piece then drawing only from pieces downstream from it.
  • Now modify the original algorithm so that instead of choosing the first available queue, we do the following:
  • First, select the first available queue and note its piece size, P.
  • If any later queues have an earlier expiration time (of their first deal), check whether that queue's downstream capacity is >= P.
    • If so, pack pieces totaling exactly P from the downstream queue.
    • Note: This means that until pieces totaling P have been packed, the largest queue used as a source of pieces is the downstream queue.
    • The modified algorithm can be used in this recursive packing, so that the highest priority pieces will always pre-empt others, if enough total pieces exist.
    • Otherwise, pack the original piece of size P.
  • Repeat until the sector has been fully packed.
• Each sector should be packed completely before the next is packed.
• New pieces should be held in a separate place while a sector is being packed, then added to the appropriate queues once the previous sector has been fully packed.
  • Otherwise, a larger piece might be packed into a subtree which will not hold it.
• Packing should never begin until enough piece bytes have been accumulated.
• The only exception is when a piece is about to expire (i.e. must be packed immediately, given knowledge of required sealing lead-time on expiry).
  • In that case, either the piece must be discarded and the deal lost;
  • Or, all available piece should be packed in the normal manner and the remainder replaced by padding deals (if needed, which depends on the per-sector padding allowance).
  • Which is the better option can be decided at that time, based on miner strategy.

[zixuanzh]

This looks reasonable to me 👍, I expect miners to optimize this operation. The bottomline here is to pack deals before they have to get on chain (Deal.StartEpoch, taking into account the time it takes to do PreCommit and ProveCommit).

Where are we enforcing the requirement of maximum allowable padding per sector?

And quick note for future considerations, we might enable transfer sector/deal, update deal, update storage in sector down the line but not required atm.

[porcuquine]

We don't currently enforce the maximum allowable padding. This issue arose as a sanity check before spec'ing that change — to insure it would not have unintended consequences, since it is a change from how implementations have ever worked in the past. We may also need to delay enforcing the check in the proofs implementation until storage miner implementations have implemented a solution, but that's not a spec issue.