[Openembedded-architecture] [openembedded-architecture] sstate equivalency

[Joshua Watt]

On Sun, Jun 10, 2018, 04:38 Martin Jansa <martin.jansa at gmail.com> wrote:

> This description sounds like there would be one global equivalency server,
> but I would expect this to be implemented in similar way how bitbake PRserv
> is currently used - so that each project or user can define which
> equivalency server to use and where to report the hashes.
>

I wasn't sure, so I approached it from the idea of there being a public
server, perhaps populated by the nightly builds. I think it is probably
more useful if there is a public one (more like the sstate cache than a
PRserv). I don't think it would be hard to do multiple levels of
equivalence servers so that an internal one can be maintained in preference
to the public one (sort of like how you can have "levels" of sstate cache),
or there is only one but they do deferrals to a higher server on a miss
(like DNS).


> I'm also surprised that there is no indication of the recipe,
> architecture, version for these hashes, just one hash for everything which
> is good for anonymity of the submitted hashes, but it also means that if I
> have very simple component like systemd-serialgetty:
>
> sstate-cache/dd/sstate:systemd-serialgetty:qemux86-oe-linux-musl:1.0:r5:qemux86:3:ddf17a1eff3be1ff6a7ff393bbbf289b_package.tgz
> then the outhash can be the same as what qemux86copy MACHINE builds, but
> how is bitbake supposed to find that instead of building ddf17a1eff3be1ff6a7ff393bbbf289b
> it can re-use sstate equivalent file:
>
> sstate-cache/ee/sstate:systemd-serialgetty:qemux86copy-oe-linux-musl:1.0:r5:qemux86copy:3:eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee_package.tgz
> ?
>
> From one point of view this is great that we can re-use already built
> sstate even if it was built for completely different MACHINE and possibly
> even different recipe and version as long as the outhash is identical, but
> it blows up really badly once you get some conflicts in outhash
> calculations (and it really depends on what we'll include in outhash, first
> we try to ignore timestamp, then users, then we might be interested only in
> the ABI for given library).
>

I'm not sure if you are referring to the input hashes or the output hashes
(from the servers perspective), so I'll address both.

I went back and forth a lot on the input hashes. It isn't hard to include
all that information and still be anonymous, you just hash all of the
relevant information together (MACHINE, BB_TASKHASH, etc.) and send that as
the request hash to the server. I had this in a previous draft, but I think
I decided that BB_TASKHASH should include all the relevant variables
anyway, so it was unnecessary (and only made it more complicated). I don't
know that I have a strong opinion either way, so if there is a good reason
to go the other way, I'm fine with that.

