Page MenuHomeSoftware Heritage
Differential D1726

Add node id -> node types bitmap
ClosedPublic
Actions

Authored by haltode on Jul 11 2019, 4:31 PM.

Details

Reviewers
zack
Maniphest Tasks
T1902: Use in-memory bitmap to store node->types relations in graph API
Commits
rDGRPHedf9e6fa4b86: server: backend: use log2 instead of hard-coded result
rDGRPH61ee41418867: server: rename graph mapping files
rDGRPH025d694fd0aa: server: store/load node types map
Summary

Add node id -> node type bitmap to effectively run edge restriction
during graph traversals.

This is still WIP because I am waiting on full scale test results. Also, this
diff is only about *loading/storing* the bitmap, not using it, because it needs
to be merged with recent D1700 work (in a separate diff).

Closes T1902.

Diff Detail

Repository
rDGRPH Compressed graph representation
Branch
node-type-map
Lint
No Linters Available
Unit
No Unit Test Coverage
Build Status
Buildable 6861
Build 9610: arc lint + arc unit

Event Timeline

haltode created this revision.Jul 11 2019, 4:31 PM
Harbormaster completed remote builds in B6826: Diff 5803.Jul 11 2019, 4:31 PM
zack requested changes to this revision.Jul 11 2019, 5:09 PM
zack added inline comments.
api/server/src/main/java/org/softwareheritage/graph/Node.java
8–31

we also need ORI here now

9–13

this deserves a comment pointing to some external reference about SWH PIDs, to explain where these weird magic labels come from

api/server/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java
15–17

DRY violation: ".nodesTypesMap" is used twice, hence it could use a constant somewhere :-)

while we are at it, minor naming bikeshed, how about .node2type instead?

api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java
77

