001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase;
019
020import java.util.Arrays;
021import java.util.Collection;
022import java.util.Iterator;
023import org.apache.hadoop.hbase.client.RegionInfo;
024import org.apache.hadoop.hbase.client.RegionReplicaUtil;
025import org.apache.hadoop.hbase.util.Bytes;
026import org.apache.yetus.audience.InterfaceAudience;
027
028/**
029 * Container for holding a list of {@link HRegionLocation}'s that correspond to the same range. The
030 * list is indexed by the replicaId. This is an immutable list, however mutation operations are
031 * provided which returns a new List via copy-on-write (assuming small number of locations)
032 */
033@InterfaceAudience.Private
034public class RegionLocations implements Iterable<HRegionLocation> {
035
036  private final int numNonNullElements;
037
038  // locations array contains the HRL objects for known region replicas indexes by the replicaId.
039  // elements can be null if the region replica is not known at all. A null value indicates
040  // that there is a region replica with the index as replicaId, but the location is not known
041  // in the cache.
042  private final HRegionLocation[] locations; // replicaId -> HRegionLocation.
043
044  /**
045   * Constructs the region location list. The locations array should contain all the locations for
046   * known replicas for the region, and should be sorted in replicaId ascending order, although it
047   * can contain nulls indicating replicaIds that the locations of which are not known.
048   * @param locations an array of HRegionLocations for the same region range
049   */
050  public RegionLocations(HRegionLocation... locations) {
051    int numNonNullElements = 0;
052    int maxReplicaId = -1;
053    int maxReplicaIdIndex = -1;
054    int index = 0;
055    for (HRegionLocation loc : locations) {
056      if (loc != null) {
057        if (loc.getRegion().getReplicaId() >= maxReplicaId) {
058          maxReplicaId = loc.getRegion().getReplicaId();
059          maxReplicaIdIndex = index;
060        }
061      }
062      index++;
063    }
064    // account for the null elements in the array after maxReplicaIdIndex
065    maxReplicaId = maxReplicaId + (locations.length - (maxReplicaIdIndex + 1));
066
067    if (maxReplicaId + 1 == locations.length) {
068      this.locations = locations;
069    } else {
070      this.locations = new HRegionLocation[maxReplicaId + 1];
071      for (HRegionLocation loc : locations) {
072        if (loc != null) {
073          this.locations[loc.getRegion().getReplicaId()] = loc;
074        }
075      }
076    }
077    for (HRegionLocation loc : this.locations) {
078      if (loc != null && loc.getServerName() != null) {
079        numNonNullElements++;
080      }
081    }
082    this.numNonNullElements = numNonNullElements;
083  }
084
085  public RegionLocations(Collection<HRegionLocation> locations) {
086    this(locations.toArray(new HRegionLocation[locations.size()]));
087  }
088
089  /**
090   * Returns the size of the list even if some of the elements might be null.
091   * @return the size of the list (corresponding to the max replicaId)
092   */
093  public int size() {
094    return locations.length;
095  }
096
097  /**
098   * Returns the size of not-null locations
099   * @return the size of not-null locations
100   */
101  public int numNonNullElements() {
102    return numNonNullElements;
103  }
104
105  /**
106   * Returns whether there are non-null elements in the list
107   * @return whether there are non-null elements in the list
108   */
109  public boolean isEmpty() {
110    return numNonNullElements == 0;
111  }
112
113  /**
114   * Returns a new RegionLocations with the locations removed (set to null) which have the
115   * destination server as given.
116   * @param serverName the serverName to remove locations of
117   * @return an RegionLocations object with removed locations or the same object if nothing is
118   *         removed
119   */
120  public RegionLocations removeByServer(ServerName serverName) {
121    HRegionLocation[] newLocations = null;
122    for (int i = 0; i < locations.length; i++) {
123      // check whether something to remove
124      if (locations[i] != null && serverName.equals(locations[i].getServerName())) {
125        if (newLocations == null) { // first time
126          newLocations = new HRegionLocation[locations.length];
127          System.arraycopy(locations, 0, newLocations, 0, i);
128        }
129        newLocations[i] = null;
130      } else if (newLocations != null) {
131        newLocations[i] = locations[i];
132      }
133    }
134    return newLocations == null ? this : new RegionLocations(newLocations);
135  }
136
137  /**
138   * Removes the given location from the list
139   * @param location the location to remove
140   * @return an RegionLocations object with removed locations or the same object if nothing is
141   *         removed
142   */
143  public RegionLocations remove(HRegionLocation location) {
144    if (location == null) return this;
145    if (location.getRegion() == null) return this;
146    int replicaId = location.getRegion().getReplicaId();
147    if (replicaId >= locations.length) return this;
148
149    // check whether something to remove. HRL.compareTo() compares ONLY the
150    // serverName. We want to compare the HRI's as well.
151    if (
152      locations[replicaId] == null
153        || RegionInfo.COMPARATOR.compare(location.getRegion(), locations[replicaId].getRegion())
154            != 0
155        || !location.equals(locations[replicaId])
156    ) {
157      return this;
158    }
159
160    HRegionLocation[] newLocations = new HRegionLocation[locations.length];
161    System.arraycopy(locations, 0, newLocations, 0, locations.length);
162    newLocations[replicaId] = null;
163
164    return new RegionLocations(newLocations);
165  }
166
167  /**
168   * Removes location of the given replicaId from the list
169   * @param replicaId the replicaId of the location to remove
170   * @return an RegionLocations object with removed locations or the same object if nothing is
171   *         removed
172   */
173  public RegionLocations remove(int replicaId) {
174    if (getRegionLocation(replicaId) == null) {
175      return this;
176    }
177
178    HRegionLocation[] newLocations = new HRegionLocation[locations.length];
179
180    System.arraycopy(locations, 0, newLocations, 0, locations.length);
181    if (replicaId < newLocations.length) {
182      newLocations[replicaId] = null;
183    }
184
185    return new RegionLocations(newLocations);
186  }
187
188  /**
189   * Set the element to null if its getServerName method returns null. Returns null if all the
190   * elements are removed.
191   */
192  public RegionLocations removeElementsWithNullLocation() {
193    HRegionLocation[] newLocations = new HRegionLocation[locations.length];
194    boolean hasNonNullElement = false;
195    for (int i = 0; i < locations.length; i++) {
196      if (locations[i] != null && locations[i].getServerName() != null) {
197        hasNonNullElement = true;
198        newLocations[i] = locations[i];
199      }
200    }
201    return hasNonNullElement ? new RegionLocations(newLocations) : null;
202  }
203
204  /**
205   * Merges this RegionLocations list with the given list assuming same range, and keeping the most
206   * up to date version of the HRegionLocation entries from either list according to seqNum. If
207   * seqNums are equal, the location from the argument (other) is taken.
208   * @param other the locations to merge with
209   * @return an RegionLocations object with merged locations or the same object if nothing is merged
210   */
211  @SuppressWarnings("ReferenceEquality")
212  public RegionLocations mergeLocations(RegionLocations other) {
213    assert other != null;
214
215    HRegionLocation[] newLocations = null;
216
217    // Use the length from other, since it is coming from meta. Otherwise,
218    // in case of region replication going down, we might have a leak here.
219    int max = other.locations.length;
220
221    RegionInfo regionInfo = null;
222    for (int i = 0; i < max; i++) {
223      HRegionLocation thisLoc = this.getRegionLocation(i);
224      HRegionLocation otherLoc = other.getRegionLocation(i);
225      if (regionInfo == null && otherLoc != null && otherLoc.getRegion() != null) {
226        // regionInfo is the first non-null HRI from other RegionLocations. We use it to ensure that
227        // all replica region infos belong to the same region with same region id.
228        regionInfo = otherLoc.getRegion();
229      }
230
231      HRegionLocation selectedLoc = selectRegionLocation(thisLoc, otherLoc, true, false);
232
233      if (selectedLoc != thisLoc) {
234        if (newLocations == null) {
235          newLocations = new HRegionLocation[max];
236          System.arraycopy(locations, 0, newLocations, 0, i);
237        }
238      }
239      if (newLocations != null) {
240        newLocations[i] = selectedLoc;
241      }
242    }
243
244    // ensure that all replicas share the same start code. Otherwise delete them
245    if (newLocations != null && regionInfo != null) {
246      for (int i = 0; i < newLocations.length; i++) {
247        if (newLocations[i] != null) {
248          if (!RegionReplicaUtil.isReplicasForSameRegion(regionInfo, newLocations[i].getRegion())) {
249            newLocations[i] = null;
250          }
251        }
252      }
253    }
254
255    return newLocations == null ? this : new RegionLocations(newLocations);
256  }
257
258  private HRegionLocation selectRegionLocation(HRegionLocation oldLocation,
259    HRegionLocation location, boolean checkForEquals, boolean force) {
260    if (location == null) {
261      return oldLocation == null ? null : oldLocation;
262    }
263
264    if (oldLocation == null) {
265      return location;
266    }
267
268    if (force || isGreaterThan(location.getSeqNum(), oldLocation.getSeqNum(), checkForEquals)) {
269      return location;
270    }
271    return oldLocation;
272  }
273
274  /**
275   * Updates the location with new only if the new location has a higher seqNum than the old one or
276   * force is true.
277   * @param location       the location to add or update
278   * @param checkForEquals whether to update the location if seqNums for the HRegionLocations for
279   *                       the old and new location are the same
280   * @param force          whether to force update
281   * @return an RegionLocations object with updated locations or the same object if nothing is
282   *         updated
283   */
284  @SuppressWarnings("ReferenceEquality")
285  public RegionLocations updateLocation(HRegionLocation location, boolean checkForEquals,
286    boolean force) {
287    assert location != null;
288
289    int replicaId = location.getRegion().getReplicaId();
290
291    HRegionLocation oldLoc = getRegionLocation(location.getRegion().getReplicaId());
292    HRegionLocation selectedLoc = selectRegionLocation(oldLoc, location, checkForEquals, force);
293
294    if (selectedLoc == oldLoc) {
295      return this;
296    }
297    HRegionLocation[] newLocations = new HRegionLocation[Math.max(locations.length, replicaId + 1)];
298    System.arraycopy(locations, 0, newLocations, 0, locations.length);
299    newLocations[replicaId] = location;
300    // ensure that all replicas share the same start code. Otherwise delete them
301    for (int i = 0; i < newLocations.length; i++) {
302      if (newLocations[i] != null) {
303        if (
304          !RegionReplicaUtil.isReplicasForSameRegion(location.getRegion(),
305            newLocations[i].getRegion())
306        ) {
307          newLocations[i] = null;
308        }
309      }
310    }
311    return new RegionLocations(newLocations);
312  }
313
314  private boolean isGreaterThan(long a, long b, boolean checkForEquals) {
315    return a > b || (checkForEquals && (a == b));
316  }
317
318  public HRegionLocation getRegionLocation(int replicaId) {
319    if (replicaId >= locations.length) {
320      return null;
321    }
322    return locations[replicaId];
323  }
324
325  /**
326   * Returns the region location from the list for matching regionName, which can be regionName or
327   * encodedRegionName
328   * @param regionName regionName or encodedRegionName
329   * @return HRegionLocation found or null
330   */
331  public HRegionLocation getRegionLocationByRegionName(byte[] regionName) {
332    for (HRegionLocation loc : locations) {
333      if (loc != null) {
334        if (
335          Bytes.equals(loc.getRegion().getRegionName(), regionName)
336            || Bytes.equals(loc.getRegion().getEncodedNameAsBytes(), regionName)
337        ) {
338          return loc;
339        }
340      }
341    }
342    return null;
343  }
344
345  public HRegionLocation[] getRegionLocations() {
346    return locations;
347  }
348
349  public HRegionLocation getDefaultRegionLocation() {
350    return locations[RegionInfo.DEFAULT_REPLICA_ID];
351  }
352
353  /**
354   * Returns the first not-null region location in the list
355   */
356  public HRegionLocation getRegionLocation() {
357    for (HRegionLocation loc : locations) {
358      if (loc != null) {
359        return loc;
360      }
361    }
362    return null;
363  }
364
365  @Override
366  public Iterator<HRegionLocation> iterator() {
367    return Arrays.asList(locations).iterator();
368  }
369
370  @Override
371  public String toString() {
372    StringBuilder builder = new StringBuilder("[");
373    for (HRegionLocation loc : locations) {
374      if (builder.length() > 1) {
375        builder.append(", ");
376      }
377      builder.append(loc == null ? "null" : loc);
378    }
379    builder.append("]");
380    return builder.toString();
381  }
382
383}