On the output hashes: It is a little more nuanced than that. For the sake
of discussion, lets say that we calculate "TASKHASH_A" as the hash for one
task named "Task A" (perhaps ddf17a1eff3be1ff6a7ff393bbbf289b), and
"TASKHASH_B" for another task named "Task B" (perhaps
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee). Lets say these two tasks are equivalent,
but no one has discovered that yet. Now, an equivalence aware executor
builds Task A, and then calculates its output hash as OUTHASH_C. When it
goes to write the sstate object, it doesn't write it out using TASKHASH_A,
but instead writes it out using OUTHASH_C. The executor then reports that
TASKHASH_A is equivalent to OUTHASH_C and moves on. A later executor now
needs to build Task B. At this point, it isn't applicable that TASKHASH_A
is equivalent to OUTHASH_C, because it is unknown that TASKHASH_B is
equivalent to OUTHASH_C (that can't be known until Task B is built). The
task executes, the output hash is calculated as OUTHASH_C, the sstate
object is written (if it doesn't already exist!), and the equivalence of
TASKHASH_B to OUTHASH_C is reported.

Now that this general procedure is outlined, let us consider 2 cases:

Case A) Task A and Task B are two independent tasks. That is, lets say Task
A is the task for MACHINE qemu86 and Task B is for the MACHINE qemu86copy,
as you described above. In this case, the two tasks will never "converge",
that is, it will never be able to use the sstate object for Task A in place
of the sstate object for Task B but... *that doesn't matter*. The object of
equivalence is to reduce rebuilds, not necessarily to reduce the sstate
cache size. It is impossible to have known that Task A and Task B are
equivalent without someone having actually *built* both of them, so in even
though they are equivalent, *both objects should have been written to the
sstate cache*. A later executor will simply restore either one from sstate
(based on the equivalent server reported OUTHASH_C of course) without
taking into account that they happen to be equivalent. Additionally, I
think that the overhead and comprehension required to maintain such a
mapping between independent tasks and reason about what is going on would
be much higher than saving a little space in sstate.

Case B) Task B is actually a later version of Task A. In this cases, the
two tasks do indeed "converge" because when a later executor goes to build
Task B, it will be told by the equivalence server that it is equivalent to
OUTHASH_C, and will find the sstate object written by Task A, since it will
match exactly, thus preventing the need to rebuild. Keen observers will of
course note that my logic from Case A is still applicable here: namely that
both Task A and Task B *must* have been built once to determine their
equivalence, and therefore both of their "classic" sstate objects (those
that use BB_TASKHASH instead of OUTHASH_C) would have been in the sstate
cache. And since I stated that the object of equivalence isn't to reduce
the size of the sstate cache, why even bother with translating to OUTHASH_C
at all? This is all true, and leads into the next question of preventing
downstream task rebuilds, which I answer more fully below. As far as why
use an sstate object named with OUTHASH_C instead of BB_TASKHASH, in this
case (where Task A and Task B are different versions of the same task), the
overhead of such a mapping is much lower that the independent case, and it
is also much easier to reason about what is going on so it makes more sense
to maintain. Additionally, naming the sstate objects by output hash has one
additional benefit: Anyone (with permission) can report a new input hash
that maps to that output hash and it could be useful to another executor
(e.g. they might actually find a sstate object named with the output hash
already existing in sstate). If you name the sstate objects with
BB_TASKHASH, then the only executors that can generate useful equivalence
mappings are those who end up populating the shared sstate caches.

All that being said, I wouldn't necessarily mind reporting the full sstate
object path (e.g.
ee/sstate:systemd-serialgetty:qemux86copy-oe-linux-musl:1.0:r5:qemux86copy:3:eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee_package.tgz)
instead of just the basic output hash. This wouldn't change anything
detailed above, and it wouldn't be used to "converge" the tasks as
mentioned above, but rather it would give the humans looking at what is
going on a much better way to debug the system. I don't particularly feel
that output hashes need to be as anonmized as the input hashes, because
reporting output hashes is most assuredly an "opt-in" sort of thing. If you
can maintain a private server, you can prevent reporting anything to the
public server. A better option that even that would be (I think) to
actually enable a "report additional statistics" option when you report an
equivalent hash. If enabled, all sorts of very useful data could be
uploaded to the equivalence server, such as the information that goes into
the sstate object path, perhaps the task siginfo, etc. Again, I'm don't
necessarily want to derail the discussion with what we *could* do (as I
realize this could, and should, be a sensitive topic), but keep it in mind
because it will probably come up again. Rest assured, I'm not going to do
anything behind anybody's back (or at all if that's the consensus): input
and output hashes are all we really need.

Of course, none of this actually prevents downstream task rebuild, as you
pointed out below....


> And I'm still missing how this will prevent rebuilding e.g. chromium
> against new zlib even when older zlib is sstate equivalent - we will reuse
> older sstate from older zlib build instead of rebuilding zlib, but what
> taskhash will OEBasicHash use when computing the new hash of
> chromium.do_configure? It should use the same one as in previous chromium
> build (if they are in the same equivalency group), because if it uses any
> other one, then we'll end with chromium rebuilding even when it's against
> identical zlib with just different hash.
>

I should have made this more clear, but it doesn't. That is the end goal.
However, you need this piece in place first, and in the interest of
breaking up the problem into manageable chunks, this seems to be the
direction I've been steered by previous discussions (which I completely
agree with).

Once you have the hash equivalence structure in place, I believe that the
general idea is to calculate task dependencies based on the output hash in
place of the task hash. This means that when the equivalence server reports
that zlibs output hash hasn't changed, chromium.do_configure doesn't re-run
because it's dependency on zlib is based on zlibs outhash, not its task
hash. This will require some core bitbake work and is going to be far more
complicated that this (relatively) simple tracking of persistent
equivalence, so it seems better to get this part out of the way first.

Of interesting note: Let's go back to Case B... if bitbake did calculate
dependencies by output hash, and Task A and Task B did have the same output
hash, than some other task that depended on the task provided by Task A and
Task B would be able to use either interchangeably.... which is pretty
awesome.

