Repository: apache/skywalking (language: python)

Issue:
[Feature] More intelligent service hierarchy analysis
### Search before asking

- [X] I had searched in the [issues](https://github.com/apache/skywalking/issues?q=is%3Aissue) and found no similar feature requirement.


### Description

We have good progress for v10 regarding service hierarchy analysis and visualization. Service hierarchy relation is there and represented well.

![image](https://github.com/apache/skywalking/assets/5441976/79056d58-5bf1-4afb-913d-07c59f94aa2a)

About this, we identified
1. mesh -> mesh-dp
2. mesh -> k8s
3. agent -> k8s
4. mesh-dp -> k8s

Actually, <1> and <4> logically should be equivalent with <2>. So @wankai123 Could we consider ignoring <2> when returning the final result to the UI? Then we could make the data more reasonable, and MESH layer to K8S layer line doesn't need to exist, and will not pass through MESH-DP layer.


### Use case

_No response_

### Related issues

_No response_

### Are you willing to submit a pull request to implement this on your own?

- [ ] Yes I am willing to submit a pull request on my own!

### Code of Conduct

- [X] I agree to follow this project's [Code of Conduct](https://www.apache.org/foundation/policies/conduct)



Discussion / hints:

Fix patch:
diff --git a/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/query/HierarchyQueryService.java b/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/query/HierarchyQueryService.java
index a669ca5b8d1d..3c8d86b738f6 100644
--- a/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/query/HierarchyQueryService.java
+++ b/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/query/HierarchyQueryService.java
@@ -26,6 +26,7 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Optional;
+import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.TimeUnit;
 import java.util.function.Predicate;
@@ -62,7 +63,7 @@ public class HierarchyQueryService implements Service {
     private IMetadataQueryDAO metadataQueryDAO;
     private Map<String, Map<String, HierarchyDefinitionService.MatchingRule>> hierarchyDefinition;
     private Map<String, Integer> layerLevels;
-    private LoadingCache<Boolean, Map<HierarchyRelatedService, ServiceRelations>> serviceHierarchyCache;
+    private LoadingCache<Boolean, Map<HierarchyRelatedService/*self*/, ServiceRelations/*upper and lower service list*/>> serviceHierarchyCache;
 
     public HierarchyQueryService(ModuleManager moduleManager, CoreModuleConfig moduleConfig) {
         this.moduleManager = moduleManager;
@@ -152,12 +153,11 @@ private Map<HierarchyRelatedService, ServiceRelations> mapServiceHierarchy() thr
         return serviceRelationsMap;
     }
 
-    private void buildServiceRelation(ServiceHierarchy hierarchy, HierarchyRelatedService self, int maxDepth, HierarchyDirection direction) throws ExecutionException {
+    private void buildServiceRelation(Map<HierarchyRelatedService, ServiceRelations> serviceRelationsMap, ServiceHierarchy hierarchy, HierarchyRelatedService self, int maxDepth, HierarchyDirection direction) throws ExecutionException {
         if (maxDepth < 1) {
             return;
         }
         maxDepth--;
-        Map<HierarchyRelatedService, ServiceRelations> serviceRelationsMap = serviceHierarchyCache.get(true);
         ServiceRelations serviceRelations = serviceRelationsMap.getOrDefault(self, new ServiceRelations());
 
         if (serviceRelations.getLowerServices().isEmpty() && serviceRelations.getUpperServices().isEmpty()) {
@@ -170,7 +170,7 @@ private void buildServiceRelation(ServiceHierarchy hierarchy, HierarchyRelatedSe
                 if (!hierarchy.getRelations().add(relation)) {
                     continue;
                 }
-                buildServiceRelation(hierarchy, lowerService, maxDepth, direction);
+                buildServiceRelation(serviceRelationsMap, hierarchy, lowerService, maxDepth, direction);
             }
         }
         if (direction == HierarchyDirection.UPPER || direction == HierarchyDirection.All) {
@@ -179,7 +179,7 @@ private void buildServiceRelation(ServiceHierarchy hierarchy, HierarchyRelatedSe
                 if (!hierarchy.getRelations().add(relation)) {
                     continue;
                 }
-                buildServiceRelation(hierarchy, upperService, maxDepth, direction);
+                buildServiceRelation(serviceRelationsMap, hierarchy, upperService, maxDepth, direction);
             }
         }
     }
@@ -191,20 +191,23 @@ private ServiceHierarchy getServiceHierarchy(String serviceId, String layer, int
         self.setName(IDManager.ServiceID.analysisId(serviceId).getName());
         self.setLayer(layer);
         self.setNormal(Layer.nameOf(layer).isNormal());
-        buildServiceRelation(hierarchy, self, maxDepth, direction);
+        buildServiceRelation(serviceHierarchyCache.get(true), hierarchy, self, maxDepth, direction);
         return hierarchy;
     }
 
     /**
      * @return return the related service hierarchy recursively, e.g. A-B-C, query A will return A-B, B-C
+     * If the relation could be conjectured will be removed, e.g. A-B-C-D and A-D, query A will return A-B, B-C, C-D because A-D could be conjectured.
      */
     public ServiceHierarchy getServiceHierarchy(String serviceId, String layer) throws Exception {
         if (!this.isEnableHierarchy) {
             log.warn("CoreModuleConfig config {enableHierarchy} is false, return empty ServiceHierarchy.");
             return new ServiceHierarchy();
         }
+        int maxDepth = 10;
         //build relation recursively, set max depth to 10
-        return getServiceHierarchy(serviceId, layer, 10, HierarchyDirection.All);
+        ServiceHierarchy hierarchy = getServiceHierarchy(serviceId, layer, maxDepth, HierarchyDirection.All);
+        return filterConjecturableRelations(serviceHierarchyCache.get(true), hierarchy, maxDepth);
     }
 
     public InstanceHierarchy getInstanceHierarchy(String instanceId, String layer) throws Exception {
@@ -357,13 +360,58 @@ private Predicate<ServiceInstance> relatedInstanceFilter(ServiceInstance instanc
         };
     }
 
+    //If the lower service relation could be found from other lower relations, then it could be conjectured.
+    private ServiceHierarchy filterConjecturableRelations(Map<HierarchyRelatedService, ServiceRelations> serviceRelationsMap,
+                                                          ServiceHierarchy hierarchy,
+                                                          int maxDepth) {
+        Set<HierarchyServiceRelation> relations = hierarchy.getRelations();
+        List<HierarchyServiceRelation> relationList = new ArrayList<>(relations);
+        for (HierarchyServiceRelation relation : relationList) {
+            HierarchyRelatedService upperService = relation.getUpperService();
+            HierarchyRelatedService lowerService = relation.getLowerService();
+            ServiceRelations serviceRelations = serviceRelationsMap.get(upperService);
+            // if only one lower service, keep the relation
+            if (serviceRelations.lowerServices.size() > 1) {
+                if (checkIfConjecturable(serviceRelationsMap, serviceRelations.lowerServices, lowerService, maxDepth)) {
+                    // if the lower service is conjecturable, remove the relation
+                    relations.remove(relation);
+                }
+            }
+        }
+        return hierarchy;
+    }
+
+    private boolean checkIfConjecturable(Map<HierarchyRelatedService, ServiceRelations> serviceRelationsMap,
+                                         List<HierarchyRelatedService> services,
+                                         HierarchyRelatedService conjecturalService,
+                                         int maxDepth) {
+        if (maxDepth < 1) {
+            return false;
+        }
+        maxDepth--;
+        for (HierarchyRelatedService service : services) {
+            if (!service.equals(conjecturalService)) {
+                List<HierarchyRelatedService> lowerServices = serviceRelationsMap.get(service).lowerServices;
+                if (lowerServices.contains(conjecturalService)) {
+                    return true;
+                } else {
+                    return checkIfConjecturable(serviceRelationsMap, lowerServices, conjecturalService, maxDepth);
+                }
+            }
+        }
+        return false;
+    }
+
+    /**
+     * Record the all upper and lower services of the specified service.
+     */
     @Data
-    static class ServiceRelations {
+    public static class ServiceRelations {
         private List<HierarchyRelatedService> upperServices = new ArrayList<>();
         private List<HierarchyRelatedService> lowerServices = new ArrayList<>();
     }
 
-    enum HierarchyDirection {
+    public enum HierarchyDirection {
         All,
         UPPER,
         LOWER
diff --git a/skywalking-ui b/skywalking-ui
index 306508856b56..f809123b4f03 160000
--- a/skywalking-ui
+++ b/skywalking-ui
@@ -1,1 +1,1 @@
-Subproject commit 306508856b56a946f3de26f749c5b69509d3d5c5
+Subproject commit f809123b4f03521a23304dbe95a497a06fb9670f


Test patch:
diff --git a/oap-server/server-core/src/test/java/org/apache/skywalking/oap/server/core/Hierarchy/HierarchyQueryServiceTest.java b/oap-server/server-core/src/test/java/org/apache/skywalking/oap/server/core/Hierarchy/HierarchyQueryServiceTest.java
new file mode 100644
index 000000000000..8049ca52c379
--- /dev/null
+++ b/oap-server/server-core/src/test/java/org/apache/skywalking/oap/server/core/Hierarchy/HierarchyQueryServiceTest.java
@@ -0,0 +1,194 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+
+package org.apache.skywalking.oap.server.core.Hierarchy;
+
+import java.util.HashMap;
+import java.util.Map;
+import org.apache.skywalking.oap.server.core.query.HierarchyQueryService;
+import org.apache.skywalking.oap.server.core.query.type.HierarchyRelatedService;
+import org.apache.skywalking.oap.server.core.query.type.HierarchyServiceRelation;
+import org.apache.skywalking.oap.server.core.query.type.ServiceHierarchy;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+import org.powermock.reflect.Whitebox;
+
+import static org.mockito.Mockito.mock;
+
+public class HierarchyQueryServiceTest {
+    private HierarchyQueryService hierarchyQueryService;
+
+    @BeforeEach
+    public void init() {
+        hierarchyQueryService = mock(HierarchyQueryService.class);
+    }
+
+    @Test
+    public void testBuildServiceRelation() throws Exception {
+        ServiceHierarchy hierarchy = invokeBuildServiceRelation();
+        Assertions.assertEquals(9, hierarchy.getRelations().size());
+        Assertions.assertEquals(mockHierarchy(false), hierarchy);
+    }
+
+    @Test
+    public void testFilterConjecturableRelations() throws Exception {
+        ServiceHierarchy hierarchy = Whitebox.invokeMethod(
+            hierarchyQueryService, "filterConjecturableRelations", mockCache(), invokeBuildServiceRelation(), 10);
+        Assertions.assertEquals(5, hierarchy.getRelations().size());
+        Assertions.assertEquals(mockHierarchy(true), hierarchy);
+    }
+
+    private ServiceHierarchy invokeBuildServiceRelation() throws Exception {
+        ServiceHierarchy hierarchy = new ServiceHierarchy();
+        HierarchyRelatedService serviceA = new HierarchyRelatedService();
+        serviceA.setId("A");
+        Whitebox.invokeMethod(
+            hierarchyQueryService, "buildServiceRelation", mockCache(), hierarchy, serviceA, 10,
+            HierarchyQueryService.HierarchyDirection.All
+        );
+        return hierarchy;
+    }
+
+    private Map<HierarchyRelatedService, HierarchyQueryService.ServiceRelations> mockCache() {
+        // A->B->C->D->E
+        // A->C
+        // A->D
+        // A->F
+        // B->E
+        // C->F
+        HierarchyRelatedService serviceA = new HierarchyRelatedService();
+        serviceA.setId("A");
+        HierarchyRelatedService serviceB = new HierarchyRelatedService();
+        serviceB.setId("B");
+        HierarchyRelatedService serviceC = new HierarchyRelatedService();
+        serviceC.setId("C");
+        HierarchyRelatedService serviceD = new HierarchyRelatedService();
+        serviceD.setId("D");
+        HierarchyRelatedService serviceE = new HierarchyRelatedService();
+        serviceE.setId("E");
+        HierarchyRelatedService serviceF = new HierarchyRelatedService();
+        serviceF.setId("F");
+
+        Map<HierarchyRelatedService, HierarchyQueryService.ServiceRelations> serviceRelationsMap = new HashMap<>();
+        HierarchyQueryService.ServiceRelations serviceRelationsA = new HierarchyQueryService.ServiceRelations();
+        serviceRelationsA.getLowerServices().add(serviceB);
+        serviceRelationsA.getLowerServices().add(serviceC);
+        serviceRelationsA.getLowerServices().add(serviceD);
+        serviceRelationsMap.put(serviceA, serviceRelationsA);
+
+        HierarchyQueryService.ServiceRelations serviceRelationsB = new HierarchyQueryService.ServiceRelations();
+        serviceRelationsB.getUpperServices().add(serviceA);
+        serviceRelationsB.getLowerServices().add(serviceC);
+        serviceRelationsB.getLowerServices().add(serviceE);
+        serviceRelationsMap.put(serviceB, serviceRelationsB);
+
+        HierarchyQueryService.ServiceRelations serviceRelationsC = new HierarchyQueryService.ServiceRelations();
+        serviceRelationsC.getUpperServices().add(serviceA);
+        serviceRelationsC.getUpperServices().add(serviceB);
+        serviceRelationsC.getLowerServices().add(serviceD);
+        serviceRelationsC.getLowerServices().add(serviceF);
+        serviceRelationsMap.put(serviceC, serviceRelationsC);
+
+        HierarchyQueryService.ServiceRelations serviceRelationsD = new HierarchyQueryService.ServiceRelations();
+        serviceRelationsD.getUpperServices().add(serviceC);
+        serviceRelationsD.getUpperServices().add(serviceA);
+        serviceRelationsD.getLowerServices().add(serviceE);
+        serviceRelationsMap.put(serviceD, serviceRelationsD);
+
+        HierarchyQueryService.ServiceRelations serviceRelationsE = new HierarchyQueryService.ServiceRelations();
+        serviceRelationsE.getUpperServices().add(serviceD);
+        serviceRelationsE.getUpperServices().add(serviceB);
+        serviceRelationsMap.put(serviceE, serviceRelationsE);
+
+        HierarchyQueryService.ServiceRelations serviceRelationsF = new HierarchyQueryService.ServiceRelations();
+        serviceRelationsF.getUpperServices().add(serviceA);
+        serviceRelationsF.getUpperServices().add(serviceC);
+        serviceRelationsMap.put(serviceF, serviceRelationsF);
+
+        return serviceRelationsMap;
+    }
+
+    private ServiceHierarchy mockHierarchy(boolean filterRelations) {
+        ServiceHierarchy hierarchy = new ServiceHierarchy();
+        HierarchyServiceRelation relationAB = new HierarchyServiceRelation();
+        HierarchyServiceRelation relationAC = new HierarchyServiceRelation();
+        HierarchyServiceRelation relationAD = new HierarchyServiceRelation();
+        HierarchyServiceRelation relationAF = new HierarchyServiceRelation();
+        HierarchyServiceRelation relationBC = new HierarchyServiceRelation();
+        HierarchyServiceRelation relationBE = new HierarchyServiceRelation();
+        HierarchyServiceRelation relationCD = new HierarchyServiceRelation();
+        HierarchyServiceRelation relationCF = new HierarchyServiceRelation();
+        HierarchyServiceRelation relationDE = new HierarchyServiceRelation();
+
+        HierarchyRelatedService serviceA = new HierarchyRelatedService();
+        serviceA.setId("A");
+        HierarchyRelatedService serviceB = new HierarchyRelatedService();
+        serviceB.setId("B");
+        HierarchyRelatedService serviceC = new HierarchyRelatedService();
+        serviceC.setId("C");
+        HierarchyRelatedService serviceD = new HierarchyRelatedService();
+        serviceD.setId("D");
+        HierarchyRelatedService serviceE = new HierarchyRelatedService();
+        serviceE.setId("E");
+        HierarchyRelatedService serviceF = new HierarchyRelatedService();
+        serviceF.setId("F");
+        //AB
+        relationAB.setLowerService(serviceB);
+        relationAB.setUpperService(serviceA);
+        //AC
+        relationAC.setLowerService(serviceC);
+        relationAC.setUpperService(serviceA);
+        //AD
+        relationAD.setLowerService(serviceD);
+        relationAD.setUpperService(serviceA);
+        //AF
+        relationAF.setLowerService(serviceF);
+        relationAF.setUpperService(serviceA);
+        //BC
+        relationBC.setLowerService(serviceC);
+        relationBC.setUpperService(serviceB);
+        //BE
+        relationBE.setLowerService(serviceE);
+        relationBE.setUpperService(serviceB);
+        //CD
+        relationCD.setLowerService(serviceD);
+        relationCD.setUpperService(serviceC);
+        //CF
+        relationCF.setLowerService(serviceF);
+        relationCF.setUpperService(serviceC);
+        //DE
+        relationDE.setLowerService(serviceE);
+        relationDE.setUpperService(serviceD);
+
+        hierarchy.getRelations().add(relationAB);
+        hierarchy.getRelations().add(relationBC);
+        hierarchy.getRelations().add(relationCD);
+        hierarchy.getRelations().add(relationCF);
+        hierarchy.getRelations().add(relationDE);
+
+        if (!filterRelations) {
+            hierarchy.getRelations().add(relationAC);
+            hierarchy.getRelations().add(relationAD);
+            hierarchy.getRelations().add(relationAF);
+            hierarchy.getRelations().add(relationBE);
+        }
+
+        return hierarchy;
+    }
+}