1 /***********************************************************************
2  * Copyright (c) 2013-2024 Commonwealth Computer Research, Inc.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Apache License, Version 2.0
5  * which accompanies this distribution and is available at
6  * http://www.opensource.org/licenses/apache2.0.php.
7  ***********************************************************************/
8 
9 package org.locationtech.geomesa.utils.uuid
10 
11 import com.typesafe.scalalogging.LazyLogging
12 import org.geotools.api.feature.simple.{SimpleFeature, SimpleFeatureType}
13 import org.locationtech.geomesa.curve.TimePeriod.TimePeriod
14 import org.locationtech.geomesa.curve.{BinnedTime, Z3SFC}
15 import org.locationtech.geomesa.utils.geotools.RichSimpleFeatureType.RichSimpleFeatureType
16 import org.locationtech.geomesa.utils.index.ByteArrays
17 import org.locationtech.jts.geom.{Geometry, Point}
18 
19 import java.util.{Date, UUID}
20 import scala.util.hashing.MurmurHash3
21 
22 /**
23  * Creates feature id based on the z3 index.
24  */
25 class Z3FeatureIdGenerator extends FeatureIdGenerator {
26   override def createId(sft: SimpleFeatureType, sf: SimpleFeature): String = {
27     if (sft.getGeometryDescriptor == null) {
28       // no geometry in this feature type - just use a random UUID
29       UUID.randomUUID().toString
30     } else {
31       Z3UuidGenerator.createUuid(sft, sf).toString
32     }
33   }
34 }
35 
36 /**
37  * UUID generator that creates UUIDs that sort by z3 index.
38  * UUIDs will be prefixed with a shard number, which will ensure some distribution of values as well
39  * as allow pre-splitting of tables based on hex values.
40  *
41  * Uses variant 2 (IETF) and version 4 (for random UUIDs, although it's not totally random).
42  * See https://en.wikipedia.org/wiki/Universally_unique_identifier#Variants_and_versions
43  *
44  * Format is:
45  *
46  *   4 bits for a shard - enough for a single hex digit
47  *   44 bits of the z3 index value
48  *   4 bits for the UUID version
49  *   12 more bits of the z3 index value
50  *   2 bits for the UUID variant
51  *   62 bits of randomness
52  */
53 object Z3UuidGenerator extends RandomLsbUuidGenerator with LazyLogging {
54 
55   import org.locationtech.geomesa.utils.geotools.Conversions.RichGeometry
56 
57   private val NullGeom = "Cannot meaningfully index a feature with a NULL geometry"
58 
59   /**
60     * Creates a UUID where the first 8 bytes are based on the z3 index of the feature and
61     * the second 8 bytes are based on a random number.
62     *
63     * This provides uniqueness along with locality.
64     *
65     * @param sft simple feature type
66     * @param sf feature
67     * @return
68     */
69   def createUuid(sft: SimpleFeatureType, sf: SimpleFeature): UUID = {
70     val (x, y) = sf.getAttribute(sft.getGeomIndex) match {
71       case null => throw new IllegalArgumentException(NullGeom)
72       case g: Geometry if g.isEmpty => (0d, 0d)
73       case p: Point => (p.getX, p.getY)
74       case g: Geometry => val p = g.safeCentroid(); (p.getX, p.getY)
75     }
76     val time =
77       sft.getDtgIndex
78           .flatMap(i => Option(sf.getAttribute(i)))
79           .map(_.asInstanceOf[Date].getTime)
80           .getOrElse(System.currentTimeMillis())
81 
82     createUuid(x, y, time, sft.getZ3Interval)
83   }
84 
85   /**
86     * Create a UUID based on the raw values that make up the z3
87     *
88     * @param geom geometry
89     * @param time millis since java epoch
90     * @param period z3 time period
91     * @return
92     */
93   def createUuid(geom: Geometry, time: Long, period: TimePeriod): UUID = {
94     if (geom == null) {
95       throw new IllegalArgumentException(NullGeom)
96     } else if (geom.isEmpty) {
97       createUuid(0, 0, time, period)
98     } else {
99       val pt = geom.safeCentroid()
100       createUuid(pt.getX, pt.getY, time, period)
101     }
102   }
103 
104 
105   /**
106    * Create a UUID based on the raw values that make up the z3, optimized for point geometries
107    *
108    * @param pt point
109    * @param time millis since java epoch
110    * @param period z3 time period
111    * @return
112    */
113   def createUuid(pt: Point, time: Long, period: TimePeriod): UUID = {
114     if (pt == null) {
115       throw new IllegalArgumentException(NullGeom)
116     } else if (pt.isEmpty) {
117       createUuid(0, 0, time, period)
118     } else {
119       createUuid(pt.getX, pt.getY, time, period)
120     }
121   }
122 
123   /**
124    * Create a UUID based on the raw values that make up the z3, optimized for point geometries
125    *
126    * @param x x coord
127    * @param y y coord
128    * @param time millis since java epoch
129    * @param period z3 time period
130    * @return
131    */
132   def createUuid(x: Double, y: Double, time: Long, period: TimePeriod): UUID = {
133     // create the random part
134     // this uses the same temp array we use later, so be careful with the order this gets called
135     val leastSigBits = createRandomLsb()
136 
137     val z3 = {
138       val BinnedTime(b, t) = BinnedTime.timeToBinnedTime(period)(time)
139       val z = Z3SFC(period).index(x, y, t)
140       ByteArrays.toBytes(b, z)
141     }
142 
143     // shard is first 4 bits of our uuid (e.g. 1 hex char) - this allows nice pre-splitting
144     val shard = math.abs(MurmurHash3.bytesHash(z3, MurmurHash3.arraySeed) % 16).toByte
145 
146     val msb = getTempByteArray
147     // set the shard bits, then the z3 bits
148     msb(0) = lohi(shard, z3(0))
149     msb(1) = lohi(z3(0), z3(1))
150     msb(2) = lohi(z3(1), z3(2))
151     msb(3) = lohi(z3(2), z3(3))
152     msb(4) = lohi(z3(3), z3(4))
153     msb(5) = lohi(z3(4), z3(5))
154     msb(6) = lohi(0, (z3(5) << 4).asInstanceOf[Byte]) // leave 4 bits for the version
155     msb(7) = z3(6)
156     // we drop the last 4 bytes of the z3 to ensure some randomness
157     // that leaves us 62 bits of randomness, and still gives us ~10 bits per dimension for locality
158 
159     // set the UUID version - we skipped those bits when writing
160     setVersion(msb)
161     // create the long
162     val mostSigBits = ByteArrays.readLong(msb)
163 
164     new UUID(mostSigBits, leastSigBits)
165   }
166 
167   /**
168     * Gets the z3 time period bin based on a z3 uuid
169     *
170     * @param uuid uuid, as bytes
171     * @return
172     */
173   def timeBin(uuid: Array[Byte], offset: Int = 0): Short = timeBin(uuid(offset), uuid(offset + 1), uuid(offset + 2))
174 
175   /**
176     * Gets the z3 time period bin based on a z3 uuid
177     *
178     * @param b0 first byte of the uuid
179     * @param b1 second byte of the uuid
180     * @param b2 third byte of the uuid
181     * @return
182     */
183   def timeBin(b0: Byte, b1: Byte, b2: Byte): Short = {
184     // undo the lo-hi byte merging to get the two bytes for the time period
185     ByteArrays.readShort(Array(lohi(b0, b1), lohi(b1, b2)))
186   }
187 
188   // takes 4 low bits from b1 as the new hi bits, and 4 high bits of b2 as the new low bits, of a new byte
189   private def lohi(b1: Byte, b2: Byte): Byte =
190     ((java.lang.Byte.toUnsignedInt(b1) << 4) | (java.lang.Byte.toUnsignedInt(b2) >>> 4)).asInstanceOf[Byte]
191 }