BigW Consortium Gitlab

pipeline_duration.rb 4.36 KB
Newer Older
1 2
module Gitlab
  module Ci
3 4
    # # Introduction - total running time
    #
5
    # The problem this module is trying to solve is finding the total running
6 7 8 9
    # time amongst all the jobs, excluding retries and pending (queue) time.
    # We could reduce this problem down to finding the union of periods.
    #
    # So each job would be represented as a `Period`, which consists of
10 11
    # `Period#first` as when the job started and `Period#last` as when the
    # job was finished. A simple example here would be:
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
    #
    # * A (1, 3)
    # * B (2, 4)
    # * C (6, 7)
    #
    # Here A begins from 1, and ends to 3. B begins from 2, and ends to 4.
    # C begins from 6, and ends to 7. Visually it could be viewed as:
    #
    #     0  1  2  3  4  5  6  7
    #        AAAAAAA
    #           BBBBBBB
    #                       CCCC
    #
    # The union of A, B, and C would be (1, 4) and (6, 7), therefore the
    # total running time should be:
    #
    #     (4 - 1) + (7 - 6) => 4
    #
30
    # # The Algorithm
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
    #
    # The algorithm used here for union would be described as follow.
    # First we make sure that all periods are sorted by `Period#first`.
    # Then we try to merge periods by iterating through the first period
    # to the last period. The goal would be merging all overlapped periods
    # so that in the end all the periods are discrete. When all periods
    # are discrete, we're free to just sum all the periods to get real
    # running time.
    #
    # Here we begin from A, and compare it to B. We could find that
    # before A ends, B already started. That is `B.first <= A.last`
    # that is `2 <= 3` which means A and B are overlapping!
    #
    # When we found that two periods are overlapping, we would need to merge
    # them into a new period and disregard the old periods. To make a new
    # period, we take `A.first` as the new first because remember? we sorted
    # them, so `A.first` must be smaller or equal to `B.first`. And we take
    # `[A.last, B.last].max` as the new last because we want whoever ended
    # later. This could be broken into two cases:
    #
    #     0  1  2  3  4
    #        AAAAAAA
    #           BBBBBBB
    #
    # Or:
    #
    #     0  1  2  3  4
    #        AAAAAAAAAA
    #           BBBB
    #
    # So that we need to take whoever ends later. Back to our example,
    # after merging and discard A and B it could be visually viewed as:
    #
    #     0  1  2  3  4  5  6  7
    #        DDDDDDDDDD
    #                       CCCC
    #
    # Now we could go on and compare the newly created D and the old C.
    # We could figure out that D and C are not overlapping by checking
    # `C.first <= D.last` is `false`. Therefore we need to keep both C
    # and D. The example would end here because there are no more jobs.
    #
73 74
    # After having the union of all periods, we just need to sum the length
    # of all periods to get total time.
75
    #
76
    #     (4 - 1) + (7 - 6) => 4
77
    #
78
    # That is 4 is the answer in the example.
79 80 81
    module PipelineDuration
      extend self

82
      Period = Struct.new(:first, :last) do
83 84 85 86 87
        def duration
          last - first
        end
      end

88
      def from_pipeline(pipeline)
89
        status = %w[success failed running canceled]
90 91
        builds = pipeline.builds.latest
          .where(status: status).where.not(started_at: nil).order(:started_at)
92

93
        from_builds(builds)
94 95
      end

96 97 98
      def from_builds(builds)
        now = Time.now

99
        periods = builds.map do |b|
100
          Period.new(b.started_at, b.finished_at || now)
101 102
        end

103
        from_periods(periods)
104 105
      end

106
      # periods should be sorted by `first`
107
      def from_periods(periods)
108
        process_duration(process_periods(periods))
109 110 111 112
      end

      private

113
      def process_periods(periods)
114
        return periods if periods.empty?
115

116
        periods.drop(1).inject([periods.first]) do |result, current|
117
          previous = result.last
118

119 120
          if overlap?(previous, current)
            result[-1] = merge(previous, current)
121 122 123
            result
          else
            result << current
124 125 126 127
          end
        end
      end

128 129 130 131 132 133
      def overlap?(previous, current)
        current.first <= previous.last
      end

      def merge(previous, current)
        Period.new(previous.first, [previous.last, current.last].max)
134 135
      end

136
      def process_duration(periods)
Lin Jen-Shin committed
137
        periods.sum(&:duration)
138 139 140 141
      end
    end
  end
end