Software Heritage The Global Graph of Public Code

Software Heritage The Global Graph of Public Code Stefano Zacchiroli Université de Paris & Software Heritage — [email protected], @zacchiro 17 June 2021 Meetup GraphRM, Roma (online) THE GREAT LIBRARY OF SOURC E CODE Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 1 / 36 About me Associate Professor, Université de Paris, on leave at Inria 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 2021-06-17, GraphRM 2 / 36 Outline 1Software Heritage 2Querying the archive 3Graph compression 4Graph challenges 5Conclusion Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 3 / 36 Software is fragile Like all digital information, FOSS is fragile inconsiderate and/or malicious code loss (e.g., Code Spaces) business-driven code loss (e.g., Gitorious, Google Code, Bitbucket) for obsolete code: physical media decay (data rot) Where is the archive... where do we go if (a repository on) GitHub or GitLab.com goes away? Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 3 / 36 Software is fragile Like all digital information, FOSS is fragile inconsiderate and/or malicious code loss (e.g., Code Spaces) business-driven code loss (e.g., Gitorious, Google Code, Bitbucket) for obsolete code: physical media decay (data rot) Where is the archive... where do we go if (a repository on) GitHub or GitLab.com goes away? Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 3 / 36 Software Heritage in a nutshell www.softwareheritage.org THE GREAT L I BRA 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 all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 4 / 36 Software Heritage in a nutshell www.softwareheritage.org THE GREAT L I BRA 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 all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 4 / 36 Software Heritage in a nutshell www.softwareheritage.org THE GREAT L I BRA 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 all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 4 / 36 Software Heritage in a nutshell www.softwareheritage.org THE GREAT L I BRA 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 all software source code Research infrastructure enable analysis of all software source code Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 4 / 36 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 2021-06-17, GraphRM 9 / 36 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 2021-06-17, GraphRM 10 / 36 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 2021-06-17, GraphRM 10 / 36 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 https://forge.softwareheritage.org/source/helloworld.git 3Fri Feb 9 15:52:50 2018 +0100 510aa88b… 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 <<Revision>> c7640e8d… +author = "Stefano Zacchiroli <zack@…>" +message = "move source code to src/\n…" +timestamp = Thu Feb 8 15:26:08 2018 +0100 +directory: Directory +parents: Revision list <<Directory>> fa8c0908… +entries ".gitignore" "COPYING" "Makefile" "README.md" "hello.c" <<Content>> a1afd006… +data = "…Yet another…" <<Directory>> 45f0c078… +entries "COPYING" "Makefile" "README.md" "src" <<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 <<Snapshot>> 510aa88b… +branches HEAD refs/heads/master refs/heads/doc 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 ... Archive content after visits 1, 2 and 3 Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 10 / 36 Archive coverage — archive.softwareheritage.org on disk: ~700 TB (uncompressed); as a graph ~20 B nodes, ~200 B edges the largest public source code archive in the world (and growing!) Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 11 / 36 Archive coverage — archive.softwareheritage.org on disk: ~700 TB (uncompressed); as a graph ~20 B nodes, ~200 B edges the largest public source code archive in the world (and growing!) Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 11 / 36 Web interface archive.softwareheritage.org DEMO TIME ! Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 12 / 36 Outline 1Software Heritage 2Querying the archive 3Graph compression 4Graph challenges 5Conclusion Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 13 / 36 Use cases — product needs e.g., for https://archive.softwareheritage.org Browsing ls git log (Linux kernel: 800K+ commits) Wayback machine tarball git bundle (Linux kernel: 7M+ nodes) Provenance tracking commit provenance (one/all contexts) note: requires backtracking origin provenance (one/all contexts) Note: we therefore need both the direct Merkle DAG graph and its transposed Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 13 / 36 Use cases — research questions For the sake of it local graph topology connected component size enabling question to identify the best approach (e.g., scale-up v. scale-out) to conduct large-scale analyses any other emerging property Software Engineering topics software provenance analysis at this scale is pretty much unexplored yet industry frontier: increase granularity down to the individual line of code replicate at this scale (famous) studies that have generally been conducted on (much) smaller version control system samples to confirm/refute their findings ... Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 14 / 36 Sample query — ratio of commits performed during weekends 1WITH revision_date AS 2(SELECT FROM_UNIXTIME(date /1000000)AS date 3FROM revision) 4SELECT yearly_rev.year AS year, 5CAST(yearly_weekend_rev.number AS DOUBLE) 6/yearly_rev.number *100.0AS weekend_pc 7FROM 8(SELECT YEAR(date)AS year,COUNT(*)AS number 9FROM revision_date 10 WHERE YEAR(date)BETWEEN 1971 AND 2018 11 GROUP BY YEAR(date))AS yearly_rev 12 JOIN 13 (SELECT YEAR(date)AS year,COUNT(*)AS number 14 FROM revision_date 15 WHERE DAY_OF_WEEK(date)>= 6 16 AND YEAR(date)BETWEEN 1971 AND 2018 17 GROUP BY YEAR(date))AS yearly_weekend_rev 18 ON yearly_rev.year =yearly_weekend_rev.year 19 ORDER BY year DESC; Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 19 / 36 Sample query — ratio of commits performed during weekends (cont.) Year Weekend Total Weekend percentage 2018 15130065 78539158 19.26 2017 33776451 168074276 20.09 2016 43890325 209442130 20.95 2015 35781159 166884920 21.44 2014 24591048 122341275 20.10 2013 17792778 88524430 20.09 2012 12794430 64516008 19.83 2011 9765190 48479321 20.14 2010 7766348 38561515 20.14 2009 6352253 31053219 20.45 2008 4568373 22474882 20.32 2007 3318881 16289632 20.37 2006 2597142 12224905 21.24 2005 2086697 9603804 21.72 2004 1752400 7948104 22.04 2003 1426033 6941593 20.54 2002 1159294 5378538 21.55 2001 849905 4098587 20.73 2000 2091770 4338842 48.21 1999 438540 2026906 21.63 1998 311888 1430567 21.80 1997 263995 1129249 23.37 1996 192543 795827 24.19 1995 176270 670417 26.29 1994 137811 581563 23.69 1993 169767 697343 24.34 1992 74923 422068 17.75 1991 92782 484547 19.14 1990 113201 340489 33.24 1989 31742 182325 17.40 1988 44983 206275 21.80 1987 27892 146157 19.08 1986 54200 237330 22.83 1985 75595 306564 24.65 1984 26391 95506 27.63 1983 89776 370687 24.21 1982 51524 191933 26.84 1981 32995 123618 26.69 1980 31832 133733 23.80 1979 20943 175164 11.95 1978 3773 33677 11.20 1977 4783 19376 24.68 1976 1907 7048 27.05 1975 2089 26579 7.85 1974 2095 14290 14.66 1973 2988 15580 19.17 1972 1755 6552 26.78 1971 1723 6125 28.13 Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 20 / 36 Sample query — average size of the most popular file types 1SELECT suffix, 2ROUND(COUNT(*)*100 /1e6)AS Million_files, 3ROUND(AVG(length)/1024)AS Average_k_length 4FROM 5(SELECT length,suffix 6FROM -- File length in joinable form 7(SELECT TO_BASE64(sha1_git)AS sha1_git64,length 8FROM content )AS content_length 9JOIN -- Sample of files with popular suffixes 10 (SELECT target64,file_suffix_sample.suffix AS suffix 11 FROM -- Popular suffixes 12 (SELECT suffix FROM ( 13 SELECT REGEXP_EXTRACT(FROM_UTF8(name), 14 '\.[^.]+$')AS suffix 15 FROM directory_entry_file)AS file_suffix 16 GROUP BY suffix 17 ORDER BY COUNT(*)DESC LIMIT 20 )AS pop_suffix 18 JOIN -- Sample of files and suffixes 19 (SELECT TO_BASE64(target)AS target64, 20 REGEXP_EXTRACT(FROM_UTF8(name), 21 '\.[^.]+$')AS suffix 22 FROM directory_entry_file TABLESAMPLE BERNOULLI(1)) 23 AS file_suffix_sample 24 ON file_suffix_sample.suffix =pop_suffix.suffix) 25 AS pop_suffix_sample 26 ON pop_suffix_sample.target64 =content_length.sha1_git64) 27 GROUP BY suffix 28 ORDER BY AVG(length)DESC; Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 21 / 36 Sample study — 50 years of gender differences in code contributions start from the Software Heritage graph dataset detect gender of author names using standard tooling (gender-guesser) analyze both authors and commits over time, bucketing by commit timestamp male authors 47.7% (630.2M) female authors 3.9% (51.3M) unknown 48.5% (640.6M) 1970 1980 1990 2000 2010 date 0.0% 2.0% 4.0% 6.0% 8.0% 10.0% 12.0% trend (lowess( =0.67,it=3, =0)) ratio of female authors total commits by author gender (left), ratio of active female commiters over time (right) Stefano Zacchiroli Gender Differences in Public Code Contributions: a 50-year Perspective IEEE Softw. 38(2): 45-50 (2021) Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 22 / 36 Discussion one can query such a corpus SQL-style but relational representation shows its limits at this scale ...at least as deployed on commercial SQL offerings such as Athena note: (naive) sharding is ineffective, due to the pseudo-random distribution of node identifiers experiments with Google BigQuery are ongoing (we broke it at the first import attempt..., due to very large arrays in directory entry tables) Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 23 / 36 Outline 1Software Heritage 2Querying the archive 3Graph compression 4Graph challenges 5Conclusion Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 24 / 36 Graph compression on the Software Heritage archive 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 ultra large scale (= the scale of Software Heritage archive or more), on a single, relatively cheap machine? Idea Apply state-of-the-art graph compression techniques from the field of Web graph / social network analysis. Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 24 / 36 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 2021-06-17, GraphRM 25 / 36 Background — (Web) graph compression (cont.) Definition (The graph of the Web) Directed graph that has Web pages as nodes and hyperlinks between them as edges. Properties (2) Similarity: pages that are close together in lexicographic order tend to have many common successors.  use reference compression Adjacency lists Node Outd. 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 ... ... ... Copy lists Node Ref. Copy list Extra nodes ... ... ... ... 15 0 13,15,16,17,18,19,23,24,203,315,1034 16 1 01110011010 22,316,317,3041 17 18 3 11110000000 50 ... ... ... Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 26 / 36 Corpus Nodes Node type N. of nodes origins 88 M snapshots 57 M releases 9.9 M revisions 1.1 B directories 4.9 B contents 5.5 B Total nodes 12 B Edges Edge type N. of edges origin  snapshot 195 M snapshot  revision 616 M snapshot  release 215 M release  revision 9.9 M revision  revision 1.2 B revision  directory 1.1 B directory  directory 48 B directory  revisiony 482 M directory  content 112 B Total edges 165 B Stats for archive snapshot 2018-09-25, from the Software Heritage graph dataset. Growth rate: exponential, doubling every 22-30 months, cf.: Roberto Di Cosmo, Guillaume Rousseau, Stefano Zacchiroli Software Provenance Tracking at the Scale of Public Source Code Empirical Software Engineering 25(4): 2930-2959 (2020) Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 27 / 36 Outline 1Software Heritage 2Querying the archive 3Graph compression 4Graph challenges 5Conclusion Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 33 / 36 Technical leads for graph geeks (selected) A graph query language for Software Heritage Design and implement a graph query language suitable for Software Heritage use cases and specifities (e.g., read-only, compressed representation, split in-memory/on-disk representation, etc). Possibly building on-top existing graph technologies: e.g., an Apache TinkerPop backend for WebGraph Learn more: https://wiki.softwareheritage.org/wiki/Graph_ query_language_for_the_archive_(internship) Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 33 / 36 Technical leads for graph geeks (selected) (cont.) Python bindings for WebGraph (Java) Enable researchers and data scientists to exploit the graph in a familiar ecosystem (NumPy, Pandas, iGraph, etc.) Requires careful performance trade-offs to minimize jumping between the two runtimes Learn more: https://wiki.softwareheritage.org/wiki/ Python_bindings_for_WebGraph_(internship) Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 34 / 36 Graph storage challenge Can your graph database do better? A recent dump of the Software Heritage graph is available in Apache ORC data format from AWS S3 as an open dataset (8.4 TiB) Schema documentation: https://docs.softwareheritage.org/ devel/swh-dataset/graph/schema.html Try it out: load it into your favorite graph database and see if it is up to the challenge. We’d love to hear about it! $ aws s3 ls s3://softwareheritage/graph/2021-03-23/orc/ PRE content/ PRE directory/ PRE origin/ PRE release/ PRE revision/ [...] $ aws s3 ls s3://softwareheritage/graph/2021-03-23/orc/directory/ | head -n 1 2021-04-13 06:59:21 3004055177 graph-03891ef6-18c0-46e7-88db-42056fa33282.orc Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 35 / 36 Outline 1Software Heritage 2Querying the archive 3Graph compression 4Graph challenges 5Conclusion Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 36 / 36 Wrapping up Software Heritage archives all public source code as a huge Merkle DAG The Software Heritage graph offers an unified view on the software commons Querying and analyzing it at scale (20/200 B nodes/edges) is an open problem Gold mine of R&D challenges and leads for graph geeks References homepage: www.softwareheritage.org development info: www.softwareheritage.org/community/developers Contacts Stefano Zacchiroli / upsilon.cc / [email protected] / @zacchiro Stefano Zacchiroli Software Heritage 2021-06-17, GraphRM 36 / 36 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 2021-06-17, GraphRM 1 / 3 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 2021-06-17, GraphRM 1 / 3 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 2021-06-17, GraphRM 1 / 3 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 2021-06-17, GraphRM 1 / 3