From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp12.migadu.com ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id wDXLAje9+mHAUgEAgWs5BA (envelope-from ) for ; Wed, 02 Feb 2022 18:19:51 +0100 Received: from aspmx1.migadu.com ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp12.migadu.com with LMTPS id QAraOja9+mG5hwAAauVa8A (envelope-from ) for ; Wed, 02 Feb 2022 18:19:50 +0100 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id ABA2341527 for ; Wed, 2 Feb 2022 18:19:50 +0100 (CET) Received: from localhost ([::1]:40400 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nFJIL-0004j2-7M for larch@yhetil.org; Wed, 02 Feb 2022 12:19:49 -0500 Received: from eggs.gnu.org ([209.51.188.92]:48458) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nFHZ9-0008VI-3H for guix-patches@gnu.org; Wed, 02 Feb 2022 10:29:03 -0500 Received: from debbugs.gnu.org ([209.51.188.43]:59199) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nFHZ8-0004eN-Ol for guix-patches@gnu.org; Wed, 02 Feb 2022 10:29:02 -0500 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1nFHZ8-0005Wk-GD for guix-patches@gnu.org; Wed, 02 Feb 2022 10:29:02 -0500 X-Loop: help-debbugs@gnu.org Subject: [bug#52555] [RFC PATCH v2 0/5] Decentralized substitute distribution with ERIS Resent-From: Maxime Devos Original-Sender: "Debbugs-submit" Resent-CC: guix-patches@gnu.org Resent-Date: Wed, 02 Feb 2022 15:29:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 52555 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: patch To: pukkamustard Cc: ~pukkamustard/eris@lists.sr.ht, 52555@debbugs.gnu.org Received: via spool by 52555-submit@debbugs.gnu.org id=B52555.164381568421149 (code B ref 52555); Wed, 02 Feb 2022 15:29:02 +0000 Received: (at 52555) by debbugs.gnu.org; 2 Feb 2022 15:28:04 +0000 Received: from localhost ([127.0.0.1]:53095 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nFHYC-0005V3-5e for submit@debbugs.gnu.org; Wed, 02 Feb 2022 10:28:04 -0500 Received: from andre.telenet-ops.be ([195.130.132.53]:48458) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nFHY7-0005Ub-3o for 52555@debbugs.gnu.org; Wed, 02 Feb 2022 10:28:02 -0500 Received: from ptr-bvsjgyhxw7psv60dyze.18120a2.ip6.access.telenet.be ([IPv6:2a02:1811:8c09:9d00:3c5f:2eff:feb0:ba5a]) by andre.telenet-ops.be with bizsmtp id qFTw2600T4UW6Th01FTwYL; Wed, 02 Feb 2022 16:27:57 +0100 Message-ID: <84d930adac8c54120b176362e66a63ebf49179c6.camel@telenet.be> From: Maxime Devos Date: Wed, 02 Feb 2022 16:27:52 +0100 In-Reply-To: <8635l1h1mx.fsf@posteo.net> References: <20211216161724.547-1-pukkamustard@posteo.net> <20220125192201.7582-1-pukkamustard@posteo.net> <86fsp1h6ce.fsf@posteo.net> <846716544b4424f02e383114ebcb52957b43dd4d.camel@telenet.be> <8635l1h1mx.fsf@posteo.net> Content-Type: multipart/signed; micalg="pgp-sha512"; protocol="application/pgp-signature"; boundary="=-MLPmcf3VaezyhnWN/EcJ" User-Agent: Evolution 3.38.3-1 MIME-Version: 1.0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=telenet.be; s=r22; t=1643815677; bh=L1cE7iw9wpDs9RBnZWsEw4oIK8YvYcba5uknLmImRGU=; h=Subject:From:To:Cc:Date:In-Reply-To:References; b=ElS/TxmLltpabQrQQ28GDGY/JGBbtspCujTfS0pWMjJ2JWZi80ZcumfDMT/28eNVa KhuLco/tCtEg77KqCfTtW5zTD6B39RO4RZLJEIMDO5zY9n03knG8nKXe+ihMZxJnnc IiiKrQbe3uh4Tf2DLipmBYsHNRxtJQWPnZLRp1iZoPFgof0/IV/vLa6X+bmSvJackl Xb7XpmF+bKN1wM+BAoUrpXKRuntXchFhhi1qN4XZ7XhFeNWWU8no+F+G3KgG6QMy6x G/0OTRGeZZcs7jo18t7Zkr2rExGt1LxbmcLtDNoKwhltjCHxeZy+FLEDl5PUHZMEyl sKz98EGtJqKqQ== X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: guix-patches@gnu.org List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-patches-bounces+larch=yhetil.org@gnu.org Sender: "Guix-patches" X-Migadu-Flow: FLOW_IN X-Migadu-Country: US ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1643822390; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:resent-cc:resent-from:resent-sender: resent-message-id:in-reply-to:in-reply-to:references:references: list-id:list-help:list-unsubscribe:list-subscribe:list-post: dkim-signature; bh=L1cE7iw9wpDs9RBnZWsEw4oIK8YvYcba5uknLmImRGU=; b=SB7dNYF3DvXvwmbePS/iYeTb+Jg41lXDtfxgpPlIDVru+nA7Gxdci52bYwo3Op/W6IRnRg /6K9YR4d8XLS80grEJJfl/rDu4cdfci0sYKuInJOgciaYm53667WBFF198LGhZx/a3R+99 YSIsO7vr4HXJ0dOiRzJX7gl1cyprrILbyUXl0+bwlaRqLLvY2S4oIs9iSWCgw+mOJxaTrQ Zdi5NHzN2bFnxj/XrWJVwkCHsrLrD05vAzalMt3B9SFfhRHBwdtHb4Lid1UujesnUDEw/U 8AJcmmCTLrgDJ/gr7YRmioTaORzyJMVO5uaMvI2GfCkH4wLFi3/8wLSUN2j1Ww== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1643822390; a=rsa-sha256; cv=none; b=sio11Egfs7gLtUkqF+UBuNrmJC9n3N7iL3i/bePPJFtwxwtGDc8DnddC8AvToDUcOF/Y3B JLhCJymmWTZ1E8XAQQjK998feIgSMJdIbxFLv3zKRj/Eui0VBJ12BHI5syHPLaFC3KThQO 38TeQvdRmJFqxs6F4JQdxLYFP5IsYvR7xqcKuuMjJE1cXA7IW3Qq55VK3scUAPIHLeFf56 Xf5VgTo8orOJaRJBUpVt/xLvBrn1daVfnxdHwSttT04WBa5U1mLDMGP8nWPtJLCg/NGBC/ UyyxRI0j1aAWDg4PlklQ+LfTYULOQhZ9zAg8NQ7lBpNnNVpqPJEtwrK255yrHQ== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=telenet.be header.s=r22 header.b="ElS/TxmL"; dmarc=fail reason="SPF not aligned (relaxed)" header.from=telenet.be (policy=none); spf=pass (aspmx1.migadu.com: domain of "guix-patches-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-patches-bounces+larch=yhetil.org@gnu.org" X-Migadu-Spam-Score: -4.23 Authentication-Results: aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=telenet.be header.s=r22 header.b="ElS/TxmL"; dmarc=fail reason="SPF not aligned (relaxed)" header.from=telenet.be (policy=none); spf=pass (aspmx1.migadu.com: domain of "guix-patches-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-patches-bounces+larch=yhetil.org@gnu.org" X-Migadu-Queue-Id: ABA2341527 X-Spam-Score: -4.23 X-Migadu-Scanner: scn1.migadu.com X-TUID: f689Cz3NNMvR --=-MLPmcf3VaezyhnWN/EcJ Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable pukkamustard schreef op wo 02-02-2022 om 12:42 [+0000]: > > E.g., if the client cannot download the data in the range [start, > > end] > > because the corresponding block has disappeared, can it not simply > > download that range from https://ci.guix.gnu.org/nar/[...] > > (not sure about the URI) using a HTTP range request? >=20 > This does not work as the mapping from block reference to location in > NAR can not be known by the client who only holds the ERIS > URN. The client not only knows the ERIS URN, it also knows the location of the nar (over classical HTTP) because it's in the narinfo. > Furthermore, some blocks will be intermediary nodes - they hold > references to content blocks (or other intermediary nodes) but not > content itself. If an intermediary node (responsible for, say, bytes 900--10000) is missing, then the bytes 900--10000 could be downloaded via HTTP. Whether the node is close to the top, or close to the bottom, in ERIS' variant of Merkle trees, doesn't matter much. Granted, if the nar is, say, 1 GiB, and the top-level block is missing, then we'll have to download 1 GiB over HTTP, even if most lower blocks exist on IPFS/GNUnet/whatever, which isn't really great. We could also do some combination of the GDBM database and HTTP Content-Range requests: most nodes are leaf nodes (*). Instead of representing all nodes in the database, we could include only (intermediate) nodes responsible for data of size, say, 4MiB. (*) At least, that's the case for binary trees, presumably something similar holds for ERIS. I don't know the specifics for ERIS, but for (balanced) binary trees, not storing the leaf nodes would save about 50% (**), which is a rather nice space saving. (**) This assumes the =E2=80=98block size=E2=80=99 is the size for storing = two pointers to the children, but in practice the block size would be quite a bit larger, so there would be more space savings? Perhaps we are overthinking things and the GDBM (***) database isn't overly large, or perhaps missing blocks are sufficiently rare such that we could simply download the _entire_ nar from classical HTTP in case of missing blocks ... (***) Guix uses SQlite databases, so I would use SQLite instead of GDBM unless there's a compelling reason to use GDBM instead. Greetings, Maxime. --=-MLPmcf3VaezyhnWN/EcJ Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- iI0EABYKADUWIQTB8z7iDFKP233XAR9J4+4iGRcl7gUCYfqi+BccbWF4aW1lZGV2 b3NAdGVsZW5ldC5iZQAKCRBJ4+4iGRcl7luwAP4x9bFYhc+pM+oN9Jed5nNRDUSl xTW+PIkxKhsPSSkOtAD8DtBwnt0Ju57kJ/OTzouZ0ZwGJRzBUCZ1bkRntYZZPg4= =r/kQ -----END PGP SIGNATURE----- --=-MLPmcf3VaezyhnWN/EcJ--