Software Heritage Analyzing the Global Graph of Public Software Development

Software Heritage Analyzing the Global Graph of Public Software Development Stefano Zacchiroli Télécom Paris, Institut Polytechnique de Paris [email protected] 7 Oct 2022 ENS Rennes THE GREAT LIBRARY OF SOURC E CODE Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 1 / 30 Outline 1Preface 2The Software Commons 3Software Heritage 4Research highlights in empirical software engineering 5Conclusion Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 2 / 30 About the speaker Professor of Computer Science, Télécom Paris, Institut Polytechnique de Paris Free/Open Source Software activist (20+ years) Debian Developer & Former 3x Debian Project Leader Former Open Source Initiative (OSI) director Software Heritage co-founder & CTO Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 2 / 30 Outline 1Preface 2The Software Commons 3Software Heritage 4Research highlights in empirical software engineering 5Conclusion Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 3 / 30 Software is everywhere (and a key mediator) in society Software Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 3 / 30 Free/Open Source Software (FOSS) is everywhere as well Definition (Free Software (1986)) A program is free software if the program’s users have the four essential freedoms: Freedom #0, to run the program, for any purpose Freedom #1, to study how the program works, and change it Freedom #2, to redistribute copies Freedom #3, to improve the program, and release improvements Current estimates: 99% of software products on the market contains at least some free software parts (Synopsis 2020). Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 4 / 30 The Commons and FOSS Definition (Commons) The commons is the cultural and natural resources accessible to all members of a society, including natural materials such as air, water, and a habitable earth. These resources are held in common, not owned privately. Definition (Software Commons) The software commons consists of all computer software which is available at little or no cost and which can be altered and reused with few restrictions. Thus all open source software and all free software are part of the [software] commons. [...] Kranich and Schement (2008); Schweik and English (2012). Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 5 / 30 Software source code is precious human knowledge Harold Abelson, Structure and Interpretation of Computer Programs (1st ed.) 1985 “Programs must be written for people to read, and only incidentally for machines to execute.” Apollo 11 source code (excerpt)Quake III source code ( excerpt ) Len Shustek, Computer History Museum 2006 “Source code provides a view into the mind of the designer.” Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 6 / 30 Software source code is precious human knowledge Harold Abelson, Structure and Interpretation of Computer Programs (1st ed.) 1985 “Programs must be written for people to read, and only incidentally for machines to execute.” Apollo 11 source code (excerpt) Quake III source code ( excerpt ) Len Shustek, Computer History Museum 2006 “Source code provides a view into the mind of the designer.” Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 6 / 30 Software Heritage in a nutshell www.softwareheritage.org THE GREAT LIBRA RY OF SO URCE CO D E Collect, preserve and share all software source code Preserving our heritage, enabling better software and better science for all Reference catalog find and reference all software source code Universal archive preserve and share all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 8 / 30 Software Heritage in a nutshell www.softwareheritage.org THE GREAT LIBRA RY OF SO URCE CO D E Collect, preserve and share all software source code Preserving our heritage, enabling better software and better science for all Reference catalog find and reference all software source code Universal archive preserve and share all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 8 / 30 Software Heritage in a nutshell www.softwareheritage.org THE GREAT LIBRA RY OF SO URCE CO D E Collect, preserve and share all software source code Preserving our heritage, enabling better software and better science for all Reference catalog find and reference all software source code Universal archive preserve and share all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 8 / 30 Archiving goals Targets: VCS repositories & source code releases (e.g., tarballs, packages) We DO archive file content (= blobs) revisions (= commits), with full metadata releases (= tags), ditto where (origin) & when (visit) we found any of the above ... in a VCS-/archive-agnostic canonical data model We DON’T archive (yet) homepages, wikis BTS/issues/code reviews/etc. mailing lists Long term vision: play our part in a "semantic wikipedia of software" Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 9 / 30 Data flow deb deb hg hg hg git git git git svn svn svn pypi pypi software origins Package repos Software Heritage Archive Forges GitHub lister GitLab lister Debian lister Git loader Mercurial loader Debian source package loader PyPI lister PyPI loader Merkle DAG + blob storage . . . . . . Distros ... Scheduling Listing (full/incremental) Loading & deduplication Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 10 / 30 Merkle trees Merkle tree (R. C. Merkle, CRYPTO 1987) Combination of tree hash function Classical cryptographic construction fast, parallel signature of large data structures widely used (e.g., Git, blockchains, IPFS, ...) built-in deduplication Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 11 / 30 Merkle trees Merkle tree (R. C. Merkle, CRYPTO 1987) Combination of tree hash function Classical cryptographic construction fast, parallel signature of large data structures widely used (e.g., Git, blockchains, IPFS, ...) built-in deduplication Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 11 / 30 Data model Origin + url: str branches Snapshot * * Release directory Revision * ** * Merkle DAG target 1 entries parents snapshots + id: sha1 Directory entries + id: sha1 + id: sha1 + author: str + name: str + message: str + timestamp: datetime + id: sha1 + author: str + message: str + timestamp: datetime Content + id:sha1 Aglobal graph linking together fully deduplicated source code artifact (files, commits, directories, releases, etc.) to the places that distribute them (e.g., Git repositories), providing a unified view on the entire Software Commons. Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 12 / 30 The archive: a (giant) Merkle DAG origin visit https://forge.softwareheritage.org/source/helloworld.git snapshot 1 timestamp Fri Feb 9 12:38:45 2018 +0100 0861db5e… <<Revision>> a3ee21ad… +author = "Stefano Zacchiroli <zack@…>" +message = "add build toolchain …" +timestamp = Thu Feb 8 10:49:29 2018 +0100 +directory: Directory +parents: Revision list <<Directory>> b94a90cd… +entries ".gitignore" "Makefile" "hello.c" <<Content>> 225ae01b… +data = "all: hello\n\n…" <<Revision>> 43ef7dcd… +author = "Stefano Zacchiroli <zack@…>" +message = "add licensing information and README" +timestamp = Thu Feb 8 10:54:09 2018 +0100 +directory: Directory +parents: Revision list <<Directory>> fa8c0908… +entries ".gitignore" "COPYING" "Makefile" "README.md" "hello.c" <<Content>> a1afd006… +data = "…Yet another…" <<Release>> edf82f21… +author = "Stefano Zacchiroli <zack@…>" +name = "1.0" +message = "1.0 release" +timestamp = Thu Feb 8 15:51:00 2018 +0100 +target <<Snapshot>> 0861db5e… +branches HEAD refs/heads/master refs/tags/1.0 Archive content after visit 1 <<Content>> c839dea9… +data = "#include …" <<Directory>> 6ca2e444… +entries "hello.c" <<Revision>> 1886826f… +author = "Stefano Zacchiroli <zack@…>" +message = "implement a trivial …" +timestamp = Thu Feb 8 10:44:35 2018 +0100 +directory: Directory +parents: Revision list = None Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 13 / 30 The archive: a (giant) Merkle DAG origin visit https://forge.softwareheritage.org/source/helloworld.git snapshot 1 https://forge.softwareheritage.org/source/helloworld.git 2 timestamp Fri Feb 9 12:38:45 2018 +0100 Fri Feb 9 13:29:00 2018 +0100 0861db5e… 0861db5e… <<Revision>> a3ee21ad… +author = "Stefano Zacchiroli <zack@…>" +message = "add build toolchain …" +timestamp = Thu Feb 8 10:49:29 2018 +0100 +directory: Directory +parents: Revision list <<Directory>> b94a90cd… +entries ".gitignore" "Makefile" "hello.c" <<Content>> 225ae01b… +data = "all: hello\n\n…" <<Revision>> 43ef7dcd… +author = "Stefano Zacchiroli <zack@…>" +message = "add licensing information and README" +timestamp = Thu Feb 8 10:54:09 2018 +0100 +directory: Directory +parents: Revision list <<Directory>> fa8c0908… +entries ".gitignore" "COPYING" "Makefile" "README.md" "hello.c" <<Content>> a1afd006… +data = "…Yet another…" <<Release>> edf82f21… +author = "Stefano Zacchiroli <zack@…>" +name = "1.0" +message = "1.0 release" +timestamp = Thu Feb 8 15:51:00 2018 +0100 +target <<Snapshot>> 0861db5e… +branches HEAD refs/heads/master refs/tags/1.0 Archive content after visits 1 and 2 <<Content>> c839dea9… +data = "#include …" <<Directory>> 6ca2e444… +entries "hello.c" <<Revision>> 1886826f… +author = "Stefano Zacchiroli <zack@…>" +message = "implement a trivial …" +timestamp = Thu Feb 8 10:44:35 2018 +0100 +directory: Directory +parents: Revision list = None Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 13 / 30 Graph dataset — example SELECT COUNT(*) AS c, word FROM ( SELECT LOWER(REGEXP_EXTRACT(FROM_UTF8( message), ’^\w+’)) AS word FROM revision) WHERE word != ’’ GROUP BY word ORDER BY COUNT(*) DESC LIMIT 5; Count Word 71 338 310 update 64 980 346 merge 56 854 372 add 44 971 954 added 33 222 056 fix Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 17 / 30 Graph dataset — example SELECT COUNT(*) AS c, word FROM ( SELECT LOWER(REGEXP_EXTRACT(FROM_UTF8( message), ’^\w+’)) AS word FROM revision) WHERE word != ’’ GROUP BY word ORDER BY COUNT(*) DESC LIMIT 5; Count Word 71 338 310 update 64 980 346 merge 56 854 372 add 44 971 954 added 33 222 056 fix Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 17 / 30 Graph dataset — example Fork arity i.e., how often is a commit based upon? SELECT fork_deg, count(*) FROM ( SELECT id, count(*) AS fork_deg FROM revision_history GROUP BY id) t GROUP BY fork_deg ORDER BY fork_deg; 0.1 1 10 100 1000 10000 100000 1x106 1x107 1x108 1x109 1x1010 0.1 1 10 100 1000 10000 100000 1x106 1x107 Number of nodes Degree Merge arity i.e., how large are merges? SELECT merge_deg, COUNT(*) FROM ( SELECT parent_id, COUNT(*) AS merge_deg FROM revision_history GROUP BY parent_id) t GROUP BY merge_deg ORDER BY merge_deg; 0.1 1 10 100 1000 10000 100000 1x106 1x107 1x108 1x109 1x1010 0.1 1 10 100 1000 10000 100000 1x106 1x107 Number of nodes Degree Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 18 / 30 Graph dataset — example Fork arity i.e., how often is a commit based upon? SELECT fork_deg, count(*) FROM ( SELECT id, count(*) AS fork_deg FROM revision_history GROUP BY id) t GROUP BY fork_deg ORDER BY fork_deg; 0.1 1 10 100 1000 10000 100000 1x106 1x107 1x108 1x109 1x1010 0.1 1 10 100 1000 10000 100000 1x106 1x107 Number of nodes Degree Merge arity i.e., how large are merges? SELECT merge_deg, COUNT(*) FROM ( SELECT parent_id, COUNT(*) AS merge_deg FROM revision_history GROUP BY parent_id) t GROUP BY merge_deg ORDER BY merge_deg; 0.1 1 10 100 1000 10000 100000 1x106 1x107 1x108 1x109 1x1010 0.1 1 10 100 1000 10000 100000 1x106 1x107 Number of nodes Degree Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 18 / 30 License dataset Stefano Zacchiroli A Large-scale Dataset of (Open Source) License Text Variants MSR 2022 (best dataset paper award) preprint: https://arxiv.org/abs/2204.00256 Dataset 6.5 million unique full texts of FOSS license variants Detected using filename patterns across the entire SWH archive LICENSE,COPYRIGHT,NOTICE, etc. Metadata: file lengths measures, detected MIME type, detected SPDX license (via ScanCode), example origin repository, oldest public commit of origin Use cases Empirical studies on FOSS licensing, including phylogenetics Training of automated license classifiers NLP analyses of legal texts Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 19 / 30 The Software Heritage Filesystem (SwhFS) The Software Heritage Filesystem (SwhFS) is a user-space POSIX filesystem that enables browsing parts of the Software Heritage archive as if it were locally available. code: forge.softwareheritage.org/source/swh-fuse documentation: docs.softwareheritage.org/devel/swh-fuse Thibault Allançon, Antoine Pietri, Stefano Zacchiroli The Software Heritage Filesystem (SwhFS): Integrating Source Code Archival with Development ICSE 2021: The 43rd International Conference on Software Engineering https://arxiv.org/abs/2102.06390 Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 20 / 30 The Software Heritage Filesystem (SwhFS) — example $ mkdir swhfs $ swh fs mount swhfs/ # mount the archive $ cd swhfs/ $ cat archive/swh:1:cnt:c839dea9e8e6f0528b468214348fee8669b305b2 #include <stdio.h> int main(void) { printf("Hello, World!\n"); } $ cd archive/swh:1:dir:1fee702c7e6d14395bbf5ac3598e73bcbf97b030 $ ls | wc -l 127 $ grep -i antenna THE_LUNAR_LANDING.s | cut -f 5 # IS THE LR ANTENNA IN POSITION 1 YET # BRANCH IF ANTENNA ALREADY IN POSITION 1 Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 21 / 30 The Software Heritage Filesystem (SwhFS) — example (cont.) $ cd archive/swh:1:rev:9d76c0b163675505d1a901e5fe5249a2c55609bc $ ls -F history/ meta.json@ parent@ parents/ root@ $ jq ’.author.name, .date, .message’ meta.json "Michal Golebiowski-Owczarek" "2020-03-02T23:02:42+01:00" "Data:Event:Manipulation: Prevent collisions with Object.prototype ..." $ find root/src/ -type f -name ’*.js’ | xargs cat | wc -l 10136 Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 22 / 30 Graph compression Paolo Boldi, Antoine Pietri, Sebastiano Vigna, Stefano Zacchiroli Ultra-Large-Scale Repository Analysis via Graph Compression SANER 2020, 27th Intl. Conf. on Software Analysis, Evolution and Reengineering. IEEE Research question Is it possible to efficiently perform software development history analyses at the scale of Software Heritage archive on a single, relatively cheap machine? Idea Apply state-of-the-art graph compression techniques from the field of Web graph / social network analysis. Results The entire archive graph (25 B nodes, 350 B edges) can be loaded in 200 GiB and then traversed at the cost of tens of ns per edge (= a few hours for a full single-thread visit). Java and gRPC APIs available: docs.softwareheritage.org/devel/swh-graph/grpc-api.html Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 23 / 30 Background — (Web) graph compression Definition (The graph of the Web) Directed graph that has Web pages as nodes and hyperlinks between them as edges. Properties (1) Locality: pages link to pages whose URLs are lexicographically similar. URLs share long common prefixes.  use D-gap compression Adjacency lists Node Outdegree Successors ... ... ... 15 11 13,15,16,17,18,19,23,24,203,315,1034 16 10 15,16,17,22,23,24,315,316,317,3041 17 0 18 5 13,15,16,17,50 ... ... ... D-gapped adjacency lists Node Outdegree Successors ... ... ... 15 11 3,1,0,0,0,0,3,0,178,111,718 16 10 1,0,0,4,0,0,290,0,0,2723 17 0 18 5 9,1,0,0,32 ... ... ... Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 24 / 30 Conclusion Software Heritage archives public code and its history as a huge Merkle DAG Querying and analyzing it at scale (25/350 B nodes/edges) is an open problem Gold mine of research leads in and around empirical software engineering Coding Developer info: www.softwareheritage.org/community/developers Work with us Open positions (tech & research): www.softwareheritage.org/jobs Student opportunities Internships, GSoC/Outreachy, student grants www.softwareheritage.org/community/students Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 30 / 30 Appendix Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 1 / 7 Compression experiment Step Wall time (hours) MPH 2 BV Compress 84 BFS 19 Permute 18 Transpose 15 Total 138 (6 days) server equipped with 24 CPUs and 750 GB of RAM RAM mostly used as I/O cache for the BFS step minimum memory requirements are close to the RAM needed to load the final compressed graph in memory Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 2 / 7 Compression efficiency (space) Forward graph total size 91 GiB bits per edge 4.91 compression ratio 15.8% Backward graph total size 83 GiB bits per edge 4.49 compression ratio 14.4% Operating cost The structure of a full bidirectional archive graph fits in less than 200 GiB of RAM, for a hardware cost of ~300 USD. Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 3 / 7 Compression efficiency (time) Benchmark — Full BFS visit (single thread) Forward graph wall time 1h48m throughput 1.81 M nodes/s (553 ns/node) Backward graph wall time 3h17m throughput 988 M nodes/s (1.01 µs/node) Benchmark — Edge lookup random sample: 1 B nodes (8.3% of entire graph); then enumeration of all successors Forward graph visited edges 13.6 B throughput 12.0 M edges/s (83 ns/edge) Backward graph visited edges 13.6 B throughput 9.45 M edges/s (106 ns/edge) Note how edge lookup time is close to DRAM random access time (50-60 ns). Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 4 / 7 Discussion Incrementality compression is not incremental, due to the use of contiguous integer ranges but the graph is append-only, so... ...based on expected graph growth rate it should be possible to pre-allocate enough free space in the integer ranges to support amortized incrementality (future work) In-memory v. on-disk the compressed in-memory graph structure has no attributes usual design is to exploit the 0..N-1 integer ranges to memory map node attributes to disk for efficient access works well for queries that does graph traversal first and "join" node attributes last; ping-pong between the two is expensive edge attributes are more problematic (work in progress) Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 5 / 7 Discussion Incrementality compression is not incremental, due to the use of contiguous integer ranges but the graph is append-only, so... ...based on expected graph growth rate it should be possible to pre-allocate enough free space in the integer ranges to support amortized incrementality (future work) In-memory v. on-disk the compressed in-memory graph structure has no attributes usual design is to exploit the 0..N-1 integer ranges to memory map node attributes to disk for efficient access works well for queries that does graph traversal first and "join" node attributes last; ping-pong between the two is expensive edge attributes are more problematic (work in progress) Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 5 / 7 Software Heritage Identifiers (SWHIDs) (full spec) An emerging standard in Linux Foundation’s SPDX 2.2 IANA-registered "swh:" URI prefix WikiData property P6138 Examples Apollo 11 AGC excerpt Quake III rsqrt Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 6 / 7 Software Heritage Identifiers (SWHIDs) (full spec) An emerging standard in Linux Foundation’s SPDX 2.2 IANA-registered "swh:" URI prefix WikiData property P6138 Examples Apollo 11 AGC excerpt Quake III rsqrt Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 6 / 7 Software Heritage Identifiers (SWHIDs) (full spec) An emerging standard in Linux Foundation’s SPDX 2.2 IANA-registered "swh:" URI prefix WikiData property P6138 Examples Apollo 11 AGC excerpt Quake III rsqrt Stefano Zacchiroli Software Heritage 2022-10-07, ENS Rennes 6 / 7