[go-ndn] Names not being comparable

[justincpresley]

Overview

With many syncs using dataset Names as direct references to the specific dataset, a problem occurs when trying to use a map, a built-in performant data structure. The problem occurs because map keys are required to implement comparable, yet Names do not implement comparable as Names are implemented as a Slice of Components, and Slices are not comparable.

Thus in order to use a map, developers are required create a indirect comparable reference to specific datasets. Lucky, a Name has easy string conversions using this to method and this from method, and a string does implement comparable. However, we have added indirection, another layer. This indirection introduces a few problems.

From a visual standpoint:
Name <-> dataset
TO
string <-> Name <-> dataset

Breaking Name Uniqueness

A Name follows a well-defined structure whereas a string does not. As such, when converting a string to a Name, the structure can either be implied automatically or produce an error. To ease the use of the go-ndn library, the structure is implied automatically such that "com/google", "/com/google", "com/google/", and "/com/google/" all result in the name /com/google. Abstractly, the comparable string layer that we have introduced creates multiple references for the same Name reference.

As developers operate in the comparable layer more, the Name layer qualities/requirements have more of a chance to not be enforced. For example if I created two datasets with the string references "com/github" and "/com/github/", it would be problematic. With proper checking, this issue is avoided. However, I would argue conceptually it is problematic.

Performance and Efficiency

By introducing this string layer, we have important decisions to make: when where and how to convert between the comparable layer and the Name layer. While the cost of conversion is seemly insignificant, it adds up when you iteratively convert for a large group. On top of that, the Name layer is especially useful for certain methods like for obtaining Canonical Order. As such, developers might be forced to convert between the layers multiple times in order to achieve desired functionality.

Solving the Issue

It is clear that abstractly, Names should be comparable as the issues outlined vanish. Therefore, how can we make this the case? I think the answer to that relies on what aspect needs to change. Is it the programming language Go that makes this impossible or is it the implementation of Names in go-ndn, or perhaps both?

In svs, storage is used to tackle this issue. Both the NDN Name and string version is stored and used. This has effectively allowed the library to not do any encoding/decoding at all during operations except for when parsing a StateVector or manually inserting an entry. If this issue was solved, we would see a drop in the storage overhead and a slight increase in performance. Nevertheless, I believe this storage fix to be an imperfect solution that ultimately avoids the issue at hand.