Designing a Direction Acyclic Graph (DAG)

Scenario

Proper application design improves the execution efficiency. Reduce shuffle operations if possible during programming and combine narrow dependency operations.

Procedure

The following example describes how to determine whether two vehicles are peers to show the DAG design principles.

• Data format: Time when a vehicle passes a toll station, license plate number, and toll station number...
• Logic: Two vehicles are considered as peers if they meet the following conditions:
  • Both vehicles pass the same toll stations in the same sequence.
  • The difference between the time that the vehicles pass the same toll station is smaller than a specified value.

There are two implementation modes for this example. Figure 1 shows logic of implementation mode 1 and Figure 2 shows logic of implementation mode 2.

Figure 1 Logic of implementation mode 1

Logic description:

1. Based on the license template number, aggregate and sequence all toll stations that a vehicle passes. The following data is obtained after processing:

   License plate No.1, [(pass time, toll station 3), (pass time, toll station 2), (pass time, toll station 4), (pass time, toll station 5)]

2. Identify the sequence number of the toll stations passed by the vehicle.

   (Toll station 3, (License plate No.1, pass time, first toll station))

   (Toll station 2, (License plate No.1, pass time, second toll station))

   (Toll station 4, (License plate No.1, pass time, third toll station))

   (Toll station 5, (License plate No.1, pass time, fourth toll station))

3. Aggregate data based on the toll stations.

   Toll station 1, [(License plate No.1, pass time, first toll station), (License plate No.2, pass time, fifth toll station), (License plate No.3, pass time, second toll station)]

4. Checks whether the difference between the time that two vehicles pass a toll station is within the range specified for determining peers. If the time difference is smaller than the specified value, collect information about the two vehicles.

   (License plate No.1, License plate No.2), (first toll station, fifth toll station)

   (License plate No.1, License plate No.3), (first toll station, second toll station)

5. Aggregate information data about two vehicles that pass the same toll stations based on their license template number.

   (License plate No.1, License plate No.2), [(first toll station, fifth toll station), (second toll station, sixth toll station), (first toll station, seventh toll station), (third toll station, eighth toll station)]

6. If the vehicles with license plate No.1 and No.2 pass the same toll stations in sequence, (for example, toll stations 3, 4, and 5 are the first, second, and third ones passed by vehicle 1, and the sixth, seventh, and eighth ones passed by vehicle 2), and the number of passed toll stations reaches the specified value, the two vehicles are considered as peers.

Disadvantages of implementation mode 1:

• The logic is complex.
• A large number of shuffle operations are performed, deteriorating performance.

Figure 2 Logic of implementation mode 2

Logic description:

1. Based on the license template number, aggregate and sequence all toll stations that a vehicle passes. The following data is obtained after processing:

   License plate No.1, [(pass time, toll station 3), (pass time, toll station 2), (pass time, toll station 4), (pass time, toll station 5)]

2. Based on the number of toll stations required for determining peers (3 toll stations in this example), segment the sequence of toll stations passed by a vehicle. For example, the preceding information is segmented into the following:

   Toll station 3 > Toll station 2 > Toll station 4, (License plate No.1, [pass time at toll station 3, pass time at toll station 2, pass time at toll station 4])

   Toll station 2 > Toll station 4 > Toll station 5, (License plate No.1, [pass time at toll station 2, pass time at toll station 4, pass time at toll station 5])

3. Aggregate information about vehicles that pass the same toll stations in the same sequence.

   Toll station 3 > Toll station 2 > Toll station 4, [(License plate No.1, [pass time at toll station 3, pass time at toll station 2, pass time at toll station 4]), (License plate No.2, [pass time at toll station 3, pass time at toll station 2, pass time at toll station 4]), (License plate No.3, [pass time at toll station 3, pass time at toll station 2, pass time at toll station 4])]

4. Determine whether the time difference that these vehicles passed through the same toll station is smaller than the specified value. If yes, the vehicles are determined to be peers.

Advantages of implementation mode 2:

• The logic is simplified.
• A groupByKey is removed, that is, a shuffle operation is deducted. This improves performance.