Skip to content

Commit f2facdc

Browse files
Adrian Coleadriancole
Adrian Cole
authored and
adriancole
committed
Ports Node (used by ClockSkew) to javascript
1 parent 1864998 commit f2facdc

File tree

2 files changed

+321
-0
lines changed

2 files changed

+321
-0
lines changed

‎zipkin-ui/js/skew.js

Lines changed: 171 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,171 @@
1+
/*
2+
* Convenience type representing a tree. This is here because multiple facets in zipkin require
3+
* traversing the trace tree. For example, looking at network boundaries to correct clock skew, or
4+
* counting requests imply visiting the tree.
5+
*/
6+
// originally zipkin2.internal.Node.java
7+
class Node {
8+
constructor(value) {
9+
this._parent = undefined; // no default
10+
this._value = value; // undefined is possible when this is a synthetic root node
11+
this._children = [];
12+
this._missingRootDummyNode = false;
13+
}
14+
15+
// Returns the parent, or undefined if root.
16+
get parent() {
17+
return this._parent;
18+
}
19+
20+
// Returns the value, or undefined if a synthetic root node
21+
get value() {
22+
return this._value;
23+
}
24+
25+
// Returns the children of this node
26+
get children() {
27+
return this._children;
28+
}
29+
30+
// Mutable as some transformations, such as clock skew, adjust the current node in the tree.
31+
setValue(newValue) {
32+
if (!newValue) throw new Error('newValue was undefined');
33+
this._value = newValue;
34+
}
35+
36+
_setParent(newParent) {
37+
this._parent = newParent;
38+
}
39+
40+
addChild(child) {
41+
if (child === this) throw new Error(`circular dependency on ${this.toString()}`);
42+
child._setParent(this);
43+
this._children.push(child);
44+
}
45+
46+
// Returns an array of values resulting from a breadth-first traversal at this node
47+
traverse() {
48+
const result = [];
49+
const queue = [this];
50+
51+
while (queue.length > 0) {
52+
const current = queue.shift();
53+
54+
// when there's a synthetic root span, the value could be undefined
55+
if (current.value) result.push(current.value);
56+
57+
const children = current.children;
58+
for (let i = 0; i < children.length; i++) {
59+
queue.push(children[i]);
60+
}
61+
}
62+
return result;
63+
}
64+
65+
toString() {
66+
if (this._value) return `Node(${JSON.stringify(this._value)})`;
67+
return 'Node()';
68+
}
69+
}
70+
71+
/*
72+
* Some operations do not require the entire span object. This creates a tree given (parent id,
73+
* id) pairs.
74+
*/
75+
class TreeBuilder {
76+
constructor(params) {
77+
const {traceId, debug = false} = params;
78+
this._mergeFunction = (existing, update) => existing || update; // first non null
79+
if (!traceId) throw new Error('traceId was undefined');
80+
this._traceId = traceId;
81+
this._debug = debug;
82+
this._rootId = undefined;
83+
this._rootNode = undefined;
84+
this._entries = [];
85+
// Nodes representing the trace tree
86+
this._idToNode = {};
87+
// Collect the parent-child relationships between all spans.
88+
this._idToParent = {};
89+
}
90+
91+
// Returns false after logging on debug if the value couldn't be added
92+
addNode(parentId, id, value) {
93+
if (parentId && parentId === id) {
94+
if (this._debug) {
95+
/* eslint-disable no-console */
96+
console.log(`skipping circular dependency: traceId=${this._traceId}, spanId=${id}`);
97+
}
98+
return false;
99+
}
100+
this._idToParent[id] = parentId;
101+
this._entries.push({parentId, id, value});
102+
return true;
103+
}
104+
105+
_processNode(entry) {
106+
let parentId = entry.parentId ? entry.parentId : this._idToParent[entry.id];
107+
const id = entry.id;
108+
const value = entry.value;
109+
110+
if (!parentId) {
111+
if (this._rootId) {
112+
if (this._debug) {
113+
const prefix = 'attributing span missing parent to root';
114+
/* eslint-disable no-console */
115+
console.log(
116+
`${prefix}: traceId=${this._traceId}, rootSpanId=${this._rootId}, spanId=${id}`
117+
);
118+
}
119+
parentId = this._rootId;
120+
this._idToParent[id] = parentId;
121+
} else {
122+
this._rootId = id;
123+
}
124+
}
125+
126+
const node = new Node(value);
127+
// special-case root, and attribute missing parents to it. In
128+
// other words, assume that the first root is the "real" root.
129+
if (!parentId && !this._rootNode) {
130+
this._rootNode = node;
131+
this._rootId = id;
132+
} else if (!parentId && this._rootId === id) {
133+
this._rootNode.setValue(this._mergeFunction(this._rootNode.value, node.value));
134+
} else {
135+
const previous = this._idToNode[id];
136+
this._idToNode[id] = node;
137+
if (previous) node.setValue(this._mergeFunction(previous.value, node.value));
138+
}
139+
}
140+
141+
// Builds a tree from calls to addNode, or returns an empty tree.
142+
build() {
143+
this._entries.forEach((n) => this._processNode(n));
144+
if (!this._rootNode) {
145+
if (this._debug) {
146+
/* eslint-disable no-console */
147+
console.log(`substituting dummy node for missing root span: traceId=${this._traceId}`);
148+
}
149+
this._rootNode = new Node();
150+
}
151+
152+
// Materialize the tree using parent - child relationships
153+
Object.keys(this._idToParent).forEach(id => {
154+
if (id === this._rootId) return; // don't re-process root
155+
156+
const node = this._idToNode[id];
157+
const parent = this._idToNode[this._idToParent[id]];
158+
if (!parent) { // handle headless
159+
this._rootNode.addChild(node);
160+
} else {
161+
parent.addChild(node);
162+
}
163+
});
164+
return this._rootNode;
165+
}
166+
}
167+
168+
module.exports = {
169+
Node,
170+
TreeBuilder
171+
};

