## 4 Design and Implementation
### High-Level Design
**Membership count**: The membership count in ESH is a 1-byte value that stores the number of alien elements or elements that have been pushed to the bucket because their hashed bucket was already full. This count is maintained to keep track of how many elements have been moved to the bucket, which helps to facilitate searching operations. In this scheme, every operation must first check the consistent state of the target bucket. When a running process wants to write or update the bucket, it acquires the lock and checks the overflow bit to determine if the bucket is full. If the conditions are met, the process proceeds with inserting a record into the bucket. However, if the bucket is already full, the process moves on to the next neighboring bucket, releasing the lock in the original bucket as described in Algorithm 1. In the ESH scheme, each segment holds a fixed number of buckets consisting of 32 bytes of metadata and 224 bytes of key-value pairs. The directory entries point to these segments, which contain the buckets. The data are stored in the buckets as arrays of records, as depicted in Figure 4. A bucket serves as a storage unit for records generated by the hashing function, as well as records moved from neighboring buckets. During the insertion of records, if a bucket has more available space compared to its neighboring buckets, the records are moved to these neighboring buckets instead of triggering doubling. This approach is utilized when a particular bucket does not have sufficient space for insertion, but there are neighboring buckets that are free or have enough space to accommodate the records. ```
1:def ESH_insert(key,value):
2:hashval=hash(key);
3:overflow_counter \(\leftarrow\) 0
4:try:
5:#check consistency and get the lock to the targeted bucket
6:target_bucket=get_segment.bucket(hashval)
7:state = target_bucket.state
8:if state = 0 #check if the bucket is consistent then
9:if get_segment.bucket=full then
10: change overflow_bit=1
11: target_bucket=get_segment.bucket\(\leftarrow\) next
12: increment overflow_counter & membership count
13:endif
14: Lock target_bucket
15:if target_bucket.count\(<=\) segment_size then
16: target_bucket.insert(key, value, hashval)
17:endif
18:if target_bucket.bucket!= full then
19: target_bucket.insert(key, value, hashval)
20:endif
21: target_bucket=get_segment.bucket(hashval)
22: update membership_counter
23: goto try:
24: update overflow_record_address
25: Unlock target_bucket
26: return Insertion_result
27:endif
```  
**Algorithm 1** ESH key-value insert algorithm  
To ensure concurrency control, the ESH scheme adopts the initial CCEH scheme, which utilizes locks and a flag to determine if a bucket is clean. This choice is based on the reasonable performance demonstrated by the CCEH scheme in the context of extendible hashing. When inserting records into the buckets, if there is no available space in any of the buckets within the same segment, the scheme checks for available space in the neighboring buckets. This approach is similar to how the CCEH scheme uses trackers for global and local depth during splitting and directory doubling operations. To efficiently utilize the available buckets, particularly those that are partially filled or empty, the scheme employs a traversal process within the same segment to find the appro  
Figure 4: Segmented extendible hashing with cache-conscious feature. priate location for inserting a record in neighboring buckets. This traversal is constrained to remain within the segment to avoid complicating the lookup process. During each insertion, the record is hashed to the correct bucket, and if that bucket is already full, the scheme tracks other buckets with fewer elements and inserts the record using probing techniques. The records within the buckets are accessed as arrays, and each bucket contains a fixed number of elements, simplifying the search operation, as seen in Algorithm 2. If a value has been moved to another bucket, it can be accessed by looping through the records belonging to the same segment.