Can we make this the result of a log2 calculation on the size of the Node.Type enum? (unless it's too annoying to code, that is)

It would be nicer, and less prone to future bugs if we ever add/remove node types in the future.

97

this is another place where the constant proposed above should be used

This revision now requires changes to proceed.Jul 11 2019, 5:09 PM
haltode added inline comments.Jul 11 2019, 5:43 PM
api/server/src/main/java/org/softwareheritage/graph/Node.java
8–31

I do prefer to add ORI support in another diff as well, there are multiple places to update (here of course, but also the example test graph, the unit tests themselves, and so on).

9–13

Dev documentation is almost entirely absent for the moment in the code, I was thinking about adding all references/external links in a separate diff (this doc task is already tracked in T1904).

api/server/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java
15–17

To be more consistent with other files, should we go with .node2swh and .swh2node as well?

api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java
77

Sure, it's a bit sad Java only has log, log10, log1p but no log2 :(

zack added inline comments.Jul 12 2019, 9:43 AM
api/server/src/main/java/org/softwareheritage/graph/Node.java
8–31

ok, fair enough. Please file a dedicated task, for better tracking of this need

9–13

*nod*

api/server/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java
15–17

yeah, good idea. So, let's streamline this completely and use:

  • .node2type.map
  • .node2pid.{csv,map}
  • .pid2node.{csv,map}

note:

  • the trailing .map for files that are in custom binary formats
  • the use of "pid" instead of "swh", because swh is contextual-implicit and PIDs are what those things really are
  • I'm guessing you'll want to keep CSV format for now (hence .csv), but eventually they'll probably all disappear in favor of more efficient binary formats; we'll switch to .map then
api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java
77

something like Math.ceil(Math.log(x) / Math.log(2)) then?

haltode updated this revision to Diff 5821.EditedJul 14 2019, 8:21 PM
  • Rename graph mapping files
  • Use log2 instead of hard-coded result
Harbormaster completed remote builds in B6861: Diff 5821.Jul 14 2019, 8:21 PM
haltode marked 9 inline comments as done.Jul 14 2019, 8:21 PM
haltode added inline comments.
api/server/src/main/java/org/softwareheritage/graph/Node.java
8–31

See T1915.

zack accepted this revision.Jul 15 2019, 10:01 AM
This revision is now accepted and ready to land.Jul 15 2019, 10:01 AM
Closed by commit rDGRPH025d694fd0aa: server: store/load node types map (authored by haltode). · Explain WhyJul 15 2019, 10:04 AM
This revision was automatically updated to reflect the committed changes.
haltode marked an inline comment as done.

Revision Contents
Changeset List

PathSize
api/
server/
src/
main/
java/
org/
softwareheritage/
graph/
12 lines
16 lines
backend/
9 lines
26 lines
31 lines
test/
dataset/
5 lines

Diff 5821

View Options

api/server/src/main/java/org/softwareheritage/graph/Graph.java

  • This file was added.
# Copyright (C) 2021 The Software Heritage developers
# See the AUTHORS file at the top-level directory of this distribution
# License: GNU General Public License version 3, or any later version
# See top-level LICENSE file for more information
"""
This module contains additional tests for the bare cooker.
Generic cooker tests (eg. without swh-graph) in test_cookers.py also
run on the bare cooker.
"""
import datetime
import io
import subprocess
import tarfile
import tempfile
import unittest.mock
from swh.graph.naive_client import NaiveClient as GraphClient
from swh.model.from_disk import DentryPerms
from swh.model.model import (
Content,
Directory,
DirectoryEntry,
Person,
Revision,
RevisionType,
TimestampWithTimezone,
)
from swh.vault.cookers.git_bare import GitBareCooker
from swh.vault.in_memory_backend import InMemoryVaultBackend
def test_graph_revisions(swh_storage):
# Build objects:
# rev1 <------ rev2
# | |
# v v
# dir1 dir2
# | / |
# v / v
# cnt1 <----° cnt2
date = TimestampWithTimezone.from_datetime(
datetime.datetime(2021, 5, 7, 8, 43, 59, tzinfo=datetime.timezone.utc)
)
author = Person.from_fullname(b"Foo <foo@example.org>")
cnt1 = Content.from_data(b"hello")
cnt2 = Content.from_data(b"world")
dir1 = Directory(
entries=(
DirectoryEntry(
name=b"file1",
type="file",
perms=DentryPerms.content,
target=cnt1.sha1_git,
),
)
)
dir2 = Directory(
entries=(
DirectoryEntry(
name=b"file1",
type="file",
perms=DentryPerms.content,
target=cnt1.sha1_git,
),
DirectoryEntry(
name=b"file2",
type="file",
perms=DentryPerms.content,
target=cnt2.sha1_git,
),
)
)
rev1 = Revision(
message=b"msg1",
date=date,
committer_date=date,
author=author,
committer=author,
directory=dir1.id,
type=RevisionType.GIT,
synthetic=True,
)
rev2 = Revision(
message=b"msg2",
date=date,
committer_date=date,
author=author,
committer=author,
directory=dir2.id,
parents=(rev1.id,),
type=RevisionType.GIT,
synthetic=True,
)
# Add all objects to storage
swh_storage.content_add([cnt1, cnt2])
swh_storage.directory_add([dir1, dir2])
swh_storage.revision_add([rev1, rev2])
# Add spy on swh_storage, to make sure revision_log is not called
# (the graph must be used instead)
swh_storage = unittest.mock.MagicMock(wraps=swh_storage)
# Add all objects to graph
swh_graph = unittest.mock.Mock(
wraps=GraphClient(
nodes=[str(n.swhid()) for n in [cnt1, cnt2, dir1, dir2, rev1, rev2]],
edges=[
(str(s.swhid()), str(d.swhid()))
for (s, d) in [
(dir1, cnt1),
(dir2, cnt1),
(dir2, cnt2),
(rev1, dir1),
(rev2, dir2),
(rev2, rev1),
]
],
)
)
# Cook
backend = InMemoryVaultBackend()
cooker = GitBareCooker(
"revision_gitbare",
rev2.id,
backend=backend,
storage=swh_storage,
graph=swh_graph,
)
cooker.cook()
# Get bundle
bundle = backend.fetch("revision_gitbare", rev2.id)
# Extract bundle and make sure both revisions are in it
olasdUnsubmitted
Not Done
Inline Actions

As this initialization really depends on the shape of the objects, it would probably be clearer if it was wrapped in the same function as the one which creates the objects in the first place. You could put the population of the edge lists next to the object initialization.

olasd: As this initialization really depends on the shape of the objects, it would probably be clearer…
with tempfile.TemporaryDirectory("swh-vault-test-bare") as tempdir:
with tarfile.open(fileobj=io.BytesIO(bundle)) as tf:
tf.extractall(tempdir)
output = subprocess.check_output(
[
"git",
"-C",
f"{tempdir}/{rev2.swhid()}.git",
"log",
"--format=oneline",
"--decorate=",
]
)
assert output.decode() == f"{rev2.id.hex()} msg2\n{rev1.id.hex()} msg1\n"
# Make sure the graph was used instead of swh_storage.revision_log
swh_storage.revision_log.assert_not_called()
swh_storage.revision_shortlog.assert_not_called()
swh_graph.visit_nodes.assert_called_once_with(str(rev2.swhid()), edges="rev:rev")
View Options

api/server/src/main/java/org/softwareheritage/graph/Node.java

  • This file was added.
# Copyright (C) 2021 The Software Heritage developers
# See the AUTHORS file at the top-level directory of this distribution
# License: GNU General Public License version 3, or any later version
# See top-level LICENSE file for more information
"""
This module contains additional tests for the bare cooker.
Generic cooker tests (eg. without swh-graph) in test_cookers.py also
run on the bare cooker.
"""
import datetime
import io
import subprocess
import tarfile
import tempfile
import unittest.mock
from swh.graph.naive_client import NaiveClient as GraphClient
from swh.model.from_disk import DentryPerms
from swh.model.model import (
Content,
Directory,
DirectoryEntry,
Person,
Revision,
RevisionType,
TimestampWithTimezone,
)
from swh.vault.cookers.git_bare import GitBareCooker
from swh.vault.in_memory_backend import InMemoryVaultBackend
def test_graph_revisions(swh_storage):
# Build objects:
# rev1 <------ rev2
# | |
# v v
# dir1 dir2
# | / |
# v / v
# cnt1 <----° cnt2
date = TimestampWithTimezone.from_datetime(
datetime.datetime(2021, 5, 7, 8, 43, 59, tzinfo=datetime.timezone.utc)
)
author = Person.from_fullname(b"Foo <foo@example.org>")
cnt1 = Content.from_data(b"hello")
cnt2 = Content.from_data(b"world")
dir1 = Directory(
entries=(
DirectoryEntry(
name=b"file1",
type="file",
perms=DentryPerms.content,
target=cnt1.sha1_git,
),
)
)
dir2 = Directory(
entries=(
DirectoryEntry(
name=b"file1",
type="file",
perms=DentryPerms.content,
target=cnt1.sha1_git,
),
DirectoryEntry(
name=b"file2",
type="file",
perms=DentryPerms.content,
target=cnt2.sha1_git,
),
)
)
rev1 = Revision(
message=b"msg1",
date=date,
committer_date=date,
author=author,
committer=author,
directory=dir1.id,
type=RevisionType.GIT,
synthetic=True,
)
rev2 = Revision(
message=b"msg2",
date=date,
committer_date=date,
author=author,
committer=author,
directory=dir2.id,
parents=(rev1.id,),
type=RevisionType.GIT,
synthetic=True,
)
# Add all objects to storage
swh_storage.content_add([cnt1, cnt2])
swh_storage.directory_add([dir1, dir2])
swh_storage.revision_add([rev1, rev2])
# Add spy on swh_storage, to make sure revision_log is not called
# (the graph must be used instead)
swh_storage = unittest.mock.MagicMock(wraps=swh_storage)
# Add all objects to graph
swh_graph = unittest.mock.Mock(
wraps=GraphClient(
nodes=[str(n.swhid()) for n in [cnt1, cnt2, dir1, dir2, rev1, rev2]],
edges=[
(str(s.swhid()), str(d.swhid()))
for (s, d) in [
(dir1, cnt1),
(dir2, cnt1),
(dir2, cnt2),
(rev1, dir1),
(rev2, dir2),
(rev2, rev1),
]
],
)
)
# Cook
backend = InMemoryVaultBackend()
cooker = GitBareCooker(
"revision_gitbare",
rev2.id,
backend=backend,
storage=swh_storage,
graph=swh_graph,
)
cooker.cook()
# Get bundle
bundle = backend.fetch("revision_gitbare", rev2.id)
# Extract bundle and make sure both revisions are in it
olasdUnsubmitted
Not Done
Inline Actions

As this initialization really depends on the shape of the objects, it would probably be clearer if it was wrapped in the same function as the one which creates the objects in the first place. You could put the population of the edge lists next to the object initialization.

olasd: As this initialization really depends on the shape of the objects, it would probably be clearer…
with tempfile.TemporaryDirectory("swh-vault-test-bare") as tempdir:
with tarfile.open(fileobj=io.BytesIO(bundle)) as tf:
tf.extractall(tempdir)
output = subprocess.check_output(
[
"git",
"-C",
f"{tempdir}/{rev2.swhid()}.git",
"log",
"--format=oneline",
"--decorate=",
]
)
assert output.decode() == f"{rev2.id.hex()} msg2\n{rev1.id.hex()} msg1\n"
# Make sure the graph was used instead of swh_storage.revision_log
swh_storage.revision_log.assert_not_called()
swh_storage.revision_shortlog.assert_not_called()
swh_graph.visit_nodes.assert_called_once_with(str(rev2.swhid()), edges="rev:rev")
View Options

api/server/src/main/java/org/softwareheritage/graph/backend/NodeIdMap.java

  • This file was added.
# Copyright (C) 2021 The Software Heritage developers
# See the AUTHORS file at the top-level directory of this distribution
# License: GNU General Public License version 3, or any later version
# See top-level LICENSE file for more information
"""
This module contains additional tests for the bare cooker.
Generic cooker tests (eg. without swh-graph) in test_cookers.py also
run on the bare cooker.
"""
import datetime
import io
import subprocess
import tarfile
import tempfile
import unittest.mock
from swh.graph.naive_client import NaiveClient as GraphClient
from swh.model.from_disk import DentryPerms
from swh.model.model import (
Content,
Directory,
DirectoryEntry,
Person,
Revision,
RevisionType,
TimestampWithTimezone,
)
from swh.vault.cookers.git_bare import GitBareCooker
from swh.vault.in_memory_backend import InMemoryVaultBackend
def test_graph_revisions(swh_storage):
# Build objects:
# rev1 <------ rev2
# | |
# v v
# dir1 dir2
# | / |
# v / v
# cnt1 <----° cnt2
date = TimestampWithTimezone.from_datetime(
datetime.datetime(2021, 5, 7, 8, 43, 59, tzinfo=datetime.timezone.utc)
)
author = Person.from_fullname(b"Foo <foo@example.org>")
cnt1 = Content.from_data(b"hello")
cnt2 = Content.from_data(b"world")
dir1 = Directory(
entries=(
DirectoryEntry(
name=b"file1",
type="file",
perms=DentryPerms.content,
target=cnt1.sha1_git,
),
)
)
dir2 = Directory(
entries=(
DirectoryEntry(
name=b"file1",
type="file",
perms=DentryPerms.content,
target=cnt1.sha1_git,
),
DirectoryEntry(
name=b"file2",
type="file",
perms=DentryPerms.content,
target=cnt2.sha1_git,
),
)
)
rev1 = Revision(
message=b"msg1",
date=date,
committer_date=date,
author=author,
committer=author,
directory=dir1.id,
type=RevisionType.GIT,
synthetic=True,
)
rev2 = Revision(
message=b"msg2",
date=date,
committer_date=date,
author=author,
committer=author,
directory=dir2.id,
parents=(rev1.id,),
type=RevisionType.GIT,
synthetic=True,
)
# Add all objects to storage
swh_storage.content_add([cnt1, cnt2])
swh_storage.directory_add([dir1, dir2])
swh_storage.revision_add([rev1, rev2])
# Add spy on swh_storage, to make sure revision_log is not called
# (the graph must be used instead)
swh_storage = unittest.mock.MagicMock(wraps=swh_storage)
# Add all objects to graph
swh_graph = unittest.mock.Mock(
wraps=GraphClient(
nodes=[str(n.swhid()) for n in [cnt1, cnt2, dir1, dir2, rev1, rev2]],
edges=[
(str(s.swhid()), str(d.swhid()))
for (s, d) in [
(dir1, cnt1),
(dir2, cnt1),
(dir2, cnt2),
(rev1, dir1),
(rev2, dir2),
(rev2, rev1),
]
],
)
)
# Cook
backend = InMemoryVaultBackend()
cooker = GitBareCooker(
"revision_gitbare",
rev2.id,
backend=backend,
storage=swh_storage,
graph=swh_graph,
)
cooker.cook()
# Get bundle
bundle = backend.fetch("revision_gitbare", rev2.id)
# Extract bundle and make sure both revisions are in it
olasdUnsubmitted
Not Done
Inline Actions

As this initialization really depends on the shape of the objects, it would probably be clearer if it was wrapped in the same function as the one which creates the objects in the first place. You could put the population of the edge lists next to the object initialization.

olasd: As this initialization really depends on the shape of the objects, it would probably be clearer…
with tempfile.TemporaryDirectory("swh-vault-test-bare") as tempdir:
with tarfile.open(fileobj=io.BytesIO(bundle)) as tf:
tf.extractall(tempdir)
output = subprocess.check_output(
[
"git",
"-C",
f"{tempdir}/{rev2.swhid()}.git",
"log",
"--format=oneline",
"--decorate=",
]
)
assert output.decode() == f"{rev2.id.hex()} msg2\n{rev1.id.hex()} msg1\n"
# Make sure the graph was used instead of swh_storage.revision_log
swh_storage.revision_log.assert_not_called()
swh_storage.revision_shortlog.assert_not_called()
swh_graph.visit_nodes.assert_called_once_with(str(rev2.swhid()), edges="rev:rev")
View Options

api/server/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java

  • This file was added.
# Copyright (C) 2021 The Software Heritage developers
# See the AUTHORS file at the top-level directory of this distribution
# License: GNU General Public License version 3, or any later version
# See top-level LICENSE file for more information
"""
This module contains additional tests for the bare cooker.
Generic cooker tests (eg. without swh-graph) in test_cookers.py also
run on the bare cooker.
"""
import datetime
import io
import subprocess
import tarfile
import tempfile
import unittest.mock
from swh.graph.naive_client import NaiveClient as GraphClient
from swh.model.from_disk import DentryPerms
from swh.model.model import (
Content,
Directory,
DirectoryEntry,
Person,
Revision,
RevisionType,
TimestampWithTimezone,
)
from swh.vault.cookers.git_bare import GitBareCooker
from swh.vault.in_memory_backend import InMemoryVaultBackend
def test_graph_revisions(swh_storage):
# Build objects:
# rev1 <------ rev2
# | |
# v v
# dir1 dir2
# | / |
# v / v
# cnt1 <----° cnt2
date = TimestampWithTimezone.from_datetime(
datetime.datetime(2021, 5, 7, 8, 43, 59, tzinfo=datetime.timezone.utc)
)
author = Person.from_fullname(b"Foo <foo@example.org>")
cnt1 = Content.from_data(b"hello")
cnt2 = Content.from_data(b"world")
dir1 = Directory(
entries=(
DirectoryEntry(
name=b"file1",
type="file",
perms=DentryPerms.content,
target=cnt1.sha1_git,
),
)
)
dir2 = Directory(
entries=(
DirectoryEntry(
name=b"file1",
type="file",
perms=DentryPerms.content,
target=cnt1.sha1_git,
),
DirectoryEntry(
name=b"file2",
type="file",
perms=DentryPerms.content,
target=cnt2.sha1_git,
),
)
)
rev1 = Revision(
message=b"msg1",
date=date,
committer_date=date,
author=author,
committer=author,
directory=dir1.id,
type=RevisionType.GIT,
synthetic=True,
)
rev2 = Revision(
message=b"msg2",
date=date,
committer_date=date,
author=author,
committer=author,
directory=dir2.id,
parents=(rev1.id,),
type=RevisionType.GIT,
synthetic=True,
)
# Add all objects to storage
swh_storage.content_add([cnt1, cnt2])
swh_storage.directory_add([dir1, dir2])
swh_storage.revision_add([rev1, rev2])
# Add spy on swh_storage, to make sure revision_log is not called
# (the graph must be used instead)
swh_storage = unittest.mock.MagicMock(wraps=swh_storage)
# Add all objects to graph
swh_graph = unittest.mock.Mock(
wraps=GraphClient(
nodes=[str(n.swhid()) for n in [cnt1, cnt2, dir1, dir2, rev1, rev2]],
edges=[
(str(s.swhid()), str(d.swhid()))
for (s, d) in [
(dir1, cnt1),
(dir2, cnt1),
(dir2, cnt2),
(rev1, dir1),
(rev2, dir2),
(rev2, rev1),
]
],
)
)
# Cook
backend = InMemoryVaultBackend()
cooker = GitBareCooker(
"revision_gitbare",
rev2.id,
backend=backend,
storage=swh_storage,
graph=swh_graph,
)
cooker.cook()
# Get bundle
bundle = backend.fetch("revision_gitbare", rev2.id)
# Extract bundle and make sure both revisions are in it
olasdUnsubmitted
Not Done
Inline Actions

As this initialization really depends on the shape of the objects, it would probably be clearer if it was wrapped in the same function as the one which creates the objects in the first place. You could put the population of the edge lists next to the object initialization.

olasd: As this initialization really depends on the shape of the objects, it would probably be clearer…
with tempfile.TemporaryDirectory("swh-vault-test-bare") as tempdir:
with tarfile.open(fileobj=io.BytesIO(bundle)) as tf:
tf.extractall(tempdir)
output = subprocess.check_output(
[
"git",
"-C",
f"{tempdir}/{rev2.swhid()}.git",
"log",
"--format=oneline",
"--decorate=",
]
)
assert output.decode() == f"{rev2.id.hex()} msg2\n{rev1.id.hex()} msg1\n"
# Make sure the graph was used instead of swh_storage.revision_log
swh_storage.revision_log.assert_not_called()
swh_storage.revision_shortlog.assert_not_called()
swh_graph.visit_nodes.assert_called_once_with(str(rev2.swhid()), edges="rev:rev")
View Options

api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java

Loading...
View Options

api/server/src/test/dataset/.gitignore

Loading...
About · Developer information · Legal