‎zipkin-ui/test/skew.test.js

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
const {Node, TreeBuilder} = require('../js/skew');
2+
const should = require('chai').should();
3+
4+
// originally zipkin2.internal.NodeTest.java
5+
describe('Node', () => {
6+
it('should construct without a value', () => {
7+
const value = {traceId: '1', id: '1'};
8+
const node = new Node(value);
9+
10+
expect(node.value).to.equal(value);
11+
});
12+
13+
it('should construct without a value', () => {
14+
const node = new Node();
15+
16+
should.equal(node.value, undefined);
17+
});
18+
19+
it('should not allow setting an undefined value', () => {
20+
const node = new Node();
21+
22+
expect(() => node.setValue()).to.throw('newValue was undefined');
23+
});
24+
25+
it('should not allow creating a cycle', () => {
26+
const fake = new Node();
27+
28+
expect(() => fake.addChild(fake)).to.throw('circular dependency on Node()');
29+
30+
const node = new Node({traceId: '1', id: '1'});
31+
32+
expect(() => node.addChild(node))
33+
.to.throw('circular dependency on Node({"traceId":"1","id":"1"})');
34+
});
35+
36+
/*
37+
* The following tree should traverse in alphabetical order
38+
*
39+
* a
40+
* / | \
41+
* b c d
42+
* /|\ \
43+
* e f g h
44+
*/
45+
it('should traverse breadth first', () => {
46+
const a = new Node('a');
47+
const b = new Node('b');
48+
const c = new Node('c');
49+
const d = new Node('d');
50+
// root(a) has children b, c, d
51+
a.addChild(b);
52+
a.addChild(c);
53+
a.addChild(d);
54+
const e = new Node('e');
55+
const f = new Node('f');
56+
const g = new Node('g');
57+
// child(b) has children e, f, g
58+
b.addChild(e);
59+
b.addChild(f);
60+
b.addChild(g);
61+
const h = new Node('h');
62+
// f has no children
63+
// child(g) has child h
64+
g.addChild(h);
65+
66+
expect(a.traverse()).to.deep.equal([
67+
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'
68+
]);
69+
});
70+
});
71+
72+
describe('TreeBuilder', () => {
73+
// Makes sure that the trace tree is constructed based on parent-child, not by parameter order.
74+
it('should construct a trace tree', () => {
75+
const trace = [
76+
{traceId: 'a', id: 'a'},
77+
{traceId: 'a', parentId: 'a', id: 'b'},
78+
{traceId: 'a', parentId: 'b', id: 'c'},
79+
];
80+
81+
const treeBuilder = new TreeBuilder({traceId: 'a'});
82+
83+
// TRACE is sorted with root span first, lets reverse them to make
84+
// sure the trace is stitched together by id.
85+
trace.slice(0).reverse().forEach((span) => treeBuilder.addNode(span.parentId, span.id, span));
86+
87+
const root = treeBuilder.build();
88+
expect(root.value).to.equal(trace[0]);
89+
expect(root.children.map(n => n.value)).to.deep.equal([trace[1]]);
90+
91+
const child = root.children[0];
92+
expect(child.children.map(n => n.value)).to.deep.equal([trace[2]]);
93+
});
94+
95+
// input should be merged, but this ensures we are fine anyway
96+
it('should dedupe while constructing a trace tree', () => {
97+
const trace = [
98+
{traceId: 'a', id: 'a'},
99+
{traceId: 'a', id: 'a'},
100+
{traceId: 'a', id: 'a'}
101+
];
102+
103+
const treeBuilder = new TreeBuilder({traceId: 'a'});
104+
trace.forEach((span) => treeBuilder.addNode(span.parentId, span.id, span));
105+
const root = treeBuilder.build();
106+
107+
expect(root.value).to.equal(trace[0]);
108+
expect(root.children.length).to.equal(0);
109+
});
110+
111+
it('should allocate spans missing parents to root', () => {
112+
const trace = [
113+
{traceId: 'a', id: 'b'},
114+
{traceId: 'a', parentId: 'b', id: 'c'},
115+
{traceId: 'a', parentId: 'b', id: 'd'},
116+
{traceId: 'a', id: 'e'},
117+
{traceId: 'a', id: 'f'}
118+
];
119+
120+
const treeBuilder = new TreeBuilder({traceId: 'a'});
121+
trace.forEach((span) => treeBuilder.addNode(span.parentId, span.id, span));
122+
const root = treeBuilder.build();
123+
124+
expect(root.traverse()).to.deep.equal(trace);
125+
expect(root.children.map(n => n.value)).to.deep.equal(trace.slice(1));
126+
});
127+
128+
// spans are often reported depth-first, so it is possible to not have a root yet
129+
it('should construct a trace missing a root span', () => {
130+
const trace = [
131+
{traceId: 'a', parentId: 'a', id: 'b'},
132+
{traceId: 'a', parentId: 'a', id: 'c'},
133+
{traceId: 'a', parentId: 'a', id: 'd'}
134+
];
135+
136+
const treeBuilder = new TreeBuilder({traceId: 'a'});
137+
trace.forEach((span) => treeBuilder.addNode(span.parentId, span.id, span));
138+
const root = treeBuilder.build();
139+
140+
should.equal(root.value, undefined);
141+
expect(root.traverse()).to.deep.equal(trace);
142+
});
143+
144+
// input should be well formed, but this ensures we are fine anyway
145+
it('should skip on cycle', () => {
146+
const treeBuilder = new TreeBuilder({traceId: 'a'});
147+
expect(treeBuilder.addNode('b', 'b', {traceId: 'a', parentId: 'b', id: 'b'}))
148+
.to.equal(false);
149+
});
150+
});

0 commit comments

Comments
 (0)