Thanks,
Joshua Watt (Champion of the comma splice)


> On Fri, Jun 8, 2018 at 5:09 AM Joshua Watt <jpewhacker at gmail.com> wrote:
>
>> Hello all,
>>
>> I've been looking into the sstate equivalency mechanism discussed
>> [previously][1], and decided that it is probably time to report what I
>> am proposing, so that more discussion can be had.
>>
>> [1]: http://lists.openembedded.org/pipermail/openembedded-architecture/
>> 2018-May/000745.html
>> <http://lists.openembedded.org/pipermail/openembedded-architecture/2018-May/000745.html>
>>
>> Please make note of the **QUESTION** lines, as they indicate
>> (known) outstanding issues haven't sorted out yet.
>>
>> Apologies for the length. You can also see this in all of its markdown
>> glory
>> [here](https://gist.github.com/JPEWdev/506b70157cdbb59454e445fe71a57c7e
>> )
>>
>> # Hash Equivalency Server
>>
>> This design proposes a design for a Hash Equivalence Server that can
>> be use to centralize the records of what task hashes can be considered
>> equivalent. The server implements a REST HTTP API based on JSON data
>> to report to bitbake clients what task hash can be considered
>> equivalent on request, and also allow selected clients to report new
>> known equivalent hashes.
>>
>> The hash equivalency server identifies task hashes based on these main
>> attributes:
>>
>> 1. `taskhash`: *Task Hash* - This is the value `${BB_TASKHASH}` that
>>    bitbake calculates from the inputs to the hash
>> 2. `method`: *Output Hash Method* - The string method used to
>>    calculate the output hash. These will be described in detail later.
>> 3. `outhash`: *Output Hash*: The hash derived from the build outputs
>>    using the `method`
>>
>> **QUESTION** Do we need the `method`? Presumably, a hash is a hash is
>> hash is unique, so the method is unnecessary since different hashing
>> methods will produce different hashes from the same input, but at the
>> same time we also *expect* different a `outhash` when the `method`
>> differs.
>>
>> The server may track and report other additional information about the
>> task hashes, but the items described above are the minimum required.
>>
>> Once bitbake has calculated the task hash and determined that it needs
>> to rerun a task, it can send a HTTP GET request to the Hash
>> Equivalency Server to ask if knows any equivalent tasks that can be
>> used in place of rebuilding. This GET request is formulated as:
>>
>>     GET /v1/outhashes?taskhash=<TASKHASH>&method=<METHOD>
>>
>> In this request, `<TASKHASH>` and `<METHOD>` are replaced by the
>> appropriate information about the task for which bitbake is making the
>> request.
>>
>> **QUESTION** I think we only need to request equivalent hashes for
>> things that have to be rebuilt... is there any reason to request them
>> for all tasks regardless of if they need to be rebuilt or not?
>>
>> **QUESTION** You could pretty easily get some useful statistics on how
>> many users are (re)building a given taskhash. I know that's a more
>> controversial topic that I would mostly like to avoid (for now), but
>> keep it in mind... In general I think having a hash equivalency server
>> opens up a lot of those kinds of possibilities.
>>
>> The response from the GET request will return the HTTP 200 OK code,
>> and the result body will be a JSON object that describes the
>> equivalent hash. At a minimum, the object will provide the `outhash`
>> field, as this is required for bitbake to discover a matching sstate
>> object. In the event there are no equivalent hashes, an empty object
>> is returned. The following is an example of the returned JSON:
>>
>> ```json
>> {
>>     "outhash": "0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33"
>> }
>> ```
>>
>> **QUESTION** Is there any reason to return more than one equivalent
>> hash?
>>
>> Once an output hash is discovered for a task, the sstate task will use
>> it in place of the `BB_TASKHASH` variable for the purpose of looking
>> up sstate objects.
>>
>> # Writing new sstate objects
>>
>> In the event that a bitbake executor cannot find an equivalent hash
>> (either because no output hashes were reported, or no such sstate
>> objects exist), it will end up performing the build, then needing to
>> write out a new sstate object. These new sstate objects will always be
>> written using the output hash in the file name (in place of the
>> current `BB_TASKHASH`). These output hashes are calculated using one
>> of the hash calculation methods described below.
>>
>> **QUESTION** Is there any desire to be able to do a build later
>> without the hash equivalency server? I don't think it would be
>> terribly difficult to have the sstate cache create symbolic links to
>> the equivalent task hashes with the name of the original task hash so
>> that builders who are unaware of the equivalency server can still find
>> the sstate objects.
>>
>> # Reporting New Equivalent Hashes
>>
>> A bitbake executor can report newly discovered equivalent hashes to
>> the hash equivalency server also via a REST API. These hashes can be
>> reported at the time the sstate object is written, using a POST
>> request:
>>
>>     POST /v1/taskhashes
>>
>> The body of the request must contain an array of JSON object that
>> describes the equivalent hashes. At a minimum, each object must
>> contain the `taskhash`, `method`, and `outhash` fields. For example:
>>
>> ```json
>> [
>>     {
>>         "taskhash": "c7c51be323b56305e1e7e74f4011e810fd340908",
>>         "method": "basic",
>>         "outhash": "0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33"
>>     },
>>     {
>>         "taskhash": "e7a3049fa3a27861d4b54d29b2e3b781f0dbf304",
>>         "method": "basic",
>>         "outhash": "114aa9bac59642fa951a0fed8359930fc602679d"
>>     },
>> ]
>> ```
>>
>> **QUESTION** What do we do if multiple different output hashes are
>> reported for the same taskhash? This is actually pretty useful
>> information, since it would indicate a non-reproducible build.
>>
>> **QUESTION** You can go pretty crazy with reporting here....
>> Hopefully, the three required fields are anonymous enough that there
>> are no qualms with reporting them.  Anything beyond that would
>> obviously be enormously helpful from a data-mining and statistics
>> perspective. You wouldn't be able to keep that anonymous enough, so it
>> would *have* to be opt-in. Again, not the focus of this discussion,
>> but keep it in mind
>>
>> ## Hash reporting security
>>
>> The use of a public hash equivalency server has the potential
>> introduce serious security flaws into consumers that choose to use it.
>> For example, it would be trivial for a malicious user to upload an
>> outhash for an unpatched version of software as being equivalent to
>> the patched version's taskhash. As such, it is important that the
>> identity for the source of all reported taskhash be confirmed before
>> they are submitted to the database. To confirm the identity of posted
>> task hashes, users who wish to supply hashes must first upload a
>> public RSA key to the server which is tied to a username. When the
>> user wishes to POST a hash, the HTTP body doesn't contain the raw
>> JSON, but instead contains a JSON Web Signature string (per
>> [RFC7515](https://tools.ietf.org/html/rfc7515)), signed with the users
>> private key. In order for the server to identify which user/key should
>> be used to verify the signature, the message should contain the "kid"
>> parameter in the unprotected header that is set to the username
>> corresponding to the signing key. Additionally, the request must also
>> include a numeric "nonce", field in the protected header. This nonce
>> value must be numerically larger than the last reported nonce by that
>> user, or the request will be rejected with an error. In this case,
>> bitbake will be made aware of the error and the last reported nonce
>> value so it can retry with a higher value.
>>
>> The server will store the username associated with all reported hashes
>> to allow for easy revocation of hashes in the event of a private key
>> breech, or a request to clear out reported hashes from the user for
>> privacy reasons.
>>
>> **QUESTION** Web technology isn't really my thing... is there a better
>> way?
>>
>> # Hashing Methods
>>
>> The hashing equivalency code needs to be provided with a hashing
>> algorithm to determine if two taskhashes are equivalent. The default
>> algorithm provided with the implementation will be named "basic" and
>> calculates a SHA1 using the algorithm found
>> [here](https://gist.github.com/JPEWdev/d5e8d339d6d33a505fee1fd049994262
>> )
>>
>> **QUESTION** It is important to note what that algorithm does hash
>> (file path, mode, file type, contents), but also what it *doesn't*
>> hash (namely the owner/group and timestamps). I think this is what we
>> would like. Any suggestions?
>>
>>
>> Thanks,
>> Joshua Watt
>> _______________________________________________
>> Openembedded-architecture mailing list
>> Openembedded-architecture at lists.openembedded.org
>> http://lists.openembedded.org/mailman/listinfo/openembedded-architecture
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openembedded.org/pipermail/openembedded-architecture/attachments/20180610/72bb3006/attachment-0002.html>